上面这个程序运行一次只能输出斐波那契数列中的一个数值, 下面对该程序进行一个改进, 使得可以输出指定的前 n 位的斐波那契数列, 程序如下:
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
int f(int n){
if(n==0){
return 1;
}else if(n==1){
return 1;
}else{
return f(n-1)+f(n-2);
}
}
int main(){
int n=5; //设置打印前 6 个斐波那契数列元素
for(int i=0;i<=n;i++){
int a=f(i);
printf("%d ",a);
}
system("pause");
return 0;
}
上述程序的运行结果是:
1 1 2 3 5 8
汉诺塔 (Tower of Hanoi)
Wikipedia 上对于汉诺塔问题的说明如下:
The Tower of Hanoi (also called the Tower of Brahma or Lucas’ Tower and sometimes pluralized) is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: 1. Only one disk can be moved at a time. 2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod. 3. No larger disk may be placed on top of a smaller disk.
With 3 disks, the puzzle can be solved in 7 moves. The minimal number of moves required to solve a Tower of Hanoi puzzle is 2n − 1, where n is the number of disks.
但是 A 柱上的圆盘并没有被移动完, 为了能移动完, 我们现在必须想办法让第 3 个圆盘到 C 柱(之后以此类推可以让第 4,5,6…64个圆盘到 C 柱);
于是, 我们把第 1 个圆盘从 B 柱移动到 A 柱, 把第 2 个圆盘从 C 柱移动到 B 柱, 把 第 1 个圆盘从 A 柱移动到 B 柱, 把第 3 个圆盘从 A 柱移动到 C 柱.
好啦, 现在第 3 个圆盘成功的到了 C 柱.
不过还没完, 我们需要重复上面的过程, 直到把第 64 个圆盘移动到 C 柱, 之后, 第 64 个圆盘在之后的移动过程中就可以不用动了, 一直待在 C 柱上.
对于剩下的 63 个圆盘重复和原来 64 个圆盘一样的移动过程即可.
这么移动的工作量是很大的, 移动完全部 64 个圆盘需要大约 1800 亿亿步:
18,446,744,073,709,551,615
根据上面的介绍, 用 C++ 实现的话, 程序是这样的:
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
//假设函数 (int n, char a, char b, char c) 的作用是将 n 个圆盘从 a 移动到 c
void f(int n, char a, char b, char c){
if(n==1){
cout<<"将盘子"<<n<<"从"<<a<<"移动到"<<c<<endl;
//当只有 1 个盘子时, 直接从 a 移动到 c
}else{
f(n-1,a,c,b);
//将 n-1 个圆盘由 a 移动到 b
cout<<"将盘子"<<n<<"从"<<a<<"移动到"<<c<<endl;
f(n-1,b,a,c);
//将 n-1 个圆盘由 b 移动到 c
}
}
int main(){
f(3,'a','b','c');
return 0;
}
上面这个程序的运行结果如下 (圆盘的序号越大则圆盘越大):
假设有三个圆盘, 移动顺序是这样的:
将盘子1从a移动到c
将盘子2从a移动到b
将盘子1从c移动到b
将盘子3从a移动到c
将盘子1从b移动到a
将盘子2从b移动到c
将盘子1从a移动到c
假设有四个圆盘, 移动顺序是这样的:
将盘子1从a移动到b
将盘子2从a移动到c
将盘子1从b移动到c
将盘子3从a移动到b
将盘子1从c移动到a
将盘子2从c移动到b
将盘子1从a移动到b
将盘子4从a移动到c
将盘子1从b移动到c
将盘子2从b移动到a
将盘子1从c移动到a
将盘子3从b移动到c
将盘子1从a移动到b
将盘子1从a移动到b
将盘子2从a移动到c
将盘子1从b移动到c
最后, 来看几个关于汉诺塔问题的动图吧.
图 12:
图 12 By André Karwath aka Aka – Own work, CC BY-SA 2.5, https://commons.wikimedia.org/w/index.php?curid=85401
图 12 By André Karwath aka Aka – Own work, CC BY-SA 2.5, https://commons.wikimedia.org/w/index.php?curid=85401
图 13:
图 13 By Trixx – I designed this using http://thewalnut.io/, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=43282866
#include<iostream>
using namespace std;
int main(){
int ans = 0;
for(int i=10000;i<=99999;i++){
//将每一位上的数字都分离出来
//(i%1000) 取余将去掉当前最高位后形成新的数字
//(i%10000)-(i%1000) 将把当前最高位之后的数字都变成 0
//((i%10000)-(i%1000))/1000 将去掉最高位后面的 0, 形成一个个位数
int a = (i-(i%10000))/10000;
int b = ((i%10000)-(i%1000))/1000;
int c = ((i%1000)-(i%100))/100;
int d = ((i%100)-(i%10))/10;
int e = (i%10);
//如果每个位上的数字都不是 4 则计数器加 1
if(a!=4&&b!=4&&c!=4&&d!=4&&e!=4){
ans++;
}
}
cout<<ans<<endl;
return 0;
}
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
int aa[10]={0,1,2,3,4,5,6,7,8,9};
int sum=0;
int sum1=0;
int sum2=0;
int ans=0;
while(next_permutation(aa,aa+10)){
if(aa[0]!=0&&aa[4]!=0){
sum1=aa[4]*1000+aa[3]*100+aa[5]*10+aa[6];
sum2=aa[0]*1000+aa[1]*100+aa[2]*10+aa[3];
sum=aa[0]*10000+aa[1]*1000+aa[5]*100+aa[3]*10;
if(sum==(sum1+sum2)){
break;
}
}
}
cout<<sum1<<endl;
cout<<sum2<<endl;
cout<<sum<<endl;
return 0;
}
>>> a = [1, 2, 3]
>>> b = [4, 5, 6]
>>> cmp(a, b) Traceback (most recent call last): File "<pyshell#60>", line 1, in <module> cmp(a, b) NameError: name 'cmp' is not defined
>>>
