620
poj 1207 The 3n + 1 problem
當我看到題目的時候我就感覺到這是一道徹徹底底的水題，因為很像A+B的作風。。。
但是看完題目我心裏想了想：應該沒有那麼水吧，可能還是要優化的，暴力可能會TLE。。。
但是我暴力過了以後我這樣想：。。。。。。。
下麵摘抄了一點文字說明：
大致題意：
根據給定的算法，可以計算一個整數的循環數
現在給定一個區間，計算這個區間的所有數的循環數，把最大的循環數輸出
PS:輸出的是整數A的循環數，而不是輸出整數A
解題思路：
注意的隻有一點：
輸入的兩個區間端點不一定是從小到大輸入的，因此要先對這兩個數排一下序。
【純暴力】AC的代碼：
#include<stdio.h>
int Process(int i)
{
int count=1;
while(i!=1)
{
if(i%2)
i=3*i+1;
else
i/=2;
count++;
}
return count;
}
//這題居然可以暴力過。。。我不解釋
int main()
{
int a,b;
while(scanf("%d%d",&a,&b)!=EOF)
{
int x=a<b?a:b;
int y=a>b?a:b;
int Max=0;
for(int i=x;i<=y;i++)
{
int temp=Process(i);
if(Max<temp)
Max=temp;
}
printf("%d %d %d\n",a,b,Max);
}
return 0;
}
寫寫自己”不暴力“的思路：
要維護兩個集合
1. 每個數當然最好有一個自己的數組專門存循環節的長度，因為很可能區間有重疊。。。
2. 另外一個集合 【鏈表】就是把 循環序列 都存起來，因為循環節很可能就是重複的，比如知道 4 的長度是 3 ，那 8/2 以後就是 4 ，就不用算了，長度就是3+1=4；這樣就要每次檢查一次，如果有就結束循環，否則如果沒有就 插入那個序列，這就涉及 搜索 ，當然最好用 二分。。。
這樣就不算水了。。。
最後我並不是用這個解法。。。我是維護了一個Trace數組，相當於維護路徑。。。之後再處理路徑上的值的循環節。。。在電腦上對了，但是一直Runtime Error。。。改了數組上下界無數次也不行。。。後來直接改成 int 數組的極大值，AC了
附代碼：
#include <stdio.h>
//自動初始化為0
int Num[99999999];
int Trace[99999999];
void RecordTrace(int count)
{
int i;
for(i=count;i>=1;i--)
{
if(Num[Trace[i]]!=0)
continue;
else
Num[Trace[i]]=i;
}
}
int Process(int pos)
{
int count=1;
Trace[1]=pos;
while(pos!=1)
{
if(pos%2)
{
pos=3*pos+1;
if(Num[pos]!=0)
{
count+=Num[pos];
RecordTrace(count);
return count;
}
else
{
count++;
Trace[count]=pos;
}
}
else
{
pos/=2;
if(Num[pos]!=0)
{
count+=Num[pos];
RecordTrace(count);
return count;
}
else
{
count++;
Trace[count]=pos;
}
}
}
return count;
}
int main()
{
int a,b;
while(scanf("%d%d",&a,&b)!=EOF)
{
int x=a<b?a:b;
int y=a>b?a:b;
int max=-1;
int i,tmp;
for(i=x;i<=y;i++)
{
if(Num[i]!=0)
{
if(Num[i]>max)
max=Num[i];
}
else
{
tmp=Process(i);
if(tmp>max)
max=tmp;
}
}
printf("%d %d %d\n",a,b,max);
}
return 0;
}
另：附上一個不水的解法
POJ 1207 HDOJ/HDU 1032 3n+1數鏈問題 絕對不水的解法
最後更新：2017-04-03 14:53:50