Chp-4 程序設計層 -6 問題求解和算法設計

第6章問題求解和算法設計2章節(jié)目標確定一個問題是否適合用計算機解決結合Polya提出的如何解決問題的列表，描述計算機問題求解的步驟區(qū)別計算機算法和開發(fā)算法描述用于表示算法的偽代碼指令使用偽代碼表示算法3章節(jié)目標應用自頂向下的方法開發(fā)算法來解決問題定義面向對象設計方法中的術語應用面向對象的方法開發(fā)一組互動對象來解決問題求證與問題求解相關的幾點思想——信息隱蔽、抽象、事物命名和測試4問題求解問題求解尋找令人感到復雜、痛苦、煩惱或未解決的難題的解決方案的行為

你如何定義問題求解？5問題求解如何解決它：數學方法的新視點作者：

GeorgePolya雖然“如何解決它”這個列表是在解決數學問題時編寫的，但它是普遍適用的。我們可以用它來解決與計算機有關的問題。6問題求解如何解決問題呢？理解問題

找出解決方案

執(zhí)行方案

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

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

在有限的時間內用有限的數據解決問題或子問題的明確指令

指令為什么必須明確？

時間和數據為什么必須有限?11計算機問題求解分析和說明階段

分析

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

開發(fā)算法

測試算法實現階段

編碼

測試維護階段

使用

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

用新的基數除十進制數

把余數作為答案最左邊的一位數

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

把奶油替代品倒入鍋里Else

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

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

把奶油緩緩注入攪拌器關閉攪拌器16開發(fā)算法當前使用的把問題轉化為方案的方法有兩種：自頂向下面向對象

但是首先，我們先來看一種算法:偽代碼

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

答案135While(商不為0)

用新的基數除十進制

余數作為結果中最左邊一位

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

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

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

Write,Print輸入從外部世界向計算機中輸入數據值

Get,Read

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

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

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

Write"Enterapositivenumber."

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

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走查數據 填寫每一個迭代值3 numberRead number1 number25570213333 numberOfPairs

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

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

數學問題

我們測試答案

計算機問題

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

要預先把設計分發(fā)給大家，由一位（非設計者）逐行讀出設計，而其他人負責指出其中的錯誤39面向對象設計面向對象設計面向對象的設計方法是用叫做對象的獨立實體生成解決方案的問題求解方法對象是在問題背景中具有意義的事物或實體

例如,一個學生,一輛車,時間,日期40面相對象設計面向對象設計的世界觀問題求解：隔離問題中的對象決定它們的屬性和性能讓它們共同解決問題什么？再說一遍！41面向對象設計一個類比:你和你的朋友打點晚餐

對象:你，朋友，晚餐類:你和朋友都是人

人有姓名,瞳孔的顏色…

人可以購物,烹飪…類的實例:你和朋友都是人這一類的實例，

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

，你們每個都可以購物，烹飪你們合作安排晚餐42面向對象設計類(或者對象類)一組具有相似的屬性和行為的對象的描述對象(類的實例)一個具體的類的實例類包含代表以下內容的域 屬性(姓名,瞳孔的顏色)和行為(責任)(購物,烹飪)定義了類的一種行為的特定算法43面向對象設計自頂向下設計

將問題分解成多個任務面向對象設計

將問題分解成合作的對象是，但是怎么做呢？44面向對象設計步驟隔離問題中的對象abstracttheobjectswithlikepropertiesintogroups(classes)determinetheresponsibilitiesofthegroupininteractingwithothergroups45面向對象設計想出一個設計作為從對象到對象類的映射

出生日期結婚日期狗的出生日期日期類對象 對象類46面向對象設計

程序設計模擬這些組日期類狗的出生日期出生日期結婚日期描述實例47面向對象設計Date'sActionsinrealworld?Wecallanobject'sinteractionswithotherobjectsitsresponsibilitiesCreateitselfKnowthestateofitsfieldsCompareitselftoanotherdateReturnadate#dayshence48面向對象設計行為在程序世界里變成了方法日期類月日年狗的出生日期出生日期結婚日期49面向對象設計方法分解過程的四個階段集體討論過濾場景責任算法50CRC卡CRC卡就是用來記錄類信息的工具，它必須做并且必須與之協作51集體討論

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

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