首页 > 代码库 > 转一下递归
转一下递归
递归专题：
我个人认为递归是算法中很重要的武器，虽然递归的效率很慢，但他是我们学习其他算法的基础，而递归这一算法又很抽象，也很难调试，所以我认为我有必要要这里好好理解递归这一有力的武器。。
表达式的转化：
#include<cstdio>
#include<iostream>
#include<math.h>
#include <string>
using namespace std;
double calc()
{
char s[10];
cin>>s;
switch (s[0])
{
case ‘+‘: {calc();printf("+");calc();break;}
case ‘-‘: {calc();printf("-");calc();break;}
case ‘*‘: {calc();printf("*");calc();break;}
case ‘/‘: {calc();printf("/");calc();break;}
default:cout<<s;
}
}
int main()
{
double f = calc();
// printf("%f\n",f);
return 0;
}
逆波兰表达式：
//#include<isotream>
#include<cstdio>
#include<math.h>
using namespace std;
double exp()
{
char a[10];
scanf("%s",a);
switch(a[0])
{
case‘+‘:return exp()+exp();
case‘-‘:return exp()-exp();
case‘*‘:return exp()*exp();
case‘/‘:return exp()/exp();
default:return atof(a); }
}
int main()
{
double ans;
ans=exp();
printf("%f",ans);
return 0;
}
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 17936 | Accepted: 11317 |
Description
Input
Output
Sample Input
1 7 3
Sample Output
8
Source
很好的算法：
f(m, n) = f(m-n, n) + f(m, n-1)
f(m, n): 把m个苹果放到n个盘子中的方法数
f(m, n-1): 把m个苹果放到n-1个盘子中的方法数(其中至少有一个空盘子)
f(m-n, n): 把m个苹果放到n个盘子中,而且每个盘子中都有苹果(先拿n个出来,等m-n个放好了,然后每个盘子放一个)
#include <iostream>
#include <vector>#include <string>#include <math.h>#include <iomanip>#include <stdlib.h>using namespace std;int PlaceApple(int m, int n)
{
if(m < 0) return 0; if(m == 0) //每个盘子一个 return 1; if(n == 1) //只有一个盘子 return 1; return PlaceApple(m - n, n) + PlaceApple(m, n - 1);
}int main(){ int num,m,n; cin>>num; while (num>0)
{ cin>>m>>n; cout<<PlaceApple(m,n)<<endl; num--;
}}例子2：
| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 14298 | Accepted: 7416 |
Description
Write a program to count the number of black tiles which he can reach by repeating the moves described above.
Input
There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.
‘.‘ - a black tile
‘#‘ - a red tile
‘@‘ - a man on a black tile(appears exactly once in a data set)
The end of the input is indicated by a line consisting of two zeros.
Output
Sample Input
6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 11 9 .#......... .#.#######. .#.#.....#. .#.#.###.#. .#.#..@#.#. .#.#####.#. .#.......#. .#########. ........... 11 6 ..#..#..#.. ..#..#..#.. ..#..#..### ..#..#..#@. ..#..#..#.. ..#..#..#.. 7 7 ..#.#.. ..#.#.. ###.### ...@... ###.### ..#.#.. ..#.#.. 0 0
Sample Output
45 59 6 13
Source
解法1：
上面的return 1+f(x-1,y)+f(x+1,y)+f(x,y+1)+f(x,y-1)这里属于递推公式，这时比如要计算f(x,y)的时，这时就会向这f(x-1,y)这个方向一直深搜下去，一直到f(x-1,y)这个方向没有地方可以走了，这时就要在当前的位置继续深搜f(x-1,y)这个方向，接着就会继续深搜f(x-1,y)这个方向，同样直到f(x-1,y)这个方向不能再进行时，继续深搜f(x+1,y)这个方向，直到这个方向无路可走，就继续深搜f(x,y+1)这个方向.......一直递归下去。到了最后一个方向不行时，这时就要返回上一层继续搜这个方向还未搜到的点.....一直的返回，
阅读这个代码应该好理解点：
#include<stdio.h>
int n,m;
char s[21][21];
int visit[21][21];
int count;
void dfs(int x,int y)
{
visit[x][y]=1;
if(x-1>0&&!visit[x-1][y]&&s[x-1][y]==‘.‘)
{
count++;
dfs(x-1,y);
}
if(y-1>0&&!visit[x][y-1]&&s[x][y-1]==‘.‘)
{
count++;
dfs(x,y-1);
}
if(x+1<=n&&!visit[x+1][y]&&s[x+1][y]==‘.‘)
{
count++;
dfs(x+1,y);
}
if(y+1<=m&&!visit[x][y+1]&&s[x][y+1]==‘.‘)
{
count++;
dfs(x,y+1);
}
}
int main (void)
{
int i,j;
int x,y;
while(scanf("%d %d",&m,&n),n!=0||m!=0)
{
count=1;
for(i=1;i<21;i++)
for(j=1;j<21;j++)
visit[i][j]=0;
for(i=1;i<=n;i++)
{
getchar();
for(j=1;j<=m;j++)
{
scanf("%c",&s[i][j]);
if(s[i][j]==‘@‘)
{
x=i;
y=j;
}
}
}
dfs(x,y);
printf("%d\n",count);
}
return 0;
}
下面再来看一个问题，就是
记得在我们最开始学习C语言的时候，每当讲到递归，无论是课本上，还是老师，都会给出两个经典例子的递归实现，其中一个就是阶乘，另外一个就是Fibonacci（中文多译成斐波那契）数列了。
用递归方法计算阶乘的代码如下：
//递归计算阶乘
long Factorial(int n)
{
if (n <= 0)
{
return 1;
}
return n * Factorial(n - 1);
}
这样的递归是一个很明显的尾部递归的例子，所谓的尾部递归（tail recursion），即递归调用是函数执行的最后一项任务，函数在递归调用返回之后不再做任何事情。尾部递归可以很方便的转换成一个简单循环，完成相同 的任务，这样，就将一个递归的实现转化成了非递归实现。
以下是阶乘算法的非递归实现：
//计算阶乘的非递归实现
long Factorial(int n)
{
long result = 1;
while (n > 1)
{
result *= n;
n--;
}
return result;
}
单从这个改写来看，我们无法看出这样的改写有多大的意义。但是有些时候，递归并不是一种很好的解决问题的方法，最常见的一个问题就是深度递归会造成堆栈溢出的错误！有时候递归还会导致程序效率的下降，下面要说的Fibonacci数列，就是一个很好的反例。
Fibonacci数列使用递归的定义（呃。。。定义就不给了），这种定义容易诱导我们使用递归形式来编程解决这个问题。下面是一个Fibonacci的递归实现，很容易就看懂了，呵呵，就是定义的程序版本：
//递归计算Fibonacci数列的值
typedef unsigned long ulong;
ulong Fiblnacci(int n)
{
if (n <= 2)
{
return 1;
}
return Fiblnacci(n - 1) + Fiblnacci(n-2);
}
这样的程序是非常简捷的，有时候，递归的程序实现看上去要比非递归的实现简捷得多。这个时候，你需要在效率和程序的可读性和可维护性上做一些取舍。
这个Fibonacci的递归实现在计算值时，每次递归调用都触发另外两个递归，而这两个递归在调用的时候每个都还要触发两外的两个递归调用，再接 下去的调用也是如此。现在，我们知道，这个冗余的递归调用是以几何级数增长的。例如，在递归计算Fibonacci(10)时，Fibonacci(3) 的值被计算了21次。
为什么会是21次呢，这里可以打个比方，比如当要计算F（10）时，这时F（10）就会吩咐下去计算F(9)的值F（9）就会吩咐去计算F（8）的值，F（8）就会吩咐计算F（7）的值，一直下去，当到F（2）时，这时返回1的值回来，接着就要返回上一层，这时F（3）又吩咐计算F（1）的值，F（1）又返回1的值回来，这时F（3）的值就确定下来了，接着F（3）心里默念的它的值把它交给了F（4），可是F（4）又要吩咐去算F（2）的值，这时F（2）又返回了1，这时F（4)的值为F（3）+F（2）；这时F（4）默念着它的值，又把它的值交给了F（5），这时F（5）又要命令去算F（3）的值，这时F（3）又要递归它的值，算出它的值后再交给F（5）；这时F（5）默念着他的值然后交给F（6），这时F（6）又要吩咐去算F（4）的值，此时F（4）就又得吩咐去算F（3）与F（2）的值，这样不断的进行下去，F（3）的值会不断的被命令去算，所以会有21次。这里足见其效率之低。。
而在递归计算Fibonacci(30)，这个调用的次数是骇人的317811次！这些个计算实际上只有一次是必要的，其余的纯属浪 费！
下面的程序使用一个简单循环来代替递归，这个非递归的形式不如上文给出的递归简单（当然，这个也很简单），也不太符合Fibonacci的递归定义，但是，它的效率提高了几十万倍！
//Fibonacci数列的非递归实现
typedef unsigned long ulong;
ulong Fibonacci(int n)
{
ulong result;
ulong prev_result;
ulong next_result;
result = prev_result = 1;
while (n > 2)
{
n--;
next_result = prev_result;
prev_result = result;
result = prev_result + next_result;
}
return result;
}
所以，本文的结论就是，当你使用递归实现一个函数之前，先问问自己使用递归的好处是否抵得上它的代价。当然，编程的时候，无论什么实现方式，我们都应该问问自己这个问题。
斐波那契数列最初出现是计算兔子的数目，所以又被称为“兔子数列”，所以看到农夫养牛等问题，还是可以联系上的。
关于斐波那契的讨论，主要集中在对其的优化，以及其扩展题目上，递归已经由只有一项在变，变成两项在变了。其扩展的题目，如何得到递归式，如何透过现象来将递归式写出来，才是真正的要点。
包括农夫养牛问题，爬楼梯问题，打靶问题等等，应该算起来都算是斐波那契问题的一些扩展。
【扩展】
1. 一个农夫养了一头牛，三年后，这头牛每年会生出1头牛，生出来的牛三年后，又可以每年生出一头牛……问农夫10年后有多少头牛?n年呢
老外喜欢养牛，在很多题目中都可以看到奶牛还是什么牛的身影。这道题目的网址为：
http://topic.csdn.net/u/20091001/15/40bf4993-8ed7-45cc-968f-97c524dae3c4.html?80749
而前段时间园子中有兄弟已经详细探讨了这个问题。
http://www.cnblogs.com/chinese-zmm/archive/2009/10/31/1593586.html
关于这个问题，其实一开始遇到是使用模拟的思路去想的，而且想得比较的糊涂，因为牛生下来之后，并不是马上就可以生小牛，是在三年后，每年生一头牛，那假设某一年，就有能生小牛的，还有一年生小牛的，还有两年生小牛的，然后就自己把自己绕住了。
但是，其实没有这么复杂，就是将其分为能生小牛的和不能生小牛的。
从而得到：
今年的牛的数目=去年的牛的数目+三年前牛的数目
也就是f(n)=f(n-1)+f(n-3)
这里
f(n-2) 第一年
f(n-1) 第二年
f(n) 第三年
看了一下题目，应该是三年后，那就应该是n-3。
代码如下：
1 #include <iostream>
2 using namespace std;
3
4 int Fibonacci(int n)
5 {
6 if (n==1 || n==2 || n==3)
7 {
8 return 1;
9 }
10 return Fibonacci(n-1)+Fibonacci(n-3);
11 }
12
13 int main()
14 {
15 cout<<Fibonacci(10+1)<<endl;
16 }
这里计算F（10）的道理跟之前一样的，F（10）这一年的值是由F（9）和F（7）这两年的和得来的，这时F（10）就会吩咐去计算F（9 ）的值，F（9）又会吩咐去计算F（8）的值.......一直到F（3）的值，这时就会返回F（3）的值给F（4），此时F（4）又要吩咐去计算F（2）的值，即算出F（4）的值后默念交给F（5），这时F（5）又要吩咐去计算F（2）的值，此时F（2）返回它的值给F（5），则F（5）的值就是F（2）+F（4）的值，接着F（5）默念的它的值交给了F（6），此时F（6）又要吩咐去计算F（4）的值，F（4）又要重新递归一次，就这样不断的进行下去。
这里输入参数为n+1，是因为是n年后的数目，所以需要加1。
这道题目，也可以使用数组将运算的结果保存下来，然后直接进行计算，这就是常说的动态规划。
代码如下：
1 int Fibonacci2(int n)
2 {
3 int *num=new int[n];
4 num[0]=num[1]=num[2]=1;
5 for (int i=3;i<n;i++)
6 {
7 num[i]=num[i-1]+num[i-3];
8 }
9 int ret=num[n-1];
10 delete []num;
11 return ret;
12 }
13
14 int main()
15 {
16 cout<<Fibonacci2(10+1)<<endl;
17 }
2. 打靶问题： 一个人打靶，成绩为0～10之间的任意一个整数。包括0和10。一共打了10次总共得分89分。问得分的可能性。
可以得到比较明显的一个递归式，f(n)=x+f(n-1)，而x的取值为0-10之间的任意一个整数。
所以我们需要去做一个变化的x，其实也就是一个循环来得到。
因为要求的结果为得分的可能性，所以我们要将结果保存起来，然后每遇到结果为89的，则将保存的结果打印出来，然后统计+1，所以我们需要一个10个数的数组来做这件事情。
递归终止条件是当n为0时终止，此时来判断分值并进行相应的操作。
1 #include <iostream>
2 using namespace std;
3
4 int countresult;
5 int store[10];
6
7
8 void getscore(int sum, int n)
9 {
10 if(sum<0 || sum+(n+1)*10<89 || sum>89)
11 return;
12 if(n==0)
13 {
14 //check the number
15 if(sum==89)
16 {
17 for(int i=0;i<10;i++)
18 cout<<store[i]<<" ";
19 cout<<endl;
20 countresult++;
21 }
22 return;
23 }
24 for(int i=0;i<=10;i++)
25 {
26 store[10-n]=i;
27 getscore(sum+i,n-1);
28 }
29 }
30
这里的递归就类似深搜了，这里不再多解释。
31 int main()
32 {
33 getscore(0,10);
34 cout<<"总数"<<countresult<<endl;
35 return 0;
36 }
注意上面的代码，其实上面还是应用了递归中常使用的一种做法--剪枝。
上面的代码并不太好，比较好的是下面的代码，但是两种方法作出的值是一样的。
1 #include <iostream>
2 using namespace std;
3
4 int sum;
5 int store[10];
6
7 void Output()
8 {
9 for(int i = 9; i>=0; --i)
10 {
11 cout<<store[i]<<" ";
12 }
13 cout<<endl;
14 ++sum;
15 }
16
17 void Cumput(int score, int num)
18 {
19 if(score < 0 || score > (num+1)*10 ) //次数num为0～9
20 return;
21 if(num == 0)
22 {
23 store[num] = score;
24 Output();
25 return;
26 }
27 for(int i = 0; i <= 10; ++i)
28 {
29 store[num] = i;
30 Cumput(score - i, num - 1);
31 }
32 }
33
34 int main(int argc, char* argv[])
35 {
36 Cumput(89, 9);
37 cout<<"总数:"<<sum<<endl;
38 return 0;
39 }
3. 爬楼梯问题：
一个N级的楼梯，一个人每次可以爬一级，也可以爬两级，问如果给定一个N要求输出所有的爬楼方法，并统计出方法数 。
可 以思考，在第n级的时候，可以通过f(n-1)爬1级得到，也可以通过f(n-2)爬两级得到，如果f(n-2)爬1级，也就是又到f(n- 1)，其实是涵盖在前面一种情况下的。所以得到递归公式： f(n)=f(n-1)+f(n-2)，很明显，得到递归公式后，就是斐波那契数列。
再扩展，如果每次可以爬一级，也可以爬两级，也可以爬三级。那此时递归公式怎么推？
此时就要加上f(n-3)的情况，而f(n-3)上面爬2级，爬1级，又回到f(n-2)或者f(n-1)，所以得到递归式为
f(n)=f(n-1)+f(n-2)+f(n-3)
关于斐波那契的类似问题很多，但是如何思考得到递归式是重点，当得到正确的递归式后，就明白是斐波那契，那就能够直接使用斐波那契相关的方法来做该问题了。
最后有一道思考题，是概率题：
一副52张的牌（去掉大小鬼），4张A排在一起的概率是多少？
为 了避免误解题意，将原题也放在这里 (A deck of 52 cards is shuffled thoroughly. What is the probability that the 4 aces are all next to each other?)
从中选择：
(a) 4!49!/52!
(b) 1/52!
(c) 4!/52!
(d) 4!48!/52!
(e) 都不是
(f) 是未知的
递归算法详解
C通过运行时堆栈支持递归函数的实现。递归函数就是直接或间接调用自身的函数。
许多教科书都把计算机阶乘和菲波那契数列用来说明递归，非常不幸我们可爱的著名的老潭老师的《C语言程序设计》一书中就是从阶乘的计算开始的函数递归。导 致读过这本经书的同学们，看到阶乘计算第一个想法就是递归。但是在阶乘的计算里，递归并没有提供任何优越之处。在菲波那契数列中，它的效率更是低的非常恐 怖。
这里有一个简单的程序，可用于说明递归。程序的目的是把一个整数从二进制形式转换为可打印的字符形式。例如：给出一个值4267，我们需要依次产生字符‘4’，‘2’，‘6’，和‘7’。就如在printf函数中使用了%d格式码，它就会执行类似处理。
我们采用的策略是把这个值反复除以10，并打印各个余数。例如，4267除10的余数是7，但是我们不能直接打印这个余数。我们需要打印的是机器字符集中 表示数字‘7’的值。在ASCII码中，字符‘7’的值是55，所以我们需要在余数上加上48来获得正确的字符，但是，使用字符常量而不是整型常量可以提 高程序的可移植性。‘0’的ASCII码是48，所以我们用余数加上‘0’，所以有下面的关系：
‘0’+ 0 =‘0’
‘0’+ 1 =‘1’
‘0’+ 2 =‘2’
...
从这些关系中，我们很容易看出在余数上加上‘0’就可以产生对应字符的代码。接着就打印出余数。下一步再取商的值，4267/10等于426。然后用这个值重复上述步骤。
这种处理方法存在的唯一问题是它产生的数字次序正好相反，它们是逆向打印的。所以在我们的程序中使用递归来修正这个问题。
我们这个程序中的函数是递归性质的,因为它包含了一个对自身的调用。乍一看，函数似乎永远不会终止。当函数调用时，它将调用自身，第2次调用还将调用自身，以此类推，似乎永远调用下去。这也是我们在刚接触递归时最想不明白的事情。但是，事实上并不会出现这种情况。
这个程序的递归实现了某种类型的螺旋状while循环。while循环在循环体每次执行时必须取得某种进展，逐步迫近循环终止条件。递归函数也是如此，它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时，它便不在调用自身 。
在程序中，递归函数的限制条件就是变量quotient为零。在每次递归调用之前，我们都把quotient除以10，所以每递归调用一次，它的值就越来越接近零。当它最终变成零时，递归便告终止。
#include <stdio.h>
int binary_to_ascii( unsigned int value)
{
unsigned int quotient;
quotient = value / 10;
if( quotient != 0)
binary_to_ascii( quotient);
putchar ( value % 10 + ‘0‘ );
}
递归是如何帮助我们以正确的顺序打印这些字符呢？下面是这个函数的工作流程。
1. 将参数值除以10
2. 如果quotient的值为非零，调用binary-to-ascii打印quotient当前值的各位数字
3. 接着，打印步骤1中除法运算的余数
注意在第2个步骤中，我们需要打印的是quotient当前值的各位数字。我们所面临的问题和最初的问题完全相同，只是变量quotient的 值变小了。我们用刚刚编写的函数（把整数转换为各个数字字符并打印出来）来解决这个问题。由于quotient的值越来越小，所以递归最终会终止。
一旦你理解了递归，阅读递归函数最容易的方法不是纠缠于它的执行过程，而是相信递归函数会顺利完成它的任务。如果你的每个步骤正确无误，你的限制条件设置正确，并且每次调用之后更接近限制条件，递归函数总是能正确的完成任务。
但是，为了理解递归的工作原理，你需要追踪递归调用的执行过程，所以让我们来进行这项工作。追踪一个递归函数的执行过程的关键是理解函数中所声 明的变量是如何存储的。当函数被调用时，它的变量的空间是创建于运行时堆栈上的。以前调用的函数的变量扔保留在堆栈上，但他们被新函数的变量所掩盖，因此 是不能被访问的。
当递归函数调用自身时，情况于是如此。每进行一次新的调用，都将创建一批变量，他们将掩盖递归函数前一次调用所创建的变量。当我追踪一个递归函数的执行过程时，必须把分数不同次调用的变量区分开来，以避免混淆。
程序中的函数有两个变量：参数value和局部变量quotient。下面的一些图显示了堆栈的状态，当前可以访问的变量位于栈顶。所有其他调用的变量饰以灰色的阴影，表示他们不能被当前正在执行的函数访问。
假定我们以4267这个值调用递归函数。当函数刚开始执行时，堆栈的内容如下图所示：
执行除法之后，堆栈的内容如下：
接着，if语句判断出quotient的值非零，所以对该函数执行递归调用。当这个函数第二次被调用之初，堆栈的内容如下：
堆栈上创建了一批新的变量，隐藏了前面的那批变量，除非当前这次递归调用返回，否则他们是不能被访问的。再次执行除法运算之后，堆栈的内容如下：
quotient的值现在为42，仍然非零，所以需要继续执行递归调用，并再创建一批变量。在执行完这次调用的出发运算之后，堆栈的内容如下：
此时，quotient的值还是非零，仍然需要执行递归调用。在执行除法运算之后，堆栈的内容如下：
不算递归调用语句本身，到目前为止所执行的语句只是除法运算以及对quotient的值进行测试。由于递归调用这些语句重复执行，所以它的效果 类似循环：当quotient的值非零时，把它的值作为初始值重新开始循环。但是，递归调用将会保存一些信息（这点与循环不同），也就好是保存在堆栈中的 变量值。这些信息很快就会变得非常重要。
现在quotient的值变成了零，递归函数便不再调用自身，而是开始打印输出。然后函数返回，并开始销毁堆栈上的变量值。
每次调用putchar得到变量value的最后一个数字，方法是对value进行模10取余运算，其结果是一个0到9之间的整数。把它与字符常量‘0’相加，其结果便是对应于这个数字的ASCII字符，然后把这个字符打印出来。
接着函数返回，它的变量从堆栈中销毁。接着，递归函数的前一次调用重新继续执行，她所使用的是自己的变量，他们现在位于堆栈的顶部。因为它的value值是42，所以调用putchar后打印出来的数字是2。
接着递归函数的这次调用也返回，它的变量也被销毁，此时位于堆栈顶部的是递归函数再前一次调用的变量。递归调用从这个位置继续执行，这次打印的数字是6。在这次调用返回之前，堆栈的内容如下：
现在我们已经展开了整个递归过程，并回到该函数最初的调用。这次调用打印出数字7，也就是它的value参数除10的余数。
然后，这个递归函数就彻底返回到其他函数调用它的地点。
如果你把打印出来的字符一个接一个排在一起，出现在打印机或屏幕上，你将看到正确的值：4267
汉诺塔问题递归算法分析：
一个庙里有三个柱子，第一个有64个盘子，从上往下盘子越来越大。要求庙里的老和尚把这64个盘子全部移动到第三个柱子上。移动的时候始终只能小盘子压着大盘子。而且每次只能移动一个。
1、此时老和尚（后面我们叫他第一个和尚）觉得很难，所以他想：要是有一个人能把前63个盘子先移动到第二个柱子上，我再把最后一个盘子直接移 动到第三个柱子，再让那个人把刚才的前63个盘子从第二个柱子上移动到第三个柱子上，我的任务就完成了，简单。所以他找了比他年轻的和尚（后面我们叫他第 二个和尚），命令：
① 你丫把前63个盘子移动到第二柱子上
② 然后我自己把第64个盘子移动到第三个柱子上后
③ 你把前63个盘子移动到第三柱子上
2、第二个和尚接了任务，也觉得很难，所以他也和第一个和尚一样想：要是有一个人能把前62个盘子先移动到第三个柱子上，我再把最后一个盘子直接移动到第 二个柱子，再让那个人把刚才的前62个盘子从第三个柱子上移动到第三个柱子上，我的任务就完成了，简单。所以他也找了比他年轻的和尚（后面我们叫他第三和 尚），命令：
① 你把前62个盘子移动到第三柱子上
② 然后我自己把第63个盘子移动到第二个柱子上后
③ 你把前62个盘子移动到第二柱子上
3、第三个和尚接了任务，又把移动前61个盘子的任务依葫芦话瓢的交给了第四个和尚，等等递推下去，直到把任务交给了第64个和尚为止（估计第64个和尚很郁闷，没机会也命令下别人，因为到他这里盘子已经只有一个了）。
4、到此任务下交完成，到各司其职完成的时候了。完成回推了：
第64个和尚移动第1个盘子，把它移开，然后第63个和尚移动他给自己分配的第2个盘子。
第64个和尚再把第1个盘子移动到第2个盘子上。到这里第64个和尚的任务完成，第63个和尚完成了第62个和尚交给他的任务的第一步。
从上面可以看出，只有第64个和尚的任务完成了，第63个和尚的任务才能完成，只有第2个和尚----第64个和尚的任务完成后，第1个和尚的任务才能完成。这是一个典型的递归问题。 现在我们以有3个盘子来分析：
第1个和尚命令：
① 第2个和尚你先把第一柱子前2个盘子移动到第二柱子。（借助第三个柱子）
② 第1个和尚我自己把第一柱子最后的盘子移动到第三柱子。
③ 第2个和尚你把前2个盘子从第二柱子移动到第三柱子。
很显然，第二步很容易实现（哎，人总是自私地，把简单留给自己，困难的给别人）。
其中第一步，第2个和尚他有2个盘子，他就命令：
① 第3个和尚你把第一柱子第1个盘子移动到第三柱子。（借助第二柱子）
② 第2个和尚我自己把第一柱子第2个盘子移动到第二柱子上。
③ 第3个和尚你把第1个盘子从第三柱子移动到第二柱子。
同样，第二步很容易实现，但第3个和尚他只需要移动1个盘子，所以他也不用在下派任务了。（注意：这就是停止递归的条件，也叫边界值）
第三步可以分解为，第2个和尚还是有2个盘子，命令：
① 第3个和尚你把第二柱子上的第1个盘子移动到第一柱子。
② 第2个和尚我把第2个盘子从第二柱子移动到第三柱子。
③ 第3个和尚你把第一柱子上的盘子移动到第三柱子。
分析组合起来就是：1→3 1→2 3→2 借助第三个柱子移动到第二个柱子 |1→3 自私人留给自己的活| 2→1 2→3 1→3 借助第一个柱子移动到第三个柱子|共需要七步。
如果是4个盘子，则第一个和尚的命令中第1步和第3步各有3个盘子，所以各需要7步，共14步，再加上第1个和尚的1步，所以4个盘子总共需要移动 7+1+7=15步，同样，5个盘子需要15+1+15=31步，6个盘子需要31+1+31=64步……由此可以知道，移动n个盘子需要（2的n次 方）-1步。
从上面整体综合分析可知把n个盘子从1座（相当第一柱子）移到3座（相当第三柱子）：
（1）把1座上（n-1）个盘子借助3座移到2座。
（2）把1座上第n个盘子移动3座。
（3）把2座上（n-1）个盘子借助1座移动3座。
下面用hanoi（n,a,b,c）表示把1座n个盘子借助2座移动到3座。
很明显: (1)步上是 hanoi(n-1,1,3,2)
(3)步上是 hanoi(n-1,2,1,3)
用C语言表示出来，就是：
#include <stdio.h>
int method(int n,char a, char b)
{
printf("number..%d..form..%c..to..%c.."n",n,a,b);
return 0;
}
int hanoi(int n,char a,char b,char c)
{
if( n==1 ) move (1,a,c);
else
{
hanoi(n-1,a,c,b);
move(n,a,c);
hanoi(n-1,b,a,c);
};
return 0;
}
int main()
{
i nt num;
scanf("%d",&num);
hanoi(num,‘A‘,‘B‘,‘C‘);
return 0;
}
递推：
献给杭电五十周年校庆的礼物
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 3580 Accepted Submission(s): 1791
或许你依然心怀忧伤
或许你近在咫尺
或许你我天各一方
对于每一个学子
母校
永远航行在
生命的海洋
今年是我们杭电建校五十周年，这是一个值得祝福的日子。我们该送给母校一个怎样的礼物呢？对于目前的大家来说，最好的礼物当然是省赛中的好成绩，我不能参赛，就送给学校一个DOOM III球形大蛋糕吧，这可是名牌，估计要花掉我半年的银子呢。
想象着正式校庆那一天，校长亲自操刀，把这个大蛋糕分给各地赶来祝贺的校友们，大家一定很高兴，呵呵，流口水了吧...
等一等，吃蛋糕之前先考大家一个问题：如果校长大人在蛋糕上切了N刀（校长刀法极好，每一刀都是一个绝对的平面），最多可以把这个球形蛋糕切成几块呢？
做不出这个题目，没有蛋糕吃的！
为-了-母-校-，为-了-蛋-糕-（不是为了DGMM，枫之羽最会浮想联翩...），加-油-！
用带定系数法求出各个系数就OK了，不用想破脑筋找规律。。。。。。
(n * n * n + 5*n) / 6 + 1;
#include <stdio.h>2
#include <stdlib.h>3
int main ()4
{5
int n;6
__int64 result;7
while ( scanf ("%d", &n) != EOF )8
{9
result = ( n * n * n + 5 * n) / 6 + 1;10
printf ("%I64d\n", result); 11
}12
return 0;13
}转一下递归