計(jì)算機(jī)程序設(shè)計(jì)基礎(chǔ)劉倩email:2課程簡(jiǎn)介大學(xué)計(jì)算機(jī)基礎(chǔ)計(jì)算機(jī)程序設(shè)計(jì)基礎(chǔ)3《計(jì)算機(jī)程序設(shè)計(jì)基礎(chǔ)》是大學(xué)計(jì)算機(jī)基礎(chǔ)教學(xué)系列中的核心課程，主要講授程序設(shè)計(jì)語(yǔ)言（C++）的基本知識(shí)和程序設(shè)計(jì)的方法和技術(shù)（數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)等方面的初步內(nèi)容）課程實(shí)踐性很強(qiáng)，應(yīng)掌握計(jì)算機(jī)程序設(shè)計(jì)的思想和方法。初步具有在各領(lǐng)域應(yīng)用計(jì)算機(jī)的能力，并為后續(xù)課程的學(xué)習(xí)創(chuàng)造條件。課程簡(jiǎn)介4學(xué)習(xí)方法做好課前預(yù)習(xí)。利用電子教案做好課后復(fù)習(xí)，有問題應(yīng)及時(shí)解決。掌握算法，不要死摳語(yǔ)法。學(xué)到實(shí)實(shí)在在的應(yīng)用技能。本課程是一門實(shí)踐性很強(qiáng)的課程，動(dòng)手越多程序編得越好。多讀源程序、多編寫程序、多上機(jī)調(diào)試（模仿）。忌上課只聽不記、忌“紙上談兵”、忌課下不練習(xí)。5具體要求：1、上課有重點(diǎn)、有選擇的記筆記。2、請(qǐng)準(zhǔn)備一個(gè)練習(xí)本，以備隨堂練習(xí)。2、上機(jī)有準(zhǔn)備：準(zhǔn)備好課本、實(shí)驗(yàn)指導(dǎo)書、作業(yè)等。3、認(rèn)真完成老師要求的課后練習(xí)，并上機(jī)驗(yàn)證（建議多做一些計(jì)算機(jī)二級(jí)考試的模擬題）學(xué)習(xí)方法上機(jī)安排專業(yè)：地信、測(cè)控上機(jī)時(shí)間：3-17周星期四11-12節(jié)上機(jī)地點(diǎn)：X7307專業(yè)：土木上機(jī)時(shí)間：3-17周星期四11-12節(jié)上機(jī)地點(diǎn)：X7105

6實(shí)驗(yàn)報(bào)告要求提前一周布置實(shí)驗(yàn)任務(wù)，請(qǐng)?jiān)谏蠙C(jī)實(shí)驗(yàn)前完成相應(yīng)實(shí)驗(yàn)要求（設(shè)計(jì)算法、編寫程序），實(shí)驗(yàn)時(shí)驗(yàn)證程序運(yùn)行是否正確。每次實(shí)驗(yàn)完成后應(yīng)將本次實(shí)驗(yàn)的相關(guān)內(nèi)容填寫到實(shí)驗(yàn)報(bào)告中，實(shí)驗(yàn)報(bào)告請(qǐng)命名為“學(xué)號(hào)姓名-實(shí)驗(yàn)報(bào)告*”的形式，如20140001李四-實(shí)驗(yàn)報(bào)告1，完成的所有實(shí)驗(yàn)報(bào)告請(qǐng)保存在以“學(xué)號(hào)姓名”命名的文件夾中，在規(guī)定時(shí)間內(nèi)統(tǒng)一提交給班長(zhǎng)，并由班長(zhǎng)負(fù)責(zé)交給輔導(dǎo)老師。7第1章緒論計(jì)算機(jī)程序設(shè)計(jì)基礎(chǔ)9本章內(nèi)容程序程序設(shè)計(jì)程序設(shè)計(jì)方法算法算法分類及特點(diǎn)算法設(shè)計(jì)的主要原則表示算法的方法計(jì)算機(jī)算法程序設(shè)計(jì)10程序就是讓計(jì)算機(jī)完成某項(xiàng)任務(wù)的一系列操作命令的集合。計(jì)算機(jī)能夠識(shí)別的操作命令即指令程序是指令的集合1.程序設(shè)計(jì)1.1程序#include<iostream>usingnamespacestd;voidmain(){doublea,b,ccout<<"Pleaseinputtwonumbera,b";cin>>a>>b;c=a+b;cout<<"a+b="<<c<<endl;}程序示例;C++中分號(hào)表示一個(gè)語(yǔ)句(命令)1112一個(gè)程序應(yīng)包括以下兩方面的內(nèi)容：

(1)

對(duì)數(shù)據(jù)的描述。

(2)對(duì)操作的描述。1.1程序

#include<iostream>usingnamespacestd;voidmain(){doublea,b,c;cout<<"Pleaseinputtwonumbera,b";cin>>a>>b;c=a+b;cout<<"a+b="<<c<<endl;}對(duì)數(shù)據(jù)的描述對(duì)數(shù)據(jù)的操作13

一個(gè)程序應(yīng)包括以下兩方面的內(nèi)容：

(1)

對(duì)數(shù)據(jù)的描述。

(2)對(duì)操作的描述。

數(shù)據(jù)是操作的對(duì)象，操作的目的是對(duì)數(shù)據(jù)進(jìn)行加工處理，以得到期望的結(jié)果。著名的計(jì)算機(jī)科學(xué)家NikiklausWirth提出了一個(gè)公式：1.1程序程序＝數(shù)據(jù)結(jié)構(gòu)＋算法即操作步驟，也就是算法。在程序中要指定數(shù)據(jù)的類型和數(shù)據(jù)的組織形式，即數(shù)據(jù)結(jié)構(gòu)。算法設(shè)計(jì)是本課程的重點(diǎn)（難點(diǎn)）141.2程序設(shè)計(jì)

用計(jì)算機(jī)語(yǔ)言為計(jì)算機(jī)編寫程序，解決某種問題，稱之為程序設(shè)計(jì)。

程序設(shè)計(jì)過程主要包括以下幾個(gè)階段：1．分析問題2．設(shè)計(jì)算法與數(shù)據(jù)結(jié)構(gòu)3．檢查算法4．編碼實(shí)現(xiàn)（編程）5．測(cè)試和調(diào)試程序15分析問題

通過原始資料，取得對(duì)問題的一個(gè)清晰的理解，進(jìn)而確定解決問題的目標(biāo)（稱為輸出）以及實(shí)現(xiàn)該目標(biāo)所需要的條件（稱為輸入）。程序設(shè)計(jì)過程求解一元二次方程。ax2+bx+c=0的根。2．設(shè)計(jì)算法與數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)描述了問題涉及的對(duì)象之間的聯(lián)系和組織結(jié)構(gòu)；算法描述了求解問題的步驟或規(guī)則。設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)往往可以簡(jiǎn)化算法，而好的算法又使程序具有更高的效率。a,b,c為整數(shù)，x為實(shí)數(shù)163．檢查算法

使用多組樣本數(shù)據(jù)，通過手工計(jì)算，對(duì)算法的正確性進(jìn)行證明和驗(yàn)證。4．編碼實(shí)現(xiàn)

選用一種程序設(shè)計(jì)語(yǔ)言（如C++語(yǔ)言）將算法轉(zhuǎn)換成計(jì)算機(jī)能夠理解的程序。程序設(shè)計(jì)過程175．測(cè)試和調(diào)試程序

“測(cè)試”是在計(jì)算機(jī)上用樣本數(shù)據(jù)運(yùn)行程序，測(cè)試代碼的正確性?！罢{(diào)試”就是查找和排除程序錯(cuò)誤，直到能夠得到正確的運(yùn)行結(jié)果為止。

程序中的錯(cuò)誤可能是語(yǔ)法錯(cuò)，也可能是邏輯錯(cuò)誤。大多數(shù)語(yǔ)法錯(cuò)誤容易找到和改正（編譯），但邏輯錯(cuò)誤很難找到。程序設(shè)計(jì)過程18程序設(shè)計(jì)和程序編碼

用某種程序設(shè)計(jì)語(yǔ)言編寫代碼，稱為編碼（coding）。

程序設(shè)計(jì)一定要在具體的程序編碼之前完成。程序設(shè)計(jì)完成的好壞直接影響了后面的編碼質(zhì)量。191.3程序設(shè)計(jì)方法程序設(shè)計(jì)需要有一定的方法來(lái)指導(dǎo)，目前，有兩種重要的程序設(shè)計(jì)方法：結(jié)構(gòu)化的程序設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì)。

1.3.1結(jié)構(gòu)化程序設(shè)計(jì)（StructuredProgramming，簡(jiǎn)稱SP）

該方法是由E.Dijkstra等人于1972年提出來(lái)的，它建立在Bohm、Jacopini證明的結(jié)構(gòu)定理的基礎(chǔ)上。結(jié)構(gòu)定理指出：任何程序邏輯都可以用順序、選擇和循環(huán)等三種基本結(jié)構(gòu)來(lái)表示。20三種基本控制結(jié)構(gòu)順序結(jié)構(gòu)AB選擇結(jié)構(gòu)ABP循環(huán)結(jié)構(gòu)AP21

用SP方法設(shè)計(jì)的程序只存在三種基本結(jié)構(gòu)，程序代碼的空間順序和程序執(zhí)行的時(shí)間順序基本一致，程序結(jié)構(gòu)清晰。結(jié)構(gòu)化的程序設(shè)計(jì)仍然是廣泛使用的一種程序設(shè)計(jì)方法。1.3.1結(jié)構(gòu)化程序設(shè)計(jì)方法22結(jié)構(gòu)化程序設(shè)計(jì)方法的設(shè)計(jì)思路

自頂向下、逐步求精。“自頂向下”

是將復(fù)雜、大的問題劃分為小問題，找出問題的關(guān)鍵、重點(diǎn)所在，然后用精確的思維定性、定量地去描述問題?！爸鸩角缶?/p>

復(fù)雜問題經(jīng)抽象化處理變?yōu)橄鄬?duì)比較簡(jiǎn)單的問題。經(jīng)若干步抽象（精化）處理，最后到求解域中只是比較簡(jiǎn)單的編程問題。23示例學(xué)生信息管理系統(tǒng)系統(tǒng)管理數(shù)據(jù)管理系統(tǒng)幫助退出系統(tǒng)修改密碼添加用戶刪除用戶學(xué)生登記學(xué)生查詢檔案管理按姓名查詢按專業(yè)查詢按宿舍查詢關(guān)于241.3.2面向?qū)ο蟮某绦蛟O(shè)計(jì)

面向?qū)ο蟮某绦蛟O(shè)計(jì)是另一種重要的程序設(shè)計(jì)方法。面向?qū)ο蟮某绦蛟O(shè)計(jì)方法認(rèn)為現(xiàn)實(shí)世界是由對(duì)象組成的。面向?qū)ο蟮某绦蛟O(shè)計(jì)方法解決某個(gè)問題，首先要確定這個(gè)問題是由哪些對(duì)象組成的。

25面向?qū)ο蟮母拍顚傩裕褐笇?duì)象已知的狀態(tài)。方法：指對(duì)象的行為或動(dòng)作，即對(duì)象可以執(zhí)行的操作。

對(duì)象包括兩個(gè)因素：一是數(shù)據(jù)（屬性）；二是需要進(jìn)行的操作（方法）。對(duì)象就是一個(gè)包含數(shù)據(jù)以及與這些數(shù)據(jù)有關(guān)的操作的集合。26面向?qū)ο蟮母拍睢惉F(xiàn)實(shí)生活中的對(duì)象可以將現(xiàn)實(shí)生活中的對(duì)象經(jīng)過抽象，映射為程序中的對(duì)象。對(duì)象在程序中是通過類（class）來(lái)描述的。class

Car{intcolor_number;intdoor_number;intspeed;

voidbrake(){…}voidspeedUp(){…}voidslowDown(){…}}

屬性(數(shù)據(jù))方法(操作)27面向?qū)ο蟮母拍睢愵惔砹艘慌鷮?duì)象的共性和特征。類是對(duì)象的抽象，而對(duì)象是類的具體實(shí)例。Carcar1;Carcar2;…

…CarcarN;……28

下課了。。。休息一會(huì)兒……..實(shí)踐探索2.計(jì)算機(jī)算法算法解決某類具體問題的方法和步驟。計(jì)算機(jī)算法利用計(jì)算機(jī)解決某類問題的方法和步驟2.1算法基本概念292.2計(jì)算機(jī)算法的分類數(shù)值算法求數(shù)值解，例如求方程的根，求一個(gè)函數(shù)的定積分等。非數(shù)值算法

包括的面十分廣泛，最常見的是事務(wù)管理領(lǐng)域，例如圖書檢索、人事管理、行車調(diào)度管理等。302.3算法的特征一個(gè)算法應(yīng)具的五個(gè)重要特征有窮性

總是可以在執(zhí)行有限步有限的時(shí)間內(nèi)完成確定性每條指令要有確切的含義，對(duì)于相同的輸入只能得出相同的結(jié)果可行性算法中描述的所有操作都可通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)輸入一個(gè)算法可有零個(gè)或多個(gè)輸入輸出一個(gè)算法可以有一個(gè)或多個(gè)輸出。任何一個(gè)算法至少應(yīng)有一個(gè)輸出312.4算法設(shè)計(jì)的主要原則正確性算法應(yīng)滿足具體問題的要求；可讀性一個(gè)可讀性好的算法有助于對(duì)算法的理解，易于調(diào)試和修改；健壯性當(dāng)輸入非法數(shù)據(jù)時(shí)，算法也能夠作出適當(dāng)?shù)姆从郴蛱幚?，而不?huì)產(chǎn)生一些莫名其妙的結(jié)果，更不會(huì)出現(xiàn)死機(jī)、系統(tǒng)崩潰等情況；高效性算法的效率與算法占用計(jì)算機(jī)設(shè)備資源成反比，而最突出的就是計(jì)算機(jī)的運(yùn)行時(shí)間和計(jì)算機(jī)的存儲(chǔ)空間。占用時(shí)間越短效率越高，占用內(nèi)存空間越少效率越高。322.5表示算法的方法表示算法可用不同的方法：自然語(yǔ)言傳統(tǒng)流程圖結(jié)構(gòu)化流程圖（N-S流程圖）偽代碼332.5.1用自然語(yǔ)言表示算法自然語(yǔ)言是人們?nèi)粘Ｊ褂玫恼Z(yǔ)言，用自然語(yǔ)言表示算法通俗易懂；但文字冗長(zhǎng)，含義往往不太嚴(yán)格，容易出現(xiàn)“歧義性”，要根據(jù)上下文才能判斷其正確含義。而且用自然語(yǔ)言來(lái)描述包含分支和循環(huán)的算法，很不方便。因此，除了一些簡(jiǎn)單的問題外，一般不用自然語(yǔ)言描述算法。34示例：一元二次方程求根S1：計(jì)算方程的判別式△=b2-4acS2：如判別式小于零，則輸出方程沒有實(shí)根的信息S3：否則，計(jì)算方程的實(shí)根，并輸出計(jì)算結(jié)果。35S1：先求1×2，得到結(jié)果2。S2：將S1得到的積2再乘以3，得到結(jié)果6。S3：將6再乘以4，得24。S4：將24乘以5，得120。示例：計(jì)算5！分析：

5!=1×2×3×4×5

思考如何計(jì)算n!？36示例：計(jì)算n!5!=1×2×3×4×5

積(2)積(6)積(24)積(120)反復(fù)（循環(huán)）求積?、佗冖邰軐⒚恳徊降某朔e放在變量t(存儲(chǔ)空間)中,讓其作為被乘數(shù)；另設(shè)一個(gè)變量i，作為乘數(shù)，乘數(shù)每次加1。被乘數(shù)t的初始值為1，乘數(shù)i的初始值為1。輸入n的值。積（中間結(jié)果）t變量(內(nèi)存)37示例：計(jì)算n!設(shè)t為被乘數(shù)，i為乘數(shù)

S1：輸入n值

S2：將1t（表示賦值，注意雙線箭頭方向）S3：將1iS4：將t×itS5：將i＋1iS6：若i

n成立，返回重新執(zhí)行S4，以及其后的步驟S5、S6；否則執(zhí)行S7S7：輸出t，算法結(jié)束如何理解？如果要求累加和，如1+2+3+…+n，該如何修改算法？S2：將0

s

S4：將s+is38課后練習(xí)請(qǐng)認(rèn)真閱讀課件《怎樣學(xué)習(xí)C++程序設(shè)計(jì)》請(qǐng)認(rèn)真預(yù)習(xí)“實(shí)驗(yàn)一”的相關(guān)資料，為第一次實(shí)驗(yàn)做好充分準(zhǔn)備請(qǐng)用自然語(yǔ)言描述下列問題的算法計(jì)算1！+2！+3！+……+n!39問題：對(duì)一個(gè)大于或等于3的正整數(shù)，判斷它是不是一個(gè)素?cái)?shù)。所謂素?cái)?shù)（質(zhì)數(shù)），是指除了1和該數(shù)本身外不能被其他任何整數(shù)整除的數(shù)。示例：素?cái)?shù)問題判斷一個(gè)數(shù)n（n≥3）是否為素?cái)?shù)的算法描述：將n作為被除數(shù)，將2到（n-1）之間的各個(gè)整數(shù)輪流作為除數(shù)去除以n，如果都不能被整除，則n為素?cái)?shù)。循環(huán)如何判斷一個(gè)數(shù)能被另一數(shù)整除？設(shè)置變量n作為被除數(shù)設(shè)置變量i作為除數(shù)，i的取值從2變化到n-1設(shè)置變量r，r為余數(shù)，如果r=0，則除盡40S1：輸入n的值(n是需要判斷的數(shù)，作為被除數(shù))S2：2i（i為除數(shù)，初值為2）S3：n/i的余數(shù)r(變量r保存余數(shù))S4：如果r=0，則打印n“不是素?cái)?shù)”，算法結(jié)束，否則執(zhí)行S5。S5：i+1iS6：如果in-1，返回重新執(zhí)行S3，以及其后的步驟；否則執(zhí)行S7。S7：打印n“是素?cái)?shù)”，算法結(jié)束。示例：素?cái)?shù)問題為什么？41分析問題假定n不是素?cái)?shù)，則可表示為：也就是說，如果n不是素?cái)?shù)，一定能找到一個(gè)整數(shù)i能整除n，于是，n不必被2到n-1之間的整數(shù)除，只需被2到之間或2到n/2之間的整數(shù)除即可。S6步驟可改為：S6：如果i≤(或n/2），返回重新執(zhí)行S3，以及其后的步驟；否則執(zhí)行S7。S7：打印n“是素?cái)?shù)”，算法結(jié)束。42修改后的算法描述S1：輸入n的值S2：2iS3：n/i的余數(shù)rS4：如果r=0，則打印n“不是素?cái)?shù)”，算法結(jié)束，否則執(zhí)行S5。S5：i+1iS6：如果i≤(或n/2），返回重新執(zhí)行S3，以及其后的步驟；否則執(zhí)行S7。S7：打印n“是素?cái)?shù)”，算法結(jié)束。432.傳統(tǒng)流程圖P6流程圖是用一些圖框表示各種類型的操作用圖形表示算法，直觀形象，易于理解。

美國(guó)國(guó)家標(biāo)準(zhǔn)化協(xié)會(huì)ANSI(AmericanNationalStandardInstitute)規(guī)定了一些常用的流程圖符號(hào)。起止框輸入輸出框判斷框處理框聯(lián)結(jié)點(diǎn)注釋框或流程線44所有的計(jì)算機(jī)程序都是三種基本結(jié)構(gòu)組合而成：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。

結(jié)構(gòu)化流程圖表示P7順序結(jié)構(gòu)AB選擇結(jié)構(gòu)ABP循環(huán)結(jié)構(gòu)AP45三種基本結(jié)構(gòu)的特點(diǎn)以上三種基本結(jié)構(gòu)，有以下共同點(diǎn)：

只有一個(gè)入口；只有一個(gè)出口；結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會(huì)被執(zhí)行；

結(jié)構(gòu)內(nèi)不存在“死循環(huán)”。順序結(jié)構(gòu)AB選擇結(jié)構(gòu)ABP循環(huán)結(jié)構(gòu)AP46順序結(jié)構(gòu)AB程序流程：按語(yǔ)句出現(xiàn)的先后順序依次執(zhí)行。用途：解決順序性的計(jì)算或處理問題。47選擇結(jié)構(gòu)程序流程：先做判斷，根據(jù)判斷做出選擇。用途：當(dāng)需要程序基于選擇或比較的結(jié)果選擇兩條路徑中的一條時(shí)，可以使用選擇結(jié)構(gòu)或稱為決策結(jié)構(gòu)。PB成立不成立abAP成立不成立abA48循環(huán)結(jié)構(gòu)用途：需要重復(fù)執(zhí)行的過程用此結(jié)構(gòu)，可使算法容易編寫，且結(jié)構(gòu)清晰。直到型循環(huán)P成立不成立abA當(dāng)型循環(huán)PA成立不成立ab49循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)從a點(diǎn)（入口）進(jìn)入，首先對(duì)給出的條件P進(jìn)行判斷，如果P成立，則執(zhí)行A操作；執(zhí)行完A操作后重新對(duì)條件P進(jìn)行判斷，如果P仍然成立，再次執(zhí)行A操作；如此反復(fù)“判斷→執(zhí)行”，直到條件P不成立為止，最后從b點(diǎn)（出口）脫離該結(jié)構(gòu)。當(dāng)型循環(huán)PA成立不成立ab50循環(huán)結(jié)構(gòu)直到型循環(huán)從a點(diǎn)（入口）進(jìn)入，首先執(zhí)行A操作，然后對(duì)給出的條件P進(jìn)行判斷，如果P不成立，則執(zhí)行A操作；執(zhí)行完A操作后重新對(duì)條件P進(jìn)行判斷，如果P仍然不成立，再次執(zhí)行A操作；如此反復(fù)“判斷→執(zhí)行”，直到條件P成立為止，最后從b點(diǎn)（出口）脫離該結(jié)構(gòu)。直到型循環(huán)P成立不成立abA51循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)是先判斷后循環(huán)；直到型循環(huán)是先執(zhí)行一次循環(huán)體(至少執(zhí)行一次)，然后再判斷是否繼續(xù)循環(huán)。當(dāng)型循環(huán)是在條件滿足時(shí)才執(zhí)行循環(huán)體，而直到型循環(huán)是在條件不滿足時(shí)才執(zhí)行循環(huán)體．因此在掌握使用這兩種循環(huán)時(shí)必須抓住這兩條區(qū)別。當(dāng)型循環(huán)和直到型循環(huán)是可以互相轉(zhuǎn)換的，凡用當(dāng)型循環(huán)處理的問題，用直到型循環(huán)可解決，反之亦然。當(dāng)型循環(huán)PA成立不成立ab直到型循環(huán)P成立不成立abA52示例問題：傳統(tǒng)流程圖描述求5!的算法。5!=1×2×3×4×5

53傳統(tǒng)流程圖設(shè)t為被乘數(shù)，i為乘數(shù)

S1：將1tS2：將1iS3：將t×itS4：將i＋1iS5：若i

5成立，返回重新執(zhí)行S3，以及其后的步驟S4、S5；否則執(zhí)行S6S6：輸出t，算法結(jié)束1

t開始1ii>5t×iti+1i輸出t成立不成立結(jié)束自然語(yǔ)言描述若i>5不成立，直到型循環(huán)循環(huán)結(jié)構(gòu)54傳統(tǒng)流程圖

直到型循環(huán)1

t開始1ii>5t×iti+1i輸出t成立不成立結(jié)束1

t開始1it×iti+1i輸出t結(jié)束當(dāng)型循環(huán)i<=5成立不成立55傳統(tǒng)流程圖N開始輸入n2in/i的余數(shù)rr=0?Ni+1ii>

Y打印“是素?cái)?shù)”Y打印“不是素?cái)?shù)”結(jié)束課堂練習(xí)：素?cái)?shù)問題自然語(yǔ)言描述S1：輸入n的值S2：2iS3：n/i的余數(shù)rS4：如果r=0，則打印n“不是素?cái)?shù)”，算法結(jié)束，否則執(zhí)行S5。S5：i+1iS6：如果i≤(或n/2）成立，返回重新執(zhí)行S3，以及其后的步驟；否則執(zhí)行S7。S7：打印n“是素?cái)?shù)”，算法結(jié)束。56流程圖N開始輸入n2in/i的余數(shù)rr=0?Ni+1ii>

Y打印“是素?cái)?shù)”Y打印“不是素?cái)?shù)”結(jié)束i<=N不是素?cái)?shù)n是素?cái)?shù)YN結(jié)束2ii<=n/i的余數(shù)r=0？i+1iYNNY開始輸入n請(qǐng)問流程圖有幾條結(jié)束路徑？改成“當(dāng)型循環(huán)”結(jié)構(gòu)此時(shí)i的值？此時(shí)i的值？573.N-S流程圖1971年由兩位美國(guó)學(xué)者I．Nassi和B．Shneiderman提出了一種新的流程圖形式，這種流程圖完全去掉了帶箭頭的流程線，稱為N-S流程圖。AB順序結(jié)構(gòu)ABP不成立成立選擇結(jié)構(gòu)A當(dāng)PA直到P循環(huán)結(jié)構(gòu)58用N-S流程圖表示求5!的算法1t1ii>5輸出tt×iti+1i直到型循環(huán)1

t開始1ii>5t×iti+1i輸出t成立不成立結(jié)束59用N-S流程圖表示判斷素?cái)?shù)的算法傳統(tǒng)流程圖N開始輸入n2in/i的余數(shù)rr=0?Ni+1ii>

Y打印“是素?cái)?shù)”Y打印“不是素?cái)?shù)”結(jié)束輸入nn%ir2i

打印“是素?cái)?shù)”當(dāng)i>

r=0?Y打印“不是素?cái)?shù)”，并退出循環(huán)Ni+1iN-S流程圖%為取余運(yùn)算，求n/i的余數(shù)60課堂練習(xí)1.請(qǐng)將求的算法用傳統(tǒng)流程圖表示出來(lái)觀察表達(dá)式與累加求和1+2+…+100的聯(lián)系每項(xiàng)為倒數(shù)，運(yùn)算符號(hào)為“+”、“-”交替出現(xiàn)。如何表示倒數(shù)？如何表示交替出現(xiàn)的加減符號(hào)？1/i1sign;sign*(-1)sign(1/i)*signterm開始0sum1ii+1ii>100N輸出sum結(jié)束Ysum+isum1sign(-1)*signsignsign*(1/i)termsum+termsum61課堂練習(xí)1.請(qǐng)將求的算法用N-S流程圖表示出來(lái)0sum1i1signsign*(1/i)termsum+termsum(-1)*signsigni+1i

輸出sumi>100開始0sum1i1sign(-1)*signsignsign*(1/i)termsum+termsumi+1ii>100N輸出sum結(jié)束Y624.偽代碼

偽代碼是用介于自然語(yǔ)言與計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來(lái)描述算法。自上而下地書寫，每一行(或幾行)表示一個(gè)基本操作。因此書寫方便，格式緊湊，也比較好懂也便于向計(jì)算機(jī)高級(jí)語(yǔ)言。

inputni←2whilei≤dor←n/i的余數(shù)ifr=0

thenbreak

elsei←i+1

ifi>

thenprint“是素?cái)?shù)”

elseprint“非素?cái)?shù)”素?cái)?shù)問題的算法偽代碼631.7算法設(shè)計(jì)策略（自學(xué)P9~11）算法的設(shè)計(jì)策略就是算法設(shè)計(jì)中運(yùn)用的科學(xué)思維方法。枚舉法遞推法遞歸法分治法64枚舉法枚舉法也稱為窮舉法，其設(shè)計(jì)思想是：在有限的范圍中，列舉和檢驗(yàn)所有可能的結(jié)果，從中找出那些符合要求的候選解作為問題的解。問題：設(shè)有算式ABCD-CDC=ABC，其中的A、B、C、D均為一位非負(fù)整數(shù)，要求找出A、B、C、D各值。

思路分析：設(shè)正整數(shù)A、B、C、D，A和C的取值范圍應(yīng)是[1，9]，B和D的取值范圍應(yīng)是[0，9]，分別對(duì)相應(yīng)范圍中的每一個(gè)數(shù)值進(jìn)行檢測(cè)，輸出滿足條件（1000×A＋100×B＋10×C＋D）-（100×C＋10×D＋C）=（100×A＋10×B＋C）的數(shù)值。65遞推法

遞推法的設(shè)計(jì)思想是：利用問題本身所具有的一種遞推關(guān)系求問題的解，即從已求得的規(guī)模為1，2，…，n-1的一系列解，構(gòu)造出問題規(guī)模為n的解。問題：計(jì)算n!思路分析：1!=1，由1!×2得2!→由2!×3得3!→…由(n-1)!×n得n!。66遞歸法

遞歸法的設(shè)計(jì)思想是：為求解規(guī)模較大的問題，設(shè)法將它分解成規(guī)模較小的問題，然后從這些小問題的解方便地構(gòu)造出大問題的解，并且這些規(guī)模較小的問題也能采用同樣的分解和綜合方法，分解成規(guī)模更小的問題，并從這些更小問題的解構(gòu)造出規(guī)模較大問題的解。特別地，當(dāng)規(guī)模N=1時(shí)，能直接得解(結(jié)束遞歸的條件)。問題：計(jì)算斐波那契(Fibonacci)數(shù)列的第n項(xiàng)函數(shù)fib(n)。斐波那契數(shù)列為：1,1,2,3,5,8,13,……67遞歸法思路分析：f(n)=f(n-1)+f(n-2)(n>1)，f(0)=f(1)=1遞歸法的執(zhí)行過程分遞推和回歸兩個(gè)階段。在遞推階段，把復(fù)雜問題的求解遞推到較簡(jiǎn)單問題的求解。例如，計(jì)算fib(n)→計(jì)算fib(n-1)和fib(n-2)→計(jì)算fib(n-3