#题解数的划分

发布于 2020-04-30 | 分类于题解 | 4分钟 | 662字数 | 浏览量：

我们先来读题

题目描述

将整数 $n$ 分成 $k$ 份，且每份不能为空，任意两个方案不相同(不考虑顺序)。

例如： $n=7，k=3$ ，下面三种分法被认为是相同的。

$1,1,5;$
$1,5,1;$
$5,1,1.$

问有多少种不同的分法。

输入格式

$n,k (6<n\le200，2 \le k \le 6)$

输出格式

11个整数，即不同的分法。

输入输出样例

输入 #1

7 3

输出 #1

说明/提示

四种分法为：

1,1,5;
1,2,4;
1,3,3;
2,2,3.

具体实现

如果看过题解：放苹果的看完题大概就联想到了放苹果，只不过是把数放到份数里面，也就对应了苹果和盘子，但是在放苹果中是允许出现空盘子的，而这里不能有空的，那怎么解决呢？

样例①：

#include<bits/stdc++.h>//万能头文件 
#include <iostream>
#include <cstring>
#include <algorithm>   
#include <math.h>
#include <cstdio>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int rank(int apple,int plate){
	if(apple == 1||apple==0) return 1;
	if(plate==1)return 1;
	if(plate==0) return 0; 
	
	
	if(apple>=plate){
		// 1.用上所有盘子  2. 存在空盘子×
		return rank(apple-plate,plate) ;//更改在这儿，他把存在空盘子的选项删了。
	}else{
		return rank(apple,apple);
	}
	
}

int main(int argc, char** argv) {
	int a,p;
	cin>>a>>p;
	cout<<rank(a,p);
	return 0;
}

大家看到了吗？看上去没毛病，但仔细一想，递归就是把问题规模缩小，第一次要是每个盘子里都放上了呢，接下来还是可以这样的，别急，我们来看正解~~说出来别不信这是正解~~

#include<bits/stdc++.h>//万能头文件 
#include <iostream>
#include <cstring>
#include <algorithm>   
#include <math.h>
#include <cstdio>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int rank(int apple,int plate){
	if(apple == 1||apple==0) return 1;
	if(plate==1)return 1;
	if(plate==0) return 0; 
	
	
	if(apple>=plate){
		// 1.用上所有盘子  2. 存在空盘子
		return rank(apple-plate,plate) + rank(apple,plate-1);
	}else{
		return rank(apple,apple);
	}
	
}
//函数貌似没改噫

int main(int argc, char** argv) {
	int a,p;
	cin>>a>>p;
	cout<<rank(a-p,p);//好像在这
	return 0;
}

正解的改法就是在第一次的时候让每个盘子先放上一个，苹果数变为苹果数减盘子数，搞定！

#题解 数的划分