解决问题的一般概念解决问题的一般概念要点要点v日常生活问题的解决日常生活问题的解决v问题的类型问题的类型v计算机解决的问题计算机解决的问题v解决问题的难点解决问题的难点一、日常生活问题的解决1.1.明确问题明确问题明确问题明确问题2.2.理解问题理解问题理解问题理解问题理解问题提出方的知识背景；了解自己的知识背景；理解问题提出方的知识背景；了解自己的知识背景；关键是必须能与客户沟通并搞清楚解决问题涉及的细节。关键是必须能与客户沟通并搞清楚解决问题涉及的细节。3.3.寻找备选方案寻找备选方案寻找备选方案寻找备选方案尽可能全面列出可行的备选方案。尽可能全面列出可行的备选方案。4.4.从备选方案列表中找出最好的解决方案从备选方案列表中找出最好的解决方案从备选方案列表中找出最好的解决方案从备选方案列表中找出最好的解决方案制定一个评定的标准，对所有的方案进行评价。制定一个评定的标准，对所有的方案进行评价。5.5.列出所选择的解决方案的指令列出所选择的解决方案的指令列出所选择的解决方案的指令列出所选择的解决方案的指令这些有限的、分步的指令必须包含在第二步所确定的知识这些有限的、分步的指令必须包含在第二步所确定的知识范围内。范围内。6.6.评价解决方案评价解决方案评价解决方案评价解决方案检查它的结果是否正确，是否令用户满意，如果结果错误检查它的结果是否正确，是否令用户满意，如果结果错误或者不能令人满意，必须重新设计一个解决方案。或者不能令人满意，必须重新设计一个解决方案。例子关于今晚做什么的问题第一步：明确问题第一步：明确问题如何度过一个漫长的夜晚。如何度过一个漫长的夜晚。第二步：理解问题。第二步：理解问题。大学生、住校、学校纪律、学习压力大学生、住校、学校纪律、学习压力.第三步：寻找备选第三步：寻找备选（1）看电视）看电视（2）玩游戏）玩游戏 （3）去教室学习）去教室学习（4）在寝室学习）在寝室学习。第四步：从备选方案列表中找出最好的解决方案。第四步：从备选方案列表中找出最好的解决方案。去教室学习去教室学习第五步：准备一个步骤（指令）列表第五步：准备一个步骤（指令）列表（1）背书包）背书包（2）进教室）进教室（3）学习高数）学习高数（4）学习英语）学习英语 （5）学习线代）学习线代 （6）回寝室）回寝室第六步：评价这个方案。第六步：评价这个方案。有意义吗？快乐吗？有意义吗？快乐吗？ 描述问题的格式描述问题的格式第一步：明确问题。第一步：明确问题。第二步：理解问题。第二步：理解问题。（1）在有助于问题理解的地方进行解释）在有助于问题理解的地方进行解释（2）描述知识背景（包括解决问题所需要的各种知识）描述知识背景（包括解决问题所需要的各种知识）第三步：寻找备选第三步：寻找备选方案方案优点优点缺点缺点（1）（2）（3）。第四步：从备选方案列表中找出最好的解决方案。第四步：从备选方案列表中找出最好的解决方案。为什么选择这个方案？为什么选择这个方案？第五步：列出所选择的解决方案的指令第五步：列出所选择的解决方案的指令（1）（2）（3）。第六步：评价这个方案。第六步：评价这个方案。这个方案有效吗？如果无效，如何进行改进？这个方案有效吗？如果无效，如何进行改进？ 例子两个整数的乘法第一步：明确问题第一步：明确问题整数乘法。整数乘法。第二步：理解问题。第二步：理解问题。只能用笔和纸，知道乘法表，只能用笔和纸，知道乘法表，.第三步：寻找备选第三步：寻找备选（1）传统算法）传统算法（2）英国算法）英国算法（3）a la russe(俄罗斯式俄罗斯式)算法算法（4）分治法）分治法第四步：从备选方案列表中找出最好的解决方案。第四步：从备选方案列表中找出最好的解决方案。传统算法。传统算法。（什么标准？）什么标准？）第五步：准备一个步骤（指令）列表第五步：准备一个步骤（指令）列表从右到左取出被乘数的每一位，与乘数相乘，把中间结果写在从右到左取出被乘数的每一位，与乘数相乘，把中间结果写在上一个中间结果的下面，同时最低位往左偏移一位。把每一行全部加起上一个中间结果的下面，同时最低位往左偏移一位。把每一行全部加起来得到结果。来得到结果。第六步：评价这个方案。第六步：评价这个方案。结果正确。结果正确。981123439242943.1962.981.1210554传统算法传统算法9811234981.1962.2943.39241210554英国算法英国算法98112341234490246824549364936122987261197441974430394881578976789767157952157952331590431590416318086318081210554a la russe(俄罗斯式俄罗斯式)算法算法把乘数和被乘数并排写在一起，每个把乘数和被乘数并排写在一起，每个操作数一列。操作数一列。1、将左边操作数整除、将左边操作数整除2，在该操作数，在该操作数下面写下商；下面写下商；2、将右边操作数乘以、将右边操作数乘以2，在该操作数，在该操作数下面写下积。下面写下积。3、以上一次的商和积作为操作数重、以上一次的商和积作为操作数重复以上规则，直到左边的操作数为复以上规则，直到左边的操作数为1为止。为止。4、接着把左列中商为偶数的行全部、接着把左列中商为偶数的行全部删除，最后把右列中剩下的数字加起删除，最后把右列中剩下的数字加起来就得到结果。来就得到结果。不需要乘法表！在计算机硬件中就用到了类似的算法进行乘法运算。X0Y1234X121*YX222*Y4936X323*YX424*Y19744X525*YX626*Y78976X727*Y157952X828*Y315904X929*Y6318081210554X = X0 + X1* 21 + X2* 22 + Xn-1* 2n-1+ + Xn* 2n其中 Xi = 0, 1 (i=0,1,n)X * Y = (X0 + X1* 21 + X2* 22 + Xn-1* 2n-1+ + Xn* 2n) * Y= X0 * Y + X1* 21 * Y + X2* 22 * Y + + Xn-1* 2n-1 * Y + + Xn* 2n * Y乘乘移位移位结果结果1）09124108.2）09342306.3）81122972.4）8134027541210554uv xy= ( 102 u + v ) ( 102 x + y )= 104 ux + 102 (uy + vx) + vy一个一个4位数分解成两个位数分解成两个2位数位数分治法分治法二、问题的类型二、问题的类型v算法方案：算法方案：可以通过一系列的动作来解决问题的方案，叫做可以通过一系列的动作来解决问题的方案，叫做算法方案算法方案。通过选定的步骤达到预期的目标，这些步骤叫做通过选定的步骤达到预期的目标，这些步骤叫做算法算法。v启发式方案：启发式方案：不能通过一些直观的步骤来解决的方案叫做不能通过一些直观的步骤来解决的方案叫做启发式方案启发式方案。（这类问题除了必须有相应的知识和经验外，还需要经过不（这类问题除了必须有相应的知识和经验外，还需要经过不断的尝试和失败才能达到最终目标。）断的尝试和失败才能达到最终目标。）韦氏大学词典（第九版）韦氏大学词典（第九版）中，算法的解释是中，算法的解释是“求解数学求解数学问题（如寻找最大公约数）的一个过程，该过程步骤有限，问题（如寻找最大公约数）的一个过程，该过程步骤有限，通常还涉及重复的操作；广义地说，算法是按部就班解决一通常还涉及重复的操作；广义地说，算法是按部就班解决一个问题或完成某个目标的过程。个问题或完成某个目标的过程。”问题解决者在算法方案和启发式方案中都可以采问题解决者在算法方案和启发式方案中都可以采取取6个步骤。个步骤。在启发式方案中，第在启发式方案中，第6步的正确性和恰当性标准步的正确性和恰当性标准不确定。不确定。在启发式方案中，问题解决者通常要反复执行这在启发式方案中，问题解决者通常要反复执行这6个步骤，并在做出决定前仔细评价每一种可能个步骤，并在做出决定前仔细评价每一种可能的方案。同一种方案不一定在任何时候都适用，的方案。同一种方案不一定在任何时候都适用，所以问题解决者在以后解决同样问题的时候必须所以问题解决者在以后解决同样问题的时候必须重新进行评价和分析。重新进行评价和分析。许多问题需要将这两种方案结合起来加以解决。许多问题需要将这两种方案结合起来加以解决。三、计算机解决的问题三、计算机解决的问题v解决方案解决方案：本课程中特指问题解决过程中的第本课程中特指问题解决过程中的第5步所列出的指步所列出的指令序列。遵从这些指令才能得到满意的结果。令序列。遵从这些指令才能得到满意的结果。v结果结果：指成果或在计算机辅助下得到的完整答案。指成果或在计算机辅助下得到的完整答案。v程序程序：指用特定的计算机语言编写的一组用于解决问题的指用特定的计算机语言编写的一组用于解决问题的指令。指令。计算机主要用来执行那些对于人来说非常困难或计算机主要用来执行那些对于人来说非常困难或非常耗时的算法方案。非常耗时的算法方案。u计算复杂的微积分；计算复杂的微积分；u将将1，000，000个名字按字母排序，个名字按字母排序，u。人类比计算机更善于使用启发式方案。人类比计算机更善于使用启发式方案。n下围棋下围棋n说汉语说汉语n。处理启发式问题所涉及的计算机技术领域叫做处理启发式问题所涉及的计算机技术领域叫做人人工智能。工智能。人工智能可以让计算机建立自己的知识库并学会人工智能可以让计算机建立自己的知识库并学会人类的语言等。人工智能是处于发展中的计算机人类的语言等。人工智能是处于发展中的计算机技术领域。技术领域。启发式方案必须首先转化成算法形式才能供计算启发式方案必须首先转化成算法形式才能供计算机使用。机使用。四、解决问题的难点四、解决问题的难点v人类在解决问题时会遇到很多问题。人类在解决问题时会遇到很多问题。通常是不能很好地完成其中的一步或几步；通常是不能很好地完成其中的一步或几步；可能错误地定义了问题；可能错误地定义了问题；没有列出足够的备选方案；没有列出足够的备选方案；排除了好的方案，错误估计了利弊；排除了好的方案，错误估计了利弊；可能搞错了步骤的顺序；可能搞错了步骤的顺序；过早专注细节、忽略了整体框架；过早专注细节、忽略了整体框架；没有对方案进行测试；没有对方案进行测试；错误或草率地评价解决方案；错误或草率地评价解决方案；问题解决的过程不问题解决的过程不容易掌握，需要花容易掌握，需要花大量的时间和实践大量的时间和实践进行完善。进行完善。v在用计算机解决问题时，最难的事情之一就是编写在用计算机解决问题时，最难的事情之一就是编写指令。指令。“我不能解释我是如何知道的，但我就是知道我不能解释我是如何知道的，但我就是知道”这种解释对这种解释对计算机来说没有什么用处。计算机是一种工具，它只能执行计算机来说没有什么用处。计算机是一种工具，它只能执行用户解释清楚的任务。用户解释清楚的任务。计算机有它自己特殊的通信系统，无论是程序员还是用户都计算机有它自己特殊的通信系统，无论是程序员还是用户都必须了解它。必须了解它。这套系统要求我们详细阐明解决方案中的每一个步骤而且顺这套系统要求我们详细阐明解决方案中的每一个步骤而且顺序正确。序正确。要知道，除非我们告诉它，否则计算机一无所知，然而虽然要知道，除非我们告诉它，否则计算机一无所知，然而虽然它很无知，但它对解决问题却很有帮助。它很无知，但它对解决问题却很有帮助。五、小结五、小结v问题解决过程中的问题解决过程中的6个步骤个步骤v算法方案算法方案v启发式方案启发式方案v计算机能够解决的问题计算机能够解决的问题六、术语六、术语v算法（算法（algorithm）v算法方案（算法方案（algorithmic solution）v启发式方案（启发式方案（heuristic solution）v程序（程序（program）v结果（结果（Result）v解决方案（解决方案（solution）