考虑下面的算法来生成一个数字序列。以整数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; } }View Code
改正后代码:
//以整数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; } }View Code
正确:
//以整数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\n",max+1); } }View Code
答案错误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; } }View Code
改正后代码:
//以整数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\n",tmp+1); } }View Code
总结:这个题是非常的坑。。。样例输出必须与样例输入一样,当改变后就一直运行错误!!1
刷杭电的题目对细节的要求很高很高!!!!!!!!!!!!!!!!!!!!!!!