The 3n + 1 problem

考虑下面的算法来生成一个数字序列。以整数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

第一次提交错误答案:
The 3n + 1 problem
//以整数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

改正后代码:

The 3n + 1 problem
//以整数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

正确:

The 3n + 1 problem
//以整数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%代码:

The 3n + 1 problem
//以整数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

 改正后代码:

The 3n + 1 problem
//以整数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

刷杭电的题目对细节的要求很高很高!!!!!!!!!!!!!!!!!!!!!!!

 

上一篇:PAT 甲级 A1001 (2019/02/10)


下一篇:SuShan过年要给孩子们发压岁钱喽,由于家里孩子很多,这可急坏了SuShan。你肯定以为她在担心钱不够,那你错了,她可是个有钱人儿,不差钱儿。她担心的是每个人分多少从而保证公平。 SuShan