1. 数字分解
【问题描述】
任何一个大于1的自然数n,总可以拆分成若干个小于n的自然数之和，当n等于5时有6种拆分方法：
5=1+1+1+1+1
5=1+1+1+2
5=1+1+3
5=1+2+2
5=1+4
5=2+3
输入：一行包含一个正整数n（1<n<10）。
输出：先将拆分方案输出，然后再输出拆分的方案数。
【输入样例】
5
【输出样例】
5=1+1+1+1+1
5=1+1+1+2
5=1+1+3
5=1+2+2
5=1+4
5=2+3
total=6
#include <iostream>
using namespace std;
int a[] = {},n,total; //输出函数
void print(int t) { //拆成t项
cout << n << "=";
for(int i = ; i <= t-; i++) {
cout << a[i] << "+";
}
cout << a[t] << endl;
total++;
} void find(int m,int t) {
for(int i = a[t-]; i<=m; i++) {
if(i < n) {
a[t] = i; //保存当前拆分的i
m-=i;
if(m ==) { //拆分结束，输出结果
print(t);
} else {
find(m,t+);
}
m+=i; //回溯：加上拆分的数，以便产生所有可能的拆分
}
}
}
int main() {
cin >> n;
find(n,);
cout << "total=" <<total << endl;
return ;
}
2.放苹果
【问题描述】
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
输入：第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
输出：对输入的每组数据M和N，用一行输出相应的K。
【输入样例】
1
7 3
【输出样例】
8
/*
m个苹果放在n个盘子中，那么定义函数为apple(m,n)： 1.m=0，没有苹果，那么只有一种放法，即apple(0,n)=1 2.n=1，只有一个盘中，不论有或者无苹果，那么只有一种放法，apple(m,1)=1 3.n>m，和m个苹果放在m个盘子中是一样的，即apple(m,n)=apple(m,m) 4.m>=n，这时分为两种情况，一是所有盘子都有苹果，二是不是所有盘子都有苹果。
不是所有盘子都有苹果和至少有一个盘子空着是一样的，即=apple(m,n-1)。所
有盘子都有苹果，也就是至少每个盘子有一个苹果，m个苹果中的n个放在n个盘子中，
剩下的m-n个苹果，这和m-n个苹果放在n个盘子中是是一样的，即=apple(m-n, n)。
这时，apple(m,n)=apple(m-n, n)+apple(m,n-1)。
*/
#include<iostream>
using namespace std;
int apple(int m,int n) { //m个苹果放到n个盘子里
if(m < || n <){
return ;
}
//判断只有一个方法放苹果的情况
if(m== || n==){
return ;
}
//否则判断苹果数是否少于盘子数，如果少，那么肯定有n-m个空盘子
//所以只要做把m个苹果放到m个盘子里
else if(m<n) {
return apple(m,m);
}
//m>=n的情况 :
//所有的盘子都有苹果，即只要把m-n个苹果放到n个盘子里
//不是所有盘子都有苹果和至少有一个盘子空着是一样的，即=apple(m,n-1)
else {
return apple(m-n,n)+apple(m,n-);
} }
int main() {
int t;
cin>>t;
while(t--) {
int m,n;
cin>>m>>n;
cout<<apple(m,n)<<endl;
}
}
1．全排列
【问题描述】
输入一个数字N（1<N<10），输出所有使用1到N数字组成的N位数(每个数字只能使用一次)。
【样例输入】
3
【样例输出】
123
132
213
231
312
321
#include <iostream>
using namespace std;
int a[],book[],n; //站在第step个盒子面前
void dfs(int step){
int i;
if(step == n+){
//输出一种全排列
for(i = ;i<=n;i++){
cout << a[i];
}
cout << endl;
return; //返回之前的一步，最近一次调用dfs函数的地方
} //站在第step个盒子面前， 遍历1到n一一去尝试
for(i = ;i <= n;i++){
//判断该数字是否还未被使用
if(book[i] == ){
a[step] = i;
book[i] = ;//表示已被使用 //接下里走到step+1的盒子面前，做同样的操作
dfs(step+);
book[i]=;//一定要将刚才尝试的数字收回，才能进行下一次的尝试
}
} return;
}
int main(){
cin >> n;
dfs();
return ;
}
2.分为互质组
【问题描述】
给定n个正整数，将他们分组，使得每组中任意两个数互质。至少要分成多少个组？
输入：第一行是一个正整数n，1<=n<=10;第二行是n个不大于10000的正整数。
输出：一个正整数，即最少需要的组数。
【输入样例】
6
14 20 33 117 143 175
【输出样例】
3
#include <iostream>
using namespace std;
int a[],b[],n;
int ans;
//定义gcd函数求两个数的最大公约数
int gcd(int a,int b) {
if(b==) {
return a;
} else {
return gcd(b,a%b);
}
}
void dfs(int x,int y) { //x：第几个数 y:已有多少组
//递归终止条件
if(x>n) {
ans = y;
return;
}
bool flag = false;
//判断当前值是否是属于已有组
for(int i = ; i <=y; i++) {
bool pd = true;
for(int j = ; j < x; j++) {
//第j个元素属于第i组，并且第x个元素与第j个元素不是互为质数，则a[x]不属于第i组
if(b[j] == i && gcd(a[x],a[j]) != ) {
pd = false;
break;
}
}
if(pd == true) { //第x个元素与第i组的所有元素都互为质数
flag = true;
//第x个元素属于第i组
b[x] = i;
//接着判断下一个元素(第x+1个元素)是否属于已有的y组
dfs(x+,y);
//将b[x]重新赋值为0
b[x]=;
}
}
if(flag == false) {
//如果当前值不属于已有的任何一组 需要新开一个组别
//第x个元素属于第y+1组
b[x] = y+;
//接着判断下一个元素(第x+1个元素)是否属于已有的y+1组
dfs(x+,y+);
b[x] = ;
}
}
int main() {
cin >> n;
for(int i = ; i <=n; i++) {
cin >> a[i];
}
//初始化b数组，第1个元素属于第1组
b[] = ;
dfs(,);
cout << ans << endl;
return ;
}