题解 | #放苹果#
放苹果
http://www.nowcoder.com/practice/bfd8234bb5e84be0b493656e390bdebf
放苹果
算法知识视频讲解
简单 通过率:43.44% 时间限制:1秒 空间限制:32M
知识点
递归
动态规划
题目
题解(31)
讨论(193)
排行
warning 校招时部分企业笔试将禁止编程题跳出页面,为提前适应,练习时请使用在线自测,而非本地IDE。
描述
题目描述
把m个同样的苹果放在n个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。
数据范围:0<=m<=10,1<=n<=10。
本题含有多组样例输入。
输入描述:
输入两个int整数
输出描述:
输出结果,int型
示例1
输入:
7 3
复制
输出:
8
#include <iostream> using namespace std; /* * 递归 * 思想:设置getSums(m,n);,苹果为m,盘子为n。 * 当盘子n>苹果m,则一定有n-m个盘子是空着,因此不会影响苹果放在盘子的种类,即getSums(m,n) = getSums(m,n); * 当盘子n<=苹果m: * 1. 至少有一个盘子是空的,则getSums(m,n) = getSums(m,n-1) 2. 每个盘子都有苹果,则拿走n-m个苹果不影响结果,getSums(m,n) = getSums(m-n,n) 即getSums(m,n) = getSums(m,n-1) + getSums(m-n,n) * 递归条件出口: 当苹果m为0,则盘子上都是空的,即输出为1; 当盘子为1,则所有苹果都放在一个盘子上,即输出为1; */ int getSums(int m, int n) { if(m == 0 || n ==1) { return 1; } if(n > m) { return getSums(m,n-1); } else { return getSums(m,n-1) + getSums(m-n,n); } } int main() { int m,n; while(cin>>m>>n) { int nums = 0; nums = getSums(m, n); cout<<nums<<endl; } }