在写这篇文章之前，xxx已经写过了几篇关于改检查class主题的文章,想要了解的朋友可以去翻一下之前的文章
/* 排坐位
要安排：3个A国人，3个B国人，3个C国人坐成一排。
要求不能使连续的3个人是同一个国籍。
求所有不同方案的总数？
*/
/*public class 排坐位 {
public static char[] c = {'A','A','A','B','B','B','C','C','C'};
public static int kinds= 0; // 不同方案总个数
// 检查是不是有同一国人连续3个
public static boolean check(char[] c){
int count = 1; // 初始个数
for(int i=0;i<c.length-1;i++){
if(c[i]==c[i+1]){
count++;
}else{
count = 1; // 初始个数
}
if(count>=3) return true;
}
return false;
}
// 全排列
public static void f(char[] c,int start,int end){
if(start == end){
if(!check(c)){ // 检查是不是有同一国人连续3个
kinds++; // 不同方案总个数加1
}
return ;
}else{
for(int i=start;i<=end;i++){
char temp = c[i];
c[i] = c[start];
c[start] = temp;
f(c,start+1,end); // 递归
temp = c[i];
c[i] = c[start];
c[start] = temp;
}
}
}
public static void main(String[] args){
f(c,0,c.length-1); // 全排列
System.out.println("kinds:"+kinds);
}
}
*/
方法二
public class 排坐位
{
public static int kinds=0;
public static int b[]=new int[9];
public static boolean vis[]=new boolean[9];
public static int a[]=new int[]{1,1,1,2,2,2,3,3,3};
static void dfs(int start,int end)
{
if(start==end)
{
kinds++;
}
else
{
for(int i=0;i<a.length;i++)
{
if(!vis[i])//未上坐
{
b[start]=a[i];
if(start>1 && b[start-2]==b[start-1] && b[start-1]==b[start])
continue;//边排边检查进步效率
vis[i]=true;
dfs(start+1,end);
vis[i]=false;
}
}
}
}
public static void main(String[] args)
{
dfs(0,a.length);
System.out.println("kinds:"+kinds);
}
}
运行结果：
kinds:283824
扩展：
如果每个国度的三个人是可重复的，即来自同一个国度的三个人是不辨别的，所以序列是可以重复的。
程序如下：
import java.util.Arrays;
public class 排坐位
{
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)
{
Arrays.fill(a,1);
Arrays.fill(b,2);
Arrays.fill(c,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++;
}
}
}
}
运行结果为（部份结果）：
CCBBAABCA
CCBBAACAB
CCBBAACBA
CCBBABAAC
CCBBABACA
CCBBABCAA
CCBBACAAB
CCBBACABA
CCBBACBAA
CCBBCAABA
CCBBCABAA
CCBCAABAB
CCBCAABBA
CCBCABAAB
CCBCABABA
CCBCABBAA
CCBCBAABA
CCBCBABAA
kinds:1314
文章结束给大家分享下程序员的一些笑话语录： 乔布斯：怎么样还是咱安全吧！黑客：你的浏览器支持国内网银吗？苹果可以玩国内的网游吗乔布斯：......不可以黑客：那我研究你的漏洞干嘛，我也需要买奶粉！
---------------------------------
原创文章 By
检查和class
---------------------------------