网站建设公众号小程序推广开发,wordpress设置用户注册,如何是wordpress,做网站的不给源文件k柱汉诺塔
题目描述
汉诺塔#xff08;Hanoi Tower#xff09;#xff0c;又称河内塔。 传说大梵天创造世界的时候做了三根金刚石柱子#xff0c;按左、中、右排序。大梵天在左侧的柱子上#xff0c;从下往上按照大小顺序摞着64片黄金圆盘#xff0c;越靠下的圆盘越大。…k柱汉诺塔
题目描述
汉诺塔Hanoi Tower又称河内塔。 传说大梵天创造世界的时候做了三根金刚石柱子按左、中、右排序。大梵天在左侧的柱子上从下往上按照大小顺序摞着64片黄金圆盘越靠下的圆盘越大。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放到右侧的柱子上。并且规定任何时候较小的圆盘都不能被较大的圆盘压着且一个步骤只能移动一个圆盘。 小明复刻了这个故事为一套游戏道具但他发现以他有生之年是移不完这些圆盘的——实际上原始的故事下需要 2^64-1 18446744073709551615约 1.8 * 10^19个步骤才能移动完毕。 基于此他将柱子的数量改为k个再将圆盘的数量改为n个。 请你帮助小明计算修改后的游戏需要多少个步骤能操作完毕。
关于输入
输入为两个正整数k和n以空格隔开分别代表修改后的游戏有k根柱子和n个圆盘。 提供三个输入样例。
关于输出
输出为一个正整数s代表需要的最少步骤数。 提供三个输出样例。
例子输入
4 5
例子输出
13
解题分析 代码实现
#include stdio.h
#include math.h
#define MAX 100int dict[MAX][MAX] {0};int help(int n, int m) {if (n 0 || m 3) {return -1;}if (n 1) {return 1;}if (dict[n][m] ! 0) {return dict[n][m];}int nowValue;if (m 3) {nowValue pow(2, n) - 1;} else {nowValue 2 * help(n - 1, m) help(1, m - 1);for (int i n - 2; i 0; i--) {int temp 2 * help(i, m) help(n - i, m - 1);if (temp nowValue) {nowValue temp;} else {break;}}}dict[n][m] nowValue;return nowValue;
}int main() {int n, m;scanf(%d, n); scanf(%d, m);printf(%d,help(m,n));return 0;
}
