一、实验题目
用递归方法设计下列各题,并给出每道题目的递归出口(递归结束的条件)和递归表达式。同时考虑题目可否设计为非递归方法,如果可以,设计出非递归的算法。
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
二、算法构造
题目一:
递归:设经过第n个村子时有duck(n)只鸭子,根据题意则有,在duck(8)=2,duck(1)为他有多少只鸭子总数,也可得出,在第n个村子会卖去duck(n)/2+1只鸭子,剩下duck(n+1)只鸭子,故有duck(n)=duck(n)/2+1+duck(n+1)=2*(duck(n+1)+1)。
于是可得 duck(n)=2 n=8
duck(n)=2*(duck(n+1)+1) 0>=n>=7
非递归:流程图如下
题目二:
递归:设fun(n)为关于自然数n的一个函数,根据题意可得以下公式:
fun(n)=1 n=1
fun(n)=n/2 n≠1且n为偶数
fun(n)=3n+1 n≠1且n为奇数
非递归:流程图如下
三、算法实现
(1)题目一
递归
#include<stdio.h>
#include<stdlib.h>
int duck(int i)
{
if(i==8)
return 2;//根据题意,当这个人到第8个村子时,只有2只鸭子,也是递归出口
else
return 2*(duck(i+1)+1);//递归体
}
int main()
{
int i=1;
printf("出发时共有%d只鸭子\n",duck(1));
for(i=1;i<8;i++)//循环到每个村子时有多少鸭子,在每个村子卖出了多少鸭子
{
printf("他在第%d个村子时有%d只鸭子,卖出了%d只鸭子\n",i,duck(i),duck(i)/2+1);
}
system("pause");
}
非递归
#include<stdio.h>
#include<stdlib.h>
int main()
{
int x,j;
int y=2,i=7;
for(i=7;i>0;i--)
{
y=(y+1)*2;//根据题意可得公式
}
for(j=1;j<8;j++)//循环算到每个村子时有多少鸭子,在每个村子卖出了多少鸭子
{
printf("他在第%d村子有%d只鸭子,",j,y);
x=y/2+1;
y=y-x;
printf("卖了%d只鸭子\n",x);
}
system("pause");
}
(2)题目二
递归
#include<stdio.h>
#include<stdlib.h>
int fun(int i,int j)
{
if(i==1)//递归出口
{
printf("STEP=%d\n",j);
return 1;
}
else//递归体
{
if(i%2==0)
{
printf("%d ",i/2);
return fun(i/2,j+1);
}
else
{
printf("%d ",i*3+1);
return fun(i*3+1,j+1);
}
}
}
int main()
{
int x;
int y=1;
scanf("%d",&x);
printf("%d ",x);
fun(x,y);
system("pause");
}
非递归
#include<stdio.h>
#include<stdlib.h>
int main()
{
int x,y,i,j;
scanf("%d",&x);
if(x==1)
printf("STEP=1");
else
{
for(i=1;x!=1;i++)
{
if(x%2==0)
{
x=x/2;
printf("%d ",x);
}
else
{
x=x*3+1;
printf("%d ",x);
}
}
printf("STEP=%d\n",i);
system("pause");
}
}
声明:本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。