常用算法設(shè)計(jì)方法

寧波高等�？茖W(xué)校電子系 周文革

    要使計(jì)算機(jī)能完成人們預(yù)定的工作，首先必須為如何完成預(yù)定的工作設(shè)計(jì)一個(gè)算法，然后再根據(jù)算法編寫程序。計(jì)算機(jī)程序要對(duì)問(wèn)題的每個(gè)對(duì)象和處理規(guī)則給出正確詳盡的描述，其中程序的數(shù)據(jù)結(jié)構(gòu)和變量用來(lái)描述問(wèn)題的對(duì)象，程序結(jié)構(gòu)、函數(shù)和語(yǔ)句用來(lái)描述問(wèn)題的算法。算法數(shù)據(jù)結(jié)構(gòu)是程序的兩個(gè)重要方面。

    算法是問(wèn)題求解過(guò)程的精確描述，一個(gè)算法由有限條可完全機(jī)械地執(zhí)行的、有確定結(jié)果的指令組成。指令正確地描述了要完成的任務(wù)和它們被執(zhí)行的順序。計(jì)算機(jī)按算法指令所描述的順序執(zhí)行算法的指令能在有限的步驟內(nèi)終止，或終止于給出問(wèn)題的解，或終止于指出問(wèn)題對(duì)此輸入數(shù)據(jù)無(wú)解。

    通常求解一個(gè)問(wèn)題可能會(huì)有多種算法可供選擇，選擇的主要標(biāo)準(zhǔn)是算法的正確性和可靠性，簡(jiǎn)單性和易理解性。其次是算法所需要的存儲(chǔ)空間少和執(zhí)行更快等。

    算法設(shè)計(jì)是一件非常困難的工作，經(jīng)常采用的算法設(shè)計(jì)技術(shù)主要有迭代法、窮舉搜索法、遞推法、貪婪法、回溯法、分治法、動(dòng)態(tài)規(guī)劃法等等。另外，為了更簡(jiǎn)潔的形式設(shè)計(jì)和藐視算法，在算法設(shè)計(jì)時(shí)又常常采用遞歸技術(shù)，用遞歸描述算法。

一、迭代法

    迭代法是用于求方程或方程組近似根的一種常用的算法設(shè)計(jì)方法。設(shè)方程為f(x)=0，用某種數(shù)學(xué)方法導(dǎo)出等價(jià)的形式x=g(x)，然后按以下步驟執(zhí)行：

（1）       選一個(gè)方程的近似根，賦給變量x₀；

（2）       將x₀的值保存于變量x1，然后計(jì)算g(x₁)，并將結(jié)果存于變量x₀；

（3）       當(dāng)x₀與x₁的差的絕對(duì)值還小于指定的精度要求時(shí)，重復(fù)步驟（2）的計(jì)算。

    若方程有根，并且用上述方法計(jì)算出來(lái)的近似根序列收斂，則按上述方法求得的x₀就認(rèn)為是方程的根。上述算法用C程序的形式表示為：

【算法】迭代法求方程的根

{     x0=初始近似根；

       do {

              x1=x0；

              x0=g(x1)；    /*按特定的方程計(jì)算新的近似根*/

              } while ( fabs(x0-x1)>Epsilon)；

       printf(“方程的近似根是%f\n”，x0)；

}

迭代算法也常用于求方程組的根，令

              X=（x₀，x₁，…，x_n-1）

設(shè)方程組為：

              x_i=g_i(X)         (I=0，1，…，n-1)

則求方程組根的迭代算法可描述如下：

【算法】迭代法求方程組的根

       {     for (i=0;i<n;i++)

                     x[i]=初始近似根;

              do {

                     for (i=0;i<n;i++)

                            y[i]=x[i];

                     for (i=0;i<n;i++)

                            x[i]=gi(X);

                     for (delta=0.0,i=0;i<n;i++)

                            if (fabs(y[i]-x[i])>delta)        delta=fabs(y[i]-x[i])；

                     } while (delta>Epsilon)；

              for (i=0;i<n;i++)

                     printf(“變量x[%d]的近似根是 %f”，I，x[i])；

              printf(“\n”)；

       }

       具體使用迭代法求根時(shí)應(yīng)注意以下兩種可能發(fā)生的情況：

（1）       如果方程無(wú)解，算法求出的近似根序列就不會(huì)收斂，迭代過(guò)程會(huì)變成死循環(huán)，因此在使用迭代算法前應(yīng)先考察方程是否有解，并在程序中對(duì)迭代的次數(shù)給予限制；

（2）       方程雖然有解，但迭代公式選擇不當(dāng)，或迭代的初始近似根選擇不合理，也會(huì)導(dǎo)致迭代失敗。

二、窮舉搜索法

       窮舉搜索法是對(duì)可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，并從眾找出那些符合要求的候選解作為問(wèn)題的解。

【問(wèn)題】       將A、B、C、D、E、F這六個(gè)變量排成如圖所示的三角形，這六個(gè)變量分別取[1，6]上的整數(shù)，且均不相同。求使三角形三條邊上的變量之和相等的全部解。如圖就是一個(gè)解。

    程序引入變量a、b、c、d、e、f，并讓它們分別順序取1至6的證書，在它們互不相同的條件下，測(cè)試由它們排成的如圖所示的三角形三條邊上的變量之和是否相等，如相等即為一種滿足要求的排列，把它們輸出。當(dāng)這些變量取盡所有的組合后，程序就可得到全部可能的解。細(xì)節(jié)見(jiàn)下面的程序。

【程序1】

# include <stdio.h>

void main()

{     int a,b,c,d,e,f;

       for (a=1;a<=6;a++)      

              for (b=1;b<=6;b++)              {

                     if (b==a)        continue;

                     for (c=1;c<=6;c++)              {

                            if (c==a)||(c==b)    continue;

                            for (d=1;d<=6;d++)              {

                                   if (d==a)||(d==b)||(d==c)      continue;

for (e=1;e<=6;e++)              {

       if (e==a)||(e==b)||(e==c)||(e==d) continue;

f=21-(a+b+c+d+e);

if ((a+b+c==c+d+e))&&(a+b+c==e+f+a))   {

printf(“%6d,a);

       printf(“%4d%4d”,b,f);

       printf(“%2d%4d%4d”,c,d,e);

       scanf(“%*c”);

}

                                          }

                                   }

                            }

                     }

              }

    按窮舉法編寫的程序通常不能適應(yīng)變化的情況。如問(wèn)題改成有9個(gè)變量排成三角形，每條邊有4個(gè)變量的情況，程序的循環(huán)重?cái)?shù)就要相應(yīng)改變。

       對(duì)一組數(shù)窮盡所有排列，還有更直接的方法。將一個(gè)排列看作一個(gè)長(zhǎng)整數(shù)，則所有排列對(duì)應(yīng)著一組整數(shù)。將這組整數(shù)按從小到大的順序排列排成一個(gè)整數(shù)，從對(duì)應(yīng)最小的整數(shù)開始。按數(shù)列的遞增順序逐一列舉每個(gè)排列對(duì)應(yīng)的每個(gè)整數(shù)，這能更有效地完成排列的窮舉。從一個(gè)排列找出對(duì)應(yīng)數(shù)列的下一個(gè)排列可在當(dāng)前排列的基礎(chǔ)上作部分調(diào)整來(lái)實(shí)現(xiàn)。倘若當(dāng)前排列為1，2，4，6，5，3，并令其對(duì)應(yīng)的長(zhǎng)整數(shù)為124653。要尋找比長(zhǎng)整數(shù)124653更大的排列，可從該排列的最后一個(gè)數(shù)字順序向前逐位考察，當(dāng)發(fā)現(xiàn)排列中的某個(gè)數(shù)字比它前一個(gè)數(shù)字大時(shí)，如本例中的6比它的前一位數(shù)字4大，這說(shuō)明還有對(duì)應(yīng)更大整數(shù)的排列。但為了順序從小到大列舉出所有的排列，不能立即調(diào)整得太大，如本例中將數(shù)字6與數(shù)字4交換得到的排列126453就不是排列124653的下一個(gè)排列。為了得到排列124653的下一個(gè)排列，應(yīng)從已經(jīng)考察過(guò)的那部分?jǐn)?shù)字中選出比數(shù)字大，但又是它們中最小的那一個(gè)數(shù)字，比如數(shù)字5，與數(shù)字4交換。該數(shù)字也是從后向前考察過(guò)程中第一個(gè)比4大的數(shù)字。5與4交換后，得到排列125643。在前面數(shù)字1，2，5固定的情況下，還應(yīng)選擇對(duì)應(yīng)最小整數(shù)的那個(gè)排列，為此還需將后面那部分?jǐn)?shù)字的排列順序顛倒，如將數(shù)字6，4，3的排列順序顛倒，得到排列1，2，5，3，4，6，這才是排列1，2，4，6，5，3的下一個(gè)排列。按以上想法編寫的程序如下。

【程序2】

# include <stdio.h>

# define SIDE_N    3

# define LENGTH  3

# define VARIABLES     6

int A,B,C,D,E,F;

int *pt[]={&A,&B,&C,&D,&E,&F};

int *side[SIDE_N][LENGTH]={&A,&B,&C,&C,&D,&E,&E,&F,&A};

int side_total[SIDE_N];

main{}

{     int i,j,t,equal;

       for (j=0;j<VARIABLES;j++)

              *pt[j]=j+1;

       while(1)

       {     for (i=0;i<SIDE_N;i++)

              {     for (t=j=0;j<LENGTH;j++)

                            t+=*side[i][j];

                     side_total[i]=t;

              }

              for (equal=1,i=0;equal&&i<SIDE_N-1;i++)

                     if (side_total[i]!=side_total[i+1]     equal=0;

              if (equal)

              {     for (i=1;i<VARIABLES;i++)

                            printf(“%4d”,*pt[i]);

                     printf(“\n”);

                     scanf(“%*c”);

              }

              for (j=VARIABLES-1;j>0;j--)

                     if (*pt[j]>*pt[j-1])  break;

              if (j==0)  break;

              for (i=VARIABLES-1;i>=j;i--)

                     if (*pt[i]>*pt[i-1])  break;

              t=*pt[j-1];* pt[j-1] =* pt[i]; *pt[i]=t;

              for (i=VARIABLES-1;i>j;i--,j++)

              {     t=*pt[j]; *pt[j] =* pt[i]; *pt[i]=t;   }

       }

}

    從上述問(wèn)題解決的方法中，最重要的因素就是確定某種方法來(lái)確定所有的候選解。下面再用一個(gè)示例來(lái)加以說(shuō)明。

【問(wèn)題】       背包問(wèn)題

    問(wèn)題描述：有不同價(jià)值、不同重量的物品n件，求從這n件物品中選取一部分物品的選擇方案，使選中物品的總重量不超過(guò)指定的限制重量，但選中物品的價(jià)值之和最大。

    設(shè)n個(gè)物品的重量和價(jià)值分別存儲(chǔ)于數(shù)組w[ ]和v[ ]中，限制重量為tw�？紤]一個(gè)n元組（x₀，x₁，…，x_n-1），其中x_i=0 表示第i個(gè)物品沒(méi)有選取，而x_i=1則表示第i個(gè)物品被選取。顯然這個(gè)n元組等價(jià)于一個(gè)選擇方案。用枚舉法解決背包問(wèn)題，需要枚舉所有的選取方案，而根據(jù)上述方法，我們只要枚舉所有的n元組，就可以得到問(wèn)題的解。

    顯然，每個(gè)分量取值為0或1的n元組的個(gè)數(shù)共為2ⁿ個(gè)。而每個(gè)n元組其實(shí)對(duì)應(yīng)了一個(gè)長(zhǎng)度為n的二進(jìn)制數(shù)，且這些二進(jìn)制數(shù)的取值范圍為0～2ⁿ-1。因此，如果把0～2ⁿ-1分別轉(zhuǎn)化為相應(yīng)的二進(jìn)制數(shù)，則可以得到我們所需要的2ⁿ個(gè)n元組。

【算法】

maxv=0;

for (i=0;i<2ⁿ;i++)

{     B[0..n-1]=0;

       把i轉(zhuǎn)化為二進(jìn)制數(shù)，存儲(chǔ)于數(shù)組B中;

       temp_w=0;

       temp_v=0;

       for (j=0;j<n;j++)

       {     if (B[j]==1)

              {     temp_w=temp_w+w[j];

                     temp_v=temp_v+v[j];

              }

              if ((temp_w<=tw)&&(temp_v>maxv))

              {     maxv=temp_v;

                     保存該B數(shù)組；

              }

       }

}

 

三、遞推法

       遞推法是利用問(wèn)題本身所具有的一種遞推關(guān)系求問(wèn)題解的一種方法。設(shè)要求問(wèn)題規(guī)模為N的解，當(dāng)N=1時(shí)，解或?yàn)橐阎�，或能非常方便地得到解。能采用遞推法構(gòu)造算法的問(wèn)題有重要的遞推性質(zhì)，即當(dāng)?shù)玫絾?wèn)題規(guī)模為i-1的解后，由問(wèn)題的遞推性質(zhì)，能從已求得的規(guī)模為1，2，…，i-1的一系列解，構(gòu)造出問(wèn)題規(guī)模為I的解。這樣，程序可從i=0或i=1出發(fā)，重復(fù)地，由已知至i-1規(guī)模的解，通過(guò)遞推，獲得規(guī)模為i的解，直至得到規(guī)模為N的解。

【問(wèn)題】       階乘計(jì)算

    問(wèn)題描述：編寫程序，對(duì)給定的n（n≦100），計(jì)算并輸出k的階乘k�。�k=1，2，…，n）的全部有效數(shù)字。

    由于要求的整數(shù)可能大大超出一般整數(shù)的位數(shù)，程序用一維數(shù)組存儲(chǔ)長(zhǎng)整數(shù)，存儲(chǔ)長(zhǎng)整數(shù)數(shù)組的每個(gè)元素只存儲(chǔ)長(zhǎng)整數(shù)的一位數(shù)字。如有m位成整數(shù)N用數(shù)組a[ ]存儲(chǔ)：

       N=a[m]×10^m-1+a[m-1]×10^m-2+ … +a[2]×10¹+a[1]×10⁰

    并用a[0]存儲(chǔ)長(zhǎng)整數(shù)N的位數(shù)m，即a[0]=m。按上述約定，數(shù)組的每個(gè)元素存儲(chǔ)k的階乘k！的一位數(shù)字，并從低位到高位依次存于數(shù)組的第二個(gè)元素、第三個(gè)元素……。例如，5！=120，在數(shù)組中的存儲(chǔ)形式為：

3

0

2

1

……

    首元素3表示長(zhǎng)整數(shù)是一個(gè)3位數(shù)，接著是低位到高位依次是0、2、1，表示成整數(shù)120。

       計(jì)算階乘k！可采用對(duì)已求得的階乘(k-1)！連續(xù)累加k-1次后求得。例如，已知4！=24，計(jì)算5！，可對(duì)原來(lái)的24累加4次24后得到120。細(xì)節(jié)見(jiàn)以下程序。

# include <stdio.h>

# include <malloc.h>

# define  MAXN   1000

void  pnext(int a[ ],int k)

{     int *b,m=a[0],i,j,r,carry;

       b=(int * ) malloc(sizeof(int)* (m+1));

       for ( i=1;i<=m;i++)        b[i]=a[i];

       for ( j=1;j<=k;j++)

       {     for ( carry=0,i=1;i<=m;i++)

              {     r=(i<a[0]?a[i]+b[i]:a[i])+carry;

                     a[i]=r%10;

                     carry=r/10;

              }

              if (carry)  a[++m]=carry;

       }

       free(b);

       a[0]=m;

}

 

void  write(int *a,int k)

{     int i;

       printf(“%4d！=”,k);

       for (i=a[0];i>0;i--)

              printf(“%d”,a[i]);

printf(“\n\n”);

}

 

void main()

{     int a[MAXN],n,k;

       printf(“Enter the number n:  “);

       scanf(“%d”,&n);

       a[0]=1;

       a[1]=1;

       write(a,1);

       for (k=2;k<=n;k++)

       {     pnext(a,k);

              write(a,k);

              getchar();

       }

}

四、遞歸

       遞歸是設(shè)計(jì)和描述算法的一種有力的工具，由于它在復(fù)雜算法的描述中被經(jīng)常采用，為此在進(jìn)一步介紹其他算法設(shè)計(jì)方法之前先討論它。

       能采用遞歸描述的算法通常有這樣的特征：為求解規(guī)模為N的問(wèn)題，設(shè)法將它分解成規(guī)模較小的問(wèn)題，然后從這些小問(wèn)題的解方便地構(gòu)造出大問(wèn)題的解，并且這些規(guī)模較小的問(wèn)題也能采用同樣的分解和綜合方法，分解成規(guī)模更小的問(wèn)題，并從這些更小問(wèn)題的解構(gòu)造出規(guī)模較大問(wèn)題的解。特別地，當(dāng)規(guī)模N=1時(shí)，能直接得解。

【問(wèn)題】       編寫計(jì)算斐波那契（Fibonacci）數(shù)列的第n項(xiàng)函數(shù)fib（n）。

       斐波那契數(shù)列為：0、1、1、2、3、……，即：

              fib(0)=0;

              fib(1)=1;

              fib(n)=fib(n-1)+fib(n-2)        （當(dāng)n>1時(shí)）。

寫成遞歸函數(shù)有：

int fib(int n)

{     if (n==0)        return  0;

       if (n==1)        return  1;

       if (n>1)          return  fib(n-1)+fib(n-2);

}

      

[1] [2] [3] [4] [5] [6] 下一頁(yè)