如何找到整数米的最大单分解? [英] How to find a maximal odd decomposition of integer M?
问题描述
设M是在范围[1的整数; 10亿。
Let M be an integer in range [1; 1,000,000,000].
一个的分解的的M是一组独特的整数,其总和等于M.
A decomposition of M is a set of unique integers whose sum is equal to M.
一个分解的奇的,如果它仅包含奇数。
A decomposition is odd if it contains only odd integers.
的M甲分解的最大的,如果有是M没有其他分解更大集合中的大小。
A decomposition of M is maximal if there is no other decomposition of M greater in size of the set.
写一个函数:
int[] maxOddDecomposition(int M)
这是返回一个数组M的的最大单分解的数组中的数字应该是升序排列。如果M没有任何奇数分解,阵列应为空。如果有一个以上的正确答案,该函数可以返回它们中的任何
that returns an array with a maximal odd decomposition of M. The numbers in array should be in ascending order. If M does not have any odd decomposition, an array should be empty. If there is more than one correct answer, the function may return any of them.
例如,M = 6有四个分解:
For example, M = 6 has four decompositions:
6 = 1 + 2 + 3
= 1 + 5
= 2 + 4
= 6
只有 1 + 5
是一个奇怪的分解,因而最大奇数分解。我们应该在阵列它回报,使得数组[0] = 1
和数组[1] = 5
。
Only 1 + 5
is an odd decomposition, thus is the maximal odd decomposition. We should return it in array such that array[0] = 1
and array[1] = 5
.
预计最坏情况下的时间和空间复杂度为O(开方(M))。
Expected worst-case time and space complexity is O(sqrt(M)).
我已经试过什么:
由于时间复杂度,必须SQRT(M),它提醒中号算法,在这里我们从1迭代到的sqrt(M)的幼稚因式分解的箱。没有进一步的想法出现了,虽然。只有它必须是非常快,只有开方(M)的步骤。
Since the time complexity has to be sqrt(M) it reminded me of naive factorization of M algorithm, where we iterate from 1 to sqrt(M). No further thoughts appeared though. Only that it must be really fast, only sqrt(M) steps.
所以,我做了一些例子。如何找到20例如一个答案?什么是奇数小于20? 1 + 3 + 5 + 7 + ......我们已经有16所以,我们可以添加4,但4是偶数。
So, I did some examples. How to find an answer for 20 for example? What are the odd numbers less than 20? 1 + 3 + 5 + 7 + ... we already have 16. So, we could add 4, but 4 is even.
那么,让我们来替换7(7 + 4)= 11,我们正在做的:1 + 3 + 5 + 11,我注意到的是,初始序列一向楼(开方(M))的元素,完美的。让我们code它在伪code:
So, let's replace 7 with (7 + 4) = 11 and we are done: 1 + 3 + 5 + 11. What I noticed is that the initial sequence had always floor(sqrt(M)) elements, perfect. Let's code it up in pseudo-code:
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。
I did a special case for M = 2, returning an empty array. I thought that's it, finito.
我没有注意到,它打破3,因为它给了 1 + 2
,而不是 3
的。而对于5,给 1 + 3 + 1
,而不是 5
。而更多的。
I didn't notice that it breaks for 3, because it gives 1 + 2
instead of 3
. And for 5, gives 1 + 3 + 1
, instead of 5
. And for many more.
你将如何解决呢?
推荐答案
下面是一个确定性的解决问题的办法。设M = {1,3,5,...,2 * K-3,2 * K-1,R},其中为r = 2 * K + 1中。明显的最大分解是不将有超过数第(k + 1)。
Here is a deterministic solution to the problem. Suppose M = {1, 3, 5, ..., 2*k-3, 2*k-1, r} where r <= 2*k + 1. It is 'obvious' that the maximal decomposition is not going to have more numbers than (k+1).
我们有以下的情况下,对于k> 3(推理和处理以前的案件是后来psented $ P $):
We have the following cases for k > 3 (the reasoning and handling of earlier cases is presented later):
案例1,如果r是奇数并等于2 * K + 1:添加r转换到列表中从而得到的第(k + 1)元素的分解
Case 1. If r is odd and equal to 2*k+1: add r into the list thereby giving a decomposition of (k+1) elements.
案例2,如果r是偶数:代替{(2 * k-1个)中,r} {2 * K-1 + R}给出k个元素的分解
Case 2. If r is even: replace {(2*k-1), r} by {2*k-1+r} giving a decomposition of k elements.
案例3.如果r是奇数和不等于2 * K + 1:取代所述第一和最后两个元素中的序列{1,2 * K-1,R}由{2 * K + R}给人(K-1)元素的分解
Case 3. If r is odd and not equal to 2*k+1: replace the first and the last two elements in the series {1, 2*k-1, r} by {2*k+r} giving a decomposition of (k-1) elements.
请注意,当输入的形式的n个将发生的(K-1)个元素的最坏情况^ 2 +(奇数2 * K + 1)。
Note that the worst case of (k-1) elements will occur when the input is of the form n^2 + (odd number < 2*k+1).
另外请注意,(情况3)将在壳体打破的元素数小于3,例如,为5和7的分解,我们将必须特殊情况下,这些数字。同样地(案例2)将突破3和将不得不特例。没有为M = 2无解。因此,限制K> 3以上。其他一切都应该很好地工作。
Also note that (Case 3) will break in case the number of elements is less than 3. For example, the decomposition of 5 and 7. We will have to special-case these numbers. Likewise (Case 2) will break for 3 and will have to be special-cased. There is no solution for M=2. Hence the restriction k > 3 above. Everything else should work fine.
这需要O(开方(M))的步骤。
This takes O(sqrt(M)) steps.
一些C / C ++ code:
Some C/C++ code:
#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
这篇关于如何找到整数米的最大单分解?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!