汉诺塔问题
如图,汉诺塔问题是指有三根杆子A,B,C。C杆上有若干碟子,把所有碟子从C杆上移到B杆上,每次只能移动一个碟子,大的碟子不能叠在小的碟子上面。求最少要移动多少次?
当n=1时:
Move 1 from A to C
当n=2时:
Move 1 from A to B
Move 2 from A to C
Move 1 from B to C
Move 2 from A to C
Move 1 from B to C
当n=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
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
源代码
#include <iostream>
#include <cstdio>
using namespace std;
void hannoi (int n, char A, char B, char C) // 把A盘里面的圆圈转移到C盘里面【A--C】。
{
if (n == 1)
{
cout << "移动圆圈" << n << "从盘" << A << "盘" << C << endl; //把最后一个圆环从起点盘移动到目标盘。
}
else
{
hannoi (n-1, A, C, B); // 把N-1个圆环从起点盘移动到(当前)没有任何圆环的过度盘;通过B、C盘在此函数调用中调用位置的互换,来实现把N-1个圆环从A盘到B盘的转移【A--B】。
cout << "移动圆圈" << n << "从盘" << A << "盘" << C << endl;
hannoi (n-1, B, A, C); // 把N-1个圆环从国度盘移动到目标盘(模仿1和2的操作方法来实现);通过A、B盘在此函数调用中位置的互换,来实现N-1个圆环从B盘到C盘的转移【B--C】。
}
}
int main()
{
int n;
cin >> n;
hannoi (n, 'a', 'b', 'c');
system("pause");
return 0;
}
fibonacci数列
斐波纳契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、……在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*)
源代码
/*
fibonacci数列
@param n
@return
*/
long fibonacci(int n)
{
if((0 == n) || (1 == n))
{
return n;
}
else
{
return fibonacci(n-1) + fibonacci(n-2);
}
}
当然递归的经典例子还有很多,比如简单的累乘,累加这里就不一一实现了,读者可以自己实现以下,如果发现问题,可以留言。