信息社會(huì)與計(jì)算技術(shù)第10章-問(wèn)題求解與算法設(shè)計(jì)

1、第10章 問(wèn)題求解與算法設(shè)計(jì)第10章 問(wèn)題求解與算法設(shè)計(jì)問(wèn)題求解過(guò)程01計(jì)算機(jī)求解問(wèn)題的方法02算法及其描述03程序基本結(jié)構(gòu)04本講提綱Raptor可視化算法流程圖設(shè)計(jì)05第10章 問(wèn)題求解與算法設(shè)計(jì)問(wèn)題求解過(guò)程問(wèn)題求解的一般過(guò)程： 明確問(wèn)題理解問(wèn)題方案設(shè)計(jì)方案選擇解決步驟方案評(píng)價(jià)問(wèn)題求解的計(jì)算機(jī)處理過(guò)程：?jiǎn)栴}描述問(wèn)題抽象建立模型設(shè)計(jì)與實(shí)現(xiàn)調(diào)試與測(cè)試第10章 問(wèn)題求解與算法設(shè)計(jì)問(wèn)題求解的計(jì)算機(jī)處理過(guò)程開(kāi)始x0 x=352*x+4*(35-x)=94輸出答案Xxx+1結(jié)束NYNY 雞兔同籠2x+4（35-x）=94設(shè)雞有x只，則x的可能取值是0至35搜索參數(shù): 答案符合的條件: 窮舉法 計(jì)算機(jī)求

2、解問(wèn)題的方法第10章 問(wèn)題求解與算法設(shè)計(jì) （1）使用計(jì)算機(jī)軟件進(jìn)行問(wèn)題求解 使用已有軟件解決問(wèn)題，這是計(jì)算機(jī)應(yīng)用的典型方式。 （2）編寫(xiě)計(jì)算機(jī)程序進(jìn)行問(wèn)題求解 抽象分析與建模，設(shè)計(jì)與實(shí)現(xiàn)，調(diào)試與測(cè)試 （3）構(gòu)建系統(tǒng)進(jìn)行問(wèn)題求解 要特別注意組成系統(tǒng)的各部分之間的相互約束、依賴(lài)和控制關(guān)系。算法及其描述第10章 問(wèn)題求解與算法設(shè)計(jì)一、算法的定義 算法（Algorithm）就是指為解決一個(gè)具體問(wèn)題而采取的方法和步驟的集合。算法是程序設(shè)計(jì)的靈魂。 生活中的算法算法無(wú)處不在：超市收銀旅程安排（時(shí)間、里程、花費(fèi)）手機(jī)話費(fèi)省錢(qián)方案如何合理安排學(xué)習(xí)和生活時(shí)間才能讓學(xué)習(xí)效率最高算法及其描述第10章 問(wèn)題求解與算法

3、設(shè)計(jì)二、算法的基本特征1.有零個(gè)或多個(gè)輸入：需要從外界獲取必要的信息2.有一個(gè)或多個(gè)輸出：需要把求得得解進(jìn)行輸出3.確定性：每一步必須明確4.有窮性：算法要包含有限的步驟5.可行性：算法描述的所有操作都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算的有限次執(zhí)行來(lái)實(shí)現(xiàn)算法及其描述第10章 問(wèn)題求解與算法設(shè)計(jì)自然語(yǔ)言表示法偽代碼表示法流程圖表示法N-S圖PAD圖三、算法的表示偽代碼表示法判斷一個(gè)年份是否為閏年的算法：BEGIN（算法開(kāi)始）輸入年份 yIF y能被4整除 THEN IF y不能被100整除 THEN 輸出“y是閏年” ELSE IF y能被400整除 THEN 輸出“y是閏年” ELSE 輸出“y不是閏

4、年” END IF END IFELSE 輸出“y不是閏年”END IFEND（算法結(jié)束）算法及其描述第10章 問(wèn)題求解與算法設(shè)計(jì)三、算法的表示流程圖是一種采用程序框、流程線及簡(jiǎn)要文字說(shuō)明來(lái)表示算法的有效方法。 其中，程序框圖用于表示算法中的具體步驟，流程線表示算法的執(zhí)行順序。算法及其描述第10章 問(wèn)題求解與算法設(shè)計(jì)三、算法的表示流程圖表示法判斷一個(gè)年份是否為閏年的算法：Y輸出Y是閏年NNYN100能整除yY100能整除y4能整除y輸入年份y輸出Y不是閏年輸出Y是閏年輸出Y不是閏年結(jié)束開(kāi)始算法及其描述第10章 問(wèn)題求解與算法設(shè)計(jì)四、算法的評(píng)價(jià) 對(duì)于算法的評(píng)價(jià)有兩個(gè)基本標(biāo)準(zhǔn)，即時(shí)間復(fù)雜度和空間復(fù)

5、雜度。 時(shí)間復(fù)雜度：常數(shù)O(1)、對(duì)數(shù)階O(log2n)、線形階O(n)、線形對(duì)數(shù)階O(nlog2n)、平方階O(n2)、立方階O(n3)、指數(shù)階O(2n)。 空間復(fù)雜度：即執(zhí)行這個(gè)算法需要占用多少資源（可以理解為占用了多少計(jì)算機(jī)存儲(chǔ)單元）。 算法的可讀性程序基本結(jié)構(gòu)第10章 問(wèn)題求解與算法設(shè)計(jì)程序設(shè)計(jì)技術(shù)的發(fā)展艾達(dá).拜倫（ 1815-1852）第一位程序員第一個(gè)計(jì)算機(jī)程序1843年計(jì)算機(jī)剛發(fā)明的最初10年高級(jí)語(yǔ)言低級(jí)語(yǔ)言匯編語(yǔ)言機(jī)器語(yǔ)言面向計(jì)算機(jī)面向過(guò)程面向?qū)ο?0世紀(jì)60年代20世紀(jì)80年代程序基本結(jié)構(gòu)第10章 問(wèn)題求解與算法設(shè)計(jì)順序結(jié)構(gòu)ABab順序結(jié)構(gòu)順序結(jié)構(gòu)是控制結(jié)構(gòu)中最簡(jiǎn)單的一種基本

6、結(jié)構(gòu)。它表示程序中的各操作是按照它們出現(xiàn)的先后順序執(zhí)行的。程序基本結(jié)構(gòu)第10章 問(wèn)題求解與算法設(shè)計(jì)選擇結(jié)構(gòu)PAB否是雙分支結(jié)構(gòu)ba單分支結(jié)構(gòu)PA否是ba程序基本結(jié)構(gòu)第10章 問(wèn)題求解與算法設(shè)計(jì)循環(huán)結(jié)構(gòu)否是abAP直到型循環(huán)PA否是ab當(dāng)型循環(huán)Raptor可視化算法流程圖設(shè)計(jì)第10章 問(wèn)題求解與算法設(shè)計(jì)Raptor的主界面菜單和工具欄符號(hào)區(qū)域觀察窗口主工作區(qū)Raptor的主控臺(tái)Raptor可視化算法流程圖設(shè)計(jì)第10章 問(wèn)題求解與算法設(shè)計(jì)求解n！問(wèn)題描述：n!=123n 或n!=n(n-1)!Raptor可視化算法流程圖設(shè)計(jì)第10章 問(wèn)題求解與算法設(shè)計(jì)循環(huán)結(jié)構(gòu)算法求n！NYi=n輸入n開(kāi)始f1，i1ff*i輸出f結(jié)束ii+1Rap