【项目-用递归方法求解】
(1)编写递归函数求出n的阶乘(自定义main函数,调用定义的递归函数)
参考解答:
#include <iostream> using namespace std; long fact(int); //函数声明 int main( ) { int n; //n为需要求阶乘的整数 long y; //y为存放n!的变量 cout<<"please input an integer :"; //输入的提示 cin>>n; //输入n y=fact(n); //调用fac函数以求n! cout<<n<<"!="<<y<<endl; //输出n!的值 return 0; } long fact(int n) //递归函数 { long f; if (n==0) f=1; //0!和1!的值为1 else f=fact(n-1)*n; //n>1时,进行递归调用 return f; //将f的值作为函数值返回 }
(2)写出求1*3*...*n的递归式,并编写出递归函数求解。
参考解答:
#include <iostream> using namespace std; long f(int); int main( ) { int n; long y; cout<<"请输入一个数 :"; cin>>n; if(n%2) //若奇数 y=f(n); else y=f(n-1); cout<<n<<"以内的奇数积是:"<<y<<endl; return 0; } long f(int n) { long s; if (n==1) s=1; else s=f(n-2)*n; return s; }
(3)编程序,用递归函数求出两个数的最大公约数。(包括编main函数,调用定义的递归函数)
参考解答:
//递归解法 #include "iostream" using namespace std; int gcd(int x, int y); void main() { int m,n; cout<<"输入两个数字:"; cin>>m>>n; cout<<"最大公约数:"; cout<<gcd(m,n)<<endl; } int gcd(int a, int b) { int t,g; //if (a < b) t=a,a=b,b=t; //无所谓大小 if (b==0) g=a; else g=gcd(b,a%b); return g; }
(4)编制递归函数fib(int n)返回第n个Fibnacci数,以此输出Fibnacci序列的第20个数。
参考解答:
//递归法 #include <iostream> using namespace std; int fib(int n); int main() { cout<<fib(20)<<endl; return 0; } //返回Fibnacci序列中的第n个数 int fib(int n) { if(n==1) return 0; else if(n==2) return 1; else return(fib(n-1)+fib(n-2)); }
(5)输入一个整数n,要求输出对应的二进制形式,请用递归函数实现。
参考解答:
#include <iostream> using namespace std; void dec2bin(int n); int main() { int n; cout<<"请输入一个整数:"; cin>>n; cout<<n<<"对应的二进制形式为:"; dec2bin(n); cout<<endl; return 0; } void dec2bin(int n) { if(n==0) return; //其实在此有个BUG,如果在main()中直接调用的是dec2bin(0),并不会输出其二进制形式0,请在评论中跟进如何处理 else { dec2bin(n/2); cout<<n%2; return; } }
提示:二进制整数n转换为二进制的方法是“除2取余法”,即将n除以2后得到的余数,由后到前“串”起来,得到对应的二进制数,如图。
(6)汉诺塔
汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。古代有一个梵塔,塔内有三个座A、B、C,A座上有64个盘子,盘子大小不等,大的在下,小的在上。有一个和尚想把这64个盘子从A座移到C座,但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘子始终保持大盘在下,小盘在上。在移动过程中可以利用B座,下面左图给出了移动方法的提示。请编制递归函数输出盘子数为4时(程序调试后,试试15个、20个,直至64个,看看会如何),移动的方案。图为盘子数为3时的输出供参考。
参考解答:
#include <iostream> using namespace std; const int discCount=3; void move(int, char, char,char); int main() { move(discCount,'A','B','C'); return 0; } void move(int n, char A, char B,char C) { if(n==1) { cout<<A<<"-->"<<C<<endl; return; } else { move(n-1,A,C,B); cout<<A<<"-->"<<C<<endl; move(n-1,B,A,C); return; } }
下面的解答还可以输出移动的次数,当盘子数太多时,这是个温柔长的过程:
//输出且计数 #include <iostream> using namespace std; const int discCount=3; long move(int, char, char,char); int main() { long count; count=move(discCount,'A','B','C'); cout<<discCount<<"个盘子需要移动"<<count<<"次。"<<endl; return 0; } long move(int n, char A, char B,char C) { long c1,c2; if(n==1) { cout<<A<<"-->"<<C<<endl; return 1; } else { c1=move(n-1,A,C,B); cout<<A<<"-->"<<C<<endl; c2=move(n-1,B,A,C); return c1+c2+1; } }
下面的代码不去输出移动方案,仅输出需要移动的次数,免去了输出花费的时间:
//仅计数 #include <iostream> using namespace std; const int discCount=3; long move(int, char, char,char); int main() { long count; count=move(discCount,'A','B','C'); cout<<discCount<<"个盘子需要移动"<<count<<"次。"<<endl; return 0; } long move(int n, char A, char B,char C) { long c1,c2; if(n==1) { return 1; } else { c1=move(n-1,A,C,B); c2=move(n-1,B,A,C); return c1+c2+1; } }
有同学的输出中,加入了“几号盘子”字样,输出信息更明白:
#include <iostream> using namespace std; void move(int n, char A, char B,char C);//盘子数由序号数增大而依次增大 int main() { move(4,'A','B','C'); return 0; } //有n个盘子, void move(int n, char A, char B,char C) { if(n==1) { cout<<n<<"号盘子:"<<A<<" to "<<C<<endl; } else { move(n-1,A,C,B); cout<<n<<"号盘子:"<<A<<" to "<<C<<endl; move(n-1,B,A,C); } }
|
时间: 2024-09-16 09:35:28