从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

我认为没有比解决二次方程更好的方法了。这很简单，

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个整数之和的函数。此功能正在严格增加。因此，当给定值for时，可以使用二进制搜索来找到nf(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;
}