不一样放牌游戏

  • 时间:
  • 来源:互联网
  • 文章标签:

题目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;
}

本文链接http://www.taodudu.cc/news/show-1781850.html