共有回帖数 0 个
-
众所周知，递归是一种重要的方法，我对递归可谓是一窍不通，至今没破……
Recursion is the name for the case when a function invokes itself or invokes a sequence of other functions,one of which eventually invokes the first function again.
递归就是一个函数调用自身或者调用一系列的函数，其中某个函数又调用了第一个函数。书上就是这么写的，我不知道我翻译的准不准确。
介绍递归最主要就是介绍栈帧和递归树，栈帧也叫过程活动记录，是编译器用来实现过程或函数调用的一种数据结构。从逻辑上讲，栈帧就是一个函数执行的环境：函数参数、函数的局部变量、函数执行完后返回到哪里等等。
举个例子：假如我们有三个函数分别叫做A、B和C，假设A调用B，B调用C，所以当函数C没有完成并返回时函数B不会完成，这样，函数A最先被调用但是是最后一个完成，直到B完成并返回后A 才会完成，用栈帧来表达就是这样——
首先让我们先来了解一下简单的递归应用：阶乘
int factorial(int n)//求n的阶乘
{
if(n==0)
return 1;//返回0的阶乘为1；
else
return n*factorial(n-1);//返回n的阶乘为n*(n-1)!，factorial通过调用自身实现递归
}
我们在来看一个比较简单的递归应用：求第n个fibonacci数
所谓的fibonacci数列指的是第零个数为0，第一个数为1（这里为了与后面对应所以第一个数称为第零个），从第三个数开始每个数都是它之前两个数的和，即： f0=0;f1=1;f2=f0+f1=1;f3=f2+f1=3……
第n个fibonacci数也就是fn，应该等于f(n-2)+f(n-1)，所以我们能写出程序：
int fibonacci(int n)
{
if(n=0)
return 0;
else if(n==1)
return 1;
else
return fibonacci(n-2)+fibonacci(n-1);
}
递归的经典应用：汉诺塔问题——有三根柱子A、B、C，柱子A由下到上有从大到小n个盘子，编号从上到下为1到n，要把这n个盘子利用柱子B全部移动到柱子C上，每次只能移动一个盘子并且要保证上面的盘子一定比下面的盘子小。
对于这个问题，我们首先是要把最下面的盘子n移动到柱子C上，这样就要求把上面的n-1个盘子利用柱子C移动到柱子B上面，然后我们又要把上面n-2个盘子从柱子B利用柱子C移动到柱子A上使第n-1个盘子能够移动到柱子C上，然后是柱子A上的n-3个盘子移动到柱子B上把第n-2个盘子移动到柱子C上……以此类推，一直到只剩盘子1，把盘子1移动到柱子C上。
根据上面的思路我们可以写出程序：
#includeiostream
using namespace std;
void hanio(int n,char,char,char);
void main()
{
char A='A',B='B',C='C';
int n=3;
hanio(n,A,B,C);
}
void hanio(int n,char A,char B,char C)
{
if(n==1)
{
cout"将第"n"个盘面从"A"柱搬到"C"柱上"endl;
}
else
{
hanio(n-1,A,C,B);
cout"将第"n"个盘面从"A"柱搬到"C"柱上"endl;
hanio(n-1,B,A,C);
}
}
运行结果是：将第1个盘面从A柱搬到C柱上，将第2个盘面从A柱搬到B柱上，将第1个盘面从C柱搬到B柱上，将第3个盘面从A柱搬到C柱上，将第1个盘面从B柱搬到A柱上，将第2个盘面从B柱搬到 C柱上，将第1个盘面从A柱搬到C柱上
科学计算表明，解决有n个盘子的汉诺塔问题，需要移动盘子的次数为2的n次方减1次。
下面我们来说回溯算法，所谓回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
回溯法的经典问题有“八皇后问题”——在8*8的棋盘上放置8个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后）这个问题我也不很明白，把代码发上来，大家自己研究吧
这里感谢开源中国G0561的代码：
/*
回溯法是 按照某种条件往前试探搜索，若前进中遭到失败，则回过头来继续搜索
回溯的设计：
1. 用栈保存好前进中的某些状态
2.制定好约束条件
*/
#includeiostream
using namespace std;
void Queen(int j,int (*a)[8]); //递归搜索试探放置皇后
int Judge(int i,int j,int (*a)[8]); //判断在a[j]是否可以放置皇后 int ncount = 0;
int main()
{
int i,j;
int a[8][8] = {0};
Queen(0,a);
coutncountendl;
system("pause");
return 0;
}
///////////////////////////////////////////////////////////
void Queen(int j,int (*a)[8])
{
int i,k,;
if (j==8) //递归结束条件
{
ncount++;
//打印正确的放置
for (i=0; i8; i++)
{
for (k=0; k8; k++)
{
couta[k]" ";
}
coutendl;
}
getchar(); //按一个确认键看下一个，可看到所有排列
coutendl;
}
for (i=0; i8; i++)
{
if (1==Judge(i,j,a)) //判断当前格子是否可以放置皇后
{
a[j] = 1; //放置皇后
Queen(j+1,a); //向下一列试探是否可以放置皇后
a[j] = 0; //回溯到上一步
}
else
{
continue;
}
}
}
///////////////////////////////////////////////////////////
int Judge(int i,int j,int (*a)[8]) //判断在a[j]是否可以放置皇后
{
int s,t;
for (s=i,t=0; t8; t++ ) //判断行
{
if (a[s][t]==1 && t!=j)
{
return 0;
}
}
// 判断列
for (t=j,s=0; s8; s++)
{
if (a[s][t]==1 && s!=i)
{
return 0;
}
}
//判断左上斜
for (s=i-1,t=j-1; s=0&&t=0; s--,t--)
{
if (a[s][t] == 1)
{
return 0;
}
}
//判断右上斜
for (s=i-1,t=j+1; s=0&&t8; s--,t++)
{
if (a[s][t] == 1)
{
return 0;
}
}
//判断左下斜
for (s=i+1,t=j-1; s8&&t=0; s++,t--)
{
if (a[s][t] == 1)
{
return 0;
}
}
//判断右下斜
for (s=i+1,t=j+1; s8&&t8; s++,t++)
{
if (a[s][t] == 1)
{
return 0;
}
}
return 1;
}
本人新菜一个，语言表达不清楚，图画的也不是很准确，请大神轻喷~
楼主 2016-04-28 11:09 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
