c++ - 3n + 1程序怎么了？

这是我的uva 3n + 1问题的代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    while(1){
        long long n, n2, i, iConst, maximum;
        vector<long long> vCycle;
        cin >> n >> n2;
        if(n < n2){
            for(long long i = n; i <= n2; i++){
                long long j = 1;
                iConst = i;
                while(iConst > 1){
                    if(iConst%2 == 0)
                        iConst = iConst / 2;
                    else
                        iConst = (iConst*3)+1;
                    j++;
                }
                vCycle.push_back(j);
            }
        }else{
            for(long long i = n2; i <= n; i++){
                long long j = 1;
                iConst = i;
                while(iConst > 1){
                    if(iConst%2 == 0)
                        iConst = iConst / 2;
                    else
                        iConst = (iConst*3)+1;
                    j++;
                }
                vCycle.push_back(j);
            }
        }
        maximum = *max_element(vCycle.begin(), vCycle.end());
        cout << n << " " << n2 << " " << maximum << endl;
    }
    return 0;
}

但是法官给出了以下错误：“超过时间限制”。
我的代码中有没有占用大量CPU的东西？
我的程序怎么了？
*问题链接：here

最佳答案

并不是这样，因为只有很少的数字需要大量的迭代才能获得最终输出，而这些输出已经被预先计算了。

例如

for n = 10,
10
5
16
8
4
2
1

for n = 20,
20
10
5
16
8
4
2
1
for n = 160,
160
80
40
20
10
5
16
8
4
2
1

看看有多少个数字在重复，您已经计算出10的步数，当计算n = 20时，我们不需要像现在已经做的那样在n变为10时再次计算它。

我建议您维护一个已计算数字的缓存，并每次检查该值是否已预先计算，如果是，则只需提供number + the existing count。
否则做数学。

这是欧拉计画的问题。最长的Collat​​z序列就是所谓的。他们需要的不仅仅是代码来解决它们。

关于c++ - 3n + 1程序怎么了？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30611190/