一 .题目分析
题目一：一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶了多少只鸭子？经过每个村子卖出多少只鸭子？
题目二：角谷定理。输入一个自然数，若为偶数，则把它除以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.递归函数
递归函数：f(n)= 2 n=7
f(n+1)2+2 0<n<7 (因为：f(n)-(f(n)/2+1)=f(n+1))
递归函数体：f(n+1)2+2，
递归出口：第7个村庄剩余2只鸭子
注：其中n为经过的村子数，f(n)为经过n村子所剩下的鸭子数
2.具体程序中
y=2(y+1)； //由y-(y/2+1)=x 得此公式
p=y/2+1; //p为局部变量，递归时不会相互影响，每个村子卖出的鸭子数等于刚进入村子的鸭子总数的一半加一
i=i-1； //上一个村子
题目二：角谷定理
1.递归函数
f(n，c) = 1 n=1
f(n/2，c) + f(n3+1，c) + f(1，c) n>1
递归函数体：f(n/2，c) + f(n3+1，c) + f(1，c)
递归出口：最终计算值为1
注：其中n为要计算的自然数，c为已经进行的步骤数，函数 f(n，c)的意义是自然数n经过c步运算后得到自然数1
2.具体程序中
num=num3+1; //n为奇数
num=num/2; //n为偶数
三.算法实现
程序源代码:
题目一：赶鸭子
public class Duck {
public static int counts=0; //设置全局变量counts 表示总共的鸭子数
public static void main(String[] args) {
Duck duck = new Duck(); //实例化duck对象
long start = System.currentTimeMillis();
counts = duck.sellDuck(7, 2); //递归方法计算 调用sellDuck方法，计算每个村子卖出的鸭子数与总鸭子数，将总鸭子数counts返回 7为村子数，2为最后剩余鸭子数
//counts= duck.sellDuck1(); //调用非递归方法计算
System.out.println("共有" +counts+ "只鸭子"); //打印总鸭子数
long end = System.currentTimeMillis();
System.out.println("运行时间为:"+(end-start)+"ms");
Test(counts); //调用测试方法，如果最后剩余2与题目相符则打印测试正常，否则打印失败
}
//递归形式
public int sellDuck(int i,int y) {
if(i>0) {
//村子数必须为正数
int x; //剩余数
y=2*(y+1); //由y-(y/2+1)=x得此公式
int p=y/2+1; //p为局部变量,递归时不会相互影响,每个村子卖出的鸭子数等于刚进入村子的鸭子总数的一半加一
i=i-1; //上一个村子
x=y-p; //剩余鸭子数等于共有的减去卖出的
sellDuck(i,y); //递归调用sellDuck函数直到村庄数到达1
System.out.println("第"+(i+1)+"个村庄，共有"+y+"只鸭子，卖出"+p+"只鸭子，剩余"+x+"只鸭子"); //打印每个村庄卖出的鸭子数
}
if(i==0){
counts=y; //当经过第一个村子之前, y为鸭子总数,将y复制给counts并返回counts
}
return counts;
}
//非递归形式
public int sellDuck1() {
int x=2; //最后剩余的鸭子数
int p=0; //卖出的鸭子数
int y=0; //到达每个村子的鸭子数，也是经过上一个村子的剩余鸭子数
for(int i=0;i<7;i++) {
//采用循环
y=2*(x+1); //由y-(y/2+1)=剩余数 得此公式
p=y/2+1; //每个村子卖出的鸭子数 等于刚进入村子的鸭子总数的一半加一
x=y; //更新剩余的鸭子数
System.out.println("第"+(7-i)+"个村庄，共有"+y+"只鸭子，卖出"+p+"只鸭子，剩余"+x+"只鸭子");
}
return y; //当经过第一个村子之前, y为鸭子总数,返回鸭子总数
}
//测试类
public static void Test(int counts){ //传入counts鸭子总数
//经过循环，计算经过七个村子发出的鸭子数
for (int i=0;i<7;i++) {
counts=counts/2-1;
}
//如果最后剩余2 则结果正确
if(counts==2){
System.out.println("测试结束，程序正确，最后剩余鸭子数为"+counts);
}
else{
System.out.println("测试结果失败");
}
}
}
题目二：角谷定理
package 角谷定理;
import java.util.Scanner;
public class Jiaogu {
public static int count=0; //设置全局变量count表示运行次数
public static void main(String[] args) {
@SuppressWarnings("resource")
Scanner sc=new Scanner(System.in);
System.out.println("请输入一个自然数：");
int num =sc.nextInt();
long start=System.currentTimeMillis();
System.out.println("运算过程如下：");
//获取运算总次数
count=calculate(num, 1); //递归方法计算,调用calculate方法
//count=calculate2(num); //非递归方法计算,调用calculate2方法
System.out.println("运算总次数为："+count);
long end=System.currentTimeMillis();
System.out.println("运行时间为："+(end-start)+"ms");
Test(num,count); //调用测试方法
}
//递归形式
public static int calculate(int num, int count) {
//当自然数为1时退出递归方法
if (num==1) {
System.out.println(num+" ");
return count;
}
//自然数为偶数时
if (num%2==0) {
System.out.println(num+" ");
num=num/2;
count++; //运算次数加1
return calculate(num,count);
}
//自然数为奇数时
else {
System.out.println(num+" ");
num=num*3+1;
count++; //运算次数加1
return calculate(num,count);
}
}
//非递归形式
@SuppressWarnings("unused")
private static int calculate2(int num) {
System.out.println(num+" ");
int count=1;
while (num>1) {
if (num%2==0){
num/=2;
count++;
System.out.println(num+" ");
}
else{
num=num*3+1;
count++;
System.out.println(num+" ");
}
}
System.out.println("经过"+count+"次可得到自然数1");
return count;
}
//测试类
public static void Test(int num,int count){
int i=1;
while (num>1){
if (num%2==0){
i++;
num/=2;
}
else{
i++;
num=num*3+1;
}
}
if (i==count){
System.out.println("测试正确!");
}
else {
System.out.println("测试错误!");
}
}
}
四.调试、测试及运行结果
题目一：赶鸭子
（一）程序调试
程序结束后计算消耗时间，并通过测试类测试程序是否正确
（二）总测试结果
递归方法计算：
非递归方法计算：
题目二：角谷定理
（一）程序调试
程序结束后计算消耗时间，并通过测试类测试程序是否正确
（二）总测试结果
递归方法计算：
非递归方法计算：
五.经验归纳
通过写程序我发现首先我得清晰的列出递归函数，找到他的递归体和递归出口。
赶鸭子问题
（1）它的递归出口是到第7个村庄剩下的鸭子数为2。递归体需要有计算，通过题目中每经过一个村子卖去所赶鸭子的一半又一只这句话即f(n)-(f(n)/2+1)=f(n+1)可知主要因素有3点，鸭子总数，卖出鸭子数，剩余鸭子数可得到公式：f(n)-(f(n)/2+1)=f(n+1)，f(n)=( f(n+1)+1) 2需要明确的是经过某村庄剩下的鸭子数就是下一个村庄的总鸭子数。所以公式中的剩下只数可更新为上一步骤算出的总数。这一点非常重要。
（2）程序中还有对程序的测试代码以及时间计算代码，具体时间计算代码如下：
long start = System.currentTimeMillis();
程序体
long end = System.currentTimeMillis();
System.out.println(“运行时间为:”+(end-start)+“ms”);
角谷定理
（1）它的递归出口是最终计算值为1。递归体需要有计算，通过题目中输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1这句话可得到公式：f(n/2，c) + f(n3+1，c) + f(1，c) ，即若n为奇数：则n= n*3+1,再将所得到的n值传入到函数f(n，c)中，从而形成递归，同理若n为偶数，则将n=n/2传入到f(n，c)中。最后函数返回c即count,代表运算次数，，
（2）程序中同样有对程序的测试代码以及时间计算代码