常用計算機算法簡介及C語言舉例

摘要:該文主要是簡單介紹了常用的幾種計算機算法，如迭代法、遞推法、遞歸法、窮舉法等，并舉例用C語言進行實現。

關鍵詞:計算機算法;C語言

中圖分類號:TP311文獻標識碼:A 文章編號:1009-3044(2010)11-2655-05

The Computer Algorithms Introduction and C Language Gives Examples

MA Li-juan

(Henan Institute of Science and Technology，Xinxiang 453003，China)

Abstract:This text mainly introduced a few Computer Algorithms， such as escalator method， recurrence method，recursive algorithm， exhaust algorithm etc.， and give examples with the C language.

Key words:Computer Algorithms;C language

計算機算法是指解決某一問題的運算序列?；蛘哒f計算機算法是問題求解過程的運算描述，一個計算機算法由有限條可完全機械地執行的、有確定結果的指令組成。計算機算法可分為兩大類:數值運算算法、非數值運算算法。數值運算算法的目的是求數值解，如:求方程的根、矩陣計算、函數的定積分等。非數值運算算法應用十分廣泛，如:圖書檢索、人事管理、文字處理等。常用的算法設計方法有數值算法如迭代法、遞推法、遞歸法等;非數值算法有窮舉法、回溯法、貪心法、分治法等。[1-2]下面就來介紹這些常用的算法。

1 迭代法

迭代法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重復性操作的特點，讓計算機對一組指令(或一定步驟)進行重復執行，在每次執行這組指令(或這些步驟)時，都從變量的原值推出它的一個新值。迭代法常用于求方程或方程組的近似根。

例如用迭代法求x=。求平方根的迭代公式為xn+1=1/2(xn+a/xn)，要求前后兩次求出的x的差的絕對值小于10-5。用迭代法求出平方根的算法如下:

1)先自定一個初值x0，作為a的平方根值，在我們的程序中取x0為a/2;

2)利用迭代公式求出一個x1。此值與真正的a的平方根值相比，誤差很大;

3)把新求得的x1代入x0中，準備用此新的x0再去求出一個新的x1;

4)利用迭代公式再求出一個新的x1的值，也就是用新的x0又求出一個新的平方根值x1，此值將更趨近于真正的平方根值;

5)比較前后兩次求得的平方根值x0和x1，如果它們的差值小于我們指定的值，即達到我們要求的精度，則認為x1就是a的平方根值。[3]

C程序如下:

#include

main( )

{float a， x0，x1;

printf(\" please input a: \");

scanf(\"%f\"，a);

x0=a/2;

x1=(x0+a/x0)/2;

do

{x0=x1;

x1=(x0+a/x0)/2;

} while(fabs(x1-x0)>=1e-5);/*迭代過程*/

printf(\"The square root of %5.2f if %8.5f\\"，a，x1);

}

2 遞推法

遞推法是根據具體問題，建立遞推關系，再通過遞推關系求解的方法。其中遞推關系是表示關于正整數參變量的一類特殊關系，它從給定的初值出發，通過這種關系一步一步地通過遞推獲得所需結果。這種遞推通常采用循環迭代的方法，如循環累乘、循環累加等。[3]

例如階乘計算，假設要求5的階乘。C程序對應如下:

#include \"stdio.h\"

main()

{int n，s=1;

for(n=1;n<=5;n++)

{s=s*n; /*1的階乘為1，1的階乘乘以2就是2的階乘，2的階乘乘以3就是3的階乘，以此類推，直到求出5的階乘*/

}

printf(\"5!=%d\"，s);

}

3 遞歸法

程序調用自身的編程技巧稱為遞歸。一個過程或函數在其定義或說明中又直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。

例如計算斐波那契(Fibonacci)數列的第n項。斐波那契數列為:0、1、1、2、3、……，即:

fib(0)=0;

fib(1)=1;

fib(n)=fib(n-1)+fib(n-2) (當n>1時)。

用C語言寫成遞歸函數為:

int fib(int n)

{if (n==0) return 0;

if (n==1) return 1;

if (n>1) return fib(n-1)+fib(n-2);/*遞歸調用*/

}

遞歸算法的執行過程分遞推和回歸兩個階段。在遞推階段，就是為了得到問題的解，將它推到比原問題更簡單的問題求解。。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是說，為計算fib(n)，必須先計算fib(n-1)和fib(n-2)，而計算fib(n-1)和fib(n-2)，又必須先計算fib(n-3)和fib(n-4)。依次類推，直至計算fib(1)和fib(0)，這時能立即得到結果1和0。在遞推階段，必須要有終止遞歸的情況。例如在函數fib中，當n為1和0時可以終止。在回歸階段，就是當簡單問題得到解后，回歸到原問題的解上來。例如得到fib(1)和fib(0)后，返回得到fib(2)的結果，……，在得到了fib(n-1)和fib(n-2)的結果后，返回得到fib(n)的結果。

遞歸算法解題通常很簡潔，但是由于遞歸引起一系列的函數調用，并且可能會有一系列的重復計算，所以遞歸算法的執行效率相對較低。[4]

4 窮舉法

窮舉法是編程中常用到的一種方法，通常在找不到解決問題的規律時對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗，并從中找出那些符合要求的候選解作為問題的解。

比如用窮舉法求百元百雞問題，公雞5元一只，母雞3元一只，小雞1元三只。現有100元要買100只雞，需包含公雞、母雞和小雞，求可能有哪幾種方案。[5]列出C程序如下:

main ( )

{int i，j，k，n=0; /*變量n表示方案數*/

for (i=1;i<20;i++) /*變量i表示公雞的數量，就算全部買公雞也只能買20只*/

for (j=1;j<33;j++)/*變量i表示母雞的數量，就算全部買母雞也只能買33只*/

for (k=1;k<300;k++)/*變量i表示小雞的數量，就算全部買小雞也只能買300只*/

{if (3*5*i+3*3*j+k==300i+j+k==100)/*一共100元，并且正好100只雞*/

{n++;

printf (\"n=%d，cook=%d，hen=%d，chick=%d\\"，n，i，j，k);

}}}

程序運行結果為:

n=1，cook=4，hen=18，chick=78

n=2，cook=8，hen=11，chick=81

n=3，cook=12，hen=4，chick=84

5 回溯法

回溯法是一種選優的搜索方法，按照選優的條件向前搜索，以達到目標，但是當搜索到某一步的時候，發現原先的選擇并不優或者達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術就是回溯法。

例如八皇后問題是能用回溯法解決的一個經典問題。八皇后問題是一個古老而著名的問題。該問題是在8*8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后不允許處在同一橫排，同一縱列，也不允許處在同一與棋盤邊框成45度角的斜線上。問有多少種擺法。[6-7]下面是用回溯法解決八皇后問題的C語言程序:

#include

#include

int col[9]={0}，a[9];/* 值col[i]表示在棋盤第i列、col[i]行有一皇后。a[k]表示第k行還沒皇后;*/

int b[17]，c[17]; /* b[k ]表示第k列右高左低斜線上沒有皇后;c[k]表示第k列左高右低斜線上沒有皇后;*/

main()

{ int m，good;

int i，j，k;

char q;

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

{if(i<9) a[i]=1;

b[i]=1;c[i]=1;

}

good=1;

col[1]=1;

m=1;

while(col[0]!=1)

{if(good)

if(m==8)

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

printf(\"col[%d] %d\\"，i，col[i]);

printf(\"input 'q' to quit\\");

scanf(\"%c\"，q);

getchar();

if(q=='q'||q=='Q') exit(0);

while(col[m]==8)

{m--;

a[col[m]]=b[m+col[m]]=c[8+m-col[m]]=1;

}

a[col[m]]=b[m+col[m]]=c[8+m-col[m]]=1;

col[m]++;

}

else

{ a[col[m]]=b[m+col[m]]=c[8+m-col[m]]=0;

m++;

col[m]=1;

}

else

{ while(col[m]==8)

{ m--;

a[col[m]]=b[m+col[m]]=c[8+m-col[m]]=1;

}

col[m]++;

}

good=a[col[m]]b[m+col[m]]c[8+m-col[m]];

}

}

6 貪心法

貪心法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。

實現該算法的過程:1)從問題的某一初始解出發;2)while 能朝給定總目標前進一步do;3)求出可行解的一個解元素;4)由所有解元素組合成問題的一個可行解。

比如刪數問題，從鍵盤輸入一個高精度的正整數N，去掉其中任意S個數字后使剩下的數最大。(例如:N = 175438，S =4，可以刪去1、5、4、3，得到78)實現很簡單，就是每次刪除一個數字，選擇一個使剩下的數最大的數字作為刪除對象。[2]對應的C程序段如下:

#define N 6

main()

{int n[N]，i=0，j，x=0，m=0，k;

for(j=0;j

scanf(\"%1d\"，n[j]);

scanf(\"%d\"，k);

while(k>x m==0)

{i=i+1;

if(n[i-1]

{printf(\"%d \"，n[i-1]);

for(j=i-1;j<=N-x-2;j++)

n[j]=n[j+1];

x=x+1;/*x統計刪除數字的個數*/

i=0;/*從頭開始查遞增區間*/

}

if(i==N-x-1)/*已無遞增區間，m=1脫離循環*/

m=1;

}

printf(\"\刪除后所得最大數: \");

for(i=1;i<=N-k;i++) /*打印剩下的左邊a-k個數字*/

printf(\"%d\"，n[i-1]);

}

7 分治法

分治法就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。分治法的基本步驟

1)分解:將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題;

2)解決:若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題;

3)合并:將各個子問題的解合并為原問題的解。

人們從大量實踐中發現，在用分治法設計算法時，最好使子問題的規模大致相同。換句話說，將一個問題分成大小相等的k個子問題的處理方法是行之有效的。許多問題可以取k=2。這種使子問題規模大致相等的做法是出自一種平衡子問題的思想，它幾乎總是比子問題規模不等的做法要好。

分治法的合并步驟是算法的關鍵所在。有些問題的合并方法比較明顯，有些問題合并方法比較復雜，或者是有多種合并方案;或者是合并方案不明顯。究竟應該怎樣合并，沒有統一的模式，需要具體問題具體分析。

比如循環賽日程表。設有n=2k個運動員要進行網球循環賽。現要設計一個滿足以下要求的比賽日程表:

1)每個選手必須與其他n-1個選手各賽一次;

2)每個選手一天只能參賽一次;

3)循環賽在n-1天內結束。

要求將比賽日程表設計成有n行和n-1列的一個表。在表中的第i行，第j列處填入第i個選手在第j天所遇到的選手。其中1≤i≤n，1≤j≤n-1。

按分治策略，我們可以將所有的選手分為兩半，則n個選手的比賽日程表可以通過n/2個選手的比賽日程表來決定。遞歸地用這種一分為二的策略對選手進行劃分，直到只剩下兩個選手時，比賽日程表的制定就變得很簡單。這時只要讓這兩個選手進行比賽就可以了。[4]對應的C程序如下:

#include

#include

#define MAX_PLAYER 16

typedef struct node

{int num;

struct node *next;

}Grid;

typedef struct Player

{int num;

Grid *next;

}Player;

void Marge(Player *player_array， int fst_player， int mid， int lst_player)

{int length = (lst_player - fst_player + 1 )/ 2 - 1;

int i， j;

for (i=fst_player; i<=lst_player; i++) /*遍歷所有選手*/

{Grid *next_grid = player_array[i].next;

Grid *next_grid2;

if ( i <= mid) next_grid2 = player_array[i+mid-fst_player+1].next;

elsenext_grid2 = player_array[i-mid+fst_player-1].next;

while(next_grid->num != 0) /*查找當前選手所有日程*/

{if (next_grid->next == NULL)break;

next_grid = next_grid->next;

}

if (i <= mid)

{next_grid->next = (Grid *)malloc(sizeof(Grid));

next_grid->next->num = player_array[i+mid-fst_player+1].num;

next_grid = next_grid->next;

}

else

{next_grid->next = (Grid *)malloc(sizeof(Grid));

next_grid->next->num = player_array[i-mid+fst_player-1].num;

next_grid = next_grid->next;

}

for (j=0; j

{next_grid->next = (Grid *)malloc(sizeof(Grid));

next_grid->next->num = next_grid2->num;

next_grid = next_grid->next;

next_grid2= next_grid2->next;

}

next_grid->next = NULL;

}

}

void Arrange(Player *player_array， int fst_player， int lst_player)

{int num = lst_player - fst_player;

int mid = (lst_player + fst_player) / 2;

if ( num == 1 ) /*解決*/

{player_array[fst_player].next = (Grid *)malloc(sizeof(Grid));

player_array[fst_player].next->num = player_array[lst_player].num;

player_array[fst_player].next->next = NULL;

player_array[lst_player].next = (Grid *)malloc(sizeof(Grid));

player_array[lst_player].next->num = player_array[fst_player].num;

player_array[lst_player].next->next = NULL;

return;

}

Arrange(player_array，fst_player，mid); /*分解*/

Arrange(player_array，mid+1，lst_player);

Marge(player_array， fst_player， mid， lst_player); /*合并*/

}

void PrintTable(Player *player_array， int num)

{int i;

for (i=0; i

{Grid *next_grid = player_array[i].next;

printf(\"%2d |\"，i+1); /*打印該選手頭部信息*/

while(next_grid->num != 0) /*查找當前選手所有日程，并打印*/

{printf(\"%3d \"，next_grid->num);

if (next_grid->next == NULL)

break;

next_grid = next_grid->next;

}

printf(\"\\");

}

}

int main()

{int num_player;

int i;

Player player_list[MAX_PLAYER];

printf(\"輸入選手數目\\");

scanf(\"%d\"，num_player);

for (i=0;i

{player_list[i].num = i+1;

player_list[i].next = NULL;

}

printf(\"\循環賽程日程表:\\");

printf(\"----\");/*打印框架*/

for (i=0;i

printf(\"----\");

printf(\"-\\");

Arrange(player_list， 0， num_player-1); /*安排選手日程表*/

PrintTable(player_list， num_player); /*打印日程表*/

printf(\"----\");/*打印框架*/

for (i=0;i

printf(\"----\");

printf(\"-\\");

}[8]

以上就是常用的集中算法，同時我們還應該知道求解同一問題，可以有許多不同的算法，我們應盡量選用一個所占存儲空間小、運行時間短、性能良好的算法。

參考文獻:

[1] 徐士良.計算機常用算法[M].2版.北京:清華大學出版社，1995.

[2] 黃潤才.計算機導論[M].北京:中國鐵道出版社，2004.

[3] 百度百科.迭代法[EB/OL]. http://baike.baidu.com/view/649495.htm?fr=ala0_1.

[4] 王曉東.計算機算法設計與分析[M].3版.北京:清華大學出版社，2007.

[5] 譚浩強.C程序設計[M].2版.北京:清華大學出版社，1999.

[6] 楊克昌.計算機常用算法與程序設計教程[M].北京:人民郵電出版社，2008.

[7] 彭學君.八皇后問題的三種方案及其程序設計[J].德州學院學報，2002(4).

[8] 王猛.利用分治法設計循環賽日程表[J].科技經濟市場，2008(7).