青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

SmartPtr
本博客已搬至:http://www.cnblogs.com/baiyanhuang/
posts - 29,comments - 176,trackbacks - 0
By SmartPtr(http://m.shnenglu.com/SmartPtr/)

給出1, 2, 3, 4四個數, 請編程輸出其全排列, 如:
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
...
這樣的題, 我們在學校的時候一般都遇到過,而我們最先能想到的,應該就是遞歸實現了,因為這和我們我理解的數學中的排列組合比較一致:先取第一個數,有4種可能,再在剩下的3個數種取出第二個數,這又有3種可能,這樣下去直到取到最后一個數。 這樣,4個數的全排列就有4*3*2 = 24個。n個數的全排列就是n*(n-1)*(n-2)*...*2*1. 按照這個描述, 我們發現有兩點在程序中遞歸實現時十分重要:
1. 哪些數已經取過了而哪些數又是沒有取過,可以用的?
2. 現在取的是哪一個數。
確保了這兩個信息,我們的遞歸實現就沒有什么問題了。對于第一個問題,我們有兩種方法可以實現:
1) 用一個對應的bool型數組來記錄被排列數組的使用狀態,這個狀態在遞歸過程中需要回溯
2) 用一個ILLEGAL值來表示不是屬于排序的數,排列數組中的數一旦被使用,就用這個值來覆蓋,當然,遞歸過程中此值也需要回溯。
同樣,現在取得是哪個數,我們也有兩種方法來表示:
1) 用參數的方式來表明這次遞歸調用是為了得第幾個值、
2) 用一個靜態變量來表示當前遞歸的深度,此深度值表明了我當前取的是哪個數。

上面兩點的兩種解決方法排列組合一下:),我們就有4種方法

首先是定義最大數組長度與非法值

#define N 10
#define ILLEAGALNUM  -100

下面列出每一種實現:

//數組存使用狀態,調用深度表示取第幾個數
void Permutation1(int a[], int n)
{
    
static int out[N]; // result array
    static bool m[N] = {1,1,1,1,1,1,1,1,1,1}; // mark array, indicate whether the coorespond element 
                                              
//in array a is already used.
    static int depth = -1;                      //recursive call depth.
    depth++;
    
for(int i = 0; i < n; ++i)
    {
        
if(depth == n)                      // if we already get the last num, print it
        {
            
static int l = 1;
            printf(
"%3d: ", l++);
            
for(int k = 0; k<n; k++) printf("%d "out[k]);
            printf(
" ");
            depth
--;
            
return;
        }
        
else if(true == m[i])                      // if element i not used
        {
            
out[depth] = a[i];
            m[i] 
= false;                      // mark element i as used
            Permutation1(a, n);                      // recursive to get next num
            m[i] = true;                      // backdate , so that we can try another case
        }
    }
    depth
--;
}

//修改數據數組表示其使用狀態,參數表示取第幾個數
void Permutation2(int a[], int index, int n)
{
    
static int out[N];
    
for(int i = 0; i < n; ++i)
    {
        
if(index == n)                      //index > n-1, try to get the n-1 num, means it is ok , printf it
        {
            
static int l = 1;
            printf(
"%3d: ", l++);
            
for(int k = 0; k<n; k++) printf("%d "out[k]);
            printf(
" ");
            
return;
        }
        
else if(a[i] != ILLEAGALNUM)
        {
            
out[index] = a[i];
            a[i] 
= ILLEAGALNUM;
            Permutation2(a, index
+1, n);
            a[i] 
= out[index];
        }
    }
}

//修改數據數組表示其使用狀態,調用深度表示取第幾個數
void Permutation3(int a[], int n)
{
    
static int out[N];
    
static int depth = -1;                      //recursive call depth.
    depth++;
    
for(int i = 0; i < n; ++i)
    {
        
if(depth == n)                      //index > n-1, try to get the n-1 num, means it is ok , printf it
        {
            
static int l = 1;
            printf(
"%3d: ", l++);
            
for(int k = 0; k<n; k++) printf("%d "out[k]);
            printf(
" ");
            depth
--;
            
return;
        }
        
else if(a[i] != ILLEAGALNUM)
        {
            
out[depth] = a[i];
            a[i] 
= ILLEAGALNUM;
            Permutation3(a, n);
            a[i] 
= out[depth];
        }
    }
    depth
--;
}


//額外的數組表示其使用狀態,參數表示取第幾個數
void Permutation4(int a[], int index, int n)
{
    
static int out[N]; // result array
    static bool m[N] = {1,1,1,1,1,1,1,1,1,1}; // mark array, indicate whether the coorespond element 
                                              
//in array a is already used.
    for(int i = 0; i < n; ++i)
    {
        
if(index == n)                      // if we already get the last num, print it
        {
            
static int l = 1;
            printf(
"%3d: ", l++);
            
for(int k = 0; k<n; k++) printf("%d "out[k]);
            printf(
" ");
            
return;
        }
        
else if(true == m[i])                      // if element i not used
        {
            
out[index] = a[i];
            m[i] 
= false;                      // mark element i as used
            Permutation4(a, index+1, n);                      // recursive to get next num
            m[i] = true;                      // backdate , so that we can try another case
        }
    }
}

 

雖然對于這樣的問題效率與空間相差不會特別明顯,但是我們還是來比較一下來找出最佳的一個。對于數組使用狀態的保存,顯然,用第一個方案需要動用一個額外的數組,而并沒有提高效率,所以我們應該采用第二個方案:修改數組值的方法。對于當前取的是哪個數,如果我們用傳參數的方式,因為在排列過程中,這個遞歸函數被調用的次數是非常多的。(6個數的全排列就要調用1957次),這樣多一個參數, 其每次調用壓棧出棧的消耗就顯得比較大了, 所以我們推薦用調用深度來表示。


經過上面的討論, Permutation3就是我們的最佳選擇。



posted on 2007-08-26 20:45 SmartPtr 閱讀(786) 評論(0)  編輯 收藏 引用
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            国产日韩欧美精品在线| 国产欧美日韩不卡| 亚洲人午夜精品| 欧美国产日韩在线| 免费观看在线综合| 亚洲视频999| 亚洲一区二区免费| 韩国久久久久| 欧美国产欧美亚洲国产日韩mv天天看完整 | 国产日韩三区| 欧美aⅴ一区二区三区视频| 蜜臀99久久精品久久久久久软件| 亚洲免费激情| 亚洲无线观看| 伊人久久婷婷色综合98网| 亚洲国产合集| 国产精品毛片| 欧美国产日韩一二三区| 欧美视频一区二区三区| 久久久亚洲高清| 欧美激情一区二区久久久| 午夜精品视频网站| 巨乳诱惑日韩免费av| 亚洲视频在线观看| 久久免费视频这里只有精品| 一区电影在线观看| 新片速递亚洲合集欧美合集| 亚洲精品在线三区| 欧美主播一区二区三区美女 久久精品人| 亚洲第一在线视频| 亚洲色图自拍| 亚洲精品在线一区二区| 午夜电影亚洲| 亚洲一区二区三区高清| 美女日韩在线中文字幕| 欧美一级视频精品观看| 欧美另类极品videosbest最新版本| 久久国产99| 国产精品乱码一区二区三区| 亚洲国产99| 国内成人精品2018免费看 | 香蕉视频成人在线观看| 欧美日产国产成人免费图片| 免播放器亚洲一区| 国产日韩欧美视频在线| 一区二区三区视频在线播放| 亚洲免费观看| 媚黑女一区二区| 免播放器亚洲| 一色屋精品视频在线观看网站| 亚洲午夜女主播在线直播| 99在线精品视频| 欧美高清视频在线观看| 欧美大胆人体视频| 亚洲丰满在线| 老司机亚洲精品| 男女精品网站| 亚洲电影一级黄| 免费亚洲一区二区| 老牛影视一区二区三区| 国内精品美女av在线播放| 欧美亚洲一区二区在线观看| 欧美一二三区在线观看| 国产精品一区二区三区久久久 | 亚洲色无码播放| 午夜一区二区三区在线观看| 国产精品久久国产三级国电话系列 | 亚洲国产高潮在线观看| 亚洲精品视频一区二区三区| 欧美福利一区二区| 99精品国产在热久久| 亚洲欧美日韩国产综合精品二区| 国产精品成人免费| 午夜在线视频观看日韩17c| 久久成人免费网| 在线观看视频一区二区欧美日韩| 麻豆91精品| 99精品国产在热久久| 久久久国际精品| 裸体丰满少妇做受久久99精品| 亚洲国产精品一区二区www| 欧美国内亚洲| 亚洲午夜久久久| 久久国内精品视频| 狠狠色狠狠色综合日日tαg| 久久精品国产精品亚洲综合| 亚洲第一偷拍| 日韩天天综合| 国产精品高潮呻吟久久av黑人| 亚洲视频在线观看一区| 亚洲欧美一级二级三级| 国产精品久久福利| 午夜国产精品视频免费体验区| 久久久国产精品亚洲一区 | 欧美成人在线网站| 亚洲精品一区二区三区四区高清 | 国产精品青草久久| 久久国产精品亚洲va麻豆| 快she精品国产999| 亚洲一区二区免费看| 国内精品视频在线播放| 久久在线播放| 一区二区三区久久网| 久久www免费人成看片高清| 在线成人h网| 久久国产精品99久久久久久老狼 | 亚洲无限av看| 国产欧美亚洲日本| 免费在线欧美视频| 亚洲经典自拍| 亚洲天堂第二页| 黄色资源网久久资源365| 欧美国产视频在线| 午夜在线观看欧美| 亚洲精品影院在线观看| 久久国产日韩| 亚洲国产人成综合网站| 国产一区二区高清| 欧美日韩久久久久久| 久久精品五月| 亚洲视频免费在线观看| 欧美高清在线观看| 欧美伊人久久大香线蕉综合69| 亚洲国产片色| 国产一区二区三区高清| 欧美区二区三区| 久久久国产成人精品| 91久久精品日日躁夜夜躁国产| 久久久精品日韩欧美| 亚洲一区在线看| 在线视频日本亚洲性| 亚洲成色精品| 黑人中文字幕一区二区三区| 国产精品高潮呻吟| 欧美片网站免费| 美女视频黄a大片欧美| 免费日韩av| 久久理论片午夜琪琪电影网| 亚洲欧美在线一区| 亚洲人成7777| 亚洲福利一区| 久久国产精彩视频| 性视频1819p久久| 亚洲欧美在线高清| 亚洲砖区区免费| 亚洲视频 欧洲视频| 亚洲精品一区二区三区福利| 亚洲毛片一区| 亚洲精品黄网在线观看| 亚洲精品一二| 999亚洲国产精| 欧美一区国产二区| 日韩亚洲欧美一区二区三区| 宅男66日本亚洲欧美视频| 亚洲精品久久久久久下一站| 亚洲电影免费在线| 亚洲国产精品电影| 欧美激情第9页| 亚洲欧洲综合另类在线| 亚洲日本aⅴ片在线观看香蕉| 男人的天堂亚洲| 免费黄网站欧美| 欧美福利一区| 欧美 亚欧 日韩视频在线| 亚洲三级网站| 一区二区三区四区五区精品视频| 日韩视频免费在线观看| 99综合电影在线视频| 一区二区三区国产精品| 久久精品国产精品亚洲精品| 开元免费观看欧美电视剧网站| 免费的成人av| 欧美日韩国产小视频在线观看| 国产精品theporn| 国产欧美精品xxxx另类| 韩日精品中文字幕| 亚洲欧洲日本在线| 亚洲男人第一av网站| 久久久久久网站| 欧美国产欧美亚洲国产日韩mv天天看完整 | 久久久免费精品视频| 久久一区二区三区国产精品| 欧美激情精品久久久久久| 欧美成人免费全部观看天天性色| 国产精品人人做人人爽| 在线观看国产精品淫| 9国产精品视频| 久久久久久9| 亚洲人成人一区二区在线观看| 欧美一区二区成人6969| 嫩模写真一区二区三区三州| 国产精品不卡在线| 亚洲成色999久久网站| 亚洲综合视频网| 亚洲欧洲在线观看| 久久精品91久久久久久再现| 欧美精品18+| 精品69视频一区二区三区| 一区二区免费在线播放| 亚洲高清免费|