草庐IT

c++ - 将数字 n 拆分为 k 个不同数字的总和

coder 2024-02-17 原文

我有一个数字 n，我必须将它分成 k 个数字，这样所有 k 个数字都是不同的，k 个数字的总和等于 n，并且 k 是最大值。例如，如果 n 为 9，则答案应为 1,2,6。如果 n 是 15 那么答案应该是 1,2,3,4,5。
这是我试过的 - 

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。应该进行哪些更改才能获得正确的结果？

最佳答案

贪心算法适用于此问题。刚开始从 1 到 m 求和这样 sum(1...m) <= n .一旦超过，将超出部分添加到 m-1 .从 1 到 m|m-1 的数字就是答案。

例如。

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))

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))

关于c++ - 将数字 n 拆分为 k 个不同数字的总和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41011408/

amp43codesectionpush_backc++algorithm

有关c++ - 将数字 n 拆分为 k 个不同数字的总和的更多相关文章

  1. ruby - 如何以所有可能的方式将字符串拆分为长度最多为 3 的连续子字符串？ - 2

    我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123

  2. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  3. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

    我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

  4. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  5. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  6. java - 为什么 ruby​​ modulo 与 java/other lang 不同？ - 2

    我基本上来自Java背景并且努力理解Ruby中的模运算。(5%3)(-5%3)(5%-3)(-5%-3)Java中的上述操作产生，2个-22个-2但在Ruby中，相同的表达式会产生21个-1-2.Ruby在逻辑上有多擅长这个？模块操作在Ruby中是如何实现的？如果将同一个操作定义为一个web服务，两个服务如何匹配逻辑。 最佳答案 在Java中，模运算的结果与被除数的符号相同。在Ruby中，它与除数的符号相同。remainder()在Ruby中与被除数的符号相同。您可能还想引用modulooperation.

  7. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  8. ruby-on-rails - 在 RSpec 中，如何以任意顺序期望具有不同参数的多条消息？ - 2

    RSpec似乎按顺序匹配方法接收的消息。我不确定如何使以下代码工作:allow(a).toreceive(:f)expect(a).toreceive(:f).with(2)a.f(1)a.f(2)a.f(3)我问的原因是a.f的一些调用是由我的代码的上层控制的，所以我不能对这些方法调用添加期望。 最佳答案 RSpecspy是测试这种情况的一种方式。要监视一个方法，用allowstub，除了方法名称之外没有任何约束，调用该方法，然后expect确切的方法调用。例如:allow(a).toreceive(:f)a.f(2)a.f(1)

  9. ruby - 是否有内置的 Ruby 1.8.7 将数组拆分为相同大小的子数组？ - 2

    我已经开始了:defsplit_array(array,size)index=0results=[]ifsize>0whileindex如果我在[1,2,3,4,5,6]上运行它，比如split_array([1,2,3,4,5,6],3)它将产生这个数组:[[1,2,3],[4,5,6]]。在Ruby1.8.7中是否已经有可用的东西可以做到这一点？ 最佳答案 [1,2,3,4,5,6].each_slice(3).to_a#=>[[1,2,3],[4,5,6]]对于1.8.6:require'enumerator'[1,2,3,4

  10. ruby - 将n维数组的每个元素乘以Ruby中的数字 - 2

    在Ruby中，是否有一种简单的方法可以将n维数组中的每个元素乘以一个数字？这样:[1,2,3,4,5].multiplied_by2==[2,4,6,8,10]和[[1,2,3],[1,2,3]].multiplied_by2==[[2,4,6],[2,4,6]]？(很明显，我编写了multiplied_by函数以区别于*，它似乎连接了数组的多个副本，不幸的是这不是我需要的)。谢谢! 最佳答案 它的长格式等价物是:[1,2,3,4,5].collect{|n|n*2}其实并没有那么复杂。你总是可以使你的multiply_by方法:c

随机推荐