所以,我必须为大学做一个工作,它包括创建一个算法。
该算法必须找到满足特定条件的数对,即:从 1
到 n
(不包含)的总和结果与从 n+1
到 m
(含)。
在最后,算法必须给出至少 15 对。
第一对是6
和8
,因为从1
到n
(不包括)(6)是 1+2+3+4+5
= 15
并且从 n+1
到 m
是 8+7
= 15
。
我创建的算法如下:
int main() {
int count = 0;
unsigned int before = 0;
unsigned int after = 0;
unsigned int n = 1;
unsigned int m = 0;
do {
before += n - 1;
after = n + 1;
for (m = after + 1; after < before; m++) {
after += m;
}
if (before == after) {
printf("%d\t%d\n", n, (m - 1));
count++;
}
n++;
} while (count < 15);
}
这实际上是可以的,但是有些输出不正确,而且在复杂性方面也很糟糕,而且由于我正在研究算法的复杂性,所以最好找到一些比这个更好的算法。
我也试过用 Java 来做,但是使用 int 对这个问题不好,而使用 long,计算需要数小时和数小时。
到目前为止我找到的数字:
6 and 8
35 and 49
204 and 288
1189 and 1681
6930 and 9800
40391 and 57121
以下可能是错误的:
100469 and 107694
115619 and 134705
121501 and 144689
740802 and 745928
1250970 and 1251592
2096128 and 2097152
2100223 and 2101246
4196352 and 8388608
18912301 and 18912497
最佳答案
除了前 6 个之外,您的结果不正确:unsigned int
类型的范围不足以存储总和。您应该为 before
和 after
使用 unsigned long long
类型。
此外,对于大值,您的算法变得非常慢,因为您从头开始为 before
的每个新值重新计算 after
,时间复杂度为 O( N2)。您可以并行保持 2 个运行和并将复杂度降低到准线性。
最后但同样重要的是,UINT32_MAX
以下只有 12 种解决方案,因此类型 unsigned long long
,保证至少有 64 个值位 n
和 m
也是如此。为避免不正确的结果,在更新 after
时应测试溢出。
进一步的测试表明,对于 8589934591
附近的 m
值,after
和 before
的总和超过 64 位。一个解决方案是当 before
和 after
达到 263 时都减去 262。通过此修改,程序可以继续搜索更大的 n
和 m
值,远远超过 32 位。
这是一个改进的版本:
#include <stdio.h>
int main() {
int count = 0;
unsigned long long n = 1;
unsigned long long m = 2;
unsigned long long before = 0;
unsigned long long after = 2;
for (;;) {
if (before < after) {
before += n;
n++;
after -= n;
} else {
m++;
/* reduce values to prevent overflow */
if (after > 0x8000000000000000) {
after -= 0x4000000000000000;
before -= 0x4000000000000000;
}
after += m;
while (before > after) {
after += n;
n--;
before -= n;
}
}
if (before == after) {
printf("%llu\t%llu\n", n, m);
count++;
if (count == 15)
break;
}
}
printf("%d solutions up to %llu\n", count, m);
return 0;
}
输出(运行时间 30 分钟):
6 8
35 49
204 288
1189 1681
6930 9800
40391 57121
235416 332928
1372105 1940449
7997214 11309768
46611179 65918161
271669860 384199200
1583407981 2239277041
9228778026 13051463048
53789260175 76069501249
313506783024 443365544448
15 solutions up to 443365544448
关于c - 如何找到从 1 到 n 和从 n+1 到 m 的和相同的数对,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52375135/