女侠，你问的问题忒牛了。弄得我一个晚上都在想什么搞，以下是我求出的算法，我个人感觉是对的。但因为太难了我不敢保证100%正确，期待大家一起来验证并提出改进建议，代码如下：[code=java]public class Test {
/**
* 功能：四对括号可以有多少种匹配排列方式？
* @param total匹配的个数
*/
/**
* 当我们用0表示左括号，1表示右括号时，发现
* 1、所有用符号法（0,1）表示的括号排列都是以0开头，以1结束，
* 2、所有用符号法（0,1）表示的括号排列中0和1的个数都相当即等于括号的个数
* 3、不是所有符合0 ,1个数相等的排列都是符合要求的，截止任意某个有1的位置，其前面的0的个数必须大于或者等于截止该位置时一的个数。
* 4、符号法（0,1）表示括号是数列的二进制数最小值是n个"0"加n个1，即01 0011 000111等；
* 5、根据条件3得出符号法（0,1）表示括号是数列的二进制数最大值是01 0101 010101 等方式；
* 6、交换数列的任意两个数字不相同的两位数，数列所对应的二进制数大小改变2的倍数
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
//fun(1);
int n=4;
System.out.println(n+"组括号匹配的数列有");
int total=fun(n);
System.out.println(n+"组括号共有"+total+"个匹配的括号数列");
}
//n表示括号的个数
public static int fun(int n){
if(n==1)
return 1;
/*
* 匹配二进制数最小值的数列
*/
String s1="";
String s2="";
for (int i = 0; i <n; i++) {
s1+="0";
s2+="1";
}
//得到数列的二进制数最小值的字符串
String minstr=s1+s2;
//得到数列的二进制数最小值对应的十进制数
int min=Integer.parseInt(minstr, 2);
/*
* 匹配二进制数最大值的数列
*/
//得到数列的二进制数最大值的字符串
String maxstr="";
for (int i = 0; i < n; i++) {
maxstr+="0"+"1";
}
//得到数列的二进制数最大值对应的十进制数
int max=Integer.parseInt(maxstr, 2);
System.out.println(minstr);
/*
* 现在开始算符合条件的数列个数
*/
int total=0;
//最大最小都是他本身
if(max==min)return 1;
//最大最小都不是他本身
if(max!=min) total=2;//最大最小分别表示一个，
int nextnum=min+2;//由条件6得出加权数是2
//看看 两数之间是否还有匹配的数列
while (nextnum<max) {
String s=Integer.toBinaryString(nextnum);
String sub="";
//给二进制数补位
for (int i = 0; i < 2*n-s.length(); i++) {
sub+="0";
}
s=sub+s;
int num=0;//临时变量看0的个数是否等于n
//因为已经有条件3推出了最大值，所有下面不需要判断是否符合条件三了
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i)=='0'){
num++;
}
}
if(num==n){
total++;
System.out.println(s);
}
nextnum+=2;////由条件6得出加权数是2
}
System.out.println(maxstr);
return total;
}
}[/code]
运行结果
[code=java]4组括号匹配的数列有
00001111
00010111
00011011
00011101
00100111
00101011
00101101
00110011
00110101
00111001
01000111
01001011
01001101
01010011
01010101
4组括号共有15个匹配的括号数列[/code]
[ 本帖最后由 兰海忠 于 2011-07-28 13:44 编辑 ] |
收藏
淘帖
踩
