<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拍精品青青草原| 亚洲精品蜜夜内射| 亚洲午夜成人精品电影在线观看 | a级精品九九九大片免费看| 亚洲丝袜美腿视频| 国产午夜免费秋霞影院| 精品国产麻豆免费人成网站| 国产亚洲精品成人AA片| 亚洲熟妇无码AV在线播放| 福利免费观看午夜体检区| 一二三区免费视频| 亚洲AV无码乱码麻豆精品国产| 亚洲国产精品嫩草影院久久| jjizz全部免费看片| 无遮挡国产高潮视频免费观看| 亚洲最大的成网4438| 亚洲JIZZJIZZ中国少妇中文| 91久久精品国产免费直播| 免费无码国产在线观国内自拍中文字幕| 亚洲人成网www| 亚洲人成网站在线观看青青| 免费三级毛片电影片| 91福利免费网站在线观看| 黑人粗长大战亚洲女2021国产精品成人免费视频 | 国产精品免费福利久久| 国产综合成人亚洲区| 亚洲国产精品专区| 亚洲AV无码乱码国产麻豆| 成人伊人亚洲人综合网站222| 999国内精品永久免费观看| 91视频免费观看高清观看完整| 亚洲AV无码成人精品区日韩| 亚洲第一页中文字幕| 亚洲欧洲成人精品香蕉网| 亚洲精品无码久久久| 国产禁女女网站免费看| 成人免费毛片内射美女APP| 亚洲免费中文字幕| 日本xxxx色视频在线观看免费| 国产高清视频免费在线观看|