Hello World
Spiga

编程小练习:拆分自然数

2009-06-21 17:54 by 老赵, 25038 visits

上次的小练习的反响很不错,于是今天我们再来做一道小题目。上次有朋友指出,“反转数组”这种题目非常无聊,“写的再好,又会比框架自带的实现好吗?”。其实做这些小题目的作用是锻炼“编程解决问题”的能力,并非是为了替换框架的实现等等。咱们小学初中高中,不都会做数学题目,几何代数的吗?目的都是为了建立基本解题能力。现在的题目也是这样,请不要误会这些习题的目的。今天的题目如下:

给出sum、min、max和n四个正整数,请输出所有将sum拆分为n个正整数之和,其中每个正整数k都满足:min <= k <= max。这n个正整数之间可以重复,不过由于加法交换率的作用,1 + 2和2 + 1便算是重复的拆分了。

例如,sum = 5,n = 3,min = 1,max = 3,这时候满足条件的拆分方式只有两种:

  • 1 + 1 + 3
  • 1 + 2 + 2

这个练习和上次不同,我们假设所有的输入都是正整数。您无需对其进行合法性判断,只要专注于业务实现便是。您在看下面的内容之前,不如自己先简单尝试一下?老赵建议,您可以在这里阐述您的思路。至于代码,您可以在自己的博客上写一篇文章,然后再这里贴上链接,如果直接在这里贴代码的话,会使评论列表变得很长,影响阅读。点此展开

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

56 条回复

  1. Nick Wang (懒人王)
    *.*.*.*
    链接

    Nick Wang (懒人王) 2009-06-21 18:13:00

    每次要我写冒泡的时候,我都要花5分钟想那种排序叫冒泡排序

  2. 老赵
    admin
    链接

    老赵 2009-06-21 18:14:00

    @Nick Wang (懒人王)
    呵呵,nb。
    冒泡排序虽然是“经典算法”,但是这种“算法”的难度,应该属于听到描述之后立即可以写出来的那种。写不出来就应该去面壁了阿。

  3. 王克伟
    *.*.*.*
    链接

    王克伟 2009-06-21 18:34:00

    算法是我的心病,我得更加努力啊。

  4. Kevin Dai
    *.*.*.*
    链接

    Kevin Dai 2009-06-21 18:58:00

    希望老赵能成为国内计算机行业的启蒙大师。

  5. 老赵
    admin
    链接

    老赵 2009-06-21 19:17:00

    @王克伟
    不要想着“算法”,会让自己害怕。
    想着“编程解决问题”,这个就变成程序员的基本要求了。

  6. Q.Lee.lulu
    *.*.*.*
    链接

    Q.Lee.lulu 2009-06-21 20:16:00

    url绑JS事件的用###或者javascript:void(0)好点

  7. 老赵
    admin
    链接

    老赵 2009-06-21 20:24:00

    @Q.Lee.lulu
    啥?

  8. 水果阿生
    *.*.*.*
    链接

    水果阿生 2009-06-21 20:31:00

    马上能写出来的只有循环嵌套写法,有n的阶乘....

  9. 老赵
    admin
    链接

    老赵 2009-06-21 20:32:00

    @水果阿生
    啥?

  10. 徐少侠
    *.*.*.*
    链接

    徐少侠 2009-06-21 21:19:00

    貌似一下子想不出非递归解

    虽然完全能写出一个循环,然后使用一堆变量来控制循环的实际运行次数和每次的求解段落

    但是觉得这个其实就是模拟递归的方式。没啥意思

    需要继续思考有关递归的办法

    --引用--------------------------------------------------
    Jeffrey Zhao: @王克伟
    不要想着“算法”,会让自己害怕。
    想着“编程解决问题”,这个就变成程序员的基本要求了。
    --------------------------------------------------------
    这个的确同意
    我其实也反对纯谈算法。用程序解决问题才是本质
    算法仅仅是用来做练习,达到我们学会本质用的

  11. 老赵
    admin
    链接

    老赵 2009-06-21 21:31:00

    @徐少侠
    呵呵,能解决递归的“开销”就是成功咯。
    例如“尾递归”,其实编译器也是把它优化为递推的。
    思维是一样的,不必强求。
    如果可以顺利地把任何递归模拟出来,也是很可圈可点的能力啊。

  12. 水果阿生
    *.*.*.*
    链接

    水果阿生 2009-06-21 21:47:00

    @Jeffrey Zhao
    甚至连时间复杂度都算错了。以为要每次循环体中使用n-i作为循环出口

  13. 木鱼
    *.*.*.*
    链接

    木鱼 2009-06-21 21:53:00

    解出来了,发现和博主的类似,不过最后的Math.Max的那里的判断我还真没考虑到 -_-'

  14. Old
    *.*.*.*
    链接

    Old 2009-06-21 22:00:00

    老实说!现在让我写查找,递归,排序等算法程序,我的速度都不及7年前刚学程序设计那会!
    :-(

  15. heros
    *.*.*.*
    链接

    heros 2009-06-21 22:01:00

    这个似乎是原来一次编程竟塞题的改编题。题目是这样,n个球,放入m个篮子,每个篮子最多放x个球,问有多少总放法。可以递归。其实可以把m个篮子看成是m位(x+1)进制的数,该数各位上的和是n。

  16. 老赵
    admin
    链接

    老赵 2009-06-21 22:02:00

    @Old
    但是编程能力说不定呢。以前就熟悉那些,现在更融会贯通。

  17. 老赵
    admin
    链接

    老赵 2009-06-21 22:04:00

    @heros
    恩,求总数,和列出所有方法,解法是否一样?值得思考一下。

  18. Reginald
    *.*.*.*
    链接

    Reginald 2009-06-21 22:07:00

    我的一个想法是 先sum/n求出结果序列的平均数,平均数如果大于max或小于min则无解, 然后第一个值a一直增大到最大值为止, 然后递归调用sum - a, min, max, n-1

    这样解的序列可能会有重复, 具体解法等写出来了贴地址到这

  19. 老赵
    admin
    链接

    老赵 2009-06-21 22:08:00

    @Reginald
    可以把思路写的详细一点,用语言而不是纯粹靠代码来说明问题,更有效果。:)

  20. heros
    *.*.*.*
    链接

    heros 2009-06-21 22:09:00

    --引用--------------------------------------------------
    Jeffrey Zhao: @heros
    恩,求总数,和列出所有方法,解法是否一样?值得思考一下。
    --------------------------------------------------------
    进制每位最小为0,而min不一定为0,可以先将该自然数减去min*n,也就成了将sum-min*n分成n个max-min到0之间数的和。

  21. Old
    *.*.*.*
    链接

    Old 2009-06-21 22:17:00

    @Jeffrey Zhao
    --引用--------------------------------------------------
    Jeffrey Zhao: @Old
    但是编程能力说不定呢。以前就熟悉那些,现在更融会贯通。
    --------------------------------------------------------
    应该是老赵说的这样!如果没做到,只能是自己的问题。
    不能给自己找辩解的接口!
    :-)

  22. 勇赴
    *.*.*.*
    链接

    勇赴 2009-06-21 23:51:00

    老大,能不能改改版面啊?唉,看着乱糟糟的。

  23. James.Ying
    *.*.*.*
    链接

    James.Ying 2009-06-21 23:52:00

    --引用--------------------------------------------------
    Jeffrey Zhao: @王克伟
    不要想着“算法”,会让自己害怕。
    想着“编程解决问题”,这个就变成程序员的基本要求了。
    --------------------------------------------------------
    这是不是所谓的无招胜有招 哈哈

  24. 老赵
    admin
    链接

    老赵 2009-06-21 23:52:00

    @勇赴
    哪里看得乱?

  25. 老赵
    admin
    链接

    老赵 2009-06-21 23:53:00

    @James.Ying
    应该还没有那么玄……其实只是“算法”和“经典算法”的区别吧。

  26. Cat Chen
    *.*.*.*
    链接

    Cat Chen 2009-06-22 01:45:00

    用第一个while初始化序列为max + max + ... + max + min + min + ... + min的形式。再用一个while套while的形式来迭代所有组合。

  27. 老赵
    admin
    链接

    老赵 2009-06-22 09:49:00

    @Cat Chen
    嗯?没有听懂……

  28. 老赵
    admin
    链接

    老赵 2009-06-22 10:48:00

    @Stranger
    你的代码好像打不开,呵呵。

  29. Stranger
    *.*.*.*
    链接

    Stranger 2009-06-22 10:48:00

    不好意思,第一次回帖,不知道怎么弄,上面发的代码打不开。
    再发一遍,请原谅。

    f(sum,max,min,n)
    {
      //参数判断
      if(sum > max * n || sum < min * n)
      {
        printf("parameter input has error!");
        exit;
      }
     
      tempMax = max;
      while(tempMax >=  min)
      {
        if(n == 1)
        {
          printf("%d\n",tempMax);
          exit;
        }
        else
        {
          if((sum - tempMax) >= min * (n - 1))
          {
           printf("%d + ",tempMax);
           //递归调用
           f(sum - tempMax,tempMax,min,n -1 );
          }
          tempMax--;
        }
      }
    }

    我的思路是模仿”找钱”的思路(由大到小分配)配合递归。
    每次先尝试给第一个分配max,则剩下的n-1个每个至少要都是min。
    如果不满足该条件,第一个就分配max-1。
    第一个分配好后,剩下的都可以依次递归。
    为了穷举这个分配过程,用一个循环来控制max的大小。
    因为每次都是从最大的值开始分配,只要是适当的时候停住,
    就可以避免重复分配,
    比如,f(7,3,2,3)
    7 = 3 + 2 + 2 后,就可以不用考虑 2 + 3 + 2 等情况。
    请大家多多指教。 :)

  30. 蛙蛙池塘
    *.*.*.*
    链接

    蛙蛙池塘 2009-06-22 10:58:00

    非常支持老赵的这一个系列,最近也对算法和数据结构感兴趣。还没有实力自己去做题,先看看大家都答案,呵呵。

  31. 老赵
    admin
    链接

    老赵 2009-06-22 11:00:00

    @蛙蛙池塘
    系列不起来啊,素材找不到,呵呵。
    我是指,有针对性,代表性,难度适中的题目。

  32. AlexLiu
    *.*.*.*
    链接

    AlexLiu 2009-06-22 11:24:00

    你的评论能滚动。。。:)

  33. firsk[未注册用户]
    *.*.*.*
    链接

    firsk[未注册用户] 2009-06-22 14:02:00

    static void Main(string[] args)
    {
    //例出所有以x
    GetExpression(5, 1, 3, 3, new Stack<int>());

    }

    private static void GetExpression(int sum, int min, int max, int n, Stack<int> numbers)
    {
    if (numbers.Count == n)
    {
    if (numbers.Sum() == sum)
    {
    Console.WriteLine(string.Join("+", numbers.Select(e => e.ToString()).Reverse().ToArray()));
    }
    return;
    }

    for (int i = min; i <= max; i++)
    {
    numbers.Push(i);
    GetExpression(sum, i, max, n, numbers);
    numbers.Pop();
    }
    }

  34. haha1[未注册用户]
    *.*.*.*
    链接

    haha1[未注册用户] 2009-06-22 14:35:00

    max/n; 找出中间数,然后左边从1开始,递增
    右边就从中间数+n-1开始,递减

  35. dragonpig
    *.*.*.*
    链接

    dragonpig 2009-06-22 20:50:00

    我来尝试非递归版

    首先定义:
    1.根据字典序排列
    字符串:1+1+3 小于 1+2+2
    2.所有字符串升序排列: 2+1+2 非法!

    已知当前最大的序列a,如果可以找到b使得a<b,并且a和b之间没有其他序列,那么通过不断生成这样的序列就是所有解了。

    通过贪心法可以很容易的找出最小序列,满足min,max,sum,n的限制。比如当min=2,max=9,sum=5,n=4。从左往右,尽量取最小数,得到的结果就是2+5+9+9。把这样一个方法定义为Reset方便以后调用。

    现在开始我们的序列生成。为了寻找次大值,我们从右往左找到第一个较小值,上例中是5。根据定义,下一个序列最小可能从6开始(因为右边的值都没法动了)。调用Reset(min=6,max=9,{5,9,9})可能有两种情况,如果成功我们就得到下一个序列了,否则说明5无法增大只好考虑下一位2了。循环执行到第一位无法继续增大而终止(即找到最大序列了)。

    Notes:感觉递推版本没有递归的可读性好,不过多一种解法可以拓宽思路,更能对方法本身作出更好的评判,欢迎大家来讨论。

    一下是源代码:

    Code

  36. dragonpig
    *.*.*.*
    链接

    dragonpig 2009-06-22 22:26:00

    BTW.建议老赵给DoBest增加一个不变量的证明,就更完美了。因为这样更令人信服DoBest最终有解。

    这个在DoBest中的不变式就是
    min * n <= sum and max * n >= sum(其实在上面那个函数中出现了。这里maxInclusive=max,minInclusive=min只是老赵命名不一样)

    假设DoBest(n)满足上式,我们只需为所有递归式证明,
    对于i = itemMinInclusive .. itemMaxInclusive

    A. i*(n-1) <= sum - i 即 i*n <= sum

    B. max * (n-1) >= sum - i
    总是成立

    简证如下:
    A.因为
    i*n <= itemMaxInclusive*n <= sum/n*n <= sum
    所以总是 i*(n-1) <= sum - i

    B.因为
    max*(n-1) = sum - (sum - max*(n-1)) >= sum - i
    所以总是 max * (n-1) >= sum - i

    有了以上证明,当n=1,总是有解,因为min<=sum<=max。最后一个数sum总能够取到。

  37. heros
    *.*.*.*
    链接

    heros 2009-06-22 23:50:00

    --引用--------------------------------------------------
    heros: 这个似乎是原来一次编程竟塞题的改编题。题目是这样,n个球,放入m个篮子,每个篮子最多放x个球,问有多少总放法。可以递归。其实可以把m个篮子看成是m位(x+1)进制的数,该数各位上的和是n。
    --------------------------------------------------------
    比如10个球放入4个篮子,每个篮子最多放4个。可以循环4位5进制数,从0000到4444,一共循环624次,取出其中各位上数之和为10且各位数组合不重复的个数就是结果。说实话这个性能不高,也是个替换递归的思路吧。

  38. 徐少侠
    *.*.*.*
    链接

    徐少侠 2009-06-23 08:40:00

    老赵,我终于算是解好了

    先来通知一下

    等会发帖,这次是非递归解。并且自己觉得已经是很简洁了哦,貌似没有浪费的循环

    过几天再搞个对象版的解,毕竟在园子里我要冒充对象狂人的。

  39. 老赵
    admin
    链接

    老赵 2009-06-23 09:04:00

    @徐少侠
    狂人兄厉害!

  40. 徐少侠
    *.*.*.*
    链接

    徐少侠 2009-06-23 13:06:00

    发好了

    你要赔几个精神损失给我了

    半夜都没睡好觉

    呵呵

  41. 勇赴
    *.*.*.*
    链接

    勇赴 2009-06-23 14:15:00

    我晕,原来自己能换模板,版面爽多了。老赵有没有研究entity framework呢?我创建子概念模型的时候,程序能跑通,就是那个edmx文件老报错一些莫名其妙的错误,搞得我很郁闷。错误信息是第一行第一列"未将对象引用设置到对象的实例"。留言不能贴图?

  42. 老赵
    admin
    链接

    老赵 2009-06-23 15:31:00

    @勇赴
    没有研究entity framework,一点不懂……
    最好不要贴图吧,容易撑开版面,贴个链接就可以了。

  43. 寒飞雨
    *.*.*.*
    链接

    寒飞雨 2009-06-23 19:51:00

    看了您的博客,感觉差距如此只大。我只能算一个刚刚入门的初学者 。
    竟然发现我得博客出现在您的首页,非常感谢。您有空看看这两篇,欢迎你的指教。
    委托:http://www.cnblogs.com/BeginnerClassroom/archive/2009/01/09/1372285.html
    自定义事件:ttp://www.cnblogs.com/BeginnerClassroom/archive/2009/01/11/1373689.html
    类和对象的概念:
    http://www.cnblogs.com/BeginnerClassroom/archive/2009/01/05/1368932.html
    虽然写的不太好,但每一篇都花 了很多心思构思,针对初学者设计。

  44. 寒飞雨
    *.*.*.*
    链接

    寒飞雨 2009-06-23 19:54:00

    您提的问题我已经回答了,谢谢。
    http://www.cnblogs.com/BeginnerClassroom/archive/2009/06/23/1509325.html#1566488
    赶紧到教室看学生啦,喝呵

  45. 勇赴
    *.*.*.*
    链接

    勇赴 2009-06-23 22:26:00

    @Jeffrey Zhao
    还是很感谢

  46. cngaofei
    *.*.*.*
    链接

    cngaofei 2009-06-23 23:04:00

    这个应该是大学数据结构里面的栈的应用里面的回溯算法,“背包”问题,当时做过,非常有意思,当时很喜欢算法,但现在工作1年多了,也没遇到过多少需要自己写算法的问题。

  47. 老赵
    admin
    链接

    老赵 2009-06-23 23:06:00

    @cngaofei
    你觉得啥叫“写算法”呀?

  48. _龙猫
    *.*.*.*
    链接

    _龙猫 2009-06-24 10:48:00

    老赵的算法看得我晕乎乎的。原来我还是没有搞明白题目

  49. 浮云wu[未注册用户]
    *.*.*.*
    链接

    浮云wu[未注册用户] 2009-06-24 11:24:00

    老赵,请教一个问题,关于在项目中应用asp.net ajax。
    你在项目中完全应用asp.net ajax吗,包括使用updatepanel和ms的客户端脚本库,还是只使用部分功能? 或者是结合其它js框架库使用。能大概说一下asp.net ajax优缺点吗?如果单独或主要使用asp.net ajax会带来什么风险吗?我在网上查了相关资料,实在太少,都是教学的,很少有说的很清楚的。
    谢谢。

  50. cngaofei
    *.*.*.*
    链接

    cngaofei 2009-06-24 13:05:00

    @Jeffrey Zhao
    哦,是我没说清楚,当然写程序都是为了解决实际问题,只要解决了问题的方法都是算法,我只是觉得以前比如学习编译原理时,词法分析或语法分析的算法实现,就很有意思,而现在的工作中,主要是接触面窄,只是做一些应用系统,面对都是基本固定的业务应用基本固定框架类库,大多是针对业务逻辑的设计。

  51. Cat Chen
    *.*.*.*
    链接

    Cat Chen 2009-06-28 15:38:00

    @Jeffrey Zhao
    自己看吧:
    http://www.cnblogs.com/cathsfz/archive/2009/06/24/1509807.html
    http://www.cnblogs.com/cathsfz/archive/2009/06/28/1512747.html

  52. 徐少侠
    *.*.*.*
    链接

    徐少侠 2009-06-29 17:25:00

    赵同志 ,面向对象的自然数分解已经写好。

    呵呵,请查收

  53. winter-cn
    *.*.*.*
    链接

    winter-cn 2009-06-30 13:40:00

    我也写了 请查收

  54. yicone
    *.*.*.*
    链接

    yicone 2009-06-30 22:44:00

    递归实现 http://www.cnblogs.com/yicone/archive/2009/06/30/1514306.html

  55. 极品菜鸟
    *.*.*.*
    链接

    极品菜鸟 2009-07-01 09:28:00

    也去开个北大青鸟吧。。

  56. 链接

    satan.student 2014-08-19 18:27:37

    这道题本质上是深度优先搜索+剪枝,但是我觉得从这个角度去想不太好想。如果从数学归纳法(递归)的角度去考虑,先规定好输入所满足的条件,自然就会在递归调用的时候注意到所给的输入必须满足条件,从而自然地推导出这样的结论。顺便提醒一下,老赵你忘了考虑sum/n应该向上还是向下取整了。

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我