#include <iostream>
using namespace std;
int enough(int goal)
{
int C { };
int i { };
if (goal > 1)
{
while (((C += i) <= goal) && ((goal - i) <= (i + 1)))
{
i += 1;
}
}
else
{
i = 1;
}
return i;
}
int main()
{
cout << enough(21);
return 0;
}
所以这个函数的作用就是返回在累加和大于参数“goal”之前,从1开始可以连续求和的最小正整数。
所以,例如:
cout << enough(9) << endl;
将打印 4 因为 1+2+3+4 > 9 但 1+2+3<9
cout << enough(21) << endl;
将打印 6 'cause 1+2+ 。 . .+6 > 21 但 1+2+ . . . 5<21
cout << enough(-7) << endl;
将打印 1 因为 1 > -7 并且 1 是最小的正整数
cout << enough(1) << endl;
将打印 1 因为 1 = 1 并且 1 是最小的正整数
起初我的逻辑是只使用 while ((C += i) <= goal)
, 但这是错误的, 例如, 对于参数 21, 你得到 C
= 20,它通过了测试并以 i
结尾增加 1(导致返回值 i
= 7,这显然是错误的)。
因此我决定创建一个测试来测试 C
和 i
, 但这是错误的,因为代码没有考虑 goal - i
和 i + 1
作为 while 电路的单独测试,但我相信它实际上改变了 int
的值s goal
和 i
, 这把一切都搞砸了。
有什么地方出错了吗?
最佳答案
您的方法不必要地冗长。对此有一个封闭形式(即 O(1))解决方案。
等差数列1,2,...,n的和S为
S = n * (n + 1) / 2
重新排列(完成平方),拒绝伪根,并适当舍入以符合问题的要求,得到结果
n = std::ceil((-1 + std::sqrt(1 + 8 * S)) / 2)
这不适用于负数 n
,也可能为 0,具体取决于特定(和未指定)的要求。
或者如果您必须使用 O(N) 方法,那么
int enough(int goal){
int i = 0;
for (int total = 0; (total += ++i, total) < goal; );
return i;
}
将执行此操作,它为 goal <= 1
返回 1 .
关于c++ - 函数 : smallest positive integer,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65416004/