我试图在http://www.programming-challenges.com提交我的代码,但我只得到了错误的答案。我试过像1000000这样的大输入数来测试,我的代码返回答案如果有人能帮忙,我将非常感激。这是我的代码:
#include <stdio.h>
unsigned int max_cycle(unsigned int i, unsigned int j);
unsigned int cycle_size(unsigned int m);
void swap(unsigned int *m, unsigned int *n);
int main(int argc, char *argv[]) {
unsigned int a, b;
int scan;
scan = scanf("%u %u", &a, &b);
printf("%u %u %u", a, b, max_cycle(a, b));
while (scan> 0) {
if((scan = scanf("%u %u", &a, &b)) > 0) {
printf("\n%u %u %u", a, b, max_cycle(a, b));
}
}
return 0;
}
unsigned int max_cycle(unsigned int x, unsigned int y) {
unsigned int length = 0;
unsigned int max = 0;
if(x > y) {
swap(&x, &y);
}
x++;
while(x < y) {
length = cycle_size(x);
if(length > max) {
max = length;
}
x++;
}
return max;
}
unsigned int cycle_size(unsigned int x) {
unsigned int cntr = 1;
while(x != 1) {
if(x % 2 == 0) {
x = x/2;
} else {
x = 3*x+1;
}
cntr++;
}
return cntr;
}
void swap(unsigned int *x, unsigned int *y) {
unsigned int term = 0;
term = *x;
*x = *y;
*y = term;
}
最佳答案
你的代码有个致命的错误。完全忽略整数溢出。你不需要搜索很长时间,直到你找到一个x开始一个不适合32位的序列由于一个序列不适合32位的X很可能产生一个长周期,所以你很可能错过最大循环长度的数字。
64位会更进一步,但不会太多。
关于c - 3n + 1个猜想中的最大循环长度,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/25595836/