7.1递归函数算法：用字符A、B和C表示3根针，则梵塔问题如下图所示。10
10 7.1 递归函数 算法：用字符A、B和C表示3根针，则梵塔问题如下图所示
7.1递归函数算法：。只有1片金片时，只要直接将金片从A针移到C针上即可；当n>1时，就需要借助另外一个针来移动。将n片金片由A移到C上可以分解为以下几个步骤：(1)将A上的n-1片金片借助C针移到B针上；(2)把A针上剩下的一片金片由A针移到C针上；（3）最后将剩下的n-1个金片借助A针由B针移到C针上。步骤(1)和(3)与整个任务类似，但涉及的金片只有n-1个了。这是一个典型递归算法。11
11 7.1 递归函数 算 法： • 只有1片金片时，只要直接将金片从A针移到C针上即可； • 当n>1时，就需要借助另外一个针来移动。 • 将n片金片由A移到C上可以分解为以下几个步骤： • (1)将A上的n−1片金片借助C针移到B针上; • (2)把A针上剩下的一片金片由A针移到C针上; • (3)最后将剩下的n−1个金片借助A针由B针移到C针上。 • 步骤(1)和(3)与整个任务类似，但涉及的金片只有n−1个了。 • 这是一个典型递归算法
7.1递归函数hanoi(N,'A',B',C');hanoi(n-1,p1,p3,p2);move(p1,p3);hanoi(n-1,p2,p1,p3);CCBCBBCBAAAA①①11??2(0)(2)(1)(3)?23312
7.1 递归函数 hanoi(N, 'A', 'B', 'C'); hanoi(n-1, p1, p3, p2); move(p1, p3); hanoi(n-1, p2, p1, p3); (0) A B C (1) A B C (2) A B C (3) B A C ① ① ① ① ② ② ② ② ③ ③ ③ ③ ④ ④ ④ ④ 12
7.1递归函数1/例7-2：梵塔问题#include<iostrean)usingnamespacestd;constintN=3；1/当金片数为3个时的情况l/函数moue（)：将金片由一根针移到另一根针上uoid move(char from, char to)cout<<"From"<<from<<"to"<<to<<endl;//函数hanoi（）：将n片金片由p1借助p2移到p3上uoid hanoi(int n, char p1, char p2, char p3)if(n==1)move(p1,p3);elsehanoi(n-1,p1,p3,p2);moe(p1,p3);hanoi(n-1,p2,p1,p3);313
13 7.1 递归函数
7.1递归函数ACFromto1测试用主函数int main()BAtoFromBtoFrom广hanoi(N,'A','B','C');CFromtoreturn o;-FromAtoBFromBCtoCFromAto分析：在程序中可以通过常量N确定总共要移动的金片数。从运行结果可以看出，只需要7步就可以将3片金片由A针移到C针上。若将64片金片全部由A针移到C针，共需要264一1步。若每移动一次需要1秒钟，需要58万亿年才能完成。14
14 7.1 递归函数 分析：在程序中可以通过常量N确定总共要移动的金片数。 从运行结果可以看出，只需要7步就可以将3片金片由A针移到 C针上。 若将64片金片全部由A针移到C针，共需要2 64―1步。 若每移动一次需要1秒钟，需要58万亿年才能完成