问题描述:角谷定理。输入一个自然数,若为偶数,则把它除以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(3*n+1)。得到自然数1的运算次数为每次运算次数之和。
(2)算法构造:
fun(n)=1 ,n=1
fun(n)=fun(n/2) ,n>1且n为偶数
fun(n)=fun(3*n+1) ,n>1且n为奇数
程序源代码:
#include<iostream>
using namespace std;
int fun(int n,int i)
{
if(n==1) //当n 为1时,退出递归
{
cout<<endl<<"STEP="<<i<<endl; //输出次数
return 1;
}
else
{
if(n%2==0) //当n为偶数时
{
cout<<n/2<<" ";
i=i+1; //次数加1
return fun(n/2,i);
}
else //当n为奇数时
{
cout<<3*n+1<<" ";
i=i+1;
return fun(3*n+1,i);
}
}
}
void main()
{
int m,j=1;
cout<<"请输入一个自然数:";
cin>>m; //输入一个自然数
fun(m,j);
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)