NYOJ—88 汉诺塔（一）

青旅半醒 2022-08-25 05:28 19阅读 0赞

## 汉诺塔（一） ##

时间限制： 1000 ms |  内存限制： 65535 KB

难度： 3

描述

在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

现在请你计算出起始有m个金片的汉诺塔金片全部移动到另外一个针上时需要移动的最少步数是多少？（由于结果太大，现在只要求你算出结果的十进制位最后六位）

输入

第一行是一个整数N表示测试数据的组数(0  
每组测试数据的第一行是一个整数m,表示起始时金片的个数。(0

输出

输出把金片起始针上全部移动到另外一个针上需要移动的最少步数的十进制表示的最后六位。

样例输入

2
    1
    1000

样例输出

1
    69375

主要解决求2^n - 1 结果 % 1000000，次用次方求模，主要思想递归将n二分，并且将求模分解

`01.` `#include`

`02.`

`03.` `long` `long` `pow_mod(``int` `a,``int` `b,``int` `c)`

`04.` `{`

`05.` `long` `long` `t;`

`06.` `if``(b==0)``return` `1%c;`

`07.` `if``(b==1)``return` `a%c;`

`08.` `t = pow_mod(a,b/2,c);``//递归调用，采用二分递归算法，,注意这里b/2会带来奇偶性问题`

`09.` `t = ( t*t )%c;``//二分，乘上另一半再求模`

`10.` `if``(b&1) t = t*a%c;``//b是奇数，因为b/2还少乘了一次a`

`11.` `return` `t;`

`12.` `}`

`13.` `int` `main()`

`14.` `{`

`15.` `int` `n,b;`

`16.` `scanf``(``"%d"``,&n);`

`17.` `while``(n--)`

`18.` `{`

`19.` `scanf``(``"%d"``,&b);`

`20.` `printf``(``"%d\n"``,pow_mod(2,b,1000000)-1);`

`21.` `}``//while`

`22.` `return` `0;`

`23.` `}`

发表评论取消回复

表情：

评论列表（有 0 条评论，19人围观）

还没有评论，来说两句吧...

相关阅读

相关 nyoj 汉诺塔（一）+快速幂

汉诺塔（一）时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里

爱被打了一巴掌/ 2024年02月17日 19:44/ 0 赞/ 44 阅读

相关一、汉诺塔问题

有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：每次只能移动一个圆盘；大盘不能叠在小盘上面。提示：可将圆

清疚/ 2023年05月21日 08:57/ 0 赞/ 18 阅读

相关 NYOJ - 汉诺塔（三）

[93 汉诺塔（三）][93] 定义一个栈一维数组，包含3个栈，代表3个柱子，依次执行指令第一次提交时，注释什么多余的语句没删除，每个栈开的长度大了，提交结果内存 97

落日映苍穹つ/ 2022年08月25日 05:28/ 0 赞/ 19 阅读

相关 NYOJ—88 汉诺塔（一）

汉诺塔（一）时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙

青旅半醒/ 2022年08月25日 05:28/ 0 赞/ 20 阅读

相关汉诺塔

Problem Description 汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒A、B和C，A上面套着

Dear 丶/ 2022年06月17日 05:28/ 0 赞/ 309 阅读

相关汉诺塔

汉诺塔 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [Statistic][] Prob

约定不等于承诺〃/ 2022年06月11日 03:24/ 0 赞/ 262 阅读

相关汉诺塔

\include<stdio.h> void hanoi(int n,char A,char B,char C) \{ if(n==1) printf("Move s

逃离我推掉我的手/ 2022年06月10日 12:57/ 0 赞/ 308 阅读

相关汉诺塔

def move(n, a, b, c): if n == 1: \ 如果a只有1盘子 print(a, '-->', c); \ 直接把盘子从a移到c els

迷南。/ 2022年05月18日 22:25/ 0 赞/ 339 阅读

相关南阳理工acm 88-汉诺塔（一）

汉诺塔（一） [http://acm.nyist.net/JudgeOnline/problem.php?pid=88][http_acm.nyist.net_Judge

小咪咪/ 2021年12月13日 03:45/ 0 赞/ 398 阅读

相关汉诺塔

// 有柱子 A,B,C // 将n个圆盘分成一个上盘，一个下盘，每次移动都是 / n=1的时

我不是女神ヾ/ 2021年07月24日 23:39/ 0 赞/ 490 阅读