第6章计算机学科基础.pptVIP

Chapter 6 Problem Solving and Algorithm Design问题求解和算法设计 Chapter Goals本章目标 Determine whether a problem is suitable for a computer solution 确定一个问题是否适合用计算机解决 Describe the computer problem-solving process and relate it to Polya’s How to Solve It list 结合Polya提出的如何解决问题的列表，描述计算机问题求解的步骤 Distinguish between following an algorithm and developing one 区别执行算法和开发算法 Apply top-down design methodology to develop an algorithm to solve a problem 应用自顶向下的方法开发算法来解决问题 Chapter Goals Define the key terms in object-oriented design 定义面向对象设计方法中的术语 Apply object-oriented design methodology to develop a collection of interacting objects to solve a problem 应用面向对象的方法开发一组互动对象来解决问题 Discuss the following threads as they relate to problem solving: information hiding, abstraction, naming things, and testing 求证与问题求解相关的几点思想 Problem Solving问题求解 Problem solving The act of finding a solution to a perplexing, distressing, vexing, or unsettled question 问题求解：找到令人感到困惑的难题的解决方案的行动。 Problem Solving问题求解 G. Polya wrote How to Solve It: A New Aspect of Mathematical Method 《如何解决它：数学方法的新视点》 His How to Solve It list is quite general 他的“如何解决它”这个列表是普遍适用的 Written in the context of solving mathematical problems 在解决数学问题这个背景下编写的 The list becomes applicable to all types of problems 这个列表完全适用于各种类型的问题 Ask Questions...提出问题 …to understand the problem What do I know about the problem? 对这个问题我了解多少？ What is the information that I have to process in order the find the solution? 要找到解决方案我必须处理哪些信息？ What does the solution look like? 解决方案是什么样的？ Ask Questions...提出问题 What sort of special cases exist? 存在什么特例？ How will I recognize that I have found the solution? 我如何知道已经找到了解决方案了？ 如何解决它？ 第一步 必须理解问题 第二步 找到信息和解决方案之间的联系。如果找不到直接的联系，则可能需要考虑辅助问题。最终，应该得到解决方案。 第三步 执行方案 第四步 分析得到的解决方案 Look for Familiar Things寻找熟悉的情况 You should never reinvent the wheel In computing, you see certain problems again and again in different guises 在计算领域中，你会看到某种问题不断地以不同的形式出现。 A good programmer sees a task, or perhaps part of a task (a subtask), that has bee