0

我正在尝试编写编程挑战书籍中的第一个问题。该代码计算从 a 到 b 生成的数字的数量。
如果 n 为偶数，则新的 n 为 n/2，如果为奇数，则为 3*n+1
例如，对于 22，它将计算数字 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 等等数字是 16。打印 113383 后代码停止，我输入为
1 1000000

#include <iostream>
#include <map>
#include <vector>

using std::cout;
using std::cin;
using std::string;
using std::endl;


using std::vector;
using std::map;
map<long,long> solution;


long sequences(long n) {
// returns the number of numbers(including 1) `n`produces till it becomes 1
    if(n==1)
        return 1;
    else{
        // assuming n>1

        if(solution.find(n)!=solution.end())
            return solution.find(n)->second;
        long size = 0;
        while(n!=1){
            if(n%2==0){
                n = n/2;
                if(solution.find(n)!=solution.end())
                    return solution.find(n)->second + size;

            }
            else{
                n = 3*n+1;
            }
            size++;
        }
        return size+1;
    }
}
long sequences(long a,long b){
    // returns the maximum numbers produced by numbers from a to b inclusive
    long result,max = -1;
    if(a<b){
        for(long i=a;i<=b;i=i+1){
            if(solution.find(i) == solution.end()){
                cout<< i << endl;
                result = sequences(i);
                solution.insert(map<long,long>::value_type(i,result));

            }
            else{
                //i present in solution
                result = solution.find(i)->second;
            }
            if(result>max)
                max = result;
        }
        return max;
    }
    return -1;
}



int main(int argc, char* argv[]) {

    long a,b,max;


    cin >> a >> b;
//  while(cin>>a>>b){
        cout<<a<<" "<<b<<" "<<sequences(a,b)<<endl;
    /*}*/

    return 0;
}
4

1 回答 1

6

你可能有一个溢出错误。对于 113383 以下的所有数字，有符号的 long 足以计算冰雹序列而不会溢出。但是对于 113383 的起始值，在冰雹序列期间达到的最大值是 2482111348。这有点太大而不能保存在有符号长整数中，其最小上限为 (2^31)-1。

于 2012-11-28T20:49:22.543 回答