题目

描述

题目描述

把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

数据范围：0<=m<=10，1<=n<=10。

本题含有多组样例输入。

输入描述：

输入两个int整数

输出描述：

输出结果，int型

示例1

输入：

7 3

输出：

8

解题思路

（1）递归对该问题进行求解

（2）输入m个苹果，n个盘子

（3）递归结束的条件为苹果放完，或者只有一个盘子，则只剩1种分法，返回1

（4）当苹果数m比盘子数少时，由于5，1，1和1，5，1 是同一种分法，超出的盘子数不起到增加分法的作用，因此放回f（m，m）

（5）当苹果数比盘子数要大时，问题变成是否考虑最后一个盘子

（6）不考虑最后一个盘子的分法为f(m，n-1)种

（7）所有盘子都要考虑的时候，必定每个盘子都要放一个，剩下的放进n个盘子

（8）所以分法为f(m-n, n)

（9）输出递归结果

代码

def f(m,n):
    if m == 0 or n == 1:
        return 1
    if m < n:
        return f(m, m)
    else:
        return (f(m, n-1)+f(m-n, n))

while True:
    try:
        m,n = map(int,input().split())
        print(f(m,n))
        
    except:
        break

Reference

华为机试题库_在线编程+题解_牛客题霸_牛客网