试题详情
简答题把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法（用K表示）？请设计一个算法计算K值（只需要计算K值，不用把具体的分法输出）。注意：5，1，1和1，5，1是同一种分法。
  • 例：M=7，N=3则有K=8
    可能的分法为：
    7，0，0
    6，1，0
    5，2，0
    4，3，0
    5，1，1
    4，2，1
    3，3，1
    3，2，2
    设f（m，n）为m个苹果，n个盘子的放法数目，则先对n作讨论，如果n>m，必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响；即if（n>m）f（m，n）=f（m，m）当n<=m时，不同的放法可以分成两类：即有至少一个盘子空着或者所有盘子都有苹果，前一种情况相当于f（m，n）=f（m，n-1）；后一种情况可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即f（m，n）=f（m-n，n）.而总的放苹果的放法数目等于两者的和，即f（m，n）=f（m，n-1）+f（m-n，n）。边界条件为m=0或n=1时，只有一种放法。

  • 关注下方微信公众号，在线模考后查看

热门试题