Ada*_*zyk 5 language-agnostic algorithm
令M为范围内的整数[1; 10亿.
M 的分解是一组唯一的整数,其总和等于M.
如果分解仅包含奇数整数,则分解为奇数.
如果在集合的大小中没有M的其他分解,则M的分解是最大的.
写一个函数:
int[] maxOddDecomposition(int M)
返回一个M的最大奇数分解的数组.数组中的数字应按升序排列.如果M没有任何奇数分解,则数组应为空.如果有多个正确答案,则该函数可以返回其中任何一个.
例如,M = 6有四个分解:
6 = 1 + 2 + 3
= 1 + 5
= 2 + 4
= 6
只是1 + 5奇数分解,因此是最大奇数分解.我们应该将它返回到数组中,以便array[0] = 1和array[1] = 5.
预期的最坏情况时间和空间复杂度为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做了一个特例,返回一个空数组.我认为就是这样,finito.
我没注意到它打破了3,因为它1 + 2代替了3.对于5,给出1 + 3 + 1,而不是5.还有更多.
你会如何解决它？
我不明白为什么人们必须把事情弄得如此复杂。奇怪的分解就像一个自共轭分区翻转并展开，例如，n = 13
4 4 3 2 => => => 7 5 1\n\nx x x x rotate x unfold out x x x x x x x\nx x x x clockwise \xe2\x86\x96 x x \xe2\x86\x97 each side x x x x x\nx x x 45 degrees x x x => x\nx x x x x x \n x x x\n奇数分解越大，相应自共轭的“边界平方”就越大。我所说的“边界正方形”是指左上角的正方形，它是所有类似大小的奇数分解中的常数。例如，我们可以写13为自共轭{5,3,3,1,1}，并且 9 单元“边界正方形”将保持不变，并具有相应的奇数分解{9,3,1}：
5 3 3 1 1 => 9 3 1\n\nx x x x x x x x x x x x x x\nx x x x x x\nx x x x\nx\nx\n要获得具有最大基数的奇数分解，请找到具有偶数余数的最大“边界正方形”。
\n\n例子：
\n\nM = 24\n\nBounding square | remainder\n1 23 \n4 20\n9 15\n16 8\n25...too large\n\nPlace the remainder in any diagonally-symmetric way you like. The simplest way might be\n\nxxxx xxxxxxxx\nxxxx => xxxx\nxxxx xxxx\nxxxx xxxx\n x\n x\n x\n x\n\nDecompose: 15,5,3,1\n我认为这个 Haskell 代码输出了所有可能性：
\n\n4 4 3 2 => => => 7 5 1\n\nx x x x rotate x unfold out x x x x x x x\nx x x x clockwise \xe2\x86\x96 x x \xe2\x86\x97 each side x x x x x\nx x x 45 degrees x x x => x\nx x x x x x \n x x x\n输出：
\n\n*Main> f 24\n[[1,3,5,15],[1,3,7,13],[1,5,7,11],[3,5,7,9]]\n\n*Main> f 23\n[[1,3,19],[1,5,17],[1,7,15],[3,5,15],[3,7,13],[5,7,11]]\n\n*Main> f 38\n[[1,3,5,7,9,13]]\n\n*Main> f 37\n[[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]]\n\n*Main> f 100\n[[1,3,5,7,9,11,13,15,17,19]]\n这是该问题的确定性解决方案。假设 M = {1, 3, 5, ..., 2*k-3, 2*k-1, r} 其中 r <= 2*k + 1。“显然”最大分解不会进行拥有比 (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