中国建设网官方网站,视觉网站建设,wordpress 弹框,织梦网站怎么搬家在数学与计算机科学中#xff0c;递归(recursion)是指一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算#x…
在数学与计算机科学中递归(recursion)是指一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算大大减少了程序的代码量。递归的能力在于用有限的语句定义对象的无限集合。一个递归问题可分为递推和回归两个阶段。在递推阶段把较复杂问题规模为n的求解推到比原问题简单一些的问题规模小于n的求解在回归阶段当获得最简单情况的解后逐级返回依次得到稍复杂问题的解。
只有同时满足下面三个条件的问题才能用递归解决。
(1) 一个问题可以转化为一个与原问题相似的、规模较小的子问题来求解。比如在n的阶乘的计算中将n的阶乘的问题转化为n-1的阶乘乘以n此问题便可解决。
(2) 这个问题与分解之后的子问题除数据规模不同求解思路完全一样。比如n的阶乘问题中求解n的阶乘的思路和求解n-1的阶乘的思路是一模一样的。
(3) 存在递归终止条件。
把问题分解为子问题再把子问题分解为子子问题一层一层分解下去不能存在无限循环这就需要有终止条件。比如n的阶乘问题中0或1的阶乘为1也就是f(1)1f(0)1,这就是递归的终止条件。
递归是很多算法实现的基础是程序设计中的一种重要思想和机制如分治、深度优先搜索、动态规划等算法中均用到递归思想。
01、汉诺塔问题
汉诺Hanoi塔问题是一个经典的运用递归方法解决问题的例子。
问题描述:
汉诺塔是一个发源于印度的益智游戏也叫河内塔。相传它源于印度神话中的大梵天创造的三根金刚柱一根柱子上叠着上下从小到大64个黄金圆盘。大梵天命令婆罗门将这些圆盘按从小到大的顺序移动到另一根柱子上其中大圆盘不能放在小圆盘上面。当这64个圆盘移动完的时候世界就将毁灭。
那么好多人会问64个圆盘移动到底会花多少时间古代印度距离现在已经很远这64个圆盘还没移动完么我们通过计算看完成这个任务到底要多少时间计算结果非常恐怖移动圆盘的次数为2n-1即18446744073709551615假设移动一次圆盘用时一秒一年为31536000秒。那么18446744073709551615/31536000约等于584942417355年即约为5850亿年。目前太阳寿命约为50亿年太阳的完整寿命大约100亿年。所以整个人类文明都等不到移动完整圆盘的那一天。很多人对汉诺塔的解法产生了兴趣。从一阶汉诺塔到N阶汉诺塔它们是否有规律性的算法能否编程输出每一次移动的方法呢这就是本例要解决的问题。
输入:
输入一个正整数n表示有n个圆盘在第一根柱子上。
输出:
输出操作序列格式为move t from x to y。每个操作一行表示把x柱子上的编号为t的盘片挪到柱子y上。柱子编号为abc要用最少的操作把所有盘子从a柱子上转移到c柱子上。
输入样例:
3
输出样例:
move 1 from a to c
move 2 from a to b
move 1 from c to b
move 3 from a to c
move 1 from b to a
move 2 from b to c
move 1 from a to c
解题思路:
实现这个算法可以简单分为以下三个步骤。
(1) 把第n-1个圆盘由a移到b。
(2) 把第n个圆盘由a移到c。
(3) 把第n-1个圆盘由b移到c。
从这里入手加上上面数学问题解法的分析不难发现移动的步数必为奇数步。
(1) 第二步是把a柱子上剩下的一个盘子移到c柱子上。
(2) 第一步可以看成把a柱子上的n-1个圆盘借助c柱子移到b柱子上。
(3) 第三步可以看成把b上的n-1个圆盘借助a柱子移到c柱子上。
如3阶汉诺塔的移动: A→C,A→B,C→B,A→C,B→A,B→C,A→C。
参考程序:
#include fstream
#include iostream
using namespace std;
/ *将x柱子上编号为 t的圆盘移动到 柱子上 * /
void Move(int t,char x,char y) [coutmove t from x to yendl;
/*将 n个圆盘从 a 柱子借助 b 柱子移到 c 柱子 * /
void Hannoi(int n,char a,char b,char c)
{if(n1)
move(1,a,c)
Move(1,a,c); /* 若只有一个圆盘则直接将该圆盘由 a 柱子移到 c 柱子 * /
else
{
Hannoi(n-1,a,c,b); / * 把 a 柱子上的 n-1个圆盘借助 c 柱子移到 b 柱子上* /
Move(n,a,c); /*把 a 柱子上剩下的一个盘子移到 c 柱子上*/
Hannoi(n-1,b,a,c); /*把b 柱子上的 n-1个圆盘借助 a 柱子移到 c 柱子上* /}
})int main()
int n;
scanf(%d,n);
Hannoi(n,a,b,c) ;
return 0;
}
02、木棒三角形
问题描述:
小A家里有很多长度不一的木棒有一天他很无聊摆弄这些木棒解闷。小A的数学学得很好所以他想在这些木棒中挑出三根木棒组成一个直角三角形当然这可能有很多种选法他还想挑出三根木棒组成一个面积最大的直角三角形。
输入:
输入有多组每组输入包括两行第一行输入一个n(0≤n≤100)表示小A有n根木棒接着一行有n个整数n≤1000表示木棒的长度长度从小到大给出。
输出:
输出面积最大的直角三角形的面积且保留3位小数若不能组成则输出“My Good!”。
输入数据:
4
1 2 3 4
5
2 3 4 5 6
6
3 4 5 6 8 10
2
1 1
输出数据:
My Good!
6.000
24.000
My Good!
解题思路:
看到题目很容易想到如果求出从n根木棒中选出三根木棒的所有情况的解那答案也就出来了。
现在的主要问题是怎么用程序枚举所有情况。我们知道直角三角形的三条边中斜边是最长的题目给出一个“长度从小到大给出”的条件这样我们可以依次枚举三角形中长度最短、第二长和最长的边具体实现代码如下。
参考程序:
#include stdio.h
#includestdlib.h
int main()
{
int i,j,k;
double ans;
int n;
int len[110];
while(scanf(rd,n)!EOF)
{for(i 1;i n;i)scanf(%d,len[i]); //存储木棒长度
ans -1;
for(i l;i n;i){ //枚举最短木棒
for(j il;j n;j){ //枚举第二长的木棒
for(k j1;k n;k){ //枚举最长的木棒
if(len[i]*len[i] len[j]*len[j] len[k]* len[k]){ //如果是直角三角形
if(0.5*len[i]*len[j] ans) //取最优解
ans 0.5*len[i]*len[j];
}
}
}
}if(ans -1)
printf(My Good! \n);
else
printf(%.3lf\n,ans);
}
