放苹果

[编程题]放苹果

热度指数：11300 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

把 M 个同样的苹果放在 N 个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
注意：5、1、1 和 1、5、1 是同一种分法，即顺序无关。

输入描述:

输入包含多组数据。

每组数据包含两个正整数 m和n（1≤m, n≤20）。

输出描述:

对应每组数据，输出一个整数k，表示有k种不同的分法。

示例1

输入

7 3

输出

算法知识视频讲解

Python

TimeMac

动态规范

while True:
    try:
        m,n = list(map(int,input().split()))
        reuslts = [[0 for i in range(n + 1)] for j in range(m + 1)] #reuslts[i][j]表示j个盘子装i个苹果
        for i in range(1,m+1):
            reuslts[i][1] = 1
            for j in range(2,n+1):
                if i < j:                    #盘子比苹果多并不会增加分法
                    reuslts[i][j] = reuslts[i][j - 1]
                elif i == j:                 #盘子和苹果一样多，相当于多了一个全部盘子只摆一个，其他摆法起码有一个空盘
                    reuslts[i][j] = reuslts[i][j - 1] + 1
                else:                        #盒子比苹果少，等于有一个空盘加上全部盘摆上一个苹果剩余的摆法
                    reuslts[i][j] = reuslts[i - j][j] + reuslts[i][j - 1]
        print(reuslts[m][n])
    except Exception as message:
        print(message)
        break

编辑于 2018-10-03 01:12:58 回复(0)

Python

Aufwiedersehen

问题“将M个苹果放入N个盘子，有几种放法”可以扩展为“将M个苹果放入N个盘子，每个盘子最少放K个，有几种放法”，即：

对于i（K<=i<=M）,j（1<=j<=N），若前j个盘子全部放i个苹果，那么问题可变为子问题：剩下M-i*j个苹果放入N-j个盘子，每个盘子最少放i+1个，有几种放法。

PS.本题允许空盘子存在，第一次做出错，才发现问题出在这儿，即K的初值取0而不是1

Python代码如下：

while True:#允许读入多组样例
    try:
        def solution(m,n,k):#m个苹果放入n个盘子，每个盘子不得少于k

            #若n个盘子每个盘子放入k个恰好放完，则有1种解法
            if k*n==m:
                return 1
            #若剩下的m个苹果无法使得每个盘子的苹果都不少于k个，则无解
            elif k*n>m:
                return 0
            
            res=0
            for i in range(k,m+1):
                for j in range(1,n+1):
                    #若前j个盘子每个盘子都放入i个苹果，那么问题变为剩下m-i*j个苹果放入剩下n-j个盘子，每个盘子至少放i+1个，有几种放法
                    res+=solution(m-i*j,n-j,i+1)
            return res

        #读入数据
        m,n=list(map(int,input().split(' ')))
        #输出结果
        print(solution(m,n,0))
    except EOFError:
        break

编辑于 2018-02-13 19:17:19 回复(0)