算法和C程序設(shè)計(jì)

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

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

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

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

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

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

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

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

9、法。(1)自然語言的算法描述如下：S1：0 SS2：1 nS3：S+n SS4：n+1 nS5：判斷n100? 是，轉(zhuǎn)S3；否則，轉(zhuǎn)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) 計(jì)算機(jī)語言的算法描述如下：#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個(gè)數(shù)，則重復(fù) */ printf ( “%d” , sum ); /* 輸出累加和 */準(zhǔn)備工作 算法步驟語句概述語言的五類語句1 函數(shù)調(diào)用語句2 表達(dá)式語句3 空語句 4 復(fù)合語句5 程序結(jié)構(gòu)控制語句 語言的所有語句必須以分號 ; 結(jié)束語句概述1 函數(shù)調(diào)用語句scanf( ”%d%d”, &a , &b ); printf( %d , x );2 表達(dá)式語句x = 3;i+; 3 空語句 ;語句概述4復(fù)合語句 statement 1; statement 2; statement n; 5 程序結(jié)構(gòu)控制語句條件控制（第四章

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