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