石家庄做网站,网站建设的数据库设计图,网站域名查询官网,海报设计制作平台目录1.斐波那契数列#xff1a;
2.青蛙跳台阶问题#xff1a;
3.汉诺塔问题 1.斐波那契数列#xff1a;
由斐波那契数列从第三项开始#xff0c;每一项等于前两项之和#xff0c;可以使用递归计算给定整数的斐波那契数。 1#xff0c;1#xff0c;2#xff0c;3
2.青蛙跳台阶问题
3.汉诺塔问题 1.斐波那契数列
由斐波那契数列从第三项开始每一项等于前两项之和可以使用递归计算给定整数的斐波那契数。 11235813213455… 分析
从第三项开始当前项为前两项之和。
注意终止条件有两个n1n2项
如果n3则进入42行循环一直自我调用。
2.青蛙跳台阶问题
题目从前有一只青蛙他想跳台阶有n级台阶青蛙一次可以跳1级台阶也可以跳2级台阶问该青蛙跳到第n级台阶一共有多少种跳法
分析
刚刚看完这个题目感觉还是有些懵的但是不能慌我们要一步一步分析找规律。 再分析前三步时我们好像以为规律是步数就是台阶数等于跳法数但分析到n5时却不一样了。它真正的规律是从第三项开始跳法数等于前一步的跳法数加上前前一步的跳法数。
如何快速得到当前所求的步数
当n5时它一次要么跳一个要么跳两个
当它跳一个跳向1台阶还剩下4个台阶以当前台阶为新起点跳4完个台阶有5种方法
当它跳两个台阶跳向2台阶还剩下3个台阶以第二个台阶为新起点跳完3个台阶有3中方法。
所以跳完5个台阶一共有35种方法
这就是引用了动态规划用上一步的结果快速计算下一步的结果。
细心的你发现它不就是一个隐藏的斐波那契数列吗 3.汉诺塔问题
题目描述 n个圆盘从下面开始按大小顺序摆放在A柱子上。 并且规定任何时候在小圆盘上都不能放大圆盘且在三根柱子之间一次只能移动一个圆盘求最少的移动步骤。
分析
题目要我们求出n个盘子从A柱移动到C柱所需的最少步骤这题明显是种找规律题目。
所以我们应该先不要慌张从n为1开始分析多多分析发现规律。
n1
可以直接从A盘移动到C盘不需要经过B盘。这时只需要1步 n2
分析第一步’A--B‘ 第二步’A--C‘ 第三步’B--C‘ 一共需要三步 n3 一共需要七步 分析这里好像我们已经发现一个规律最小步数2^n-1;
如果n无限大那么我们是不是可以用分割的思想将n分为1和n-1;
这时采用递归的方法递归的终止条件为 n1 在柱间移动的代码 分析
move函数作用来打印 起始位置 到 停留的位置
fun函数表示每个盘子在ABC三个柱间移动的过程A起始柱B转移盘C目标盘
n为盘子的个数pose1表示A柱pose2表示B柱pose3表示C柱
代码思路是将盘子分为1和n-1
17行将n-1个盘子从A通过C柱移动到B柱
18h行move打印最后一个盘子从A柱移动到C柱
也就是一开始n个盘子n1进入funn-1pose1pose2pose3
在 funn-1pose1pose2pose3中(n-1)!1,
再进入funn-2pose1pose2pose3
一直地推……
直到n1然后回归
递归终止条件为n1时只剩下一个盘子就是最底下那个最大的。将此盘直接从A盘--C盘
此时n-1个盘子在B柱在19行再调用fun函数将n-1个盘子从B柱通过A柱移动到C柱任务完成。
