c++ - 函数 : smallest positive integer

Question

#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 , 这把一切都搞砸了。

有什么地方出错了吗？

Answer 1

您的方法不必要地冗长。对此有一个封闭形式(即 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 .