(广度优先搜索)打印所有可能的括号组合_JAVA_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > JAVA > (广度优先搜索)打印所有可能的括号组合

(广度优先搜索)打印所有可能的括号组合

 2014/11/20 13:40:26  MouseLearnJava  程序员俱乐部  我要评论(0)
  • 摘要:问题:给定一个正整n,作为括号的对数,输出所有括号可能的组合,如n=2(())()()n=3的情况((()))(()())(())()()(())()()()在之前的一篇文章中,我们采用了深度优先搜索的方式实现:(深度优先搜索)打印所有可能的括号组合本博文中,我们将给出采用广度优先搜索的方式实现,程序如下:publicclassParenthesesGenerator{publicvoidgenerateParentheses(intparenthesesCount){bfs(""
  • 标签:

?

问题:给定一个正整n,作为括号的对数,输出所有括号可能的组合,如
n=2
(())
()()

n = 3的情况
((()))
(()())
(())()
()(())
()()()

在之前的一篇文章中,我们采用了深度优先搜索的方式实现:(深度优先搜索)打印所有可能的括号组合

本博文中,我们将给出采用广度优先搜索的方式实现,程序如下:

class="java" name="code">public class ParenthesesGenerator {
 
    public void generateParentheses(int parenthesesCount) {
        bfs("", parenthesesCount, parenthesesCount);
    }
 
    /**
     * 采用深度搜索优先的方式 BFS(breadth-first search)
     *
     * @param currentParentheses
     * @param remanentLeftParenthesesRemain
     * @param remanentRightParenthesesRemain
     */
    private void bfs(String currentParentheses,
            int remanentLeftParenthesesRemain,
            int remanentRightParenthesesRemain) {
        /**
         * 如果左括号数和右括号数都为0的时候,表示已经找到一种解决方式, 直接输出结果
         */
        if (remanentLeftParenthesesRemain == 0
                && remanentRightParenthesesRemain == 0) {
            System.out.println(currentParentheses);
        }
 
        /**
         * 如果右括号剩余数大于左括号剩余数,则添加一个右括号,右括号剩余数减去1,然后递归调用自身
         */
        if (remanentRightParenthesesRemain > remanentLeftParenthesesRemain) {
            bfs(currentParentheses + ")", remanentLeftParenthesesRemain,
                    remanentRightParenthesesRemain - 1);
        }
 
        /**
         * 如果左括号数还有剩余,则将当前括号组成字符添加一个左括号, 然后递归调用本身
         */
        if (remanentLeftParenthesesRemain > 0) {
            bfs(currentParentheses + "(", remanentLeftParenthesesRemain - 1,
                    remanentRightParenthesesRemain);
        }
 
    }
}

?

测试程序及其结果如下

public class ParenthesesGeneratorTest {
    public static void main(String[] args) {
        ParenthesesGenerator test = new ParenthesesGenerator();
        for (int i = 1; i < 5; i++) {
            System.out.printf("有%d括号的所有组合:\n", i);
            test.generateParentheses(i);
        }
    }
}

?

有1括号的所有组合:
()
有2括号的所有组合:
()()
(())
有3括号的所有组合:
()()()
()(())
(())()
(()())
((()))
有4括号的所有组合:
()()()()
()()(())
()(())()
()(()())
()((()))
(())()()
(())(())
(()())()
(()()())
(()(()))
((()))()
((())())

原文地址 http://thecodesample.com/?p=954

更多代码实例请访问 http://thecodesample.com/

  • 相关文章
发表评论
用户名: 匿名