赞
踩
这道题本来很容易的,就是一次全排列然后检查而已。
- public class Test3
- {
- static int kinds=0;
- static int b[]=new int[10];
- static boolean vis[]=new boolean[10];
- public static void main(String[] args)
- {
- int a[]=new int[]{0,1,1,1,2,2,2,3,3,3};
- dfs(1,a);
- System.out.println("kinds:"+kinds);
- }
- static void dfs(int start,int a[])
- {
- if(start==a.length)
- {
- kinds++;
- }
- else
- {
- for(int i=1;i<a.length;i++)
- {
- if(!vis[i])//未上坐
- {
- b[start]=a[i];
- if(start>2 && b[start-2]==b[start-1] && b[start-1]==b[start])
- continue;//边排边检查提高效率
- vis[i]=true;
- dfs(start+1,a);
- vis[i]=false;
- }
- }
- }
- }
- }
- //kinds:283824
-
一不小心以为不可以重复,一个同学给我指出来了,来自同一个国家,但个体可以不同,所以序列是可以重复的。如果要求序列也不重复的话,问题就会复杂些了。
下面是代码。
- /**
- * 和上一篇的售票员卖车票很相似
- * 因为有3国人 所以结果必然是3的倍数。
- * 可以使第一个座位是A。这样程序就能快3倍了。
- * 采用回溯,边排边测试,提高效率。
- */
- import java.util.Arrays;
-
-
- public class Test4
- {
- static int kinds=0;
- static int a[]=new int[4];
- static int b[]=new int[4];
- static int c[]=new int[4];
- static int aim[]=new int[10];
- public static void main(String[] args)
- {
- // aim[1]=1;
- Arrays.fill(a,1);
- Arrays.fill(b,2);
- Arrays.fill(c,3);
- // dfs(2,2,3,3);
- dfs(1,3,3,3);
- System.out.println("kinds:"+kinds);
- }
- static void dfs(int start,int a,int b,int c)
- {
- if(start==10)
- {
- kinds++;
- // for(int i=1;i<start;i++)
- // {
- // System.out.printf("%c",(aim[i]+64));
- // }
- // System.out.println();
- }
- else if(start<3)//肯定不会出现三个座来自国家相同的,因为就两座位。
- {
- aim[start]=1;
- a--;
- dfs(start+1,a,b,c);
- a++;
-
- aim[start]=2;
- b--;
- dfs(start+1,a,b,c);
- b++;
-
- aim[start]=3;
- c--;
- dfs(start+1,a,b,c);
- c++;
- }
- else
- {
- aim[start]=1;
- if(!(aim[start-2]==aim[start-1] && aim[start-1]==aim[start]) && a>0)//不是3连号,且A国家还有人未上坐
- {
- a--;
- dfs(start+1,a,b,c);
- a++;
- }
-
- aim[start]=2;
- if(!(aim[start-2]==aim[start-1] && aim[start-1]==aim[start]) && b>0)//同理
- {
- b--;
- dfs(start+1,a,b,c);
- b++;
- }
-
- aim[start]=3;
- if(!(aim[start-2]==aim[start-1] && aim[start-1]==aim[start]) && c>0)//同理
- {
- c--;
- dfs(start+1,a,b,c);
- c++;
- }
- }
- }
- }
- //计算是1314.好巧的数字啊
-
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。