算法和C程序設計

1、算法和C程序設計王黨校一個程序應包括兩個方面的內容:對數(shù)據(jù)的描述：數(shù)據(jù)結構(data structure)對操作的描述：算法(algorithm)著名計算機科學家沃思提出一個公式: 數(shù)據(jù)結構 + 算法 = 程序 N沃思教授1958年,蘇黎世工學院學士學位，美國加州大學伯克利分校獲得博士學位上世紀50年代末到60年代初，沃思設計了第一個語言Euler。在斯坦福大學定義了另一種語言來描寫Algol W的編譯器，由此奠定了沃思作為程序設計語言專家的地位成名后的他拒絕了斯坦福大學的挽留，回到母校蘇黎世工學院。成功設計了PASCAL語言。1971年，沃思首次提出了“結構化程序設計”(Structured

2、 Programming)的概念，在程序設計領域引發(fā)了一場革命1984年獲圖靈獎 2.1 算法的概念 算法： 計算機求解某一問題而采用的具體方法和步驟，就稱為“算法”。對同一個問題，可有不同的解題方法和步驟 為了有效地進行解題，不僅需要保證算法正確，還要考慮算法的質量，選擇合適的算法。希望方法簡單，運算步驟少。 2.1 算法的概念(1)數(shù)值運算算法：求數(shù)值解，例如求方程的根、求函數(shù)的定積分等。(2)非數(shù)值運算算法：包括的面十分廣泛，最常見的是用于事務管理領域，例如圖書檢索、人事管理、車輛調度管理等。計算機算法可分為兩大類別：有窮性：包含有限的操作步驟確定性：算法中的每一個步驟都應當是確定的 有

3、零個或多個輸入：輸入是指在執(zhí)行算法時需要從外界取得必要的信息 有一個或多個輸出：算法的目的是為了求解，“解” 就是輸出 有效性：算法中的每一個步驟都應當能有效地執(zhí)行，并得到確定的結果 。3、算法的特性： 2.2 算法的描述方法可以用不同的方法表示算法，常用的有：自然語言傳統(tǒng)流程圖N-S流程圖偽代碼計算機語言 1、 用自然語言表示算法自然語言就是人們日常使用的語言，可以是漢語或英語或其它語言用自然語言表示的算法通俗易懂，但文字冗長，容易出現(xiàn)“歧義性”自然語言表示的含義往往不太嚴格，要根據(jù)上下文才能判斷其正確含義，描述包含分支和循環(huán)的算法時也不很方便因此，除了那些很簡單的問題外，一般不用自然語言描

4、述算法 2、 用傳統(tǒng)的流程圖表示算法 美國國家標準化協(xié)會ANSI(American National Standard Institute)規(guī)定了一些常用的流程圖符號：起止框判斷框處理框輸入/輸出框注釋框流程線連接點三種基本結構Bohra和Jacopini提出了以下三種基本結構：順序結構、選擇結構、循環(huán)結構 用這三種基本結構作為表示一個良好算法的基本單元。三種基本結構的圖示： 順序結構選擇結構循環(huán)結構的圖示： 當型(While型)循環(huán)結構 直到型(Until型)循環(huán) 3、用N-S流程圖表示算法1973年美國學者I.Nassi和B.Shneiderman提出了一種新的流程圖形式。在這種流程圖中，

5、完全去掉了帶箭頭的流程線。全部算法寫在一個矩形框內，在該框內還可以包含其它的從屬于它的框，或者說，由一些基本的框組成一個大的框。這種流程圖又稱N-S結構化流程圖 。 N-S流程圖用以下的流程圖符號： (1)順序結構(2)選擇結構(3)循環(huán)結構 用三種N-S流程圖中的基本框，可以組成復雜的N-S流程圖。圖中的A框或B框，可以是一個簡單的操作，也可以是三個基本結構之一。 A框可以是一個選擇結構 B框可以是一個循環(huán)結構 4、用偽代碼表示算法概念：偽代碼是用介于自然語言和計算機語言之間的文字和符號來描述算法。特點：它如同一篇文章一樣 ，自上而下地寫下來。每一行(或幾行)表示一個基本操作。它不用圖形符號

6、，因此書寫方便 、格式緊湊，也比較好懂，也便于向計算機語言算法(即程序)過渡。用處：適用于設計過程中需要反復修改時的流程描述。 IF x is positive THEN print x ELSE print -x也可以用漢字偽代碼表示： 若 x為正 打印 x 否則 打印 -x也可以中英文混用，如： IF x 為正 print x ELSE print -x例： “打印x的絕對值”的算法可以用偽代碼表示為： 5、用計算機語言表示算法概念：用計算機實現(xiàn)算法。計算機是無法識別流程圖和偽代碼的。只有用計算機語言編寫的程序才能被計算機執(zhí)行。因此在用流程圖或偽代碼描述出一個算法后，還要將它轉換成計算機語

7、言程序。 特點：用計算機語言表示算法必須嚴格遵循所用的語言的語法規(guī)則，這是和偽代碼不同的。用處：要完成一件工作，包括設計算法和實現(xiàn)算法兩個部分。設計算法的目的是為了實現(xiàn)算法。強調說明： 寫出了C程序，仍然只是描述了算法，并未實現(xiàn)算法。只有運行程序才是實現(xiàn)算法。應該說，用計算機語言表示的算法是計算機能夠執(zhí)行的算法。例1、從a,b中找出一個較大數(shù)賦給max。 (1)自然語言的算法描述如下： 第一步：從鍵盤輸入兩個數(shù)a和b；第二步：如果a大于b，則把a的值賦給max， 否則，把b的值賦給max；第三步：輸出max的值。例1、從a,b中找出一個較大數(shù)賦給max。 (2) 傳統(tǒng)流程圖的算法描述如下： Y

8、Nab?輸出maxmax=bmax=a結束開始輸入a,b例1、從a,b中找出一個較大數(shù)賦給max。 (3) N-S流程圖的算法描述如下： 例1、從a,b中找出一個較大數(shù)賦給max。 (4) 偽代碼的算法描述如下： begininput a and bif ab a maxelse b maxprint maxend 例1、從a,b中找出一個較大數(shù)賦給max。 (5) 計算機語言的算法描述如下： #include void main()int a,b,max;scanf(%d%d,&a,&b);if(ab) max=a;else max=b;printf(%d,max);例2、計算S=,寫出其算

9、法。(1)自然語言的算法描述如下：S1：0 SS2：1 nS3：S+n SS4：n+1 nS5：判斷n100? 是，轉S3；否則，轉S6S6：輸出S的值。(2) 傳統(tǒng)流程圖的算法描述如下：(3) N-S流程圖的算法描述如下： (4) 偽代碼的算法描述如下： begin 0 S 1 n do S+n S n+1 n while n100 print S end(5) 計算機語言的算法描述如下：#include void main()int n,S; S=0;n=1;doS=S+n;n=n+1;while(n0) /* 判斷輸入數(shù)0否 */ sum = sum + x; /* 是0，則加到累加和中

10、 */ while ( count 100 ); /* 未輸入完100個數(shù)，則重復 */ printf ( “%d” , sum ); /* 輸出累加和 */準備工作 算法步驟語句概述語言的五類語句1 函數(shù)調用語句2 表達式語句3 空語句 4 復合語句5 程序結構控制語句 語言的所有語句必須以分號 ; 結束語句概述1 函數(shù)調用語句scanf( ”%d%d”, &a , &b ); printf( %d , x );2 表達式語句x = 3;i+; 3 空語句 ;語句概述4復合語句 statement 1; statement 2; statement n; 5 程序結構控制語句條件控制（第四章

11、）循環(huán)控制（第五章）C 程序的基本結構結構化程序設計基本要求：自頂向下，模塊化設計；使用三種基本結構構造程序；程序書寫規(guī)范，切勿隨心所欲； 清晰第一，效率第二。思路清晰書寫清晰（變量名、函數(shù)名、注解等）書寫使用階梯形例 輸入m, n 計算m!和n! # include void main( ) int m, n, resm, resn; scanf(%d%d, &m, &n); resm = fact(m); /* 調用函數(shù)fact計算m!*/ resn = fact(n); /* 調用函數(shù)fact計算n!*/ printf(%d, %dn, resm, resn); /* main函數(shù)結束 */ 求階乘函數(shù)int fact( int k