将数字n分解为k个不同数字的总和

问题描述

我有一个数字n，我必须将其拆分为k个数字，以使所有k个数字都不同，k个数字的总和等于n，而k为最大.例如，如果n为9，则答案应为1,2,6.如果n为15，则答案应为1,2,3,4,5.
这就是我尝试过的-

I have a number n and I have to split it into k numbers such that all k numbers are distinct, the sum of the k numbers is equal to n and k is maximum. Example if n is 9 then the answer should be 1,2,6. If n is 15 then answer should be 1,2,3,4,5.
This is what I've tried -

void findNum(int l, int k, vector<int>& s)
{
    if (k <= 2 * l) {
        s.push_back(k);
        return;
    }
    else if (l == 1) {
        s.push_back(l);
        findNum(l + 1, k - 1, s);
    }
    else if(l == 2) {
        s.push_back(l);
        findNum(l + 2, k - 2, s);
    }
    else{
        s.push_back(l);
        findNum(l + 1, k - l, s);
    }

}

最初，k = n和l =1.结果数字存储在s中.即使返回数字n作为k个不同数字的总和，该解决方案也不是最优解(k不是最大).n = 15的示例输出为1,2,4,8.应该做出什么改变才能获得正确的结果?

Initially k = n and l = 1. Resulting numbers are stored in s. This solution even though returns the number n as a sum of k distinct numbers but it is the not the optimal solution(k is not maximal). Example output for n = 15 is 1,2,4,8. What changes should be made to get the correct result?

推荐答案

贪心算法可解决此问题.只需开始从1到 m 求和，以使 sum(1 ... m)< = n .一旦超出，将多余的添加到 m-1 .答案从1到m | m-1.

Greedy algorithm works for this problem. Just start summing up from 1 to m such that sum(1...m) <= n. As soon as it exceeds, add the excess to m-1. Numbers from 1 upto m|m-1 will be the answer.

例如

18
1+2+3+4+5 < 18
+6 = 21 > 18
So, answer: 1+2+3+4+(5+6-(21-18))

28
1+2+3+4+5+6+7 = 28
So, answer: 1+2+3+4+5+6+7

伪代码(在恒定时间内，复杂度为O(1))

Pseudocode (in constant time, complexity O(1))

Find k such that, m * (m+1) > 2 * n
Number of terms = m-1
Terms: 1,2,3...m-2,(m-1 + m - (sum(1...m) - n))

这篇关于将数字n分解为k个不同数字的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！