给定n，找到最大数量的数字相加以得到n。

Question

这是一个Oracle面试中的问题。例如，如果我的输入是6，那么

• 5+1=6 答案：2
• 4+2=6 答案：2
• 3+2+1=6 答案：3

因此，最终答案应为3。（即需要3、2、1来得到总和6）

注意：不允许重复使用数字（即1+1+1+1+1+1=6不行）

我用递归解决了这个问题，但面试官并不满意。动态规划是否可行？

- explorer

---

这个问题看起来很熟悉，它是来自学校还是来自欧拉计划（Project Euler）？ - Craftein

这个问题有一个常数解，不需要递归，所以面试官不满意。 - Ivaylo Strandjev

你需要左侧的两个数字不相等吗？ - ajay

@Desolator 为什么不可能？ - explorer

@Desolator 至少存在一个非重复正整数序列，它们的和为9（即只有一个元素的序列{9}）。这样的序列数量是有限的。因此，在它们中间一定有一个最长的序列（例如{2,3,4}就是这样一个序列，还有其他相同长度的序列）。 - n. m.

Answer 1

求 x 个数的最小和为

只需找到满足不等式的 x：

以下是代码：

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int x = 1;
    while ((x+1)*x/2 <= n) x++;
    x--; // now (x+1)*x/2 > n , so x is too large
    printf("%d\n", x);
    return 0;
}

如果n非常大，您可以使用二分搜索。

- Cruise Liu

---

你从哪里得到这个公式的？ - haccks

(x+1)x/2<=n 表示可以找到 x 个数，它们的和为 n；n<(x+2)(x+1)/2 表示不可能找到 x+1 个数，使它们的和为 n，因为 x+1 个数的总和始终大于或等于 (x+2)*(x+1)/2。 - Cruise Liu

@abi 让我举个例子来解释一下。1+2+3=6。1+2+3+4=10。9小于10，所以你不能将它表示为4个数字的和。但是你可以从那组4个数字中准确地删除一个数字（哪一个？1+2+3+4-9=1），并得到9。实际上，2+3+4=9。 - n. m.

@abi 首先，对于 N = 1 + 2 + .. + x 形式，最多可能有 x 个数字分割（显而易见）。同样地，对于 M = 1 + 2 .. + (x-1)，最大的分割数是 x-1。 - csslayer

@abi（续） 对于[M+1，N-1]中的所有数字，最大分区数至少为x-1，因为我们可以通过1+..+(x-2)+remaining构建一个分区。假设可以将其分成x个部分，则按顺序考虑第一个（x-1）个部分。它们的总和大于M，并且第（x-1）个数字大于等于x-1。但是剩余部分小于等于x-1。因此，无法将其分成x个部分。 - csslayer

Answer 2

我本来要回答的，但是@Cruise Liu比我快。我尝试解释一下。 这是一种整数分割的类型，但你不需要生成元素，因为你只关心“元素数量”。即最终答案是3而不是{1, 2, 3}。

给定一个数字N，你还有另一个限制，即数字不能重复。 因此，最好的情况是如果N实际上是一个数字，比如1、3、6、10、15。

i.e. f(x) = x * (x + 1) / 2. 

例如，取数字6。存在函数f(x) = 6。具体来说，f(3) = 6。因此，你得到答案是3。

这意味着，如果存在整数X使得f(x) = N，则存在一个数字集合1,2,3...x，这些数字相加得到N。这是最大的可能数量（不重复）。

但是，在f(x) = N的情况下，有时x不是整数。

f(x) = x * (x + 1 ) / 2 = N
i.e. x**2 + x = 2*N
x**2 + x - 2*N = 0

解决这个二次方程，我们得到：

由于数字x不是负数，我们不能有：

因此，我们得到：

当N = 6时：

这是一个完美的整数。但是当N = 12时：

它等于8.845 / 2，是一个分数。向下取整值为4，这就是答案。

简而言之：实现一个函数f(N) = (int) ((-1.0 + sqrt(1 + 8*N))/2.0 )

即：

int max_partition_length(int n){
    return (int)((-1.0 + sqrt(1 + n*8))/2);
}

- algrebe

---

非常感谢@JDS。阅读了您的评论后，我在网上查看了一下。最简单的方法是使用LaTeX生成公式，并将其作为图像添加到这里？（这就是我从所有关于LaTeX的问题中得出的结论。其他人说，这只可能在数学和物理论坛上实现）。 - algrebe

是的，基本上就是这样。我使用了 LaTeXiT （我不知道是否有类似的 Windows/Linux 软件）来自动裁剪生成的图像。 - JDS