黑马程序员技术交流社区

标题: java 算法 [打印本页]

作者: 王丽 时间: 2011-7-27 13:09
标题: java 算法
这是一道笔试题，请大家帮解决一下，四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））

作者: 王松朝 时间: 2011-7-27 14:11
应该是8种吧,按2^3种,没算.

作者: 匿名 时间: 2011-7-27 14:21
（）（）（）（）
（）（）（（））          （（））（）（）
（）（（）（））          （（）（））（）
（）（（（）））          （（（）））（）
（（）（）（））
（（）（（）））          （（（））（））
（（（）（）））
（（（（））））

12种

作者: 匿名 时间: 2011-7-27 18:50
标题: 回复藤椅的帖子
敢问此楼，要是3000对括号，那有多少种啊？

作者: 匿名 时间: 2011-7-27 23:11
标题: 回复板凳的帖子
大哥大家都在等你的答案呢你都不解决没人能解决了

作者: 兰海忠 时间: 2011-7-28 13:41
女侠，你问的问题忒牛了。弄得我一个晚上都在想什么搞，以下是我求出的算法，我个人感觉是对的。但因为太难了我不敢保证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 编辑 ]

作者: 匿名 时间: 2011-7-28 13:51
标题: 回复地板的帖子
嗯你这个不对，所谓匹配就是有括号就要对应的括回。。你再加个几个条件语句就哦拉

作者: 匿名 时间: 2011-7-28 13:55
标题: 回复地板的帖子
给个提示就是0后面必须对应一个1 ，这个1的位置不确定。但是必须在0后

比如你的00011011就不对，则个0可以放在00011101这样就是匹配。。
懂了吗改一下就这个程序就哦了

作者: 匿名 时间: 2011-7-28 14:01
标题: 回复 8 # 的帖子
比如你的00011011就不对，对应的括号（（（））（））这样子不对吗？一个大括号包含两个小括号，两个小括号其中的一个又包含一个小括号。这样不对吗？

作者: 匿名 时间: 2011-7-28 14:20
标题: 回复 9 # 的帖子
也对啊不好意思是我错了

作者: 匿名 时间: 2011-7-29 04:44
标题: 感谢
题确实很难，很感谢大家的的帮忙

作者: 匿名 时间: 2011-7-29 09:28
标题: 回复 11 # 的帖子
是很难，又很麻烦的题。。。。老罗都笑话我了。。。我这个郁闷啊。。。
代码，我写不出来了，写代码的时候又想到新的东西了。。。我服了丽姐。。。

[img]http://hi.csdn.net/attachment/201107/29/6237444_1311902940fIFq.jpg[/img]

作者: 匿名 时间: 2011-7-29 09:45
我想提供一个算法思路是：把"()"做为一个字符串插入原来已有的字符串中，…。手机上网，无法代码…

作者: 匿名 时间: 2011-7-29 10:10
标题: 回复
别服我啊，我不会才问大家的。。。

作者: 匿名 时间: 2011-7-29 10:15
标题: 回复 13 # 的帖子
原有的字符串你是怎么得出来的，（）插入到原有字符串的时候，不能（。。。。。。）任意中间插入吗？？这题是我想复杂了吗？？？郁闷啊一上午，头都大了。怎么想也想不明白了

有没有想过即使得出一种方式但是这种方式的匹配也不值1种

看我画的图
[img]http://hi.csdn.net/attachment/201107/29/6237444_1311902940fIFq.jpg[/img]

作者: 王松朝 时间: 2011-7-29 10:27
想到一个思路,个人觉得应该可行:
N对括号就有 2N个位置标签,用递归每次取出两个位置标签(小位置方0…),作为一个对象放入SET集合(原素无法重复),集合的大小就是所有排列

作者: 王松朝 时间: 2011-7-29 10:37
my god！手机居然和电脑一样会自己帮人按键了!!!
现在打字更费劲了
将整个字符串作为对象,刚没说清楚.
就是太费CPU了

作者: 匿名 时间: 2011-7-29 10:55
:L  不好意思啊各位，代码中确实忽略了一些问题，条件2条件3都都列出来了没有在代码中添加条件3的判断以为没有必要呢，应该是条件2条件3同时满足才算匹配，看来我也有机会去编动车的程序啵！废话少说了在代码中添加下列条件。[code=java]//条件2条件3同时满足时候算匹配
                     for (int i = 0; i < s.length(); i++) {
                              if(s.charAt(i)=='0'){
                                    num++;
                              }else if(s.charAt(i)=='1'){
                                    num1++;
                              }
                              //根据条件3找到不成功的案例
                              if(num1>num){
                                    b=false;
                                    continue;
                              }
                     }
                     //如果没有找到不匹配的案例说明成功
                     if(b&&num==num1){
                              total++;
                              System.out.println(s);
                     }
                     nextnum+=2;////由条件6得出加权数是2
            }[/code]这段代码替换原来
从[code=java] //因为已经有条件3推出了最大值，所有下面不需要判断是否符合条件三了[/code]到[code=java] nextnum+=2;////由条件6得出加权数是2
            }[/code]
的代码
运行结果
[code=java]4组括号匹配的数列有
00001111
00010111
00011011
00011101
00100111
00101011
00101101
00110011
00110101
01000111
01001011
01001101
01010011
01010101
4组括号共有14个匹配的括号数列[/code]

大家看还有什么遗漏的地方提一下把这道题完成了就不玩这种丢人的事情了哦对了因为int型数组只能表示32位所以n最多只能是15（1<=n<=15）

作者: 匿名 时间: 2011-7-29 11:02
回15楼：原有字符串最开始肯定是空，进行递规操作，对原字符串进行任意位置插入（所有位置都要遍历一次）…肯定有重复，生成结果放入set中。

作者: 匿名 时间: 2011-7-29 11:07
因为插入的时候是按"()"插入的，生成结果肯定符合，剩下工作就是对字符串的的所有位置进行遍历插入

作者: 兰海忠 时间: 2011-7-29 11:18
标题: 回复 20 # 的帖子
有代码更有说服力，你这样不贴代码即使说得口水干了，对我这种IQ不高的人来说就是念天书，还是不知道什么搞

作者: 王松朝 时间: 2011-7-29 12:20
代码看起来更费劲吧,全是襄套的循环…

作者: 匿名 时间: 2011-7-29 12:36
public class Test{
/*
   * sum 共有sum中排序
   * M,N左右括号的个数
   */
private static int sum = 0;
private static final int M = 4;
private static final int N = 4;
public static void main(String[] args) {
fun(M,N);
System.out.println(sum);
}
/*
   * 判断这种排序是否成功
   * m,n 表示还剩余的左右括号的个数
   * 如果剩余的左括号比右括号多，说明先前的右括号比左括号多，那么这种排序就错误
   * 如果左右括号没了，那么这种排序正确，sum 加1
   */
private static boolean isRight(int m,int n) {
if(m-n>0){
return false;
}else if(m==0 ||n == 0){
sum += 1;
return false;
}
return true;
}
private static boolean fun(int m, int n) {
InsertLeft(m-1,n);
InsertRight(m,n-1);
return true;
}
//插入左括号
private static void InsertLeft(int m,int n) {
if(isRight(m,n)){
fun(m,n);
}
}
//插入右括号
private static void InsertRight(int m,int n) {
if(isRight(m,n)){
fun(m,n);
}
}
}
//14种排序方法

作者: 王松朝 时间: 2011-7-29 12:42
用java久了，都把二叉树给忘了,用二叉树貌似比较简单吧,code去

作者: 匿名 时间: 2011-7-29 12:59
标题: 回复板凳的帖子
要不你算一下3000对括号有多少种？
18对括号有477,638,700种，19对括号有1,767,263,190种

作者: 匿名 时间: 2011-7-29 13:18
回复21楼：我都声明了…没有网，手机上的

作者: 匿名 时间: 2011-7-29 13:38
标题: 回复 23 # 的帖子
牛逼赞一个

作者: 匿名 时间: 2011-7-29 21:30
忒幸亏了，终于弄出来了。
使用递归实现思路：
1. 都以最后一个括号为目标，用他的左括号在其他括号中间移动（关键的思想）
如（）（）（）（）可以在移成这样：
（）（）（（））
（）（（）（））
（（）（）（））
2. 由上面分析出要处理的有两部分别是：
第一部分：（）（）（（））....
第二部分：（）（（）（））、（（）（）（））.....
3. 最后就是每完成一次减1，直到只有一个括号为止。
下面看代码：[code=java]package com.itcast.test;

public class Recursion {

public static void main(String[] args) {
System.out.println(select(4));
}
/*
   * sum=1表示并排的括号如：（）；（）（）；（）（）（）
   */
public static int sum = 1;
public static int select(int num) {
if (num == 1) {
return sum;
}
// 括号的个数-1
/*
   * 假如num初始为4
   * （）（）（（））
   * （）（（）（））
   * （（）（）（））
   * 得到3个
   */
sum += --num;
/*
   * 假如num初始为4
   * （）（）|（（））
   * （（））|（（））
   * 处理|左边的
   * 得到1个
   */
for (int i = num - 1; i > 1; i--) {
select(num - 1);
}
/*
   * 假如num初始为4
   * （）（（）（））
   * （）（（（）））
   * 处理括号里面的
   */
for (int i = num; i > 1; i--) {
select(i);
}
// 每次减一个括号的递归调用
return select(num);
}
}[/code]代码简单，但是真的想得头都炸了，还望版主多多多多的支持啊:lol

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2