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

当我得到前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。
有没有别的办法解决这个问题？

最佳答案

我认为没有比解决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";
    }
}

结果是一个浮点数，如果希望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;
}

关于algorithm - 从n个数字的总和中找到最接近的n，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39669641/