Chp-4 程序設(shè)計(jì)層 -6 問(wèn)題求解和算法設(shè)計(jì)

第6章問(wèn)題求解和算法設(shè)計(jì)2章節(jié)目標(biāo)確定一個(gè)問(wèn)題是否適合用計(jì)算機(jī)解決結(jié)合Polya提出的如何解決問(wèn)題的列表，描述計(jì)算機(jī)問(wèn)題求解的步驟區(qū)別計(jì)算機(jī)算法和開發(fā)算法描述用于表示算法的偽代碼指令使用偽代碼表示算法3章節(jié)目標(biāo)應(yīng)用自頂向下的方法開發(fā)算法來(lái)解決問(wèn)題定義面向?qū)ο笤O(shè)計(jì)方法中的術(shù)語(yǔ)應(yīng)用面向?qū)ο蟮姆椒ㄩ_發(fā)一組互動(dòng)對(duì)象來(lái)解決問(wèn)題求證與問(wèn)題求解相關(guān)的幾點(diǎn)思想——信息隱蔽、抽象、事物命名和測(cè)試4問(wèn)題求解問(wèn)題求解尋找令人感到復(fù)雜、痛苦、煩惱或未解決的難題的解決方案的行為

你如何定義問(wèn)題求解？5問(wèn)題求解如何解決它：數(shù)學(xué)方法的新視點(diǎn)作者：

GeorgePolya雖然“如何解決它”這個(gè)列表是在解決數(shù)學(xué)問(wèn)題時(shí)編寫的，但它是普遍適用的。我們可以用它來(lái)解決與計(jì)算機(jī)有關(guān)的問(wèn)題。6問(wèn)題求解如何解決問(wèn)題呢？理解問(wèn)題

找出解決方案

執(zhí)行方案

分析得到的解決方案7策略提出問(wèn)題!對(duì)這個(gè)問(wèn)題我了解多少?要找到解決方案我必須處理哪些信息？解決方案是什么樣的?存在什么特例?我如何知道已經(jīng)找到解決方案了？8策略提出問(wèn)題!永遠(yuǎn)不要徹底重新做一件事！如果以前曾經(jīng)解決過(guò)相同或相似的問(wèn)題，只需要再次使用那種成功的方案即可一個(gè)好的程序員看到以前解決的任務(wù)或者任務(wù)中的一部分時(shí)會(huì)直接選用已有的方案

你能想到兩個(gè)相似的問(wèn)題嗎？9策略分治法!把一個(gè)大問(wèn)題劃分為幾個(gè)能解決的小單元抽象概念的運(yùn)用可以反復(fù)利用分治法，直到每個(gè)子任務(wù)都是可以實(shí)現(xiàn)的為止10算法算法

在有限的時(shí)間內(nèi)用有限的數(shù)據(jù)解決問(wèn)題或子問(wèn)題的明確指令

指令為什么必須明確？

時(shí)間和數(shù)據(jù)為什么必須有限?11計(jì)算機(jī)問(wèn)題求解分析和說(shuō)明階段

分析

說(shuō)明算法開發(fā)階段

開發(fā)算法

測(cè)試算法實(shí)現(xiàn)階段

編碼

測(cè)試維護(hù)階段

使用

維護(hù)你能說(shuō)出一個(gè)反復(fù)出現(xiàn)的主題嗎?12階段交互我們需要增加其他的箭頭嗎？（如果這個(gè)問(wèn)題被修正以后會(huì)發(fā)生什么？）13偽代碼偽代碼用混合的英語(yǔ)和格式使算法的步驟明確的語(yǔ)言把十進(jìn)制數(shù)轉(zhuǎn)換成其他進(jìn)制數(shù)的算法的偽代碼While(商不為0)

用新的基數(shù)除十進(jìn)制數(shù)

把余數(shù)作為答案最左邊的一位數(shù)

用商替換原來(lái)的十進(jìn)制數(shù)14執(zhí)行算法圖6.4蛋黃奶油酸辣醬的菜譜15執(zhí)行算法準(zhǔn)備做蛋黃奶油酸辣醬的算法If在意卡路里

把奶油替代品倒入鍋里Else

把奶油倒入鍋內(nèi)打開火爐把鍋放在火爐上While(未起泡)

把鍋置于火爐上把其他配料放入攪拌器啟動(dòng)攪拌器While(還有奶油)

把奶油緩緩注入攪拌器關(guān)閉攪拌器16開發(fā)算法當(dāng)前使用的把問(wèn)題轉(zhuǎn)化為方案的方法有兩種：自頂向下面向?qū)ο?/p>

但是首先，我們先來(lái)看一種算法:偽代碼

17偽代碼偽代碼一種英語(yǔ)和意圖相混合的能將算法步驟表述明確的語(yǔ)言偽代碼中沒(méi)有語(yǔ)法規(guī)定Pseudocodeisnotcasesensitive偽代碼中是不區(qū)分大小寫的18執(zhí)行算法8除93是？ 93/8商11余5 11/6商1余3 1/8商0余1

答案135While(商不為0)

用新的基數(shù)除十進(jìn)制

余數(shù)作為結(jié)果中最左邊一位

用商替換原來(lái)的十進(jìn)制數(shù)19執(zhí)行算法得到答案的更簡(jiǎn)單方案20完整的偽代碼解決方案Write"Enterthenewbase"ReadnewBaseWrite"Enterthenumbertobeconverted"ReaddecimalNumberSetquotientto1While(quotientisnotzero) SetquotienttodecimalNumberDIVnewBase SetremaindertodecimalNumberREMnewBase Maketheremainderthenextdigittotheleftintheanswer SetdecimalNumbertoquotientWrite"Theansweris"Writeanswer21偽代碼的功能變量出現(xiàn)在偽代碼中的名字，引用的是存儲(chǔ)值的位置

quotient,decimalNumber,newBase賦值把值放入變量

Setquotientto64 quotient<--64 quotient<--6*10+422偽代碼的功能輸出把值輸出到輸出設(shè)備

Write,Print輸入從外部世界向計(jì)算機(jī)中輸入數(shù)據(jù)值

Get,Read

23偽代碼的功能重復(fù)重復(fù)一系列指令 Setcountto1 While(count<10) Write"Enteranintegernumber" ReadaNumber Write"Youentered"+aNumber Setcounttocount+1

讀了幾個(gè)值?24偽代碼的功能選擇選擇執(zhí)行或跳過(guò)某項(xiàng)操作

Readnumber If(number<0) Writenumber+"islessthanzero."or

Write"Enterapositivenumber."

Readnumber If(number<0) Writenumber+"islessthanzero." Write"Youdidn'tfollowinstructions."25偽代碼的功能選擇選擇執(zhí)行某項(xiàng)操作

If(age<12) Write"Paychildren'srate" Write"Yougetafreeboxofpopcorn" elseIf(age<65) Write"Payregularrate" else Write"Payseniorcitizensrate"

26偽代碼的功能Write"Howmanypairsofvaluesaretobeentered?"ReadnumberOfPairsSetnumberReadto0While(numberRead<numberOfPairs) Write"Entertwovaluesseparatedbyablank;pressreturn" Readnumber1 Readnumber2 If(number1<number2) Printnumber1+""+number2 Else Printnumber2+""number1 IncrementnumberRead 27走查數(shù)據(jù) 填寫每一個(gè)迭代值3 numberRead number1 number25570213333 numberOfPairs

輸出是什么?28自頂向下設(shè)計(jì)方法自頂向下設(shè)計(jì)把問(wèn)題分解成一套子問(wèn)題，然后再把子問(wèn)題分解成子問(wèn)題，直到每個(gè)子問(wèn)題都足夠基礎(chǔ)，不再需要再進(jìn)一步分解為止模塊一個(gè)用于解決問(wèn)題或子問(wèn)題的封閉步驟集合抽象步驟細(xì)節(jié)仍未明確的算法步驟具體步驟細(xì)節(jié)完全明白的算法步驟29自頂向下設(shè)計(jì)方法這個(gè)過(guò)程將在多個(gè)層次中重復(fù)，把每個(gè)任務(wù)擴(kuò)展成最小的細(xì)節(jié)可將困難繁重的任務(wù)推到較低的層次中。圖6.7

自頂向下設(shè)計(jì)的例子30一個(gè)通用的實(shí)例籌劃一個(gè)大型集會(huì)圖6.6劃分聚會(huì)計(jì)劃31一個(gè)計(jì)算機(jī)實(shí)例問(wèn)題創(chuàng)建一個(gè)包括每個(gè)人的姓名、地址、電話號(hào)碼和電子郵件地址的地址列表。按字母順序輸出該列表加入這個(gè)列表的姓名是出現(xiàn)在小紙片和名片上的32一個(gè)計(jì)算機(jī)實(shí)例Main Level0EnternamesandnumbersintolistPutlistintoalphabeticalorderPrintlistEnternamesandnumbersintolist Level1While(morenames) Entername Entertelephonenumber Enteremailaddress Insertinformationintolist哪些步驟是抽象的？哪些步驟是具體的？哪些步驟是丟失的？33一個(gè)計(jì)算機(jī)實(shí)例Enternamesandnumbersintolist(revised) Level1SetmoreNamestotrueWhile(moreNames) Promptforandentername Promptforandentertelephonenumber Promptforandenteremailaddress Insertinformationintolist Write"Entera1tocontinueora0tostop." Readresponse If(response=0) SetmoreNamestofalse哪些步驟是具體的？哪些步驟路是抽象的？34一個(gè)計(jì)算機(jī)實(shí)例Promptforandentername Level2Write"Enterlastname;pressreturn."ReadlastNameWrite"Enterfirstname;pressreturn."ReadfirstNamePromptforandentertelephonenumber Level2Write"Enterareacodeand7-digitnumber;pressreturn."ReadtelephoneNumberPromptforandenteremailaddress Level2Write"Enteremailaddress;pressreturn."ReademailAddress35一個(gè)計(jì)算機(jī)實(shí)例Putlistintoalphabeticalorder具體還是抽象？Printthelist Level1Write"Thelistofnames,telephonenumbers,andemail addressesfollows:"GetfirstitemfromthelistWhile(moreitems) Writeitem'sfirstName+""+lastName Writeitem'stelephoneNumber Writeitem'semailAddress Writeablankline Getnextitemfromthelist36一個(gè)計(jì)算機(jī)實(shí)例注：在循環(huán)中插入信息37測(cè)試算法重要的區(qū)別

數(shù)學(xué)問(wèn)題

我們測(cè)試答案

計(jì)算機(jī)問(wèn)題

我們測(cè)試過(guò)程38測(cè)試算法桌面檢查在紙上跟蹤的一種設(shè)計(jì)的執(zhí)行情況走查由小組成員手動(dòng)地模擬設(shè)計(jì)，采用的是示例數(shù)據(jù)審查

要預(yù)先把設(shè)計(jì)分發(fā)給大家，由一位（非設(shè)計(jì)者）逐行讀出設(shè)計(jì)，而其他人負(fù)責(zé)指出其中的錯(cuò)誤39面向?qū)ο笤O(shè)計(jì)面向?qū)ο笤O(shè)計(jì)面向?qū)ο蟮脑O(shè)計(jì)方法是用叫做對(duì)象的獨(dú)立實(shí)體生成解決方案的問(wèn)題求解方法對(duì)象是在問(wèn)題背景中具有意義的事物或?qū)嶓w

例如,一個(gè)學(xué)生,一輛車,時(shí)間,日期40面相對(duì)象設(shè)計(jì)面向?qū)ο笤O(shè)計(jì)的世界觀問(wèn)題求解：隔離問(wèn)題中的對(duì)象決定它們的屬性和性能讓它們共同解決問(wèn)題什么？再說(shuō)一遍！41面向?qū)ο笤O(shè)計(jì)一個(gè)類比:你和你的朋友打點(diǎn)晚餐

對(duì)象:你，朋友，晚餐類:你和朋友都是人

人有姓名,瞳孔的顏色…

人可以購(gòu)物,烹飪…類的實(shí)例:你和朋友都是人這一類的實(shí)例，

你們都有自己的名字，有自己瞳孔的顏色

，你們每個(gè)都可以購(gòu)物，烹飪你們合作安排晚餐42面向?qū)ο笤O(shè)計(jì)類(或者對(duì)象類)一組具有相似的屬性和行為的對(duì)象的描述對(duì)象(類的實(shí)例)一個(gè)具體的類的實(shí)例類包含代表以下內(nèi)容的域 屬性(姓名,瞳孔的顏色)和行為(責(zé)任)(購(gòu)物,烹飪)定義了類的一種行為的特定算法43面向?qū)ο笤O(shè)計(jì)自頂向下設(shè)計(jì)

將問(wèn)題分解成多個(gè)任務(wù)面向?qū)ο笤O(shè)計(jì)

將問(wèn)題分解成合作的對(duì)象是，但是怎么做呢？44面向?qū)ο笤O(shè)計(jì)步驟隔離問(wèn)題中的對(duì)象abstracttheobjectswithlikepropertiesintogroups(classes)determinetheresponsibilitiesofthegroupininteractingwithothergroups45面向?qū)ο笤O(shè)計(jì)想出一個(gè)設(shè)計(jì)作為從對(duì)象到對(duì)象類的映射

出生日期結(jié)婚日期狗的出生日期日期類對(duì)象 對(duì)象類46面向?qū)ο笤O(shè)計(jì)

程序設(shè)計(jì)模擬這些組日期類狗的出生日期出生日期結(jié)婚日期描述實(shí)例47面向?qū)ο笤O(shè)計(jì)Date'sActionsinrealworld?Wecallanobject'sinteractionswithotherobjectsitsresponsibilitiesCreateitselfKnowthestateofitsfieldsCompareitselftoanotherdateReturnadate#dayshence48面向?qū)ο笤O(shè)計(jì)行為在程序世界里變成了方法日期類月日年狗的出生日期出生日期結(jié)婚日期49面向?qū)ο笤O(shè)計(jì)方法分解過(guò)程的四個(gè)階段集體討論過(guò)濾場(chǎng)景責(zé)任算法50CRC卡CRC卡就是用來(lái)記錄類信息的工具，它必須做并且必須與之協(xié)作51集體討論

一種集體問(wèn)題求解的方法，包括集體中每個(gè)成員的自由發(fā)言所有的點(diǎn)子都是具有潛力的好點(diǎn)子首先快速而瘋狂的想，最后去思考小幽默成就大力量集體討論是為了生成候選類列表52過(guò)濾確定問(wèn)題解決方案中的核心類在這份列表中，其實(shí)有兩個(gè)類是相同的在這份列表中，也許有的類根本就不屬于問(wèn)題的求解方案53場(chǎng)景給每個(gè)類分配責(zé)任責(zé)任的類型有兩種類自身必須知道什么（知識(shí)）(知識(shí)責(zé)任)類必須能夠做什么(行為責(zé)任)54場(chǎng)景封裝把數(shù)據(jù)和行為集中在一起，使數(shù)據(jù)和行為的邏輯屬性與他們的實(shí)現(xiàn)細(xì)節(jié)分離類把它的數(shù)據(jù)封裝了起來(lái)55責(zé)任算法必須為責(zé)任編寫算法知識(shí)責(zé)任通常只返回一個(gè)對(duì)象的變量的內(nèi)容行為責(zé)任復(fù)雜一些，通常涉及計(jì)算56一個(gè)計(jì)算機(jī)實(shí)例讓我們?cè)僦貜?fù)一次前面例子中使用的問(wèn)題求解過(guò)程，不過(guò)這次使用的是面向?qū)ο蟮姆椒w討論與過(guò)濾讓我們用波浪線標(biāo)出問(wèn)題陳述中的名詞，用下劃線標(biāo)注動(dòng)詞一個(gè)計(jì)算機(jī)實(shí)例第一遍列出的類如下：列表姓名電話號(hào)媽電子郵件地址列表順序姓名列表小紙片名片過(guò)濾列表列表,姓名,電話號(hào)碼，電子郵件地址58CRC卡你能想出其他有用的責(zé)任嗎?59CRC卡你能想出其他有用的責(zé)任嗎?

60CRC卡這個(gè)類與Name類和Person類有什么不同呢?61責(zé)任算法Person類Initializename.initialize() Write"Enterphonenumber;pressreturn."GettelephonenumberWrite"Enteremailaddress;pressreturn."GetemailaddressPrintname.print() Write"Telephonenumber:"+telephoneNumberWrite"Emailaddress:"+emailAddress自己進(jìn)行初始化自己輸出