<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

    posts - 73,  comments - 55,  trackbacks - 0
    /*
    ?*?原題如下:用1、2、2、3、4、6這六個數字,用java寫一個main函數,打印出所有不同的排列,
    ?*?如:612234、412346等,要求:"4"不能在第三位,"3"與"6"不能相連.?
    ?*?
    ?*?1?把問題歸結為圖結構的遍歷問題。實際上6個數字就是六個結點,把六個結點連接成無向連通圖,對于每一個結點求這個圖形的遍歷路徑,
    ?*?所有結點的遍歷路徑就是最后對這6個數字的排列組合結果集。?
    ?*?2?顯然這個結果集還未達到題目的要求。從以下幾個方面考慮:?
    ?*?1.?3,6不能相連:實際要求這個連通圖的結點3,5之間不能連通,?可在構造圖結構時就滿足改條件,然后再遍歷圖。?
    ?*?2.?不能有重復:?考慮到有兩個2,明顯會存在重復結果,可以把結果集放在TreeSet中過濾重復結果?
    ?*?3.?4不能在第三位:?仍舊在結果集中去除滿足此條件的結果。
    ?
    */


    import ?java.util.Iterator;
    import ?java.util.TreeSet;

    public ? class ?Test? {

    ?
    private ?String[]?b? = ? new ?String[]? {? " 1 " ,? " 2 " ,? " 2 " ,? " 3 " ,? " 4 " ,? " 6 " ?} ;

    ?
    private ? int ?n? = ?b.length;

    ?
    private ? boolean []?visited? = ? new ? boolean [n];

    ?
    private ? int [][]?a? = ? new ? int [n][n];

    ?
    private ?String?result? = ? "" ;

    ?
    private ?TreeSet?set? = ? new ?TreeSet();

    ?
    public ? static ? void ?main(String[]?args)? {
    ??
    new ?Test().start();
    ?}


    ?
    private ? void ?start()? {

    ??
    // ?Initial?the?map?a[][]
    ?? for ?( int ?i? = ? 0 ;?i? < ?n;?i ++ )? {
    ???
    for ?( int ?j? = ? 0 ;?j? < ?n;?j ++ )? {
    ????
    if ?(i? == ?j)? {
    ?????a[i][j]?
    = ? 0 ;
    ????}
    ? else ? {
    ?????a[i][j]?
    = ? 1 ;
    ????}

    ???}

    ??}


    ??
    // ?3?and?5?can?not?be?the?neighbor.
    ??a[ 3 ][ 5 ]? = ? 0 ;
    ??a[
    5 ][ 3 ]? = ? 0 ;

    ??
    // ?Begin?to?depth?search.
    ?? for ?( int ?i? = ? 0 ;?i? < ?n;?i ++ )? {
    ???
    this .depthFirstSearch(i);
    ??}


    ??
    // ?Print?result?treeset.
    ??Iterator?it? = ?set.iterator();
    ??
    while ?(it.hasNext())? {
    ???String?string?
    = ?(String)?it.next();
    ???System.out.println(string);
    ??}

    ?}


    ?
    private ? void ?depthFirstSearch( int ?startIndex)? {
    ??visited[startIndex]?
    = ? true ;
    ??result?
    = ?result? + ?b[startIndex];
    ??
    if ?(result.length()? == ?n)? {
    // ???"4"?can?not?be?the?third?position.
    ??? if ?(result.indexOf( " 4 " )? != ? 2 )? {
    // ????Filt?the?duplicate?value.
    ????set.add(result);
    ???}

    ??}

    ??
    for ?( int ?j? = ? 0 ;?j? < ?n;?j ++ )? {
    ???
    if ?(a[startIndex][j]? == ? 1 ? && ?visited[j]? == ? false )? {
    ????depthFirstSearch(j);
    ???}

    ??}


    ??
    // ?restore?the?result?value?and?visited?value?after?listing?a?node.
    ??result? = ?result.substring( 0 ,?result.length()? - ? 1 );
    ??visited[startIndex]?
    = ? false ;
    ?}

    }


    只要這樣定義圖,根本不用在代碼中寫IF ELSE語句。
    實際上基于圖的算法好處在于,只要你能定義好滿足題目要求的圖結構,遍歷的結果就是你要的結果,不用任何對遍歷結果做任何處理。包括本題中的:4不能在第三位置,3,5不能相連,唯一性要求,其實都可以在體現在構造的圖形結構里,然后直接遍歷圖取得自己要的結果。而不用再次處理結果集。只是說這里實際上對其它要求要體現在圖結構里有困難(理論上是可以的),但起碼3,5不能相接是很好構造的,就是上面的代碼段來解釋的。

    關于圖形數據結構建議先看看數據結構的書,主要是將如何利用二維數組描述圖結構,再看看圖的深度遍歷實現原理。最后再應用到這個問題上來,自然就不難明白了。

    posted on 2007-03-02 17:37 保爾任 閱讀(2377) 評論(0)  編輯  收藏 所屬分類: Arithmetic & Data Structure

    <2007年3月>
    25262728123
    45678910
    11121314151617
    18192021222324
    25262728293031
    1234567

    常用鏈接

    留言簿(4)

    隨筆分類

    隨筆檔案

    文章分類

    文章檔案

    搜索

    •  

    最新評論

    閱讀排行榜

    評論排行榜

    主站蜘蛛池模板: 久久天天躁狠狠躁夜夜免费观看| 一级毛片直播亚洲| 亚洲av永久无码| www.91亚洲| 香蕉免费一区二区三区| 亚洲精品无播放器在线播放 | 一级毛片在线免费视频| 亚洲AV无码成人精品区在线观看| 精品久久久久成人码免费动漫| 麻豆一区二区三区蜜桃免费| 久久精品国产亚洲AV网站| 成人毛片18女人毛片免费| 国产A∨免费精品视频| 亚洲精品一卡2卡3卡三卡四卡| 一本色道久久88亚洲综合| 最近中文字幕大全免费视频| 国产精品亚洲专区无码不卡| 亚洲视频在线观看视频| 亚洲成a人无码av波多野按摩 | 免费毛片在线看片免费丝瓜视频| WWW国产成人免费观看视频| 亚洲综合小说另类图片动图| 国产亚洲一区区二区在线| 成人毛片18女人毛片免费| 特级无码毛片免费视频尤物 | 国产成人亚洲合集青青草原精品 | 免费精品国偷自产在线在线| 在线视频网址免费播放| 亚洲AV无码男人的天堂| 久久久久久久亚洲Av无码| 亚洲男人的天堂一区二区| 99久久免费精品国产72精品九九| 国产午夜免费高清久久影院| 羞羞视频网站免费入口| 亚洲视频一区二区三区四区| 久久噜噜噜久久亚洲va久| 久久精品国产精品亚洲艾草网美妙| 女人让男人免费桶爽30分钟| 蜜臀AV免费一区二区三区| 在线观看免费无码专区| 一区二区三区免费在线视频 |