1、2程序的靈魂一算法12.1 算法的概念12.2 簡(jiǎn)單算法舉例12.3 算法的特性42.4 怎樣表示一個(gè)算法42.4.1 用自然語(yǔ)言表示算法42.4.2 用流程圖表示算法42.4.3 三種基本結(jié)構(gòu)和改進(jìn)的流程圖82.4.4 用N-S流程圖表示算法92.4.5 用偽代碼表示算法102.4.6 用計(jì)算機(jī)語(yǔ)言表示算法112.5 結(jié)構(gòu)化程序設(shè)計(jì)方法112程序的靈魂一算法一個(gè)程序應(yīng)包拾： 對(duì)數(shù)據(jù)的描述。在程序中要指定數(shù)據(jù)的類型和數(shù)據(jù)的組織形式，即數(shù)據(jù)結(jié)構(gòu)(datastmcture)。 對(duì)操作的描述。即操作步驟，也就是算法(algorithm)。NikiklausWuth提出的公式：數(shù)據(jù)結(jié)構(gòu)+算法=程序教材

2、認(rèn)為：*程序=算法+數(shù)據(jù)結(jié)構(gòu)+程序設(shè)計(jì)方法+語(yǔ)言工具和環(huán)境這4個(gè)方面是一個(gè)程序涉及人員所應(yīng)具備的知識(shí)。本課程的目的是使同學(xué)知道怎樣編寫(xiě)一個(gè)C程序，進(jìn)行編寫(xiě)程序的初步訓(xùn)練，因此,只介紹算法的初步知識(shí)。2.1算法的概念做任何事情都有一定的步驟。為解決一個(gè)問(wèn)題而采取的方法和步驟，就稱為算法。 計(jì)算機(jī)算法：計(jì)算機(jī)能夠執(zhí)行的算法。 計(jì)算機(jī)算法可分為兩大類： 數(shù)值運(yùn)算算法：求解數(shù)值： 非數(shù)值運(yùn)算算法：事務(wù)管理領(lǐng)域。2.2簡(jiǎn)單算法舉例【例2.1求1X2X3X4X5。第頁(yè)靳潤(rùn)昭C語(yǔ)言教程講義2001年2月17口最原始方法：步驟1:先求1X2,得到結(jié)果2。步驟2：將步驟1得到的乘枳2乘以3,得到結(jié)果6。步驟3：

3、將6再乘以4,得24。步驟4：將24再乘以5,得120。這樣的算法雖然正確，但太繁。改進(jìn)的算法：S1:使t=lS2:使1=2S3:使txi,乘積仍然放在在變量t中，可表示為txi-tS4:使1的值+1,即1+1iS5:如果iW5,返回重新執(zhí)行步驟S3以及其后的S4和S5：否則，算法結(jié)束。如果計(jì)算100!只需將S5:若iW5改成iWlOO即可。如果該求1X3X5X7X9X11,算法也只需做很少的改動(dòng)：SI:l-*tS2:3-*iS3:txi-*tS4:i+2-*tS5:若iCll,返回S3,否則，結(jié)束。該算法不僅正確，而且是計(jì)算機(jī)較好的算法，因?yàn)橛?jì)算機(jī)是高速運(yùn)算的自動(dòng)機(jī)器，實(shí)現(xiàn)循壞輕而易舉。思考

4、：若將S5寫(xiě)成：S5:若1<11,返回S3;否則，結(jié)束?！纠?.2】有50個(gè)學(xué)生，要求將他們之中成績(jī)?cè)?0分以上者打印出來(lái)。如果，n表示學(xué)生學(xué)號(hào)，山表示第個(gè)學(xué)生學(xué)號(hào)；g表示學(xué)生成績(jī)，旨表示第個(gè)學(xué)生成績(jī)；則算法可表示如下：SI:l-*iS2:如果gi$80,則打印m和g”否則不打印S3:i+liS4:若iW50,返回S2,否則，結(jié)束?！纠?.3】判定20002500年中的每一年是否閏年，將結(jié)果輸出。潤(rùn)年的條件：1）能被4整除，但不能被100整除的年份；2）能被100整除，又能被400整除的年份；設(shè)y為被檢測(cè)的年份，則算法可表示如下：Sl：2000->yS2:若y不能被4整除，貝IJ輸

5、出y“不是閏年”，然后轉(zhuǎn)到S6S3:若y能被4整除，不能被100整除，則輸出y“是閏年”,然后轉(zhuǎn)到S6S4:若y能被100整除，又能被400整除，輸出y“是閏年”否則輸出y“不是閏年”，然后轉(zhuǎn)到S6S5:輸出y“不是閏年”。S6:y+l->vS7:當(dāng)yW2500時(shí)，返回S2繼續(xù)執(zhí)行,否則，結(jié)束。11111'I11-卜【例2.4】求23499100。算法可表示如下：SI:sigh=lS2:sum=lS3:deno=2S4:sigh=(I)xsighS5:term=sighx(l/deno)S6:term=sum+termS7:deno=deno+1S8:若denolOO,返回S4；

6、否則,結(jié)束?！纠?.5】對(duì)一個(gè)人于或等于3的正整數(shù)，判斷它是不是一個(gè)素?cái)?shù)。算法可表示如下：S1:輸入n的值S2:i=2S3:n被1除，得余數(shù)rS4:如果尸0,表示n能被1整除，則打印n“不是素?cái)?shù)”，算法結(jié)束；否則執(zhí)行S5S5:i+1iS6:如果in-1,返回S3：否則打印n“是素?cái)?shù)”：然后算法結(jié)束。改進(jìn)：S6:如果iW亦，返回S3：否則打印n“是素?cái)?shù)”；然后算法結(jié)束。2.3算法的特性 有窮性：一個(gè)算法應(yīng)包含有限的操作步驟而不能是無(wú)限的。 確定性：算法中每一個(gè)步驟應(yīng)當(dāng)是確定的，而不能應(yīng)當(dāng)是含糊的、模棱兩可的。 有零個(gè)或多個(gè)輸入。 有一個(gè)或多個(gè)輸出。 有效性：算法中每一個(gè)步驟應(yīng)當(dāng)能有效地執(zhí)行，并得

7、到確定的結(jié)果。對(duì)于程序設(shè)計(jì)人員，必須會(huì)設(shè)計(jì)算法，并根據(jù)算法寫(xiě)出程序。2.4怎樣表示一個(gè)算法241用自然語(yǔ)言表示算法除了很簡(jiǎn)單的問(wèn)題，一般不用自然語(yǔ)言表示算法。2.4.2用流程圖表示算法流程圖表示算法，直觀形象，易于理解。起Lt框輸入輸出框判斷框遊框舷線連摻點(diǎn)第6頁(yè)靳潤(rùn)昭C語(yǔ)言教程講義2001年2月17口第#頁(yè)靳潤(rùn)昭C語(yǔ)言教程講義2001年2月17口【例2.6將例2.1求5!的算用流程圖表示。第#頁(yè)靳潤(rùn)昭C語(yǔ)言教程講義2001年2月17口第#頁(yè)靳潤(rùn)昭C語(yǔ)言教程講義2001年2月17口第#頁(yè)靳潤(rùn)昭C語(yǔ)言教程講義2001年2月17口第#頁(yè)靳潤(rùn)昭C語(yǔ)言教程講義2001年2月17口【例2.7將例2.2的

8、算用流程圖表示。第#頁(yè)靳潤(rùn)昭C語(yǔ)言教程講義2001年2月17口第7頁(yè)靳潤(rùn)昭C語(yǔ)言教程講義2001年2月17口【例2.8將例2.3判定閏年的算用流程圖表示。第#頁(yè)靳潤(rùn)昭C語(yǔ)言教程講義2001年2月17口11111【例2.9】將例2.4求23499100的算用流程圖表示。一個(gè)流程圖包拾：1. 表示相應(yīng)操作的框；2. 帶箭頭的流程線；3. 框內(nèi)外必要的文字說(shuō)明。2.4.3三種基本結(jié)構(gòu)和改進(jìn)的流程圖1. 順序結(jié)構(gòu)：2. 選擇結(jié)構(gòu):3. 循壞結(jié)構(gòu)三種基本結(jié)構(gòu)的共同特點(diǎn)： 只有一個(gè)入口； 只有一個(gè)出口； 結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會(huì)被執(zhí)行到： 結(jié)構(gòu)內(nèi)不存在“死循環(huán)”。2.4.4用NS流程圖表示算法1973年美

9、國(guó)學(xué)者提出了一種新型流程圖：N-S流程圖。順序結(jié)構(gòu)：第12頁(yè)靳潤(rùn)昭C語(yǔ)言教程講義2001年2月17口第13頁(yè)靳潤(rùn)昭C語(yǔ)言教程講義2001年2月17口選擇結(jié)構(gòu):循壞結(jié)構(gòu):當(dāng)P1成立AA直到Pl成立IF打E卩ni,gji+i直到i>50245用偽代碼表示算法偽代碼使用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來(lái)描述算法。第14頁(yè)靳潤(rùn)昭C語(yǔ)言教程講義2001年2月17口2.4.6用計(jì)算機(jī)語(yǔ)言表示算法 我們的任務(wù)是用計(jì)算機(jī)解題，就是用計(jì)算機(jī)實(shí)現(xiàn)算法； 用計(jì)算機(jī)語(yǔ)言表示算法必須嚴(yán)格遵循所用語(yǔ)言的語(yǔ)法規(guī)則。【例2.20】求1X2X3X4X5用C語(yǔ)言表示。mainQmti,t;t=l；1=2；while(i<=5)1=1+1;pnntf(“d篤t);【例2.21】求級(jí)數(shù)的值。mainQintsig