在线现看午夜福利片|女人16久久免费视频|鲁丝片一区鲁丝片二区鲁丝|一区二区三区欧美在线

  1. 
    
    <b id="glvx9"></b>
        1. <blockquote id="glvx9"><meter id="glvx9"></meter></blockquote>
            查看全部128種考試
            軟件水平考試
             考試動態(tài) 報(bào)考指南 歷年真題 模擬試題 復(fù)習(xí)資料 心得技巧 專業(yè)英語 技術(shù)文章 軟考論壇 考試用書
             程序員 軟件設(shè)計(jì)師 網(wǎng)絡(luò)管理員 網(wǎng)絡(luò)工程師 系統(tǒng)分析師 數(shù)據(jù)庫系統(tǒng)工程師
            1
            2
            3
            4
            5
            6
            7
            8
            9
            10
            ak47  
            【字體: 程序員考試:數(shù)據(jù)結(jié)構(gòu)筆記
            程序員考試:數(shù)據(jù)結(jié)構(gòu)筆記
            spks.exam8.com 來源:考試吧Exam8.com) 更新:2005-3-25 11:20:00 軟件水平考試 考試論壇


            七、遞歸

              遞歸算法通常具有這樣的特征:為求解規(guī)模為N的問題,設(shè)法將它分解成一些規(guī)模較小的問題,然后從這些較小問題的解能方便地構(gòu)造出題目所需的解。而這些規(guī)模較小的問題也采用同樣的方法分解成規(guī)模更小的問題,通過規(guī)模更小的問題構(gòu)造出規(guī)模校小的問題的解,如此不斷的反復(fù)分解和綜合,總能分解到最簡單的能直接得到解的情況。

              因此,在解遞歸算法的題目時(shí),要注意以下幾點(diǎn):

              1) 找到遞歸調(diào)用的結(jié)束條件或繼續(xù)遞歸調(diào)用條件.

              2) 想方設(shè)法將處理對象的規(guī)?s小或元素減少.

              3) 由于遞歸調(diào)用可理解為并列同名函數(shù)的多次調(diào)用,而函數(shù)調(diào)用的原則是一層一層調(diào)用,一層一層返回.因此,還要注意理解調(diào)用返回后的下一個語句的作用.在一些簡單的遞歸算法中,往往不需要考慮遞調(diào)用返回后的語句處理.而在一些復(fù)雜的遞歸算法中,則需要考慮遞歸調(diào)用返回后的語句處理和進(jìn)一步的遞歸調(diào)用.

              4) 在讀遞歸程序或編寫遞歸程序時(shí),必須要牢記遞歸函數(shù)的作用,這樣便于理解整個函數(shù)的功能和知道哪兒需要寫上遞歸調(diào)用語句.當(dāng)然,在解遞歸算法的題目時(shí),也需要分清遞歸函數(shù)中的內(nèi)部變量和外部變量.

              表現(xiàn)形式:

              ●定義是遞歸的(二叉樹,二叉排序樹)
              ●存儲結(jié)構(gòu)是遞歸的(二叉樹,鏈表,數(shù)組)
              ●由前兩種形式得出的算法是遞歸的
              一般流程: function(variable list(規(guī)模為N))
               { if(規(guī)模小,解已知) return 解;
                else {
                 把問題分成若干個部分;
                 某些部分可直接得到解;
                 而另一部分(規(guī)模為N-1)的解遞歸得到;
                }
              }
              例1:求一個鏈表里的最大元素.
              大家有沒想過這個問題用遞歸來做呢?
              非遞歸方法大家應(yīng)該都會哦?
                Max(nodetype *h) {
                 nodetype *p;
                 nodetype *q; //存放含最大值的結(jié)點(diǎn)
                 Int max=0;
                 P=h;
                 While(p!=NULL){
                  if (max<p->data) {
                   max=p->data;
                   q=p;
                  }
                  p=p->next;
                 }
                 return q;
                }
              下面真經(jīng)來了,嘻嘻嘻~~~
                *max(nodetype *h) {
                 nodetype *temp;
                 temp=max(h->next);
                 if(h->data>temp->data)
                  return h;
                 else
                  return temp;
                }
              大家有空想想下面這個算法:求鏈表所有數(shù)據(jù)的平均值(我也沒試過),不許偷懶,用遞歸試試哦!
              遞歸程序員考試題目類型:1)就是鏈表的某些操作(比如上面的求平均值)
                          2)二叉樹(遍歷等)

              例2.判斷數(shù)組元素是否遞增
                 int jidge(int a[],int n) {
                  if(n==1) return 1;
                  else
                   if(a[0]>a[1]) return 0;
                   else return jidge(a+1,n-1);
                 }

              例3.求二叉樹的高度(根據(jù)二叉樹的遞歸性質(zhì):(左子樹)根(右子樹))
                 int depth(nodetype *root) {
                  if(root==NULL) 
                   return 0;
                  else {
                   h1=depth(root->lch);
                   h2=depth(root->rch);
                   return max(h1,h2)+1;
                  }
                  }
              自己想想求二叉樹結(jié)點(diǎn)個數(shù)(與上例類似)

              例4.已知中序遍歷和后序遍歷,求二叉樹.
               設(shè)一二叉樹的:
               中序 S:E D F B A G J H C I
                  ^start1 ^j ^end1
               后序 T:E F D B J H G I C A
                  ^start2 ^end2
                node *create(char *s,char *t, int start1,int start2,int end1,int end2) 
                { if (start1>end1) return NULL; //回歸條件
                 root=(node *)malloc(sizeof(node));
                 root->data=t[end2];
                 找到S中T[end2]的位置為 j
                 root->lch=create(S,T,s1,j-1,start1,j+start2-start1-1);
                 root->rch=create(S,T,j+1,end1,j+start2-start1,end2-1);
                 return root;
                }

              例5.組合問題
               n 個數(shù): (1,2,3,4,…n)求從中取r個數(shù)的所有組合.
               設(shè)n=5,r=3;
               遞歸思想:先固定一位 5 (從另四個數(shù)當(dāng)中選二個)
                          5,4 (從另三個數(shù)當(dāng)中選一個)
                          5,4,3 (從另二個數(shù)當(dāng)中選零個)
               即:n-2個數(shù)中取r-2個數(shù)的所有組合
                 …
              程序:
               void combire(int n,int r) {
                for(k=n;k>=n+r-1;k--) {
                 a[r]=k;
                 if(r==0) 打印a數(shù)組(表示找到一個解);
                 else combire(n-1,r-1);
                }
               } 

            上一頁  [1] [2] [3] [4] [5] [6] [7] [8] [9] 下一頁

            轉(zhuǎn)帖于:軟件水平考試_考試吧
            文章搜索  
            看了本文的網(wǎng)友還看了:
            網(wǎng)友評論
            昵 稱: *  評 分: 1分 2分 3分 4分 5分
            標(biāo)題:   匿名發(fā)表    (共有條評論)查看全部評論>>
            版權(quán)聲明 -------------------------------------------------------------------------------------
              如果軟件水平考試網(wǎng)所轉(zhuǎn)載內(nèi)容不慎侵犯了您的權(quán)益,請與我們聯(lián)系,我們將會及時(shí)處理。如轉(zhuǎn)載本軟件水平考試網(wǎng)內(nèi)容,請注明出處。
            關(guān)于本站  網(wǎng)站聲明  廣告服務(wù)  聯(lián)系方式  付款方式  站內(nèi)導(dǎo)航  客服中心  友情鏈接  考試論壇  網(wǎng)站地圖
            Copyright © 2004-2008 考試吧軟件水平考試網(wǎng) All Rights Reserved    
            中國科學(xué)院研究生院權(quán)威支持(北京) 電 話:010-62168566 傳 真:010-62192699
            百度大聯(lián)盟黃金認(rèn)證  十佳網(wǎng)絡(luò)教育機(jī)構(gòu)  經(jīng)營許可證號:京ICP060677