我不知道这是怎么回事..当我在我的电脑上运行时,它很好用,但是当我在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