问题是找到存在最长 collatz 系列的数字 i<=n， n<=500000。 数 n 的 Collatz 级数以 1 终止，条件为 如果 n 为偶数，则下一项 = n/2 如果 n 为奇数，则下一项 = 3*n + 1
事实上，对于所有数字，collatz 级数总是以 1 结尾。
因此，任何数字都不会在其 collatz 系列中重复。利用这个事实，我编写了以下代码 逻辑： 我开始一个 while 循环，一直持续到 n，对于每次迭代，我存储该 i 的序列长度。 如果 i 出现在某个 n>= r> i 的序列中，那么我终止循环并将 i 的长度添加到 r。 例如，假设 3 的系列是 3、10、5、16、8、4、2、1。现在对应于 2 的长度已经存储在 series_length 数组中，所以我使用该值。
然后旁边的 for 循环找到最长的序列并显示答案。
准确地说，该代码适用于 n <= 1818，但显示分段错误(不知道为什么:((。请帮忙
法典：
#include <stdio.h>
int length = 0, series_length[500000], maxlength = 0;
void store_length(int n) {
while(n > 1 && series_length[n] == 0) {
length++;
if(n%2 == 0) {
n = n/2;
}
else {
n = 3*n + 1;
}
}
length += series_length[n];
}
int main() {
int n, i = 1, result;
scanf("%d", &n);
series_length[1] = 1;//redundant statement
while(i <= n) {
store_length(i);
series_length[i] = length;
length = 0;
i++;
}
for(int i = 1;i <= n; i++) {
if(maxlength <= series_length[i]) {
maxlength = series_length[i];
result = i;
}
}
printf("%d %dn", result, maxlength);
return 0;
}
输入- 10 输出- 9 20(如预期(
输入- 100000 输出- 分段错误 预期- 77031 351
您的n值超出了范围。
函数n = 3*n + 1;中有一行store_length
使用 gdb 运行它，并按照100000给出的输入运行它
Thread 1 received signal SIGSEGV, Segmentation fault.
0x0000000000401545 in store_length (n=532060) at 29_01.c:6
6 while(n > 1 && series_length[n] == 0) {
(gdb) p n
$1 = 532060
- 仅在适合时才存储它
- 。如果已经计算出来，则使用它
- 避免全局变量
- 首选无符号值
- [使用描述性变量名称]
#include <stdio.h>
#define THE_SIZE 500000
unsigned series_length[THE_SIZE]= {0,};
unsigned get_length(unsigned val) {
unsigned steps;
for (steps=0; val > 1 ; steps++) {
if (val < THE_SIZE && series_length[val]) { steps += series_length[val]; break; }
if(val %2 ) val = 3*val + 1;
else val /= 2;
}
return steps;
}
int main( int argc, char **argv) {
unsigned top, val , result;
unsigned best,maxlength ;
sscanf(argv[1], "%u", &top);
series_length[1] = 1;//redundant statement
best = maxlength = 0;
for(val=1;val <= top; val++) {
result = get_length(val);
// store it if it fits;
if(val<THE_SIZE) series_length[val] = result;
if (result < maxlength) continue;
best = val; maxlength = result;
}
printf("%u %un", best, maxlength);
return 0;
}
最后，只是为了好玩，使数组更小
#define THE_SIZE 500
，并且程序应针对给定值给出相同的结果。(确实如此(
在 n = 487039 的情况下，您可以获得最大值 24,648,077,896。
因此，必须对n使用类型long long int，并且应使用 24,648,077,896 个整数的数组以避免分段错误。不幸的是，我从未成功分配100GB的块。因此，您的优化是不可行的。
如果没有数组优化，我可以在 265 毫秒内扫描所有 500000 n 个值。
这是我的代码：
#include <stdio.h>
int collatz_length(int n) {
int length = 0;
long long int v = (long long int)n;
while (v > 1) {
if ((v&1) == 0)
v = v / 2;
else
v = v*3 + 1;
length++;
}
return length;
}
int main() {
int max_i, max_l = 0;
for (int i = 500000; i > 0; i--) {
int l = collatz_length(i);
if (l > max_l){
max_l = l;
max_i = i;
}
}
printf("i: %d l: %dn", max_i, max_l);
return 0;
}