Question

一道我的代码会超时的acm水题求优化或直接告诉我

我不知道 运算效率很快的代码应该怎么写 应该是有技巧性的吧？





Answer 1

去你们online judge试过了。。这个问题很可能不是效率的问题，有可能是溢出导致3n+1算出来是0，或者直接输入的时候溢出成0，然后死循环了，以下是一个AC的代码，可以看出效率没有提升多少，但也是15ms跑完了。

#include<stdio.h>
int main()
{
    int count;
    unsigned long long n;
    while(scanf("%I64u",&n)!=EOF) {
        count = 0; 
        while (n!=1) 
            if (!(n&1)) {n = n>>1; count++; }
            else {n += 1 + (n>>1); count+=2; }
        printf("%d\n",count);  
    }
    return 0;
}

不知道题目中的2^32范围内的输入n在实际计算过程中会变到多大，就是说这个代码我也不能保证没有溢出。

就问题本身而言，这是个经典数学猜想（搜索关键字 奇偶归一猜想 wiki百科上有），目前还不知道是否一定能最终变成1，所以也没有保证多项式时间内解出的算法。

追问

else {n += 1 + (n>>1); count+=2; }
这段代码 你是将两步计算 合成了一步是吗？
你的分析对我很有帮助 我去百度了一下奇偶归一猜想 很有意思的……

追答

是的。 估计你能看明白就没解释。
没问题了记得采纳啊兄弟

追问

肯定的啊 你的答案那么详细！！

追答

不客气！