一、一半又一只
一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？
1.题目分析
设经过第n个村子时有fun(n)只鸭子，卖去fun(n)/2+1只鸭子，剩下fun(n+1)只鸭子，则有fun(n)=fun(n)/2+1+fun(n+1),即fun(n)=2*(fun(n+1)+1)。经过第8个村子时有2只鸭子，即fun(8)=2。出发时共赶fun(1)只鸭子，经过第n个村子时卖出fun(n)/2+1只鸭子。
2.算法构造
fun(n)=2*(fun(n+1)+1)，1<=n<8
fun(n)=2， n=8
3.算法实现
程序源代码:
/**
*author:谷美颖
*date:2018.11.15
*version:1.1
*description:一半又一只
一个人赶着鸭子去每个村庄卖，
每经过一个村子卖去所赶鸭子的一半又一只。
这样他经过了七个村子后还剩两只鸭子，
问他出发时共赶多少只鸭子？
经过每个村子卖出多少只鸭子？
**/
#include <stdio.h>
/*
fun()函数用来计算鸭子数，参数n为经过的村子数
*/
int fun(int n)
{
if(n==8) //递归出口。村子数为8时递归结束，鸭子数为2
return 2;
else
return 2*(fun(n+1)+1); //递归体
}
void main()
{
printf("出发时共赶%d只鸭子\n",fun(1));
for(int i=1;i<8;i++)
{
printf("经过第%d个村子卖出%d只鸭子\n",i,fun(i)/2+1);//输出经过每个村子卖出的鸭子数
}
}
二、角谷定理。
输入一个自然数，若为偶数，则把它除以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.题目分析
设fun(n)表示关于自然数n的一个函数，由题意已知，当n=1时，fun(1)=1。当n>1且n为偶数时，fun(n)=fun(n/2)；当 n>1且n为奇数时，fun(n)=fun(3n+1)。得到自然数1的运算次数为每次运算次数之和。
2.算法构造
fun(1)=1，n=1
fun(n)=fun(n/2)，n>1且n为偶数
fun(n)=fun(3n+1)，n>1且n为奇数
3.算法实现
/**
*author:谷美颖
*date:2018.11.15
*version:2.1
*description:角谷定理。
输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1。
经过如此有限次运算后，总可以得到自然数值1。求经过多少次可得到自然数1。
**/
#include<stdio.h>
/*
fun()函数用来实现角谷定理的算法。参数n为初始自然数，i用来计算次数，初始次数为1
*/
int fun(int n,int i)
{
if(n==1) //递归出口。当n为1时，退出递归
{
printf("\n");
printf("STEP=%d\n",i); //输出次数
return 1;
}
else //递归体
{
if(n%2==0) //当n为偶数时
{
printf("%d ",n/2);
i=i+1; //次数加1
return fun(n/2,i); //递归体
}
else //当n为奇数时
{
printf("%d ",3*n+1);
i=i+1;
return fun(3*n+1,i); //递归体
}
}
}
void main()
{
int m,j=1;
printf("请输入一个自然数:");
scanf("%d",&m); //输入一个自然数
printf("%d ",m);
fun(m,j);
}
三、电话号码的字符组合
电话号码对应的字符组合：在电话或者手机上，一个数字如2对应着字母ABC，7对应着PQRS。那么数字串27所对应的字符的可能组合就有3*4=12种（如AP，BR等）。现在输入一个3到11位长的电话号码，请打印出这个电话号码所对应的字符的所有可能组合和组合数。
1.题目分析
用数组存放数字字符的转换
show(0,2)-> output[0]=A-> show(1,2)-> 1!=2-> output[1]=D-> ；k=1 show(2,2)-> 2=len-> 输出AD-> i+1-> output[1]=E-> show(2,2)-> 2=len-> 输出AE i=2-> output[1]=F-> show(2,2)-> 2=len-> 输出AF ；再回到k=0-> i=1 output[0]=ch[0][1]=B 输出BD,BE,BF i=2 输出CD,CE,CF
2.算法构造
在此论证算法设计中的一些必要的设计依据。
for(int i=0;i<total[input[k]];i++){ // 递归出口
output[k]=ch[input[k]][i];
fun(k+1,len); //递归体
}
3.算法实现
程序源代码（请写入必要的注释）。
/**
*author:谷美颖
*date:2018.11.17
*version:3.1
*description:电话号码对应的字符组合
在电话或者手机上，一个数字如2对应着字母ABC，7对应着PQRS。
那么数字串27所对应的字符的可能组合就有3*4=12种（如AP，BR等）。
现在输入一个3到11位长的电话号码，请打印出这个电话号码所对应的字符的所有可能组合和组合数。
**/
#include<stdio.h>
#include<string.h>
const char ch[10][10]={
"",//0
"",//1
"ABC",//2
"DEF",//3
"GHI",//4
"JKL",//5
"MNO",//6
"PQRS",//7
"TUV",//8
"WXYZ"//9
};
const int total[10]={0,0,3,3,3,3,3,4,3,4}; //各个数字代表的字符总数构成的数组
char input[20]; //保存输入电话字符数组
int number[20]; //保存输入电话的数字
char output[20]; //输出可能字符组合
/*
fun()函数用来匹配对应字符，参数k标记指针，len为字符串长度
*/
void fun(int k,int len){
if(k==len){
output[len]='\0'; //设为结束标志,输出
printf("%s\n",output);
return ;
}
for(int i=0;i<total[input[k]];i++){ // 递归出口
output[k]=ch[input[k]][i];
fun(k+1,len); //递归体
}
}
int main(){
printf("请输入电话号码：\n");
scanf("%s",input); //输入电话字符数组
int len=strlen(input);
int sum=1;
for(int i=0;i<len;i++){
input[i]-='0'; //char类型转换成int数组
sum*=total[input[i]];
}
fun(0,len);
printf("总的组合数:%d\n",sum);
return 0;
}
四、分桔子
日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完 后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？
1.题目分析
sum=2520 aver=2520/6=420；老六得到橘子后，给老大1/3后为420，所以给了老大210，老大给出原来的1/8加得到的210对于420，所以原来有240个橘子；下一个人原来的橘子数:
(nextfirstnum+givernum)(7-n)/(8-n)=420 firstnum=420(8-n)/(7-n)-givertnum
2.算法构造
在此论证算法设计中的一些必要的设计依据。
0 n>6
givernum=firstnum/(9-n) n=1
givernum=(firstnum+foregivernum)/(9-n) n>1
3.算法实现
程序源代码（请写入必要的注释）。
/**
*author:谷美颖
*date:2018.11.17
*version:4.1
*description:分桔子
日本著名数学游戏专家中村义作教授提出这样一个问题：
父亲将2520个桔子分给六个儿子。
分完 后父亲说：
“老大将分给你的桔子的1/8给老二；
老二拿到后连同原先的桔子分1/7给老三；
老三拿到后连同原先的桔子分1/6给老四；
老四拿到后连同原先的桔子分1/5给老五；
老五拿到后连同原先的桔子分1/4给老六；
老六拿到后连同原先的桔子分1/3给老大”。
结果大家手中的桔子正好一样多。
问六兄弟原来手中各有多少桔子？
**/
#include<stdio.h>
//fun()函数用来实现分桔子,参数first代表原有的桔子, forenum代表前n-1一个人给的桔子数,n代表老几
int fun(int firstnum,int foregivernum,int n){
int givernum=0;
if(n>5){ //递归出口
return 0;
}
else{
//计算分给下一个数目
if(n==1){ //第一个人是先直接给
printf("老%d原来的桔子数:%d\n",n,firstnum);
printf("老%d得到的桔子数:%d\n",n,foregivernum);
givernum=firstnum/(9-n);
printf("老%d给出的桔子数:%d\n",n,givernum);
foregivernum=givernum;
}
else{ //先得到后再给
printf("老%d得到的桔子数:%d\n",n,foregivernum);
int givernum=(firstnum+foregivernum)/(9-n);//当前给出的桔子数
printf("老%d给出的桔子数:%d\n",n,givernum);
foregivernum=givernum;
}
//下一个人原来的桔子数
int firstnum=420*(8-n)/(7-n)-foregivernum;
printf("老%d原来的桔子数:%d\n",n+1,firstnum);
n=n+1;
fun(firstnum,foregivernum,n); //递归体
}
return 0;
}
int main(){
fun(240,210,1);
return 0;
}
五、总结：
1.先观察是否能得到问题小规模化时的解决方法。
2.分析问题规模慢慢变大时其解决方法的过程是否相同。
3.分析问题之间的递归关系。（难点在此处，递归关系的发现是关键之处）
4.将1作为边界，列出关系式。编程解决之。
