黑马程序员技术交流社区
标题:
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-28 13:51
标题:
回复 地板 的帖子
嗯 你这个不对，所谓匹配就是有括号就要对应的括回。。你再加个几个条件语句就哦拉
作者:
匿名
时间:
2011-7-28 13:55
标题:
回复 地板 的帖子
给个提示就是0后面必须对应一个1 ，这个1的位置不确定。但是必须在0后
比如你的00011011就不对，则个0可以放在00011101这样就是匹配。。
懂了吗 改一下 就这个程序就哦了
作者:
匿名
时间:
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 11:02
回15楼：原有字符串最开始肯定是空，进行递规操作，对原字符串进行任意位置插入（所有位置都要遍历一次）…肯定有重复，生成结果放入set中。
作者:
匿名
时间:
2011-7-29 11:07
因为插入的时候是按"()"插入的，生成结果肯定符合，剩下工作就是对字符串的的所有位置进行遍历插入
作者:
王松朝
时间:
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 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