c - 为什么在uva在线中超过3n + 1的时间限制

我不知道这是怎么回事..当我在我的电脑上运行时，它很好用，但是当我在uva中提交时，它说超过了时间限制，请帮助

#include <stdio.h>

int main（）
{

long int i,j,c,t,k,u,r;
scanf("%d %d",&i,&j);
printf("%d %d",i,j);
r = 0;
if(i>j){
    t = i;
    i = j;
    j = t;
}
for(k = i; k<=j;k++){
    c = 1;
    u = k;
    while(u>1){
        if(u%2 == 0)
            u = u/2;
        else
            u = 3*u+1;
        c++;
        if(c>=r)
            r = c;
    }
}
printf (" %d",r);
return 0;

}

最佳答案

当通过以下命令在我的ubuntu Linux 14.04上运行以下代码时，大约需要1秒钟才能运行：

./untitled > outfile.txt

所以这可能很有用。

注意：对于欧拉问题，必须对此进行重大修改

注意：问题显示“ UNDER”为100万，但是此代码从100万开始，而不是从999999开始

//  Longest Collatz sequence
// Problem 14

/*
 * criteria
 * The following iterative sequence is defined for the set of positive integers:
 *     n → n/2 (n is even)
 *     n → 3n + 1 (n is odd)
 *
 * example:
 * Using the rule above and starting with 13, we generate the following sequence:
 *     13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
 * It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms.
 * Although it has not been proved yet (Collatz Problem),
 * it is thought that all starting numbers finish at 1.
 *
 * the question:
 * Which starting number, under one million, produces the longest chain?
 *
 * Note:
 * Once the chain starts the terms are allowed to go above one million.
 */

#include <stdio.h>

// prototypes
void fastWrite( size_t a );



int main( void )
{
    #define MAX_START_VALUE (1000000)

    size_t LongestChain = 0;
    size_t LongestStartValue = 0;

    for( size_t i=MAX_START_VALUE; i; i--)
    {
        size_t chainLength = 0;
        size_t result = i;

        // for debug
        char buffer[] = "current start value:";
        for( size_t j=0; buffer[j]; j++) putchar_unlocked( buffer[j] );
        putchar_unlocked( ' ');
        fastWrite( i );
        // end debug

        while( result != 1 )
        {
            chainLength++;

            if( result&1 )
            { // then odd
                result = 3*result +1;
            }

            else
            { // else even
                result >>= 1;
            }

            // for debug
            //./fastWrite( result );
            // end debug
        }
        chainLength++;

        // for debug
        char buffer2[] = "chain length: ";
        for( size_t k=0; buffer2[k]; k++) putchar_unlocked( buffer2[k] );
        fastWrite( chainLength );
        putchar_unlocked( '\n' );
        // end debug

        if ( chainLength > LongestChain )
        {
            LongestChain = chainLength;
            LongestStartValue = i;
        }
    }



    fastWrite( LongestStartValue );
    putchar_unlocked('\n');
    //putchar_unlocked('\n');
} // end function: main


inline void fastWrite(size_t a)
{
    char snum[20];
    //printf( "%s, %lu\n", __func__, a );

    int i=0;
    do
    {
        // 48 is numeric character 0
        snum[i++] = (char)((a%10)+(size_t)48);
        a=a/10;
    }while(a>0);

    i=i-1; // correction for overincrement from prior 'while' loop

    while(i>=0)
    {
        putchar_unlocked(snum[i--]);
    }
    putchar_unlocked('\n');
} // end function: fastWrite