组合问题

[编程题]组合问题

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

把m个同样的足球放进n个同样的篮子里，允许有的篮子为空，问共有几种分法？

例如：3, 2, 1和2, 1, 3是同一种分法。

输入描述:

一行两个数字n，m（1<=n<=70，1<=m<=70）用空格隔开，表示篮子数和足球数。

输出描述:

一个整数 x 表示不同的分法数。

示例1

输入

3 7

输出

算法知识视频讲解

豪好学习

设f(m,n) 为m个足球，n个篮子的放法数目，则先对n作讨论

当n>m：必定有n-m个篮子永远空着，去掉它们对摆放足球方法数目不产生影响。

即if(n>m) f(m,n) = f(m,m)

当n<=m：不同的放法可以分成两类：

1、有至少一个篮子空着，即相当于f(m,n) = f(m,n-1);

2、所有篮子都有足球，相当于可以从每个篮子中拿掉一个足球，不影响不同放法的数目，即f(m,n) = f(m-n,n).而总的放足球的放法数目等于两者的和，即 f(m,n) =f(m,n-1)+f(m-n,n)

递归出口条件说明：
当n=1时，所有足球都必须放在一个篮子里，所以返回１；

当m==0(没有足球可放)时，定义为１种放法；

ref：https://blog.csdn.net/u013074465/article/details/45505279

编辑于 2020-02-28 15:27:35 回复(0)

Last101

import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
String[] strs=sc.nextLine().split(" ");
int n=Integer.parseInt(strs[0]);
int m=Integer.parseInt(strs[1]);
System.out.println(solution(n,m));
}
private static int solution(int n,int m){
if(n==1||m==0)
return 1;
else if(n>m){
return solution(m,m);
}else
return solution(n,m-n)+solution(n-1,m);
}

}

这道题用递归和动态规划都可以！

发表于 2020-03-03 12:26:42 回复(0)

喷跑的小牛

c++

6.
组合问题
把m个同样的足球放进n个同样的篮子里，允许有的篮子为空，问共有几种分法？
例如：3, 2, 1和2, 1, 3是同一种分法。
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 256M，其他语言512M
输入描述：
一行两个数字n，m（1<=n<=70，1<=m<=70）用空格隔开，表示篮子数和足球数。
输出描述：
一个整数 x 表示不同的分法数。
示例1
输入例子：
3 7
输出例子：
8
*/

#include <iostream>

using namespace std;

int f(int n, int m) {
    if (n == 1 || m == 0) {
        return 1;
    } else if (m < n) {
        return f(m, m);
    } else {
        //情况一：每个篮子里面都放有一个苹果，决定放法数的就是剩余苹果在n个篮子的放法数
        //情况二：至少有一个空篮子，即m个苹果在n-1个篮子的情况下的方法
        return f(n, m - n) + f(n - 1, m);
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    cout << f(n, m);

    return 0;
}

发表于 2023-09-14 16:50:49 回复(0)

Python

PurDragon

if __name__ == "__main__":
    nm = list(input().split(" "))
    n = int(nm[1])
    m = int(nm[0])

    dp = [[0 for i in range(m+1)] for j in range(n+1)]
    dp[0][0] = 0

    for i in range(1, m+1):
        dp[0][i] = 1

    for i in range(1, n+1):
        for j in range(1, m+1):
            if i >= j:
                dp[i][j] = dp[i][j-1] + dp[i-j][j]
            else:
                dp[i][j] = dp[i][j-1]

    print(str(dp[n][m]))

发表于 2020-02-15 22:20:00 回复(0)