POJ（3n+1 problem的几种解法）

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 int p[10005];
 4 int fmax(int i,int j)
 5 {
 6     if(i>j)
 7         return i;
 8     else
 9         return j;
10 }
11 void ff()
12 {
13     int i,j,sum;
14     memset(p,-1,sizeof(p));
15     p[1]=1;
16     p[2]=2;
17     for(i=3;i<=10000;i++)
18     {
19         j=i;
20         sum=0;
21         while(1){
22             if(j%2 == 0)
23                 j/= 2;
24             else j=j*3+1;
25             ++sum;
26             if(j<=10000&&p[j]!=-1)
27                 break;
28         }
29         p[i]=p[j]+sum;
30 
31     }
32 }
33 int main()
34 {
35     int i,j,tpi,tpj,tp,sum,max,k;
36     ff();
37     while(scanf("%d%d",&i,&j)==2)
38     {
39         tpi=i;
40         tpj=j;
41         if(i>j)
42         {
43             tp=i;i=j;j=tp;
44         }
45         max=p[i];
46         for(k=i;k<=j;k++)
47             max=fmax(max,p[k]);
48         printf("%d %d %d\n",tpi,tpj,max);
49     }
50     return 0;
51 }

这种貌似是预先处理的方法。我也不知道具体叫什么来着。

View Code

 1 #include<stdio.h>
 2 int f(int n)
 3 {
 4     int i,j,sum=1;
 5     if(n==1||n==2)
 6         return n;
 7     else
 8     if(n>2)
 9     {
10         while(1)
11         {
12             if(n%2==1)
13             {
14                 sum++;
15                 n=n*3+1;
16             }
17             else
18             {
19                 sum++;
20                 n=n/2;
21             }
22             if(n==1)
23                 break;
24         }
25     }
26     return sum;
27 }
28 int max(int i,int j)
29 {
30     if(i>j)
31         return i;
32     else
33         return j;
34 }
35 int main()
36 {
37     int i,j,k,sum,tpi,tpj,tp;
38     while(scanf("%d%d",&i,&j)==2)
39     {
40         tpi=i;
41         tpj=j;
42         if(i>j)
43         {
44             tp=i;i=j;j=tp;
45         }
46         sum=f(i);
47         for(k=i+1;k<=j;k++)
48         {
49             sum=max(sum,f(k));
50         }
51         printf("%d %d %d\n",tpi,tpj,sum);
52     }
53     return 0;
54 }

这种就没什么技巧了。

keep moving...