1、大學(xué)計(jì)算機(jī)基礎(chǔ)第5章 算法與程序設(shè)計(jì)基礎(chǔ)5.1 算法基礎(chǔ)一、算法的概念1. 用計(jì)算機(jī)解決問題時(shí)，計(jì)算機(jī)執(zhí)行的任何操作或計(jì)算都是按指定順序執(zhí)行一系列指令的結(jié)果。因此在用計(jì)算機(jī)解題前，需要將解題方法轉(zhuǎn)換成一系列具體的、在計(jì)算機(jī)上可以執(zhí)行的步驟，這些步驟和方法就是算法，而解決問題的過程就是算法實(shí)現(xiàn)的過程。2. 算法的基本特征輸入（Input）輸出（Output）可行性（Effectiveness）確定性（Definiteness）有窮性（Finiteness）二、算法的表示自然語言法傳統(tǒng)流程圖N-S流程圖偽代碼法【例】輸入3個(gè)數(shù)，打印輸出其中最大的數(shù)。下面分別用4種方法來描述這個(gè)問題的算法。三、 算

2、法的評(píng)價(jià)在算法正確的前提下，對(duì)一個(gè)算法的評(píng)價(jià)我們主要從時(shí)間復(fù)雜度和空間復(fù)雜度兩方面來考慮。 1. 時(shí)間復(fù)雜度時(shí)間復(fù)雜度是指一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間。一個(gè)算法的耗時(shí)與算法中語句的執(zhí)行次數(shù)成正比。 2. 空間復(fù)雜度空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲(chǔ)空間的大小。在許多情況下各種因素是互相制約的。5.2 程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)是指設(shè)計(jì)、編制、調(diào)試程序的方法和過程。一、計(jì)算機(jī)程序的組成程序程序 = 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) + 算法算法一個(gè)程序包括以下兩個(gè)方面的內(nèi)容： 對(duì)數(shù)據(jù)的描述指定程序要處理的數(shù)據(jù)類型和數(shù)據(jù)的組織形式，也就是常說的數(shù)據(jù)結(jié)構(gòu)。 對(duì)操作的描述是指對(duì)數(shù)據(jù)的操作步驟。二、程序設(shè)計(jì)方法1. 結(jié)構(gòu)

3、化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)采用自頂向下、逐步求精的方法。結(jié)構(gòu)化程序有順序、選擇、循環(huán)三種基本結(jié)構(gòu)。1）順序結(jié)構(gòu)2）選擇結(jié)構(gòu)3）循環(huán)結(jié)構(gòu)2. 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法（Object Oriented Pro-gramming, OOP）面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中，問題分解不再是采用自頂向下、逐步求精的結(jié)構(gòu)化方法，而是將問題分解為對(duì)象。 對(duì)象的數(shù)據(jù)（稱為屬性） 作用于數(shù)據(jù)上的操作（稱為方法） 我們?cè)賹?duì)象的屬性和方法封裝成一個(gè)整體，稱為類。 從本質(zhì)上說，結(jié)構(gòu)化方法強(qiáng)調(diào)的是如何做（How to do）？強(qiáng)調(diào)代碼如何實(shí)現(xiàn)。而面向?qū)ο蠓椒◤?qiáng)調(diào)的是做什么（What to do）？程序設(shè)計(jì)過程中大量的工作是在

4、創(chuàng)建各種類，設(shè)計(jì)類中的對(duì)象具有什么屬性、可以執(zhí)行什么操作。在類中將屬性和方法進(jìn)行封裝后，對(duì)象間通過消息傳遞機(jī)制實(shí)現(xiàn)各種功能的調(diào)用。 面向?qū)ο蟮募夹g(shù)進(jìn)一步縮小了人腦與電腦思維方式上的差異，并可以使人們?cè)诶糜?jì)算機(jī)解決問題時(shí)，不是將主要精力花在如何描述解決問題的過程上(即編程上)，而是花在對(duì)要解決問題的分析上。三、程序設(shè)計(jì)語言1. 機(jī)器語言機(jī)器語言是由0或1二進(jìn)制代碼按一定規(guī)則組成的、能被機(jī)器直接理解和執(zhí)行的指令集合。2. 匯編語言匯編語言采用助記符來表示機(jī)器指令代碼或地址。3. 高級(jí)語言高級(jí)語言是一種接近自然語言和數(shù)學(xué)公式的程序設(shè)計(jì)語言。5.3結(jié)構(gòu)化程序設(shè)計(jì)初步結(jié)構(gòu)化程序設(shè)計(jì)初步一、數(shù)據(jù)的類型與

5、本質(zhì)在計(jì)算機(jī)世界中，數(shù)據(jù)是計(jì)算機(jī)操作的對(duì)象，是能被計(jì)算機(jī)識(shí)別、存儲(chǔ)并能被計(jì)算機(jī)程序所處理的符號(hào)集合。計(jì)算機(jī)中的數(shù)據(jù)不僅包含整型、實(shí)型等常見的數(shù)值型數(shù)據(jù)，還包括字符、字符串、圖形、圖像、聲音、視頻等非數(shù)值型數(shù)據(jù)。1. 數(shù)據(jù)類型決定數(shù)值的范圍2. 數(shù)據(jù)類型決定數(shù)據(jù)的存儲(chǔ)方式3. 數(shù)據(jù)類型決定數(shù)據(jù)的操作二、結(jié)構(gòu)化程序設(shè)計(jì)案例編寫Hello程序1. Raptor實(shí)現(xiàn) 在Raptor中提供將流程圖轉(zhuǎn)換成程序設(shè)計(jì)語言代碼的功能，通過“Generate”菜單可以將Hello.rap程序轉(zhuǎn)換成不同的程序設(shè)計(jì)語言，如C+、C#、Java 、Ada等源程序。轉(zhuǎn)換成的C+代碼如下：#include #include

6、 using namespace std;int main() cout Hello World! endl; return 0;轉(zhuǎn)換成的Java代碼如下：* * NAME: * DATE: * FILE: * COMMENTS: */public class hello extends eecs.Gui public static void main(String args) printLine(Hello World!); / close main / close hello2. c語言實(shí)現(xiàn)#include int main()printf(“Hello World!”);return 0

7、;5.4 結(jié)構(gòu)化程序結(jié)構(gòu)化程序設(shè)計(jì)設(shè)計(jì)案例案例一、順序結(jié)構(gòu)案例1簡(jiǎn)單加法計(jì)算器 1. 問題描述：在此計(jì)算器上完成加法計(jì)算 2. 算法分析：要進(jìn)行計(jì)算，需要完成 ：（1）. 從鍵盤上輸入任意兩個(gè)數(shù)；（2）. 由計(jì)算機(jī)計(jì)算并輸出兩數(shù)之和。 3. 相應(yīng)的算法設(shè)計(jì)為： 輸入兩個(gè)數(shù)； 計(jì)算兩數(shù)之和； 輸出兩數(shù)之和； 程序結(jié)束。 4. 流程圖.對(duì)應(yīng)的源程序代碼：（）c語言源程序： #includeint main()int x,y,sum; printf(“請(qǐng)輸入兩個(gè)數(shù)n”);scanf(“%d,%d”,&x,&y);sum=x+y;printf(“%d+%d=%dn”,x,y,sum);

8、（）（）VB語言源程序：語言源程序：Private Sub Button1_Click() Handles Button1.Click Dim a As Integer, b As Integer, sum As Integer a = Val(TextBox1.Text) b = Val(TextBox2.Text) sum = a + b TextBox3.Text = sum End Sub（）（）Python 語言源程序語言源程序a=eval(input(please input the first number: )b=eval(input(plese input the secon

9、d number: )sum=a+bprint (sum= %s %sum) 【舉一反三】如果要求兩數(shù)之差，之積，該如何改寫源程序代碼呢？二、順序結(jié)構(gòu)案例2生成驗(yàn)證碼.問題描述：假期，你跟同學(xué)出門旅游，旅館的WiFi驗(yàn)證碼是房號(hào)的某幾位數(shù)（房號(hào)共6位：8 + 1位樓號(hào)+2位樓層號(hào)+2位房間號(hào)）。假定當(dāng)天的WiFi驗(yàn)證碼是將房號(hào)的最后3位逆序輸出（例如，你住在2號(hào)樓15層的34號(hào)房。那么你的房號(hào)為：821534，旅館應(yīng)得出你的驗(yàn)證碼為：435）。你知道當(dāng)你輸入你的房號(hào)后，旅館是如何計(jì)算出你的驗(yàn)證碼的？.算法分析算法分析：要獲得WiFi驗(yàn)證碼，首先我們要知道房間號(hào)，因此需要輸入房間號(hào)，然后需要對(duì)此

10、房間號(hào)進(jìn)行相應(yīng)的處理，以獲得驗(yàn)證碼，最后還需要將這個(gè)驗(yàn)證碼輸出。那么，如何分出一個(gè)整數(shù)中各位的數(shù)字呢？其實(shí)，我們使用算術(shù)運(yùn)算中的除法（整除）和求模（求余）運(yùn)算就可以很容易地得到。.算法設(shè)計(jì)：算法設(shè)計(jì)： 輸入房間號(hào)，如本例中的821534，設(shè)為變量number； 計(jì)算第一位驗(yàn)證碼，即房號(hào)的個(gè)位數(shù)。number對(duì)10取余，輸出； 計(jì)算第二位驗(yàn)證碼，即房號(hào)的十位數(shù)。number對(duì)10整除后，得到新的number，再對(duì)10取余，輸出； 計(jì)算第三位驗(yàn)證碼，即房號(hào)的百位數(shù)。number對(duì)10整除后，得到新的number，再對(duì)10取余，輸出； 程序結(jié)束。.流程圖：流程圖：三、選擇結(jié)構(gòu)案例簡(jiǎn)單四則運(yùn)算計(jì)算器.

11、問題描述：還是簡(jiǎn)單的計(jì)算。這一次，我們讓計(jì)算機(jī)按我們輸入的運(yùn)算符完成相應(yīng)的算術(shù)運(yùn)算。.算法分析：此例中，計(jì)算機(jī)進(jìn)行的運(yùn)算類型依賴于我們的輸入。也就是說，根據(jù)我們的輸入會(huì)進(jìn)行不同的運(yùn)算。那么，需要完成的運(yùn)行步驟為：1）. 輸入要執(zhí)行的運(yùn)算符；2）. 輸入要計(jì)算的數(shù)據(jù)；3）.判斷運(yùn)算符，并執(zhí)行相關(guān)的運(yùn)算；4）.輸出結(jié)果。.算法設(shè)計(jì)：輸出提示語句（1：+； 2：-； 3：*）；輸入運(yùn)算符；輸入運(yùn)算數(shù)據(jù)；判斷運(yùn)算符（1：執(zhí)行加法運(yùn)算；2：執(zhí)行減法運(yùn)算；3：執(zhí)行乘法運(yùn)算）輸出結(jié)果；程序結(jié)束。.流程圖：.對(duì)應(yīng)的源程序代碼（）c語言源程序：#includeint main()int a, b, operat

12、or;printf(“請(qǐng)選擇要執(zhí)行的運(yùn)算: n”);printf(“ 1: 加法運(yùn)算 +n”);printf(“ 2：減法運(yùn)算 -n”);printf(“ 3：乘法運(yùn)算 *n”);printf(“你的選擇是： ”);scanf(“%d”,&operator);printf(“請(qǐng)輸入要運(yùn)算的數(shù)據(jù)： ”);scanf(“%d%d”,&a,&b);if(operator=1) c=a+b;if(operator=2) c=a-b;if(operator=3) c=a*b;printf(“%dn”,c);return 0; （）VB語言源程序： Private Sub Butt

13、on1_Click() Handles Button1.Click Dim a As Integer, b As Integer Dim c As Integer a = Val(Textbox1.Text) b = Val(Textbox2.Text) If ListBox1.Text = + Then c = a + b ElseIf ListBox1.Text = - Then c = a - b ElseIf ListBox1.Text = * Then c = a * b End If TextBox3.Text = c End Sub （）Python語言源程序：operator=

14、input(please enter operator)a=eval(input(please enter the first number)b=eval(input(plese enter the second number)if operator=+ : c=a+belif operator=- : c=a-belif operator=* : c=a*bprint( a, operator, b,=, c)四、選擇結(jié)構(gòu)案例-檢驗(yàn)驗(yàn)證碼1. 問題描述：旅館確定驗(yàn)證碼后，房客需要將驗(yàn)證碼輸入，由系統(tǒng)判斷是否能使用網(wǎng)絡(luò)。2. 算法分析: 現(xiàn)在我們需要完成的任務(wù)除了生成驗(yàn)證碼之外，還需要1）.

15、告知用戶驗(yàn)證碼生成策略；2）. 輸入驗(yàn)證碼；3）. 比較并判斷驗(yàn)證碼輸入是否正確；4）. 給出結(jié)論（是否能進(jìn)入網(wǎng)絡(luò)）。3. 算法設(shè)計(jì)：輸出顯示驗(yàn)證碼生成策略；輸入房間號(hào)；系統(tǒng)生成驗(yàn)證碼code1；輸入驗(yàn)證碼code2；如果輸入的驗(yàn)證碼code2與系統(tǒng)生成的驗(yàn)證碼code1相等，則顯示“可以使用網(wǎng)絡(luò)”，否則顯示“驗(yàn)證碼錯(cuò)誤，不能使用網(wǎng)絡(luò)”；程序結(jié)束。4. 流程圖五、循環(huán)結(jié)構(gòu)案例-小學(xué)生四則運(yùn)算練習(xí)題1. 問題描述：暑假，小學(xué)數(shù)學(xué)老師要求家長(zhǎng)每天給小學(xué)生布置若干道100以內(nèi)的加減乘法運(yùn)算。鄰居來找你幫忙，于是，你按鄰居的要求編寫了一個(gè)程序，每次給鄰居家的小弟弟出10道題，并判斷對(duì)錯(cuò)。2. 算法分析

16、：需要由計(jì)算機(jī)給出隨機(jī)數(shù)據(jù)，要用到隨機(jī)數(shù)的生成。其實(shí)，每種語言都有相應(yīng)的隨機(jī)數(shù)生成函數(shù)。我們只需要選用即可。那么，我們需要做的就是：1）. 生成隨機(jī)數(shù)（每次2個(gè)）作為運(yùn)算數(shù)據(jù)；2）. 生成隨機(jī)數(shù)，對(duì)應(yīng)運(yùn)算符；3）. 產(chǎn)生表達(dá)式(當(dāng)ab時(shí)，交換a和b)； 4）. 按相應(yīng)的表達(dá)式求值，并輸出。3. 算法設(shè)計(jì)： 生成兩個(gè)隨機(jī)數(shù)a，b； 生成一個(gè)隨機(jī)數(shù)operator； 如果operator為1，輸出題目 a+b=，同時(shí)計(jì)算結(jié)果result； 如果operator為2，輸出題目a-b=，同時(shí)計(jì)算結(jié)果result； 否則，輸出題目a*b=，同時(shí)計(jì)算結(jié)果result； 輸入用戶的計(jì)算結(jié)果c； 比較c與re

17、sult，如果c與result相等，輸出”right”；如果不相等，輸出”wrong”； 計(jì)算出題數(shù)count 如果出題數(shù)少于10題，則返回1，否則執(zhí)行8； 結(jié)束。4. 流程圖：5. 對(duì)應(yīng)的源程序代碼:（1）c語言源程序：#include#include#includeint main()int count=0, a, b,operator;srand(time(0);while(count10) a=rand()%100; b=rand()%100; operator=rand()%3+1;if(operator=1) printf(“%4d +%4d = “, a,b); result=a

18、+b;else if(operator=2) if(ab)a=a+b；b=a-b；a=a-b;printf(“%4d -%4d = “, a,b);result=a-b; else printf(“%4d *%4d = “, a,b);result=a*b;scanf(“%d”,&c);if(c=result) printf(“rightn”);else printf(“wrongn”);count+;（2）VB語言源程序：Private Sub Button1_Click() Handles Button1.Click Dim i As Integer, a As Integer,

19、b As Integer, t As Integer Dim myasw As Integer, c As Integer, op As Integer Dim opr As String, my_question As String Randomize() i = 1 While i = 10 a = Int(Rnd() * 101) b = Int(Rnd() * 101) op = Int(Rnd() * 3 + 1) If op = 1 Then opr = +“ c = a + bElseIf op = 2 Then opr = - If a b Then t = a a = b b = t End If c = a bElse op=3 opr = * c = a * bEnd If myasw = InputBox(a & opr & b & =, My answer, ) my_question = a & opr & b & = & myasw If myasw = c Then ListBox1.Items.Add(my_question & right) Else ListBox1.Items.Add(my_question & wrong) End If i = i + 1 E