如何找到整数 M 的最大奇数分解？

Question

令M为范围[1； 1,000,000,000].

M的分解是一组唯一的整数，其总和等于M。

如果分解只包含奇数，则分解为奇数。

M 的分解是最大如果没有其他 M 的分解在集合的大小上更大。

写一个函数：

int[] maxOddDecomposition(int M)

return是一个数组，其中 M 的最大奇数分解。数组中的数字应按升序排列。如果 M 没有任何奇数分解，则数组应该为空。如果有多个正确答案，该函数可能 return 其中任何一个。

例如M = 6有四次分解：

6 = 1 + 2 + 3
  = 1 + 5
  = 2 + 4
  = 6

只有1 + 5是奇分解，因此是最大奇分解。我们应该 return 它在数组中使得 array[0] = 1 和 array[1] = 5.

预期的最坏情况时间和 space 复杂度为 O(sqrt(M))。

我尝试过的：

由于时间复杂度必须为 sqrt(M)，这让我想起了 M 算法的朴素分解，我们从 1 迭代到 sqrt(M)。不过没有进一步的想法出现。只是它必须非常快，只有 sqrt(M) 步。

所以，我做了一些例子。例如，如何找到 20 的答案？ 20以内的奇数有哪些？ 1 + 3 + 5 + 7 + ... 我们已经有了 16。所以，我们可以加 4，但 4 是偶数。

所以，让我们用 (7 + 4) = 11 替换 7，我们就完成了：1 + 3 + 5 + 11。我注意到初始序列总是有 floor(sqrt(M)) 元素，完美的。让我们用伪代码编写代码：

int len = floor(sqrt(M));
int result[] = new int[len];
int sum = 0;
for (i = 0; i < len - 1; i++) {
    result[i] = 1 + 2*i;
    sum += result[i];
}
result[len - 1] = M - sum;
return result;

我为 M = 2 做了一个特例，returning 一个空数组。我以为就这样了，finito。

我没有注意到它会中断 3，因为它给出 1 + 2 而不是 3。对于 5，给出 1 + 3 + 1，而不是 5。还有更多。

你会怎么解决？

Answer 1

这是一个可行的想法。它需要从你构造的贪心集合中净删除最多 1 个数。

像往常一样构造你的 O(sqrt(M)) 列表（没有 result[len - 1] = M - sum;）。如果总和不是平方数（即精确）：

加上下一个最大的奇数
计算你现在的总和和你的目标数字之间的差 -> N
- 若N为奇数，则去掉对应的数
- 如果N是偶数但不是2，去掉比N小的最大奇数，1
- 如果 N 为 2，删除您刚刚添加的 倒数第二个 数字。这将使差异 0

证明：

如果您按顺序添加连续的奇数，则列表应尽可能密集 - 即您不能有更大的列表
此外，差值始终以您在第 2 步中添加的奇数为界，因此 net 删除最多两个数字始终是奇差或偶差的帐户。

示例：

假设你想要 42：构建 [1, 3, 5, 7, 9, 11]，添加 13 => sum = 49，删除 7（没有净删除）
你想要 39：构建 [1, 3, 5, 7, 9, 11]，添加 13，删除 1 和 9（净删除 1）
您想要 38：构建 [1, 3, 5, 7, 9, 11]，添加 13，删除 11（无净删除）

编辑：最后一个案例中的错误由@user1952500 更正

Answer 2

这是问题的确定性解决方案。假设 M = {1, 3, 5, ..., 2*k-3, 2*k-1, r} 其中 r <= 2*k + 1。最大分解为 'obvious'数字不会超过 (k+1).

对于k > 3，我们有以下情况（前面的情况的推理和处理稍后介绍）：

情况 1。如果 r 是奇数且等于 2*k+1：将 r 添加到列表中，从而给出 (k+1) 个元素的分解。

情况 2. 如果 r 是偶数：将 {(2*k-1), r} 替换为 {2*k-1+r} 给出 k 个元素的分解。

情况3.若r为奇数且不等于2*k+1：将数列{1, 2*k-1, r}中的第一个和最后两个元素替换为{2*k+ r} 给出 (k-1) 个元素的分解。

请注意，当输入的形式为 n^2 +（奇数 < 2*k+1）时，将出现 (k-1) 个元素的最坏情况。

另请注意，如果元素数量小于 3，（情况 3）将中断。例如，分解 5 和 7。我们将不得不对这些数字进行特殊处理。同样（情况 2）将中断 3 并且必须是特殊情况。 M=2 无解。因此，上面的限制 k > 3。其他一切都应该工作正常。

这需要 O(sqrt(M)) 个步骤。

一些C/C++代码：

#include <stdio.h>

int main(int argc, char *argv[])
{
    printf("Enter M:");
    int m = 0;
    scanf("%d", &m);

    int arr[100] = {0};
    printf("The array is:\n");
    switch(m) {
        case 2:
            printf("No solution\n");
            return 0;
        case 1:
        case 3:
        case 5:
        case 7:
            printf("%d\n", m);
            return 0;
    }

    int sum = 0;
    int count = 0;
    for (int i = 1; (sum + i) < m; i+= 2) {
        arr[count++] = i;
        sum += i;
    }
    int start = 0;
    int r = m - sum;
    if (r % 2 == 0) {
        arr[count - 1] += r;
    } else if (r > arr[count - 1]) {
        arr[count++] = r;
    } else {
        start = 1;
        arr[count - 1] += r + 1;
    }

    for (int i = start; i < count; i++) {
        printf("%d\n", arr[i]);
    }

    return 0;
}

示例：

Enter M:24
The array is:
1
3
5
15

Enter M:23
The array is:
3
5
15

Answer 3

我不明白为什么人们要把它搞得这么复杂。一个奇数分解就像一个 self-conjugate 的分区打开它的一侧并展开，例如 n = 13

4 4 3 2     =>              =>            =>              7 5 1

x x x x   rotate             x         unfold out      x x x x x x x
x x x x   clockwise     ↖  x  x  ↗      each side       x x x x x
x x x     45 degrees      x  x  x           =>               x
x x                      x  x  x  x 
                          x  x  x

奇数分解越大，对应的自共轭"bounding-square"越大。 "bounding-square" 是指左上角的正方形，它在所有类似大小的奇数分解中都是一个常数。例如，我们可以将 13 写成自共轭 {5,3,3,1,1}，而 9 格 "bounding square" 将保持不变，相应的奇分解 {9,3,1}:

5 3 3 1 1        =>            9 3 1

x x x x x                x x x x x x x x x
x x x                          x x x
x x x                            x
x
x

要得到基数最大的奇数分解，找到最大的"bounding square"，余数为偶数。

示例：

M = 24

Bounding square | remainder
1                 23 
4                 20
9                 15
16                8
25...too large

Place the remainder in any diagonally-symmetric way you like. The simplest way might be

xxxx         xxxxxxxx
xxxx   =>    xxxx
xxxx         xxxx
xxxx         xxxx
             x
             x
             x
             x

Decompose: 15,5,3,1

我认为这个Haskell代码输出了所有的可能性：

f m = g [1,3..bestRoot*2 - 1] remainder 0 []
  where root = floor (sqrt (fromIntegral m))
        bestRoot = head $ dropWhile (\x -> odd (m - x^2)) [root,root - 1..1]
        remainder = m - bestRoot^2
        g (x:xs) r prev res
          | null xs   = [reverse ((x + r):res)]
          | otherwise = do r' <- takeWhile (<= div remainder bestRoot) [prev,prev + 2..]
                           g xs (r - r') r' ((x + r'):res)

输出：

*Main> f 24
[[1,3,5,15],[1,3,7,13],[1,5,7,11],[3,5,7,9]]

*Main> f 23
[[1,3,19],[1,5,17],[1,7,15],[3,5,15],[3,7,13],[5,7,11]]

*Main> f 38
[[1,3,5,7,9,13]]

*Main> f 37
[[1,3,5,7,21],[1,3,5,9,19],[1,3,7,9,17],[1,5,7,9,15],[3,5,7,9,13]]

*Main> f 100
[[1,3,5,7,9,11,13,15,17,19]]

如何找到整数 M 的最大奇数分解？

How to find a maximal odd decomposition of integer M?

language-agnostic

algorithm