poj 1207 The 3n + 1 problem

2023-11-05 05:08

文章标签 poj problem 3n 1207

本文主要是介绍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;elsei/=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;elseNum[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;
}

另：附上一个不水的解法