Chp-5-程序设计层--4-问题求解及算法设计.ppt

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,问题求解和算法设计,2,章节目标,确定一个问题是否适合用计算机解决,结合,Polya,提出的如何解决问题的列表，描述计算机问题求解的步骤,区别计算机算法和开发算法,描述用于表示算法的伪代码指令,使用伪代码表示算法,3,章节目标,应用自顶向下的方法开发算法来解决问题,定义面向对象设计方法中的术语,应用面向对象的方法开发一组互动对象来解决问题,求证与问题求解相关的几点思想,信息隐蔽,、,抽象,、,事物命名和测试,4,问题求解,问题求解,寻找令人感到复杂,、,痛苦,、,烦恼或未解决的难题的解决方案的行为,你如何定义问题求解？,5,问题求解,如何解决它：数学方法的新视点,作者：,George Polya,虽然“如何解决它”这个列表是在解决数学问题时编写的，,但它是普遍适用的。,我们可以用它来解决与计算机有关,的问题。,6,问题求解,如何解决问题呢？,理解问题,找出解决方案,执行方案,分析得到的解决方案,7,策略,提出问题,!,对这个问题我了解多少,?,要找到解决方案我必须处理哪些信息？,解决方案是什么样的,?,存在什么特例,?,我如何知道已经找到解决方案了？,8,策略,提出问题,!,永远不要彻底重新做一件事！,如果以前曾经解决过相同或相似的问题，只需要再次使用那种成功的方案即可,一个好的程序员看到以前解决的任务或者任务中的一部分时会直接选用已有的方案,你能想到两个相似的问题吗？,9,策略,分治法,!,把一个大问题划分为几个能解决的小单元,抽象概念的运用,可以反复利用分治法，直到每个子任务都是可以实现的为止,10,算法,算法,在,有限的时间,内用,有限的数据,解决问题或子问题的,明确,指令,指令为什么必须明确？,时间和数据为什么必须有限,?,11,计算机问题求解,分析和说明阶段,分析,说明,算法开发阶段,开发算法,测试算法,实现阶段,编码,测试,维护阶段,使用,维护,你能说出一个,反复出现的主,题吗,?,12,阶段交互,我们需要增,加其他的箭,头吗？,（如果这个问题,被修正以后会,发生什么？）,13,伪代码,伪代码,用混合的英语和格式使算法的步骤明确的语言,把十进制数转换成其他进制数的算法的伪代码,While(,商不为,0),用新的基数除十进制数,把余数作为答案最左边的一位数,用商替换原来的十进制数,14,执行算法,图,6.4,蛋黄奶油酸辣酱的菜谱,15,执行算法,准备做蛋黄奶油酸辣酱的算法,If,在意卡路里,把奶油替代品倒入锅里,Else,把奶油倒入锅内,打开火炉,把锅放在火炉上,While(,未起泡,),把锅置于火炉上,把其他配料放入搅拌器,启动搅拌器,While(,还有奶油,),把奶油缓缓注入搅拌器,关闭搅拌器,16,开发算法,当前使用的把问题转化为方案的方法有两种：,自顶向下,面向对象,但是首先，我们先来看一种算法,:,伪代码,17,伪代码,伪代码,一种英语和意图相混合的能将算法步骤表述明确的语言,伪代码中没有语法规定,伪代码中是不区分大小写的,18,执行算法,8,除,93,是？,93/8,商,11,余,5,11/6,商,1,余,3,1/8,商,0,余,1,答案,1 3 5,While(,商不为,0),用新的基数除十进制,余数作为结果中最左边一位,用商替换原来的十进制数,19,执行算法,得到答案的更简单方案,20,完整的伪代码解决方案,Write Enter the new base,Read newBase,Write Enter the number to be converted,Read decimalNumber,Set quotient to 1,While(quotient is not zero),Set quotient to decimalNumber DIV newBase,Set remainder to decimalNumber REM newBase,Make the remainder the next digit to the left in the answer,Set decimalNumber to quotient,Write The answer is,Write answer,21,伪代码的功能,变量,出现在伪代码中的名字，引用的是存储值的位置,quotient,decimalNumber,newBase,赋值,把值放入变量,Set quotient to 64,quotient-64,quotient-6*10+4,22,伪代码的功能,输出,把值输出到输出设备,Write,Print,输入,从外部世界向计算机中输入数据值,Get,Read,23,伪代码的功能,重复,重复一系列指令,Set count to 1,While(count 10),Write Enter an integer number,Read aNumber,Write You entered +aNumber,Set count to count+1,读了几个值,?,24,伪代码的功能,选择,选择执行或跳过某项操作,Read number,If(number 0),Write number+is less than zero.,or,Write Enter a positive number.,Read number,If(number 0),Write number+is less than zero.,Write You didnt follow instructions.,25,伪代码的功能,选择,选择执行某项操作,If(age 12),Write Pay childrens rate,Write You get a free box of popcorn,else If(age 65),Write Pay regular rate,else,Write Pay senior citizens rate,26,伪代码的功能,Write How many pairs of values are to be entered?,Read numberOfPairs,Set numberRead to 0,While(numberRead numberOfPairs),Write Enter two values separated by a blank;press return,Read number1,Read number2,If(number1 number2),Print number1+number2,Else,Print number2+number1,Increment numberRead,27,走查,数据 填写每一个迭代值,3,numberReadnumber1number2,55 70,2 1,33 33,numberOfPairs,输出是什么,?,28,自顶向下设计方法,自顶向下设计,把问题分解成一套子问题，然后再把子问题分解成子问题，直到每个子问题都足够基础，不再需要再进一步分解为止,模块,一个用于解决问题或子问题的封闭步骤集合,抽象步骤,细节仍未明确的算法步骤,具体步骤,细节完全明白的算法步骤,29,自顶向下设计方法,这个过程将在多个层次中重复，把每个任务扩展成最小的细节,可将困难繁重的任务推到较低的层次中。,图,6.7,自顶向下设计的例子,30,一个通用的实例,筹划一个大型集会,图,6.6,划分聚会计划,31,一个计算机实例,问题,创建一个包括每个人的姓名、地址、电话号码和电子邮件地址的地址列表。,按字母顺序输出该列表,加入这个列表的姓名是出现在小纸片和名片上的,32,一个计算机实例,Main,Level 0,Enter names and numbers into list,Put list into alphabetical order,Print list,Enter names and numbers into list,Level 1,While(more names),Enter name,Enter telephone number,Enter email address,Insert information into list,哪些步骤是抽象的？哪些步骤是具体的？哪些步骤,是丢失的？,33,一个计算机实例,Enter names and numbers into list(revised),Level 1,Set moreNames to true,While(moreNames),Prompt for and enter name,Prompt for and enter telephone number,Prompt for and enter email address,Insert information into list,Write Enter a 1 to continue or a 0 to stop.,Read response,If(response=0),Set moreNames to false,哪些步骤是具体的？哪些步骤路是抽象的？,34,一个计算机实例,Prompt for and enter name,Level 2,Write Enter last name;press return.,Read lastName,Write Enter first name;press return.,Read firstName,Prompt for and enter telephone number,Level 2,Write Enter area code and 7-digit number;press return.,Read telephoneNumber,Prompt for and enter email address,Level 2,Write Enter email address;press return.,Read emailAddress,35,一个计算机实例,Put list into alphabetical order,具体还是抽象？,Print the list,Level 1,Write The list of names,telephone numbers,and email,addresses follows:,Get first item from the list,While(more items),Write items firstName+lastName,Write items telephoneNumber,Write items emailAddress,Write a blank line,Get next item from the list,36,一个计算机实例,注：在循环中插入信息,37,测试算法,重要的区别,数学问题,我们测试答案,计算机问题,我们测试过程,38,测试算法,桌面检查,在纸上跟踪的一种设计的执行情况,走查,由小组成员手动地模拟设计，采用的是示例数据,审查,要预先把设计分发给大家，由一位（非设计者）逐行读出设计，而其他人负责指出其中的错误,39,面向对象设计,面向对象设计,面向对象的设计方法是用叫做对象的独立实体生成解决方案的问题求解方法,对象,是在问题背景中具有意义的事物或实体,例如,一个学生,一辆车,时间,日期,40,面相对象设计,面向对象设计的世界观,问题求解：,隔离问题中的,对象,决定它们的,属性,和,性能,让它们共同解决问题,什么？再说一遍！,41,面向对象设计,一个类比,:,你和你的朋友打点晚餐,对象,:,你，朋友，晚餐,类,:,你和朋友都是人,人有姓名,瞳孔的颜色,人可以购物,烹饪,类的实例,:,你和朋友都是人这一类的实例，,你们都有自己的名字，有自己瞳孔的颜色,，你们每个都可以购物，烹饪,你们,合作,安排晚餐,42,面向对象设计,类,(,或者对象类,),一组具有相似的属性和行为的对象的描述,对象,(,类的实例,),一个具体的类的实例,类,包含代表以下内容的域,属性,(,姓名,瞳孔的颜色,),和,行为,(,责任,),(,购物,烹饪,),定义了类的一种行为的特定算法,43,面向对象设计,自顶向下设计,将问题分解成多个任务,面向对象设计,将问题分解成合作的对象,是，但是怎么做呢？,44,面向对象设计,步骤,隔离,问题中的对象,abstract,the objects with like properties into groups(classes),determine,the responsibilities of the group in interacting with other groups,45,面向对象设计,想出一个设计作为从对象到对象类的映射,出生日期,结婚日期,狗的出生,日期,日期类,对象 对象类,46,面向对象设计,程序设计模拟这些组,日期类,狗的出生日期,出生日期,结婚日期,描述 实例,47,面向对象设计,Dates,Actions in,real world,?,We call an objects interactions,with other objects its,responsibilities,Create itself,Know the state of its fields,Compare itself to another date,Return a date#days hence,48,面向对象设计,行为在程序世界里变成了方法,日期类,月,日,年,狗的出生日期,出生日期,结婚日期,49,面向对象设计方法,分解过程的四个阶段,集体讨论,过滤,场景,责任算法,50,CRC,卡,CRC,卡就是用来记录类信息的工具，它必须做并且必须,与之协作,51,集体讨论,一种集体问题求解的方法，包括集体中每个成员的自由发言,所有的点子都是具有潜力的好点子,首先快速而疯狂的想，最后去思考,小幽默成就大力量,集体讨论是为了生成候选类列表,52,过滤,确定问题解决方案中的核心类,在这份列表中，其实有两个类是相同的,在这份列表中，也许有的类根本就不属于问题的求解方案,53,场景,给每个类分配责任,责任的类型有两种,类自身必须知道什么（知识）,(,知识责任,),类必须能够做什么,(,行为责任,),54,封装,封装,把数据和行为集中在一起，使数据和行为的逻辑属性与他们的实现细节分离,类把它的数据封装了起来,55,责任算法,必须为责任编写算法,知识责任通常只返回一个对象的变量的内容,行为责任复杂一些，通常涉及计算,56,一个计算机实例,让我们再重复一次前面例子中使用的问题求解过程，不过这次使用的是面向对象的方法,集体讨论与过滤,让我们用波浪线标出问题陈述中的名词，用下划线标注动词,一个计算机实例,第一遍列出的类如下：,列表,姓名,电话号妈,电子邮件地址,列表,顺序,姓名,列表,小纸片,名片,过滤列表,列表,姓名,电话号码，电子邮件地址,58,CRC,卡,你能想出其他有用的责任吗,?,59,CRC,卡,你能想出其他有用的责任吗,?,60,CRC,卡,这个类与,Name,类和,Person,类有什么不同呢,?,61,责任算法,Person,类,Initialize,name.initialize(),Write Enter phone number;press return.,Get telephone number,Write Enter email address;press return.,Get email address,Print,name.print(),Write Telephone number:+telephoneNumber,Write Email address:+emailAddress,自己进行初始化,自己输出,62,责任算法,Name,类,Initialize,Enter the first name;press return.,Read firstName,Enter the last name;press return.,Read lastName,Print,Print First name:+firstName,Print Last name:+lastName,63,重要思想,信息隐藏,隐蔽模块的细节以控制对这些细节的访问的做法,抽象,复杂系统的一种模型，只包括对观察者来说必须的细节,信息隐藏,和,抽象,就像硬币的两面,64,重要思想,数据抽象,把数据的逻辑概观和它的实现分离开,过程抽象,把动作的逻辑概观和它的实现分开,控制抽象,把控制结构的逻辑概观和它的实现分离开,65,重要思想,抽象是人们用来处理复杂事物的最强有力的工具。,66,重要思想,标识符,给数据和过程一个名字，这些名字叫做标识符,数据和动作的标识符都是抽象的一种形式,67,重要思想,程序设计语言,用于构造程序的规则，符号和专用字集合,程序,用于执行特定任务的指令序列,语法,规定有效指令的结构的正式规则,语义,赋予程序设计语言中的指令含义的一套规则,