1、信息技術(shù)算法與程序設(shè)計(jì)王宏曉,算法與程序設(shè)計(jì),計(jì)算機(jī)解決問(wèn)題的基本過(guò)程： 1.分析問(wèn)題 2.確定方案。 兩類(lèi)方案： 一類(lèi)可以通過(guò)執(zhí)行若干步驟解決問(wèn)題叫算法方案； 另一類(lèi)不能通過(guò)若干步驟直接解決，還需要反復(fù)驗(yàn)證才能解決的，叫啟發(fā)式方案。 3.設(shè)計(jì)步驟（算法設(shè)計(jì)和描述） 4.程序設(shè)計(jì) 對(duì)算法方案編寫(xiě)特定的程序，也就是用計(jì)算機(jī)能理解的語(yǔ)言將算法表達(dá)成程序，得出最終結(jié)果，即程序設(shè)計(jì)。,算法與程序設(shè)計(jì),計(jì)算機(jī)解決的問(wèn)題分三類(lèi)： 一、用現(xiàn)有工具軟件可解決的； 二、需要編寫(xiě)程序通過(guò)若干步驟才能解決的： 1.計(jì)算型 2.邏輯型 3.需要反復(fù)執(zhí)行一組計(jì)算或邏輯型指令 三、需要編程，但不能通過(guò)既定步驟解決，如PC

2、產(chǎn)品顧問(wèn)，遠(yuǎn)程醫(yī)療，人機(jī)對(duì)弈等等，需要啟發(fā)式方案-人工智能技術(shù)。,算法與程序設(shè)計(jì)-算法的概念,算法就是解決問(wèn)題的步驟序列。,算法（Algorithm）是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問(wèn)題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問(wèn)題的策略機(jī)制。即對(duì)一定規(guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。如果一個(gè)算法有缺陷，或不適合于某個(gè)問(wèn)題，執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問(wèn)題。不同的算法可能用不同的時(shí)間、空間或效率來(lái)完成同樣的任務(wù)。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來(lái)衡量。 算法的特征：可行性、確定性、有窮性。,算法與程序設(shè)計(jì),算法的描述方法：自然語(yǔ)言、結(jié)構(gòu)化流程圖、偽代碼。,算法的描述

3、(1),問(wèn)題：“某班同學(xué)身高的最高值是多少？”,1用自然語(yǔ)言描述,步驟1：輸入第一個(gè)同學(xué)的身高值 步驟2：輸入下一個(gè)同學(xué)的身高值 步驟3：比較兩個(gè)同學(xué)的身高值 步驟4：選出較大值 步驟5：再輸入下一個(gè)同學(xué)的身高值 步驟6：再用這個(gè)同學(xué)的身高值和較大值進(jìn)行比較 步驟7：再選出較大值 重復(fù)第（5）至（7），直到輸入最后一個(gè)同學(xué)的身高，比較后選出較大值 步驟8：該較大值即為全班同學(xué)的最高身高,算法與程序設(shè)計(jì),2用流程圖描述,算法的描述(2),最值問(wèn)題 輸入20個(gè)數(shù)，求其中最大值max和最小值min。,打擂臺(tái)法,算法與程序設(shè)計(jì),算法的描述(3),偽代碼:類(lèi)似于程序設(shè)計(jì)語(yǔ)言的代碼，偽代碼沒(méi)有統(tǒng)一規(guī)定，只

4、要合理，沒(méi)矛盾就行，基本指令：賦值指令，循環(huán)指令，條件指令和輸出指令。,3用偽代碼描述,偽代碼是采用一種類(lèi)似于程序設(shè)計(jì)語(yǔ)言的代碼來(lái)描述算法?；局噶睿?l 賦值指令：助記符 表達(dá)式； 如：p1 10; l 輸出指令：輸出 （表達(dá)式）； l 循環(huán)指令： while（條件表達(dá)式） 循環(huán)體 l 條件指令： if （條件表達(dá)式） 指令序列1 else 指令序列2 ,算法與程序設(shè)計(jì),import java.io.*; /導(dǎo)入所需要的公共類(lèi) public class TestMax public static void main(String args) throws IOException double

5、 m=Input(); double x=Input(); while (x0) if (xm) m=x; else x=Input(); System.out.println(最大值= +m); /輸出比較結(jié)果 ,static double Input() throws IOException InputStreamReader reader=new InputStreamReader(System.in); BufferedReader input=new BufferedReader(reader); System.out.print(輸入身高值:); String s=input.re

6、adLine(); double n=Double.parseDouble(s); return n; ,算法的程序?qū)崿F(xiàn),算法與程序設(shè)計(jì),關(guān)系運(yùn)算符： = =（等于）、!=（不等于）、（大于）、=（大于等于）關(guān)系表達(dá)式的結(jié)果類(lèi)型為布爾型，即關(guān)系式成立為true，不成立為false。 例如：105； /結(jié)果為true10.55； /結(jié)果為truea= =b； /結(jié)果為falsetruefalse； /錯(cuò)誤，boolean 型數(shù)據(jù)只能比較= =或!=，不能比較大小。 邏輯運(yùn)算符：!（非）、&（與）、|（或） Python: not and or ! false /結(jié)果為true 如：!(108)

7、/結(jié)果為false ! true /結(jié)果為falsefalse | true /結(jié)果為true false | false /結(jié)果為falsetrue | true /結(jié)果為truetrue & false /結(jié)果為false true & true /結(jié)果為true,2.常見(jiàn)的算法描述方法有： 自然語(yǔ)言（如漢語(yǔ)，英文） 流程圖描述 偽代碼描述,3.結(jié)構(gòu)化程程序設(shè)計(jì)語(yǔ)言中程序的三種最基本結(jié)構(gòu)：,順序結(jié)構(gòu) 選擇結(jié)構(gòu) 循環(huán)結(jié)構(gòu),1.算法：解決問(wèn)題的方法與步驟,4.編程解題的過(guò)程 人工解題(分析問(wèn)題) 描述算法(設(shè)計(jì)算法) 編寫(xiě)程序 調(diào)試程序,算法與程序設(shè)計(jì),算法與程序設(shè)計(jì),程序設(shè)計(jì)語(yǔ)言的發(fā)展歷程：

8、 機(jī)器語(yǔ)言匯編語(yǔ)言高級(jí)語(yǔ)言 常見(jiàn)的高級(jí)語(yǔ)言： Visual Basic、Pascal、C、C+、Prolog、Java、LISP、Algol、Cobol、Basic、Python（我們教學(xué)要學(xué)的語(yǔ)言）等 第一個(gè)高級(jí)程序設(shè)計(jì)語(yǔ)言是 Fortran 高級(jí)語(yǔ)言發(fā)展歷程：非結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言,算法與程序設(shè)計(jì)-程序設(shè)計(jì)語(yǔ)言,程序設(shè)計(jì)語(yǔ)言的產(chǎn)生與發(fā)展,程序設(shè)計(jì)語(yǔ)言是指人們編制程序所使用的計(jì)算機(jī)語(yǔ)言。程序設(shè)計(jì)語(yǔ)言經(jīng)歷了從機(jī)器語(yǔ)言到高級(jí)語(yǔ)言的發(fā)展歷程。 機(jī)器語(yǔ)言（machine language）是一種指令集的體系。這種指令集，稱(chēng)機(jī)器碼（machine code），是電腦

9、的CPU可直接解讀的數(shù)據(jù)。機(jī)器語(yǔ)言是用二進(jìn)制代碼表示的計(jì)算機(jī)能直接識(shí)別和執(zhí)行的一種機(jī)器指指令系統(tǒng)令的集合。它是計(jì)算機(jī)的設(shè)計(jì)者通過(guò)計(jì)算機(jī)的硬件結(jié)構(gòu)賦予計(jì)算機(jī)的操作功能。機(jī)器語(yǔ)言具有靈活、直接執(zhí)行和速度快等特點(diǎn)。不同型號(hào)的計(jì)算機(jī)其機(jī)器語(yǔ)言是不相通的，按著一種計(jì)算機(jī)的機(jī)器指令編制的程序，不能在另一種計(jì)算機(jī)上執(zhí)行。 一條指令就是機(jī)器語(yǔ)言的一個(gè)語(yǔ)句，它是一組有意義的二進(jìn)制代碼，指令的基本格式如，操作碼字段和地址碼字段，其中操作碼指明了指令的操作性質(zhì)及功能，地址碼則給出了操作數(shù)或操作數(shù)的地址。,程序設(shè)計(jì)語(yǔ)言的產(chǎn)生與發(fā)展,程序設(shè)計(jì)語(yǔ)言的產(chǎn)生與發(fā)展,匯編語(yǔ)言 使用一種類(lèi)似英語(yǔ)縮略詞且?guī)в兄浶苑?hào)的語(yǔ)言 用匯

10、編語(yǔ)言寫(xiě)的程序，必須通過(guò)匯編程序的翻譯，轉(zhuǎn)換成機(jī)器語(yǔ)言，才能被計(jì)算機(jī)執(zhí)行。,算法與程序設(shè)計(jì),程序設(shè)計(jì)語(yǔ)言的產(chǎn)生與發(fā)展,高級(jí)語(yǔ)言 第一個(gè)高級(jí)程序設(shè)計(jì)語(yǔ)言是fortran語(yǔ)言，主要用于科學(xué)和工程計(jì)算。 高級(jí)語(yǔ)言中使用的表達(dá)式更接近數(shù)學(xué)表達(dá)式，使用的語(yǔ)句更接近自然語(yǔ)言。 例如前面計(jì)算“98”的問(wèn)題，若用visual Basic語(yǔ)言編程，就變得十分簡(jiǎn)單，而且易于理解。 Print 9+8 高級(jí)語(yǔ)言編寫(xiě)的程序（稱(chēng)為源程序）必須經(jīng)過(guò)翻譯器將其翻譯成機(jī)器語(yǔ)言，才能被計(jì)算機(jī)執(zhí)行。 高級(jí)語(yǔ)言由于抽象度高，源代碼與硬件無(wú)關(guān)，可移植性強(qiáng)。 常見(jiàn)的高級(jí)語(yǔ)言有fortran,Basic,Pascal,C,C+,java

11、,Prolog。,算法與程序設(shè)計(jì),程序的編輯與翻譯,以匯編語(yǔ)言或高級(jí)語(yǔ)言所編寫(xiě)的程序被稱(chēng)為“源代碼” 源代碼需要我們逐輸入到計(jì)算機(jī)中，并以文本文件形式保存起來(lái)，這個(gè)過(guò)程稱(chēng)為程序的編輯。 高級(jí)語(yǔ)言的翻譯程序有兩種類(lèi)型：編譯程序和解釋程序。,算法與程序設(shè)計(jì),編譯程序的主要功能是將高級(jí)語(yǔ)言編寫(xiě)的程序在執(zhí)行前翻譯成等效的機(jī)器語(yǔ)言程序，以便在機(jī)器上直接執(zhí)行。其編譯過(guò)程如下圖,算法與程序設(shè)計(jì),解釋程序的作用是逐條分析源程序中的語(yǔ)句，每解釋一句由計(jì)算機(jī)執(zhí)行執(zhí)行一句。它和編譯程序的差別在于不產(chǎn)生目標(biāo)程序，而是直接執(zhí)行源程序，每次執(zhí)行都要進(jìn)行逐條解釋。其解釋過(guò)程如圖,算法與程序設(shè)計(jì),編譯過(guò)程又可以分成兩個(gè)階段：

12、編譯和匯編。 編譯是指編譯器讀取源程序（字符流），對(duì)之進(jìn)行詞法和語(yǔ)法的分析，將高級(jí)語(yǔ)言指令轉(zhuǎn)換為功能等效的匯編代碼。 第一個(gè)階段是預(yù)處理階段，在正式的編譯階段之前進(jìn)行。預(yù)處理階段將根據(jù)已放置在文件中的預(yù)處理指令來(lái)修改源文件的內(nèi)容。 第二個(gè)階段編譯、優(yōu)化階段，編譯程序所要作得工作就是通過(guò)詞法分析和語(yǔ)法分析，在確認(rèn)所有的指令都符合語(yǔ)法規(guī)則之后，將其翻譯成等價(jià)的中間代碼表示或匯編代碼。 匯編實(shí)際上指匯編器(as)把匯編語(yǔ)言代碼翻譯成目標(biāo)機(jī)器指令的過(guò)程。目標(biāo)文件中所存放的也就是與源程序等效的目標(biāo)的機(jī)器語(yǔ)言代碼。目標(biāo)文件由段組成。通常一個(gè)目標(biāo)文件中至少有兩個(gè)段： 代碼段：該段中所包含的主要是程序的指令。

13、該段一般是可讀和可執(zhí)行的，但一般卻不可寫(xiě)。 數(shù)據(jù)段：主要存放程序中要用到的各種全局變量或靜態(tài)的數(shù)據(jù)。一般數(shù)據(jù)段都是可讀，可寫(xiě)，可執(zhí)行的。,算法與程序設(shè)計(jì),連接程序（linker） 編譯器和匯編程序都經(jīng)常依賴(lài)于連接程序，它將分別在不同的目標(biāo)文件中編譯或匯編的代碼收集到一個(gè)可直接執(zhí)行的文件中。在這種情況下，目標(biāo)代碼，即還未被連接的機(jī)器代碼，與可執(zhí)行的機(jī)器代碼之間就有了區(qū)別。連接程序還連接目標(biāo)程序和用于標(biāo)準(zhǔn)庫(kù)函數(shù)的代碼，以及連接目標(biāo)程序和由計(jì)算機(jī)的操作系統(tǒng)提供的資源（例如，存儲(chǔ)分配程序及輸入與輸出設(shè)備）。有趣的是，連接程序現(xiàn)在正在完成編譯器最早的一個(gè)主要活動(dòng)（這也是“編譯”一詞的用法，即通過(guò)收集不同的來(lái)源來(lái)構(gòu)造）。連接過(guò)程對(duì)操作系統(tǒng)和處理器有極大的依賴(lài)性。,算法與程序設(shè)計(jì),程序開(kāi)發(fā)環(huán)境(IDE(Integrated Developmen