algorithm - 从 n 个数字的总和中找到最接近的 n

Question

当我得到前 n 个数字的总和时，我正在尝试求解 n 的最接近值。 这意味着如果我的总和为 60，我的 n 应该是 10，因为前 10 个数字的总和是 55，如果我包括 11，总和将是 66，超过我要求的总和。

int num=1, mysum = 0;  
int givensum=60;
while (mysum < givensum) {
    mysum += num;
    num++;
}
cout<<num-1;
return 0;

我能想到的另一种解决方法是求解二次方程
n(n+1)/2 = givensum 并从中得到 n。 还有其他方法可以解决这个问题吗？

Answer 1

我认为没有比解决 quadratic equation 更好的方法了。 .非常简单，

n*(n+1)/2 = sum
n^2 + n - sum*2 = 0
assumin ax^2 + bx + c = 0
a = 1, b = 1, c = -2*sum

因为我们不需要否定答案:

n = ( -b + sqrt(b^2 - 4ac) ) / 2a

这是实现:

#include <iostream>
#include <cmath>
using namespace std;


int main()
{
    int sum = 60;
    int a = 1;
    int b = 1;
    int c = -sum*2;

    double delta = b*b - 4*a*c;
    if ( delta >= 0 ){
        double x1 = -b + sqrt(delta);
        //double x2 = -b - sqrt(delta); // we don't need the negative answer
        x1 /= 2*a;
        //x2 /= 2*a;
        cout << x1 << endl;
    }
    else {
        cout << "no result";
    }
}

结果是一个 float ，如果你希望 n 个元素的总和小于或等于输入的总和，你应该用 floor 向下取整功能。

---

考虑函数 f(n) = n*(n+1)/2，它产生前 n 个整数之和。这个函数是严格递增的。因此，当 f(n) 的值被提供给您时，您可以使用二进制搜索来查找 n:

#include <iostream>
#include <cmath>
using namespace std;


int main()
{
    int sum = 61;
    int low = 1, high = sum, mid;
    while ( low < high ){
        mid = ceil ( (low+high)/2.0 );
        int s = mid*(mid+1)/2;
        if ( s > sum ){
            high = mid-1;
        } else if ( s < sum ) {
            low = mid;
        } else {
            low = mid;
            break;
        }
    }
    cout << low << endl;
}