程序设计基础内部讲义

《程序设计基础内部讲义》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、仅供2012级教学使用郑州大学2012级计算机科学与技术程序设计基础内部讲义讲授教师：王黎明班级：姓名：-122-仅供2012级教学使用第一章解决问题的一般概念要点l日常生活问题的解决l问题的类型l计算机解决的问题l解决问题的难点一、日常生活问题的解决1.明确问题：2.理解问题：理解问题提出方的知识背景；了解自己的知识背景；关键是必须能与客户沟通并搞清楚解决问题涉及的细节。3.寻找备选方案：尽可能全面列出可行的备选方案。4.从备选方案列表中找出最好的解决方案：制定一个评定的标准，对所有的方案进行评价。5.列出所选择的解决方案的指令：这些有限的

2、、分步的指令必须包含在第二步所确定的知识范围内。6.评价解决方案：检查它的结果是否正确，是否令用户满意，如果结果错误或者不能令人满意，必须重新设计一个解决方案。解决问题的这6个步骤可以适用于绝大多数情况。大多数人可能不知道这6个步骤，但却一直在使用它们。[例子]关于今晚做什么的问题第一步：明确问题如何度过一个漫长的夜晚。第二步：理解问题。大学生、住校、学校纪律、学习压力......-122-仅供2012级教学使用第三步：寻找备选（1）看电视（2）玩游戏（3）去教室学习（4）在寝室学习第四步：从备选方案列表中找出最好的解决方案。去教室学习第五步

3、：准备一个步骤（指令）列表（1）背书包（2）进教室（3）学习高数（4）学习英语（5）学习线代（6）回寝室第六步：评价这个方案。有意义吗？快乐吗？描述问题的格式第一步：明确问题。第二步：理解问题。（1）在有助于问题理解的地方进行解释（2）描述知识背景（包括解决问题所需要的各种知识）第三步：寻找备选方案优点缺点（1）（2）（3）……第四步：从备选方案列表中找出最好的解决方案。为什么选择这个方案？第五步：列出所选择的解决方案的指令（1）（2）（3）……第六步：评价这个方案。这个方案有效吗？如果无效，如何进行改进？[例子]两个整数的乘法第一步：明确问

4、题整数乘法。第二步：理解问题。只能用笔和纸，知道乘法表，......第三步：寻找备选（1）传统算法（2）英国算法-122-仅供2012级教学使用（3）alarusse(俄罗斯式)算法（4）分治法第四步：从备选方案列表中找出最好的解决方案。传统算法。（什么标准？）第五步：准备一个步骤（指令）列表从右到左取出被乘数的每一位，与乘数相乘，把中间结果写在上一个中间结果的下面，同时最低位往左偏移一位。把每一行全部加起来得到结果。第六步：评价这个方案。结果正确。传统算法英国式算法alarusse(俄罗斯式)算法把乘数和被乘数并排写在一起，每个操作数一列。

5、1、将左边操作数整除2，在该操作数下面写下商；2、将右边操作数乘以2，在该操作数下面写下积。3、以上一次的商和积作为操作数重复以上规则，直到左边的操作数为1为止。4、接着把左列中商为偶数的行全部删除，最后把右列中剩下的数字加起来就得到结果。不需要乘法表！！！在计算机硬件中就用到了类似的算法进行乘法运算。分治法-122-仅供2012级教学使用uv×xy=(102u+v)×(102x+y)=104ux+102(uy+vx)+vy二、问题的类型l算法方案：可以通过一系列的动作来解决问题的方案，叫做算法方案。通过选定的步骤达到预期的目标，这些步骤叫做

6、【算法】。l启发式方案：不能通过一些直观的步骤来解决的方案叫做启发式方案。（这类问题除了必须有相应的知识和经验外，还需要经过不断的尝试和失败才能达到最终目标。）《韦氏大学词典（第九版）》中，算法的解释是“求解数学问题（如寻找最大公约数）的一个过程，该过程步骤有限，通常还涉及重复的操作；广义地说，算法是按部就班解决一个问题或为达到某个目标的过程。”l问题解决者在算法方案和启发式方案中都可以采取6个步骤。l在启发式方案中，第6步的正确性和恰当性标准不确定。l在启发式方案中，问题解决者通常要反复执行这6个步骤，并在做出决定前仔细评价每一种可能的方案

7、。同一种方案不一定在任何时候都适用，所以问题解决者在以后解决同样问题的时候必须重新进行评价和分析。l许多问题需要将这两种方案结合起来加以解决。三、计算机解决的问题l解决方案：本课程中特指问题解决过程中的第5步所列出的指令序列。遵从这些指令才能得到满意的结果。l结果：指成果或在计算机辅助下得到的完整答案。l程序：指用特定的计算机语言编写的一组用于解决问题的指令。l计算机主要用来执行那些对于人来说非常困难或非常耗时的算法方案。-122-仅供2012级教学使用n计算复杂的微积分；n将1，000，000个名字按字母排序，n。。。l人类比计算机更善于使

8、用启发式方案。n下围棋n说汉语n。。。l处理启发式问题所涉及的计算机技术领域叫做人工智能。人工智能可以让计算机建立自己的知识库并学会人类的语言等，通过人工的手段赋予