思路:先把1~10000数经过多少次变换的1存入count[MAX_N]数组中,比如count[1]=1就表示1经过一次变换,count[2]=2就表示2经过了2次变换,count[i]=k表示i经过了k次变换。
因为输入时m,n谁大谁小不定,所以可以先得到m,n的最大,最小数,然后在求[min(m,n),max(m,n)]中的最大值。
//#define LOCAL #include<cstdio> #include<cstring> #include<algorithm> int const MAX_N=10050; int count[MAX_N]; int fun(int x) { int sum=1; while(x>1) { if(x%2) x=x*3+1; else x=x/2; sum++; } return sum; } int main() { #ifdef LOCAL freopen("271.in","r",stdin); freopen("271.out","w",stdout); #endif memset(count,0,sizeof(count)); int i,m,n,maxx,mm,nn; for(i=1;i<MAX_N;i++) { count[i]=fun(i); } while(~scanf("%d%d",&m,&n)) { maxx=0; mm=std::max(m,n); nn=std::min(m,n); for(i=nn;i<=mm;i++) { if(count[i]>maxx) { maxx=count[i]; } } printf("%d %d %d\n",m,n,maxx); } return 0; }
The 3n + 1 problem,布布扣,bubuko.com
原文:http://www.cnblogs.com/jianfengyun/p/3720009.html