问题重述:
角谷定理。输入一个自然数,若为偶数,则把它除以2,若为奇数,则把它乘以3加1。经过如此有限次运算后,总可以得到自然数值1。求经过多少次可得到自然数1。
如:输入22,
输出 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
STEP=16
题目分析:
根据题意有:
最后Xlast=1
算法构造:
根据上述公式可以看出:
函数出口:Xlast=1
函数体:
根据当前的数字判断其奇偶性,若为偶数,则把它除以2,若为奇数,则把它乘以3加1,然后再次递归判断,直到最后一次的数字为1时跳出函数
算法实现:
#include<iostream>
using namespace std;
/*
Author:Qiaoxue Zheng
Date:2018/11/15
Dscribtion:To get the steps according to Kakutani Theory
*/
/*
Function:Kakutani
Parameter:
number:natural number
Return:steps
*/
int Kakutani(int number) {
int count = 0;
cout << number<<" ";//output each number
count++;//count steps
//exit,the last number is 1
if (number == 1) {
return count;
}
//body
else {
if (number % 2 == 0) {//Even numbers
count += Kakutani(number / 2);
return count;
}
else {//Odd number
count += Kakutani(number * 3 + 1);
return count;
}
}
}
//Main function
int main() {
int number = 0;
cout << "please input a int number:";
cin >> number;
cout<<endl<<"总步数:"<<Kakutani(number)<<endl;
system("pause");
return 0;
}
运行结果:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)