不一样放牌游戏

题目1（整数拆分）

将一个正整数N分解成几个正整数相加，可以有多种分解方法，
例如7=6+1，7=5+2，7=5+1+1，...编程求出正整数N的所有整数分解式子。

输入格式：
每个输入包含一个测试用例，即正整数N (0<N≤30)。

输出格式：
按递增顺序输出N的所有整数分解式子。
递增顺序是指：对于两个分解序列N1={n1,n2,⋯}和N2={m1,m2,⋯}，
若存在i使得n1=m1,⋯,ni=mi，但是n(i+1)<m(i+1),则N1序列必定在N​2序列之前输出。
每个式子由小到大相加，式子间用分号隔开，且每输出4个式子后换行。

输入样例：
7
输出样例：
7=1+1+1+1+1+1+1;7=1+1+1+1+1+2;7=1+1+1+1+3;7=1+1+1+2+2
7=1+1+1+4;7=1+1+2+3;7=1+1+5;7=1+2+2+2
7=1+2+4;7=1+3+3;7=1+6;7=2+2+3
7=2+5;7=3+4;7=7

代码1：（n如果过百就可能超时）

#include "stdio.h"
int n,sum,ans;
int a[100];
void dfs(int step,int x)
{//step代表站在第几个盒子面前，x代表当前的放的最小数 
	int i;
	if(sum==n)//如果此刻相等，那么此刻盒子里未放东西 
	{
		printf("%d=",n);
		for(i=1;i<=step-1;i++)
			if(i==1)
				printf("%d",a[i]);
			else
				printf("+%d",a[i]);
		ans++;
		if(ans%4==0)
			printf("\n");
		else
		{
			if(step!=2)
				printf(";");
		}
		return;
	}
	else if(sum>n)
	return;
	for(i=x;i<=n;i++)//每次放的数都必须>=上一次的数
	{ 
		a[step]=i;
		sum+=a[step];
		dfs(step+1,i);
		sum-=a[step];//此刻盒子里的数要取出来放别的数 
	}
	return; 
}
int main()
{
	while(~scanf("%d",&n)){
		sum=0;ans=0;
		dfs(1,1);//站在第一个盒子面前，准备放1 
	}
	return 0;
}

题目2：（相对题目1增添了条件）

将整数n分成k份，且每份不能为空，问有多少种不同的分法。
当n=7,k=3时，下面三种分法被认为是相同的：
（1，1，5），（1，5，1），（5，1，1）

输入描述:
一行两个数n,m。（6<=n<=200，2<=m<=6）

输出描述:
一行一个整数，即不同的分法数。

代码2：（注意其中的改动，比上一个代码省大量的时间）
当然如果用动态规划来写，更节约时间

/*
将整数n分成k份，相当于我手上有着许多张（1-n）的牌
我需要取任意三张牌分别放到三个盒子里面，且需要避免重复 
*/
#include<stdio.h>
int a[10];//用来放置拆分后的数字 
int n,m,ans,sum;
void dfs(int step,int x)
{//step表示此刻站在第几个的盒子面前 
	if(sum>n)//如果已经超过的n，接下来的盒子肯定没有办法放牌了 
		return; 
	//我们走到m个盒子面前，因为这是最后一个要放的盒子，
	所以我们没有必要非要再往里面放牌了，
	我们判定将要放的牌是否可以放到盒子里面即可，
	这样可以少往后搜一次，自然可以大量节约时间 
	if(step==m)
	{
		if(n-sum>=x)//判定第m个盒子可以放>=x的牌不，这是一种放法 
			ans++;
		return; 
	}
	int i; 
	for(i=x;i<=(n-sum)/(m-step+1);i++)//牌按着从小到大排序，这样可有效的避免重复 
	{                                 //i的取值[x,(n-sum)/(m-step+1)];
		a[step]=i;                    //前step-1个盒子已放好，剩下的盒子数为(m-step+1)
		sum+=i;                       //此刻sum表示已放好的值，n剩下的为(n-sum)
		dfs(step+1,i);
		sum-=i;
	}
	return ;
}
int main()
{
	ans=0;sum=0; 
	scanf("%d %d",&n,&m);
	dfs(1,1);//站在第一个盒子面前我准备放1 
	printf("%d\n",ans); 
	return 0;
} 

题目3：（相对题目2又增添了条件）

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，
问共有多少种不同的分法？（用K表示）
5，1，1和1，5，1 是同一种分法。

Input
第一行是测试数据的数目t（0 <= t <= 20）。
以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。

Output
对输入的每组数据M和N，用一行输出相应的K。

Sample Input
1
7 3

Sample Output
8

代码3（n也不能太大）：（可以用的动态规划来写，省时）

苹果数是一个整数，拆分放到盘子里面
相当于整数拆分，只是这里可以有空盘子 

#include<stdio.h>
int a[10];//用来放置拆分后的数字 
int n,m,ans,sum;
void dfs(int step,int x)
{
	if(sum>n)
		return; 
	if(sum==n)//只要盘子不用多，少用盘子我们也可以算一中放法 
	{
		ans++;
		return;
	}
	if(step==m+1)//没有（m+1）个盘子，因此不可能放苹果 
		return;
	int i;           //这里必须是n，因为没有办法判定会放到多少个盘子里 
	for(i=x;i<=n;i++)//牌按着从小到大排序，这样可有效的避免重复 
	{                               
		a[step]=i;
		sum+=i;
		dfs(step+1,i);
		sum-=i;
	}
	return ;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		ans=0;sum=0; 
		scanf("%d %d",&n,&m);
		dfs(1,1);//站在第一个盘子面前放1，不是说有的盘子可以不放吗，请看上面	dfs（if(step>m+1)） 
		printf("%d\n",ans); 
	}
	return 0;
} 

题目4：（放牌，相比全排列难了一些）

题目描述

小明被劫持到X赌城，*与其他3人玩牌。 
一副扑克牌（去掉大小王牌，共52张），均匀发给4个人，每个人13张。 
这时，小明脑子里突然冒出一个问题： 
如果不考虑花色，只考虑点数，也不考虑自己得到的牌的先后顺序 
自己手里能拿到的初始牌型组合一共有多少种呢？ 

输出

请输出该整数，不要输出任何多余的内容或说明文字。

代码4：

/*
分析：
方法1：深搜

题上说了，不考虑花色，那么题意就变为：13种牌，每种牌各有4张一样的
题上又说，不考虑取牌的顺序，那么我们就没有必要一张一张的取牌了，
我们可以一次拿多	张，也不可以不拿，可以多拿几次，也可以少拿几次

这里为了我们取牌方便，我们把同一种类的放在一块，那么就变成了13堆，
当我们站在不同的堆面前，我们可以拿0或1或2或3或4张，然后继续去下一堆拿牌
当我们恰好拿够13张时，我们就可以ans+1了，之后返回，
然后再把我们最后一次拿的牌放回去，看看是否可以继续选择别的种类的牌，
这样的话，其实就是深搜返回的过程了

方法2：暴力
还可以13层for循环（i=0;i<=4;i++）
满足条件i+j+k+l+m+l+n+o+p+q+r+s+t==13
*/
#include<stdio.h>
int ans;
void dfs(int step,int sum)
{//step表示第几堆，sum表示手中的牌数
    if(step==14)//不存在第14堆
        return ;
    int i;
    for(i=0;i<=4;i++)
    {
    	sum+=i;//一次性在x堆拿i张牌
    	
  	 	//如果在该堆取i张恰好达到13张，就可以直接返回了，
    	因为如果再去取i++，牌数一定会大于13的，牌数永远不会超过13张，
    	这样也节省了时间
  		if(sum==13)
    	{
     		 ans++;
      	 	 return;
   	 	}
 		dfs(step+1,sum);//去下一堆
		sum-=i;//把i张牌再放回去,选择再去拿i+1张牌
	}
   		return;
}
int main()
{
  ans=0;
  dfs(1,0);//站在第一堆面前，起初手中为0张牌
  printf("%d\n",ans);
  return 0;
}

本文地址：https://blog.csdn.net/Helinshan/article/details/109258127