一.题目分析
用递归方法设计下列各题,并给出每道题目的递归出口(递归结束的条件)和递归表达式。同时考虑题目可否设计为非递归方法,如果可以,设计出非递归的算法。
1.一个人赶着鸭子去每个村庄卖,每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子,问他出发时共赶多少只鸭子?经过每个村子卖出多少只鸭子?
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
二.算法构造
1.赶鸭子问题。递归公式:由x-(x/2+1)=剩余数 可得x=2*(剩余数)+1 其中x为刚到达这个村子的鸭子数,剩余数为经过这个村子后剩余的鸭子数
P=x/2+1 等于经过这个村子卖出的鸭子数
递归出口:x<=0
递归转化为非递归:采用循环
2.角骨定理。递归公式:n==1 1;(递归出口)
n%2==0 n =n/2;
n%2==1 n= n * 3 + 1;
递归:使用while循环
三.算法实现
程序源代码(请写入必要的注释)。//赶鸭子问题
//赶鸭子问题
#include<stdio.h>
#include<Windows.h>
//递归
void duck1(int r,int n)//r最后一次鸭子的个数 n经过的村子个数
{
int a = 0;//经过n-1个村子时鸭子的个数
a = (r + 1) * 2;
printf("有%d只鸭子\n", a);
printf("经过第%d个村子,这次卖出去%d只鸭子\n", n, a - r);
n = n - 1;
if (n > 0)
duck1(a, n);
}
void duck2(int r,int n)
{
int a = 0;// 经过n - 1个村子时鸭子的个数
int p = 0;//卖出去的鸭子数
for (int i = 0; i < 7; i++)
{
a = (r + 1) * 2;
p = a / 2 + 1;
r = a;//更新剩余的鸭子数
printf("有%d只鸭子\n", a);
printf("经过第%d个村子,这次卖出去了%d只鸭子\n",7-i, p);
}
}
int main()
{
int num = 7;
printf("递归:\n");
duck1(2, num);
printf("\n非递归:\n");
duck2(2, num);
//测试
int count = 510;
for (int i = 0; i < 7; i++) {
count = count / 2 - 1;
}if (count == 2) {
printf("测试代码,测试正确,最后剩余%d", count);
}
else {
printf("测试结果失败");
}
system("pause");
return 0;
}
角骨定理
#include<stdio.h>
#include<Windows.h>
#pragma warning(disable:4996)
//递归
int step1(int n,int count)
{
printf("%d ", n);
if (n == 1) //递归出口
{
printf("递归:需要%d次\n", count);
return 1;
}
else
{
if (n % 2 == 0)//偶数
{
n = n / 2;
}
else //奇数
{
n = n * 3 + 1;
}
count = count + 1;
step1(n,count);//递归调用
}
return 0;
}
//非递归
int step2(int n,int count)
{
printf("%d ", n);
count = 1;
while (n!=1) //while循环,如果不等于1则进行判断
{
if (n % 2 == 0)//偶数
{
printf("%d ", n / 2);
n = n / 2;
}
else //奇数
{
printf("%d ", n * 3 + 1);
n = n * 3 + 1;
}
count = count + 1;
}
printf("非递归:需要%d次\n", count);
return 0;
}
int main()
{
int n = 0;
int count = 1;
scanf("%d", &n);
step1(n, count);
step2(n,count);
system("pause");
return 0;
}
四.调试、测试及运行结果
1赶鸭子问题
调试①递归 总共有510只鸭子
②非递归
测试
运行结果
2.角骨定理
①递归
②非递归
运行结果
五.经验归纳
本次上机,对于在递归的练习中,发现在写递归函数时一要找到递归关系,二要找到递归出口,不然很容易出现死循环,在将递归问题转化为非递归问题时,使用循环将其转换,递归就是自己调用自己的过程,刚开始入手总是很难想到递归关系。程序中遇到很多逻辑问题,可以通过调试发现程序出现的问题,从而更快速地发现并解决问题。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)