网站推广网络,网站建设策划方案模板,石家庄做网站seo,网页设计个人博客题意明确#xff0c;让计算出起始有m个金片的汉诺塔金片全部移动到另外一个针上时需要移动的最少步数是多少#xff1f;#xff08;由于结果太大#xff0c;现在只要求算出结果的十进制位最后六位#xff09; 解题思路#xff1a;大家都很熟悉汉诺塔求移动次数公式为f(n1… 题意明确让计算出起始有m个金片的汉诺塔金片全部移动到另外一个针上时需要移动的最少步数是多少由于结果太大现在只要求算出结果的十进制位最后六位 解题思路大家都很熟悉汉诺塔求移动次数公式为f(n1)f(n)*21; 由于0m1000000000按要求只需要输出结果的十进制最后六位即f(n1)(f(n)*21)%1000000注意是1后面是6个0刚开始我就弄错了。由于m 取值范围太大如果按公式计算一定会超时。经过测试多组数据发现当m100005时有如下规律f(123456)f(23456); f(123456789)f(23456789)老实说这规律确实不好找即略去最高位。但还要注意一点当 m%1000006 时则 m100000m%10。这道题让我纠结了好长时间 代码如下 View Code 1 #includeiostream 2 using namespace std; 3 #define Max 100006 4 int an[Max]; 5 int main() 6 { 7 int n,i,m; 8 an[1]1; 9 for(i2;iMax;i)10 an[i](an[i-1]*21)%1000000;11 cinn;12 while(n--)13 {14 cinm;15 if(m100005)16 {17 if(m%1000006) m100000m%10;18 else m%100000;19 }20 coutan[m]endl;21 }22 return 0;23 } 转载于:https://www.cnblogs.com/yueshuqiao/archive/2011/08/29/2158887.html
