考虑下面的算法来生成一个数字序列。以整数n开始。如果n为偶数，则除以2。如果n是奇数，乘以3再加1。用新值n重复此过程，n=1时终止。例如，将为n=22生成以下数字序列：22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1该算法对于每个整数n将终止于n=1（但尚未证明）。然而，该推测对所有整数至少保留1000000。对于输入n，n的周期长度是生成到1的数，包括1的数。在上面的示例中，循环长度22是16。给定任意两个数字i和j，您将确定i和j之间所有数字的最大周期长度，包括两个端点。
对于每对输入整数i和j，输出i，j的顺序与它们在输入中出现的顺序相同，然后输出i和j之间的整数的最大周期长度。这三个数字应用一个空格隔开，所有三个数字在一行上，每行输入输出一行。
样例输入
1 10 100 200 201 210 900 1000
样例输出
1 10 20 100 200 125 201 210 89 900 1000 174
第一次提交错误答案：
//以整数n开始。如果n为偶数，则除以2。如果n是奇数，乘以3再加1。用新值n重复此过程，n=1时终止。 #include<iostream> using namespace std; int sum=0; int a[1000000+5]={0}; int gcd(int n){ if(a[n]){ return a[n]; } sum=1; while(n!=1){ if(n%2==0){ n/=2; sum++; // sum%=1000000; }else { n=n*3+1; n%=1000000; sum++; // sum%=100000; } } a[n]=sum; return sum; } int main() { int m,n,t,tmp; while(cin>>m>>n){//m<=n if(m > n) { t = m; m = n; n = t; } tmp=-1; for(int i=m;i<=n;i++){ sum=1; if(a[i]) t=a[i]; else a[i]=t=gcd(i); if(t>tmp) tmp=t; } cout<<m<<" "<<n<<" "<<tmp<<endl; } }
改正后代码：
//以整数n开始。如果n为偶数，则除以2。如果n是奇数，乘以3再加1。用新值n重复此过程，n=1时终止。 #include<iostream> using namespace std; int sum=0; int a[1000000+5]={0}; int gcd(int n){ if(a[n]){ return a[n]; } sum=1; while(n!=1){ if(n%2==0){ n/=2; sum++; // sum%=1000000; }else { n=n*3+1; n%=1000000; sum++; // sum%=100000; } } a[n]=sum; return sum; } int main() { int m,n,t,tmp; while(cin>>m>>n){//m<=n cout<<m<<" "<<n<<" "; if(m > n) { t = m; m = n; n = t; } tmp=-1; for(int i=m;i<=n;i++){ sum=1; if(a[i]) t=a[i]; else a[i]=t=gcd(i); if(t>tmp) tmp=t; } cout<<tmp<<endl; } }
正确：
//以整数n开始。如果n为偶数，则除以2。如果n是奇数，乘以3再加1。用新值n重复此过程，n=1时终止。 #include<iostream> using namespace std; int gcd(int sum){ int num=0; while(sum!=1){ if(sum%2==0) sum/=2; else sum=3*sum+1; num++; } return num; } int main() { int i,j,t,sum,num; while(cin>>i>>j){ printf("%d %d ",i,j); if(i>j){ t=i; i=j; j=t; } int max=0;//记录最大值 for( int x=i;x<=j;x++){ sum=x; num=gcd(sum); if(num>max) max=num; } printf("%d ",max+1); } }
答案错误33%代码：
//以整数n开始。如果n为偶数，则除以2。如果n是奇数，乘以3再加1。用新值n重复此过程，n=1时终止。 #include<iostream> using namespace std; int gcd(int n){ int num=0; while(n!=1){ if(n%2==0) n/=2; else n=n*3+1; num++; } return num; } int main() { int m,n,t,tmp; while(cin>>m>>n){//m<=n if(m > n) { t = m; m = n; n = t; } tmp=0; for(int i=m;i<=n;i++){ t=gcd(i); if(t>tmp) tmp=t; } cout<<m<<" "<<n<<" "<<tmp+1<<endl; } }
改正后代码：
//以整数n开始。如果n为偶数，则除以2。如果n是奇数，乘以3再加1。用新值n重复此过程，n=1时终止。 #include<iostream> using namespace std; int gcd(int n){ int num=0; while(n!=1){ if(n%2==0) n/=2; else n=n*3+1; num++; } return num; } int main() { int m,n,t,tmp; while(cin>>m>>n){//m<=n printf("%d %d ",m,n); if(m > n) { t = m; m = n; n = t; } // printf("%d %d ",m,n); tmp=0; for(int i=m;i<=n;i++){ t=gcd(i); if(t>tmp) tmp=t; } // cout<<m<<" "<<n<<" "<<tmp+1<<endl; printf("%d ",tmp+1); } }
总结：这个题是非常的坑。。。样例输出必须与样例输入一样，当改变后就一直运行错误！！1
刷杭电的题目对细节的要求很高很高！！！！！！！！！！！！！！！！！！！！！！！