<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)

    隨筆分類

    隨筆檔案

    文章分類

    文章檔案

    搜索

    •  

    最新評論

    閱讀排行榜

    評論排行榜

    主站蜘蛛池模板: 亚洲VA综合VA国产产VA中| 亚洲女人初试黑人巨高清| 77777亚洲午夜久久多人| 国产成人无码综合亚洲日韩| 亚洲gv白嫩小受在线观看| 亚洲视频欧洲视频| 亚洲欧美日韩一区二区三区在线 | 亚洲情XO亚洲色XO无码| 国产亚洲3p无码一区二区| 亚洲国产精品成人综合久久久 | 国产亚洲成归v人片在线观看 | 91免费国产在线观看| 免费网站看v片在线香蕉| 国产亚洲精品激情都市| 亚洲国产精品综合久久网各| 美女免费视频一区二区三区| 无码人妻精品中文字幕免费| 免费高清av一区二区三区| 亚洲日韩精品无码一区二区三区 | 国产亚洲精品不卡在线| 亚洲国产精品成人综合色在线婷婷| 自拍偷自拍亚洲精品偷一| 日韩精品免费视频| 波多野结衣久久高清免费 | 男的把j放进女人下面视频免费| 在线免费一区二区| 久久久久亚洲精品影视| 免费高清A级毛片在线播放| 国产成人精品免费视频网页大全| 免费亚洲视频在线观看| 亚洲三级在线播放| 波多野结衣免费一区视频| 国产免费爽爽视频免费可以看| 亚洲AV日韩AV永久无码久久| 一级中文字幕免费乱码专区| 亚洲欧洲免费无码| 亚洲天堂久久精品| APP在线免费观看视频| 亚洲国产精品狼友中文久久久| 亚洲精品一二三区| 久久精品国产免费观看三人同眠|