锐客网

  1. 首页 > it技术 > >

递归算法练习

c

转载地址：https://blog.csdn.net/thegreatmz/article/details/72598216
1.题目：一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？
题目分析：经过7个村庄后还剩两只鸡鸭子，每经过一个村庄卖当前鸭子的一半加一只，所以递归体是经过前一个村子的鸭子数除以2再减去1就是到达下一个村子的时候的鸭子数，所以要想求在第一个村子的鸭子数，必须从后往前推。
算法实现：

#include #include "iostream" using namespace std; int number = 2,x,i=7; int Number(int i) { if(0 == i) //当i为0时，结束递归调用 { cout << "他出发时共赶了" << number << "只鸭子。" << endl; //当经过的村子数为0时，number为出发时的鸭子数 } else { number = (number + 1 ) * 2; //计算在经过第i个村子前的鸭子数number x = number / 2 + 1; //计算在经过第i 个村子时卖的鸭子数x cout << "经过第" << i << "个村子时，他卖出" << x << "只鸭子。" << endl; return Number(i - 1); } } int main() { Number(7); }

2.题目：角谷定理。输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1。经过如此有限次运算后，总可以得到自然数值1。求经过多少次可得到自然数1。
如：输入22，
输出 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
STEP=16
题目分析：当x等于1时，输出step；当x为偶数时，step=step+1；当x为奇数时，step=step+1。
【递归算法练习】算法实现：
#include void Function(int *step,int n)//因为传入的参数需要经过变化所以一定要用指针！！ { if(n == 1) { printf("%d",n); return; } if( n % 2 == 0) { printf("%d ",n); (*step)++; //自加的优先级比*更高所以必须加上括号 Function(step,n / 2); }else if(n % 2 != 0) { printf("%d ",n); (*step)++; Function(step,3 * n + 1); } } int main () { int n; int step = 0; printf("请输入您的数字:\n"); scanf("%d",&n); printf("变化过程："); Function(&step,n); printf("\n"); printf("总共的步数:%d",step); return 0; }

3.题目：电话号码对应的字符组合：在电话或者手机上，一个数字如2对应着字母ABC，7对应着PQRS。那么数字串27所对应的字符的可能组合就有3*4=12种（如AP，BR等）。现在输入一个3到11位长的电话号码，请打印出这个电话号码所对应的字符的所有可能组合和组合数。
题目分析：当输入的是一个数字时，返回这个数字所有可能性的组合，递归体是当输入一串数字，每个数字代表不同的字符串，返回最后一个数字跟前面已产生的字符串进行组合，所以首先应该建一个数组，用来存放每个数字代表的字符串组合，然后在建一个数组，用来存放每个字符串的长度，在函数中，先进行判断是否是最后一位，然后根据判断执行函数。
算法实现：
#include #include char c[10][10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; //数字代表的字符 int cnt=1; int total[10]={0,0,3,3,3,3,3,4,3,4}; //数字代表的字符个数void RS(int *number,int *answer,int index,int n) {if(index==n)//判断是否为最后一位 { for( int i=0; i

4.题目：日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完 后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？
题目分析：每个儿子的橘子数目有两种，原有的和现有的，除了老大，其他的儿子原有的+别人给的-给别人的=现有的=平均数，所以原有的=现有的+给别人的-别人给的。大儿子得到六儿子之前的是：大儿子原有的-给二儿子的（1/8）=现有的-别人给的（六二子给的）；六儿子现有的（ave）=（六儿子原有的+别人给的）（2/3）,所以,( 7/8大儿子原有的)=现有的-六儿子给的，所以大儿子现有的=得到六儿子之前的8/7倍。 拿二儿子作说明：老二拿到后连同原先的桔子分1/7给老三。（原有的+拿到的）6/7=ave,所以give=（原有的+拿到的）1/7=ave6/71/7=give=ave/(8-i-1)(此时i为1) 每个儿子现有的和原有的关系为： a[i]=a[i]+(a[i]/(8-i-1))-(a[i-1]/(8-(i-1)-1))
算法实现：
#include using namespace std; int main() { int a[6]; //存放六个儿子原先手中的橘子数目 int left = 0; //存放下一个儿子得到的橘子数目 int ave = 420; for(int i=0; i<6; i++) { if(i==0) { a[i]=(ave-ave/2)*(8-i)/(8-i-1); //第一个儿子的数目, left=a[i]-ave/2; } else { a[i]=ave*(8-i)/(8-i-1)-left; //由left求第i+1个儿子的橘子数目 left=ave/(8-i-1); //第i+1个儿子得到的橘子数目 } } for(int i=0; i<6; i++) { cout<<"第"<

5.题目：编写一个函数求n的阶乘。
#include int Function(int n); int main() { int n; std::cin>>n; int result=Function(n); std::cout<

6.题目：编写一个函数实现n^k，使用递归实现。
#include int Function(int n,int k) { if(k==0) return 1; if(k==1) return n; else return n*Function(n,k-1); } int main() { int n,k; std::cin>>n; std::cin>>k; std::cout<

归纳总结：递归是将一个规模较大的问题分解为若干个规模较小的子问题，且这些子问题相互独立且与原问题相同。递归函数至少要有一个出口，也就是判断结束调用的条件来结束递归体，跳出循环。

    推荐阅读


    上一篇：分布式的CAP理论

    下一篇：数据库|牛客数据库SQL实战 51-60（substr切割字符串、group_concat组拼接、limit_offset分页、exists条件成立判断、case分支、表的复用）