Feng.Li's Java See

          抓緊時間,大步向前。
          隨筆 - 95, 文章 - 4, 評論 - 58, 引用 - 0

          導航

          <2007年12月>
          2526272829301
          2345678
          9101112131415
          16171819202122
          23242526272829
          303112345

          常用鏈接

          留言簿(7)

          隨筆分類

          隨筆檔案

          文章檔案

          相冊

          大家都在博

          • 東東同學
          • 也許,在每個人的心靈深處,都會有一份屬于自己的寧靜
          • 亞明先生
          • 誰說世間無高人?且看我“物質生活”
          • 大飛
          • 此大飛,非彼大飛,乃宿舍長兼學生會主席
          • 玉東同學
          • 小男人

          搜索

          •  

          最新評論

          閱讀排行榜

          評論排行榜

          遞歸求解問題的通用方法

          程序設計中遞歸不失為一種優雅的方法,可以用簡單的代碼解決看似復雜的問題。本文闡述了如何使用遞歸程序來解決一系列復雜的問題,并對遞歸程序的執行原理以及通用求解問題的方法作出了分析

          編寫遞歸程序有幾個重要的原則,細節詳敘如后。
              1. 要解決的問題可拆分為幾個與原問題類似的子問題(子問題仍可拆分)。
              2. 每個子問題必須比原來問題的規模更小(即使小一號也行,當然如果能夠迅速減小規模更好)。
              3. 遇到足夠小的子問題時就直接解決之,防止問題無限細分下去,也就是防止無限遞歸(遞歸終止條件很重要)。 
          先看一個最簡單的遞歸程序,下面程序求整數n的階乘:
          int factorial(int n)
          {
              return n <= 1 ? 1 : n*factorial(n-1);
          }
          所謂遞歸程序,就是程序在執行中又調用其自身,如上面函數factorial在其函數體內調用了函數factorial。函數在每次被調用時都會生成一個包含自身局部變量的副本,即算是函數調用自身時也是如此。
          遞歸程序主體主要由兩部分構成:一是遞歸執行部分,包含遞歸執行所需的條件;一是遞歸終止部分,含遞歸終止條件。上面求階乘的程序中把這兩部分寫在一行代碼里面,把其分別抽出來便是:
          int factorial(int n)
          {
              if(n <= 1) return 1;     // 遞歸終止體
              return n*factorial(n-1); // 遞歸執行體

          }


          下面以幾個經典算法問題的遞歸程序求解為例來分析編寫遞歸程序中可以遵循的簡單規則。
          1. 求正整數n所有可能的和式的組合,如給定正整數3,所有和加起來等于3的和式如下:
          3 = 3 + 0
          3 = 2 + 1
          3 = 1 + 1 + 1
          其中一個和式中的因子只能為自然數,因子允許重復出現。

          這個問題是一個組合問題的變形,用遞歸程序實現如下(分析見注釋):
          #define MAXSIZE 50       
          static int buff[MAXSIZE]; // 存儲和式因子組合的緩沖
          /// 求當前和式中因子之和。
          int Sum(int buff[],int i)
          {
              int sum = 0;
              for(int m=0; m<=i; m++)
                  sum += buff[m];
              return sum;
          }
          /// 打印當前滿足條件的和式。
          void printFactor(int buff[],int i,const int number)
          {
              int count = 0, m;
              for(m=0; m<=i; m++)
                  printf("%4d",buff[m]);
              if(number==buff[0])
                  printf("%4d",0);
              printf("\n");
          }
          /// 遞歸求解所有和式組合。
          /// i - 當前可選自然數的最大值。
          /// top - 當前組合中因子個數。
          /// number - 問題中要求解和式的正整數。
          void divide(int i,int top,int number)
          {   
              for(int j=i; j>0; j--)               // 注意這里的循環條件,可以有效防止出現重復的組合
              {
                  buff[top ] = j;

                  if(number == Sum(buff,top))      // 首先要確定遞歸中止條件
                      printFactor(buff,top,number);
                  else if(number < Sum(buff,top))  // 繼續增加和式中的因子
                      continue;

                  if(top >= number)                // 和式中的因子不應該超過和的大小
                      continue;

                  divide(j,top+1,number);          // 減小問題規模,繼續遞歸
              }
              return;
          }

          int main()
          {
              int i,top = 0;
              int number = 8;
              printf("input a souce number:");
              scanf("%d",&number);
              i = number;
              divide(i,top,number);

              return 0;
          }

          2. 給定正整數k,以及1-k共 k個正整數的一個排列,假如是 1,2,3,...,k,求所有和此排列“不相交”的排列。
          所謂不相交,是指新的排列和已有排列在同一位置上的數都不相同。如假設k=3,則其排列:
          1 2 3 和 3 2 1是相交的,因為第二個位置上都是2;而排列1 2 3 和 3 1 2則不相交。

          問題分析:此問題是普通排列問題的變形,只要在排列問題的遞歸程序中加上位置的限制即可,程序實現如下,具體分析見注釋

          posted on 2007-12-26 20:04 小鋒 閱讀(682) 評論(0)  編輯  收藏 所屬分類: algorithm

          主站蜘蛛池模板: 广州市| 万荣县| 家居| 于都县| 旺苍县| 河北区| 周口市| 承德市| 高邮市| 江陵县| 百色市| 合江县| 旅游| 阜城县| 墨江| 甘肃省| 赤水市| 遂宁市| 东至县| 阿拉善左旗| 尤溪县| 南宫市| 墨竹工卡县| 斗六市| 永德县| 浦江县| 静乐县| 济宁市| 峨山| 南汇区| 隆安县| 望城县| 叶城县| 铁岭县| 揭西县| 镇康县| 绥江县| 余江县| 福安市| 马鞍山市| 威海市|