角谷定理

一、题目描述

输入一个自然数，若为偶数，则把它除以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、递归算法
根据角度定理的思想，定义一个有两个变量的递归函数：Kakutani(n,s)。其中n表示要计算的自然数，s表示已进行的步骤数。函数的意义是自然数n经过s步运算后得到自然数1。容易得到下面的递归公式：
Kakutani(n,s) = { Kakutani(1,s) = 1 num=1
---------------------| Kakutani(num/2,s)+Kakutani(num*3+1,s)+Kakutani(1,s) num>1
2、非递归算法
具体算法实现如图所示。

图2.2 角度定理非递归实现

三、算法实现

//角谷定理递归实现
int Kakutani(int num, int step){
	if (1 == num){
		return step;
	}
	else{
		if (0 == num % 2){
			step++;
			printf("%d ", num / 2);
			return Kakutani(num / 2, step);
		}
		else{
			step++;
			printf("%d ", num * 3 + 1);
			return Kakutani(num * 3 + 1, step);
		}
	}
}

//角谷定理非递归实现
int Kakutani_un(int num){
	int step = 1;
	while (num > 1){
		if (0 == num % 2){
			step++;
			num = num / 2;
			printf("%d ", num);
		}
		else{
			step++;
			num = num * 3 + 1;
			printf("%d ", num);
		}
	}
	return step;
}

四、调试、测试及运行

1、调试
（1）进入Kakutani()函数，调用递归结束开始返回的各数据的值。

（2）Kakutani()函数调用结束各数据的值。

（3）进入Kakutani_un()函数，调用递归结束开始返回的各数据的值。

（4）Kakutani_un()函数调用结束各数据的值。

2、测试
测试代码：
void test(int num, int step)
{
int i = 1;
while (num > 1){
if (0 == num % 2){
i++;
num /= 2;
}
else{
i++;
num = num * 3 + 1;
}
}
if (i == step){
printf(“测试正确\n”);
}
}
测试结果：

3、运行

五、总结

使用vs编译出现如下错误：
错误1error LNK1168:无法打开
E:\Visual Studio-workspace\chapter_6\Debug\chapter_6.exe 进行写入
E:\Visual Studio-workspace\chapter_6\chapter_6\LINK chapter_6
解决办法有三种（前两种治标不治本，第三种办法可以根治）：
1.什么都不干，等一会，大概几分钟吧，就可以成功生成了。
2.把之前Debug文件夹里生成的.exe文件删掉，就可以成功生成了。
3.最根本的办法：打开控制面板->管理工具->服务->启用Application Experience服务。