网站开发现状都用php,兰州模板网站seo价格,软件开发报价单,郴州公司注册目录 汉诺塔递归
汉诺塔子移动次数的计算
牛牛的汉诺塔
选择正常的递归模拟计算子移动次数
根据具体数据得出数学规律
根据递归图得出数学规律
将递归函数转化为递推式
结尾 汉诺塔递归
汉诺塔是一个经典问题#xff0c;相传在古印度圣庙中#xff0c;有一种被称为汉…目录 汉诺塔递归
汉诺塔子移动次数的计算
牛牛的汉诺塔
选择正常的递归模拟计算子移动次数
根据具体数据得出数学规律
根据递归图得出数学规律
将递归函数转化为递推式
结尾 汉诺塔递归
汉诺塔是一个经典问题相传在古印度圣庙中有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上有三根杆(编号A、B、C)在A杆自下而上、由大到小按顺序放置n个金盘。游戏的目标把A杆上的金盘全部移到C杆上并仍保持原有顺序叠好。操作规则每次只能移动一个盘子并且在移动过程中三根杆上都始终保持大盘在下小盘在上操作过程中盘子可以置于A、B、C任一杆上。 汉诺塔以及其衍生问题往往使用递归来求解也是学习和理解递归很好的老师。
其伪代码如下 Function Hanoi(n,a,b,c)if n1 thenprint(a-c)elseHanoi(n-1,a,c,b)print(a-c)Hanoi(n-1,b,a,c)end if
end Function
定义递归函数hanoi(n,a,b,c)表示将n个盘子从a柱移动到c柱以b柱为辅助柱。
维护定义的含义内部逻辑先将n-1个盘子从a柱移动到b柱以c柱为辅助柱。再将最大盘子从a柱移动到c柱以b柱为辅助柱。最后将n-1个盘子从b柱移动到c柱以a柱为辅助柱。
递归结束出口为n1时从a柱移动到c柱以b柱为辅助柱。
C代码 #include iostream
using namespace std;// 函数声明
void hanoi(int n, char a, char b, char c) {if (n 1) {cout a - c endl;return;}hanoi(n-1, a, c, b);cout a - c endl;hanoi(n-1, b, a, c);
}汉诺塔子移动次数的计算
牛牛的汉诺塔 链接登录—专业IT笔试面试备考平台_牛客网 来源牛客网 时间限制C/C 1秒其他语言2秒 空间限制C/C 262144K其他语言524288K 64bit IO Format: %lld 题目描述 汉诺塔是一个经典问题相传在古印度圣庙中有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上有三根杆(编号A、B、C)在A杆自下而上、由大到小按顺序放置n个金盘。游戏的目标把A杆上的金盘全部移到C杆上并仍保持原有顺序叠好。操作规则每次只能移动一个盘子并且在移动过程中三根杆上都始终保持大盘在下小盘在上操作过程中盘子可以置于A、B、C任一杆上。 汉诺塔以及其衍生问题往往使用递归来求解也是学习和理解递归很好的老师。 其伪代码如下 Function Hanoi(n,a,b,c) if n1 then print(a-c) else Hanoi(n-1,a,c,b) print(a-c) Hanoi(n-1,b,a,c) end if end Function 牛牛很快就理解了代码的意思并且写出了求解汉诺塔的程序他现在想研究汉诺塔的规律。 请你统计以下信息A-B,A-C,B-A,B-C,C-A,C-B的次数以及所有移动的总步数。 输入描述: 仅一行输入一个正整数n(1≤n≤60)(1 leq n leq 60)(1≤n≤60)表示汉诺塔的层数。 输出描述: 首先输出6行 A-B:XX A-C:XX B-A:XX B-C:XX C-A:XX C-B:XX 分别表示每种移动情况出现的次数 最后输出一行 SUM:XX 表示所有移动情况的总和。 示例1 输入 复制3 3 输出 复制A-B:1 A-C:3 B-A:1 B-C:1 C-A:0 C-B:1 SUM:7 A-B:1 A-C:3 B-A:1 B-C:1 C-A:0 C-B:1 SUM:7 说明 伪代码所示算法的移动序列如下 A-C A-B C-B A-C B-A B-C A-C 统计 A-B出现1次 A-C出现3次 B-C出现1次 B-A出现1次 C-B出现1次 总计7次 选择正常的递归模拟计算子移动次数 #include bits/stdc.h
using namespace std;
using LL long long;
LL N 1000005;
LL MOD 1e4 7;
LL N1 10005;void Hanoi(int n, char a, char b, char c, int count_ab, int count_ac, int count_ba, int count_bc, int count_ca, int count_cb) {if (a A c B) count_ab;if (a A c C) count_ac;if (a B c A) count_ba;if (a B c C) count_bc;if (a C c A) count_ca;if (a C c B) count_cb;if (n 1) {return;} else {Hanoi(n - 1, a, c, b, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);Hanoi(n - 1, b, a, c, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);}
}
int main() {int count_ab 0;int count_ac 0;int count_ba 0;int count_bc 0;int count_ca 0;int count_cb 0;char a A, b B, c C;int n;cinn;Hanoi(n, a, b, c, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);int countcount_abcount_account_bacount_bccount_cacount_cb;coutA-B:count_abendl;coutA-C:count_acendl;coutB-A:count_baendl;coutB-C:count_bcendl;coutC-A:count_caendl;coutC-B:count_cbendl;coutSUM:count;
}
我们可以通过递归关系式来表达这个问题的解法次数。对于n个盘子移动它们所需的步骤T(n)可以表示为
T(n)2T(n−1)1
这里的思路是移动n-1个盘子到临时柱子这需要T(n-1)步移动最大的盘子到目标柱子这需要1步最后再将n-1个盘子从临时柱子移动到目标柱子上再次需要T(n-1)步。
我们可以进一步解开这个递归式 当n 1时只需要移动一次所以T(1) 1。 当n 2时T(2) 2T(1) 1 3。 当n 3时T(3) 2T(2) 1 7。
以此类推我们发现这是一个等比数列的求和问题其总和公式为
T(n)2^n−1
因此汉诺塔问题的时间复杂度为O(2^n)。这个复杂度表明了随着盘子数量的增加需要的移动次数呈指数级增长这也解释了为什么汉诺塔问题在盘子数量稍多时就变得难以直接通过手动移动来解决。 当n60时时间复杂度是O(2^60)2^10≈100010^32^602^10*2^10*2^10*2^10*2^10*2^10。也就是六个10^3相乘等于10^18远远超过10^910^9对应的时间大概是1s这样的递归是一定会超时的。
根据具体数据得出数学规律
我们将正常递归模拟计算子移动次数的代码进行修改用来计算前n项的子移动次数数据。 #include bits/stdc.h
using namespace std;
using LL long long;
LL N 1000005;
LL MOD 1e4 7;
LL N1 10005;void Hanoi(int n, char a, char b, char c, int count_ab, int count_ac, int count_ba, int count_bc, int count_ca, int count_cb) {if (a A c B) count_ab;if (a A c C) count_ac;if (a B c A) count_ba;if (a B c C) count_bc;if (a C c A) count_ca;if (a C c B) count_cb;if (n 1) {return;} else {Hanoi(n - 1, a, c, b, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);Hanoi(n - 1, b, a, c, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);}}
int main() {char a A, b B, c C;cout ;cout setw(8) a-b setw(8) a-c setw(8) b-a setw(8) b-c setw(8) c-a setw(8) c-b setw(8) SUM endl;for (int i 1; i 20; i) {int count_ab 0;int count_ac 0;int count_ba 0;int count_bc 0;int count_ca 0;int count_cb 0;Hanoi(i, a, b, c, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);int count count_ab count_ac count_ba count_bc count_ca count_cb;cout nsetw(2) i:;cout setw(7) count_ab ;cout setw(7) count_ac ;cout setw(7) count_ba ;cout setw(7) count_bc ;cout setw(7) count_ca ;cout setw(7) count_cb ;cout setw(7) count endl;}} //输出a-b a-c b-a b-c c-a c-b SUM
n 1: 0 1 0 0 0 0 1
n 2: 1 1 0 1 0 0 3
n 3: 1 3 1 1 0 1 7
n 4: 4 3 1 4 2 1 15
n 5: 4 9 6 4 2 6 31
n 6: 15 9 6 15 12 6 63
n 7: 15 31 27 15 12 27 127
n 8: 58 31 27 58 54 27 255
n 9: 58 117 112 58 54 112 511
n10: 229 117 112 229 224 112 1023
n11: 229 459 453 229 224 453 2047
n12: 912 459 453 912 906 453 4095
n13: 912 1825 1818 912 906 1818 8191
n14: 3643 1825 1818 3643 3636 1818 16383
n15: 3643 7287 7279 3643 3636 7279 32767
n16: 14566 7287 7279 14566 14558 7279 65535
n17: 14566 29133 29124 14566 14558 29124 131071
n18: 58257 29133 29124 58257 58248 29124 262143
n19: 58257 116515 116505 58257 58248 116505 524287
n20: 233020 116515 116505 233020 233010 116505 1048575
我们将a-b,a-c,b-a,b-c,c-a,c-b分别记为1,2,3,4,5,6。
我们希望找出前后项的规律很容易发现同一个n中1号等于4号3号等于6号。
因此我们将数据截取出1,2,3,5四列数据。做法很简单只需要简单修改代码即可。 #include bits/stdc.h
using namespace std;
using LL long long;
LL N 1000005;
LL MOD 1e4 7;
LL N1 10005;void Hanoi(int n, char a, char b, char c, int count_ab, int count_ac, int count_ba, int count_bc, int count_ca, int count_cb) {if (a A c B) count_ab;if (a A c C) count_ac;if (a B c A) count_ba;if (a B c C) count_bc;if (a C c A) count_ca;if (a C c B) count_cb;if (n 1) {return;} else {Hanoi(n - 1, a, c, b, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);Hanoi(n - 1, b, a, c, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);}}
int main() {char a A, b B, c C;cout ;cout setw(8) a-b ;cout setw(8) a-c ;cout setw(8) b-a ;
// cout setw(8) b-c ;cout setw(8) c-a ;
// cout setw(8) c-b ;cout setw(8) SUM endl;for (int i 1; i 20; i) {int count_ab 0;int count_ac 0;int count_ba 0;int count_bc 0;int count_ca 0;int count_cb 0;Hanoi(i, a, b, c, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);int count count_ab count_ac count_ba count_bc count_ca count_cb;cout n setw(2) i :;cout setw(7) count_ab ;cout setw(7) count_ac ;cout setw(7) count_ba ;
// cout setw(7) count_bc ;cout setw(7) count_ca ;
// cout setw(7) count_cb ;cout setw(7) count endl;}} //输出a-b a-c b-a c-a SUM
n 1: 0 1 0 0 1
n 2: 1 1 0 0 3
n 3: 1 3 1 0 7
n 4: 4 3 1 2 15
n 5: 4 9 6 2 31
n 6: 15 9 6 12 63
n 7: 15 31 27 12 127
n 8: 58 31 27 54 255
n 9: 58 117 112 54 511
n10: 229 117 112 224 1023
n11: 229 459 453 224 2047
n12: 912 459 453 906 4095
n13: 912 1825 1818 906 8191
n14: 3643 1825 1818 3636 16383
n15: 3643 7287 7279 3636 32767
n16: 14566 7287 7279 14558 65535
n17: 14566 29133 29124 14558 131071
n18: 58257 29133 29124 58248 262143
n19: 58257 116515 116505 58248 524287
n20: 233020 116515 116505 233010 1048575
我们希望由上面的数据找出前后项的关系我们对a-b,a-c,b-a,c-a重新进行编号分别记为1,2,3,4。
我们需要用的n-1项的1,2,3,4号数据推导出n项的1,2,3,4号数据。
找规律的思路是我们可以先关注n项的1号数据看n-1项的某一号数据是否可以单独推导出n项的1号数据。1对1的关系。如果1对1的关系找不到那就找n-1项的多号数据是否可以推导出1号数据以此类推。 先关注n项1号与n-1项一对一的关系。
当n7时1号等于n6的2号*2-3等于3号*23。
当n8时1号等于n7的2号*2-4等于3号*24。
当n9时1号等于n8的2号*2-4等于3号*24。
当n10时1号等于n9的2号*2-5等于3号*25。
很容易发现递推公式n项的1号等于n-1项的2号*2-n/2或者等于3号*2n/2。
找到1号的递推式我们接着找2号的递推式。 先关注n项2号与n-1项一对一的关系。
当n7时2号等于n6的1号*21。
当n8时2号等于n7的1号*21。
当n9时2号等于n8的1号*21。
当n10时2号等于n9的1号*21。
很容易发现递推公式n项的2号等于n-1项的2号*21。
找到2号的递推式我们接着找3号的递推式。 先关注n项3号与n-1项一对一的关系。
当n7时3号等于n6的1号*2-3。
当n8时3号等于n7的1号*2-3。
当n9时3号等于n8的1号*2-4。
当n10时3号等于n9的1号*2-4。
很容易发现递推公式n项的3号等于n-1项的1号*2-n-1/2。
找到3号的递推式我们接着找4号的递推式。 先关注n项4号与n-1项一对一的关系。
当n7时4号等于n6的3号*2。
当n8时4号等于n7的3号*2。
当n9时4号等于n8的3号*2。
当n10时4号等于n9的3号*2。
很容易发现递推公式n项的4号等于n-1项的3号*2。
接着我们就可以利用递推式直接求前后项的数据。 其实我们可以发现上述的前后项关系不仅仅是上述的几种例如n项的1号等于n-1项的1号2号n项的3号等于n-1项的1号4号等等。我们知道的是这些推导公式都可以推导出前后项关系得到递推式。 #includebits/stdc.h
using namespace std;
using LLlong long;
int main(){int n;cinn;vectorvectorLL a(n1,vectorLL(4));a[1][1]1;for(int i2;in;i){a[i][0]a[i-1][1]a[i-1][2];a[i][1]a[i-1][0]*21;a[i][2]a[i-1][3]*2(i-1)/2;a[i][3]a[i-1][2]*2;}coutA-B:a[n][0]endl;coutA-C:a[n][1]endl;coutB-A:a[n][2]endl;coutB-C:a[n][0]endl;coutC-A:a[n][3]endl;coutC-B:a[n][2]endl;coutSUM:a[n][0]*2a[n][1]a[n][2]*2a[n][3]endl;
}
根据递归图得出数学规律 #include bits/stdc.h
using namespace std;
using LL long long;
int main() {int n;cin n;LL count_ab 0, count_ac 0, count_ba 0, count_bc 0, count_ca 0, count_cb 0;LL length 1;for (int i 1; i n; i) {if (i ! 1)length * 2;if (i % 2 1) {LL tempcount length / 3;count_ac tempcount;count_cb tempcount;count_ba tempcount;LL tempcount1 length % 3;if (tempcount1 1) {count_ac;} else {count_ac;count_cb;}} else {LL tempcount length / 3;count_ab tempcount;count_bc tempcount;count_ca tempcount;LL tempcount1 length % 3;if (tempcount1 1) {count_ab;} else {count_ab;count_bc;}}}cout A-B: count_ab endl;cout A-C: count_ac endl;cout B-A: count_ba endl;cout B-C: count_bc endl;cout C-A: count_ca endl;cout C-B: count_cb endl;cout SUM: count_ab count_ac count_ba count_bc count_ca count_cb endl;
}
将递归函数转化为递推式 #include bits/stdc.h
using namespace std;
using LL long long;
int main() {int n;cin n;vectorvectorLL dp(3,vectorLL(7));dp[1][2] 1;for (int i 2; i n; i) {dp[2][1] dp[1][2] dp[1][3];dp[2][2] dp[1][1] dp[1][4] 1;dp[2][3] dp[1][1] dp[1][5];dp[2][4] dp[1][2] dp[1][6];dp[2][5] dp[1][6] dp[1][3];dp[2][6] dp[1][5] dp[1][4];dp[1][1] dp[2][1];dp[1][2] dp[2][2];dp[1][3] dp[2][3];dp[1][4] dp[2][4];dp[1][5] dp[2][5];dp[1][6] dp[2][6];}cout A-B: dp[1][1] endl;cout A-C: dp[1][2] endl;cout B-A: dp[1][3] endl;cout B-C: dp[1][4] endl;cout C-A: dp[1][5] endl;cout C-B: dp[1][6] endl;cout SUM: dp[1][1] dp[1][2] dp[1][3] dp[1][4] dp[1][5] dp[1][6] endl;
}
结尾
最后感谢您阅读我的文章希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点请随时在评论区留言。 同时不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中我将继续探讨这个话题的不同方面为您呈现更多深度和见解。 谢谢您的支持期待与您在下一篇文章中再次相遇
