Chp-4 程序设计层 -6 问题求解和算法设计

第6章问题求解和算法设计2章节目标确定一个问题是否适合用计算机解决结合Polya提出的如何解决问题的列表，描述计算机问题求解的步骤区别计算机算法和开发算法描述用于表示算法的伪代码指令使用伪代码表示算法3章节目标应用自顶向下的方法开发算法来解决问题定义面向对象设计方法中的术语应用面向对象的方法开发一组互动对象来解决问题求证与问题求解相关的几点思想——信息隐蔽、抽象、事物命名和测试4问题求解问题求解寻找令人感到复杂、痛苦、烦恼或未解决的难题的解决方案的行为

你如何定义问题求解？5问题求解如何解决它：数学方法的新视点作者：

GeorgePolya虽然“如何解决它”这个列表是在解决数学问题时编写的，但它是普遍适用的。我们可以用它来解决与计算机有关的问题。6问题求解如何解决问题呢？理解问题

找出解决方案

执行方案

分析得到的解决方案7策略提出问题!对这个问题我了解多少?要找到解决方案我必须处理哪些信息？解决方案是什么样的?存在什么特例?我如何知道已经找到解决方案了？8策略提出问题!永远不要彻底重新做一件事！如果以前曾经解决过相同或相似的问题，只需要再次使用那种成功的方案即可一个好的程序员看到以前解决的任务或者任务中的一部分时会直接选用已有的方案

你能想到两个相似的问题吗？9策略分治法!把一个大问题划分为几个能解决的小单元抽象概念的运用可以反复利用分治法，直到每个子任务都是可以实现的为止10算法算法

在有限的时间内用有限的数据解决问题或子问题的明确指令

指令为什么必须明确？

时间和数据为什么必须有限?11计算机问题求解分析和说明阶段

分析

说明算法开发阶段

开发算法

测试算法实现阶段

编码

测试维护阶段

使用

维护你能说出一个反复出现的主题吗?12阶段交互我们需要增加其他的箭头吗？（如果这个问题被修正以后会发生什么？）13伪代码伪代码用混合的英语和格式使算法的步骤明确的语言把十进制数转换成其他进制数的算法的伪代码While(商不为0)

用新的基数除十进制数

把余数作为答案最左边的一位数

用商替换原来的十进制数14执行算法图6.4蛋黄奶油酸辣酱的菜谱15执行算法准备做蛋黄奶油酸辣酱的算法If在意卡路里

把奶油替代品倒入锅里Else

把奶油倒入锅内打开火炉把锅放在火炉上While(未起泡)

把锅置于火炉上把其他配料放入搅拌器启动搅拌器While(还有奶油)

把奶油缓缓注入搅拌器关闭搅拌器16开发算法当前使用的把问题转化为方案的方法有两种：自顶向下面向对象

但是首先，我们先来看一种算法:伪代码

17伪代码伪代码一种英语和意图相混合的能将算法步骤表述明确的语言伪代码中没有语法规定Pseudocodeisnotcasesensitive伪代码中是不区分大小写的18执行算法8除93是？ 93/8商11余5 11/6商1余3 1/8商0余1

答案135While(商不为0)

用新的基数除十进制

余数作为结果中最左边一位

用商替换原来的十进制数19执行算法得到答案的更简单方案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伪代码的功能选择选择执行或跳过某项操作

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

Write"Enterapositivenumber."

Readnumber If(number<0) Writenumber+"islessthanzero." Write"Youdidn'tfollowinstructions."25伪代码的功能选择选择执行某项操作

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自顶向下设计方法自顶向下设计把问题分解成一套子问题，然后再把子问题分解成子问题，直到每个子问题都足够基础，不再需要再进一步分解为止模块一个用于解决问题或子问题的封闭步骤集合抽象步骤细节仍未明确的算法步骤具体步骤细节完全明白的算法步骤29自顶向下设计方法这个过程将在多个层次中重复，把每个任务扩展成最小的细节可将困难繁重的任务推到较低的层次中。图6.7

自顶向下设计的例子30一个通用的实例筹划一个大型集会图6.6划分聚会计划31一个计算机实例问题创建一个包括每个人的姓名、地址、电话号码和电子邮件地址的地址列表。按字母顺序输出该列表加入这个列表的姓名是出现在小纸片和名片上的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一个计算机实例注：在循环中插入信息37测试算法重要的区别

数学问题

我们测试答案

计算机问题

我们测试过程38测试算法桌面检查在纸上跟踪的一种设计的执行情况走查由小组成员手动地模拟设计，采用的是示例数据审查

要预先把设计分发给大家，由一位（非设计者）逐行读出设计，而其他人负责指出其中的错误39面向对象设计面向对象设计面向对象的设计方法是用叫做对象的独立实体生成解决方案的问题求解方法对象是在问题背景中具有意义的事物或实体

例如,一个学生,一辆车,时间,日期40面相对象设计面向对象设计的世界观问题求解：隔离问题中的对象决定它们的属性和性能让它们共同解决问题什么？再说一遍！41面向对象设计一个类比:你和你的朋友打点晚餐

对象:你，朋友，晚餐类:你和朋友都是人

人有姓名,瞳孔的颜色…

人可以购物,烹饪…类的实例:你和朋友都是人这一类的实例，

你们都有自己的名字，有自己瞳孔的颜色

，你们每个都可以购物，烹饪你们合作安排晚餐42面向对象设计类(或者对象类)一组具有相似的属性和行为的对象的描述对象(类的实例)一个具体的类的实例类包含代表以下内容的域 属性(姓名,瞳孔的颜色)和行为(责任)(购物,烹饪)定义了类的一种行为的特定算法43面向对象设计自顶向下设计

将问题分解成多个任务面向对象设计

将问题分解成合作的对象是，但是怎么做呢？44面向对象设计步骤隔离问题中的对象abstracttheobjectswithlikepropertiesintogroups(classes)determinetheresponsibilitiesofthegroupininteractingwithothergroups45面向对象设计想出一个设计作为从对象到对象类的映射

出生日期结婚日期狗的出生日期日期类对象 对象类46面向对象设计

程序设计模拟这些组日期类狗的出生日期出生日期结婚日期描述实例47面向对象设计Date'sActionsinrealworld?Wecallanobject'sinteractionswithotherobjectsitsresponsibilitiesCreateitselfKnowthestateofitsfieldsCompareitselftoanotherdateReturnadate#dayshence48面向对象设计行为在程序世界里变成了方法日期类月日年狗的出生日期出生日期结婚日期49面向对象设计方法分解过程的四个阶段集体讨论过滤场景责任算法50CRC卡CRC卡就是用来记录类信息的工具，它必须做并且必须与之协作51集体讨论

一种集体问题求解的方法，包括集体中每个成员的自由发言所有的点子都是具有潜力的好点子首先快速而疯狂的想，最后去思考小幽默成就大力量集体讨论是为了生成候选类列表52过滤确定问题解决方案中的核心类在这份列表中，其实有两个类是相同的在这份列表中，也许有的类根本就不属于问题的求解方案53场景给每个类分配责任责任的类型有两种类自身必须知道什么（知识）(知识责任)类必须能够做什么(行为责任)54场景封装把数据和行为集中在一起，使数据和行为的逻辑属性与他们的实现细节分离类把它的数据封装了起来55责任算法必须为责任编写算法知识责任通常只返回一个对象的变量的内容行为责任复杂一些，通常涉及计算56一个计算机实例让我们再重复一次前面例子中使用的问题求解过程，不过这次使用的是面向对象的方法集体讨论与过滤让我们用波浪线标出问题陈述中的名词，用下划线标注动词一个计算机实例第一遍列出的类如下：列表姓名电话号妈电子邮件地址列表顺序姓名列表小纸片名片过滤列表列表,姓名,电话号码，电子邮件地址58CRC卡你能想出其他有用的责任吗?59CRC卡你能想出其他有用的责任吗?

60CRC卡这个类与Name类和Person类有什么不同呢?61责任算法Person类Initializename.initialize() Write"Enterphonenumber;pressreturn."GettelephonenumberWrite"Enteremailaddress;pressreturn."GetemailaddressPrintname.print() Write"Telephonenumber:"+telephoneNumberWrite"Emailaddress:"+emailAddress自己进行初始化自己输出