计算机问题求解word版本.pptVIP

2018年09月18日 计算机问题求解 计算机 问题求解 问题1a: 计算机究竟能干什么？ 问题1b: 人究竟是如何解题的？ 问题1：为什么计算机能帮我们解题？ Part I 了解计算机 Beyond formal education, normal maturation or aging itself is sadly accompanied by the monotonic dimming of ones curiosity. - Bulent Atalay Amazing Machine 问题2： 你理解“抽象”的含义吗？如果从解题的角度让你“极度抽象”，你会如何想象计算机这个“黑匣子”的内部结构呢？ Even More Amazing 注意：每个operation有相应的operand（1个或多个） 问题3：我们可以让计算机“间接地”执行什么操作？ 你试试让计算机比较两个1-bit二进制数是否相等，只用前面提到的运算，如果需要，你可以使用辅助的bits, 注意：这里testing操作有两个不同的operands. x y eq Equality test (x,y) zero eq; flip eq;/* equality on test x flip eq; test y flip eq; If x=y eq=1 Otherwise eq=0 你能将这个操作扩展到, 比如, 32位内的整数吗? 问题4： Eq最终的值取决于什么？ 增加两个操作，可间接地利用判断相等的操作 实现加法 计算两个1-bit二进制数的和 x y z1 z0 x+y add (x,y) 1. zero z0; 2. zero z1; 3. equality test(x,y); 4. test eq goto 7 5. flip z0; /*x,y不同，和为1(01) 6. exit; 7. test x flip z1; /*x,y是1，则结果是2(10) 问题5： 你能说出这新增操作的关键价值吗？ goto, exit 问题6： 那么如果只允许使用原来的三个操作，你还能完成这个任务吗？ 没法分支，没法分情况处理。 add (x,y) 1. zero z0; 2. flip z0; 3. zero z1; 4. equality test(x,y); 5. zero t 6. test eq flip t; 7. test t flip z0; 8. test t flip z1; …… (是否有可能让x=y=0时z1变为0） x y z1 z0 t x+y 输出置为01 (t=0), 假如x,y不等，结果正确。 若x=y, 输出置为10 (t=1)，可能错 我们很容易区分两加数是否相等，但确难以判断在相等的前提下是0还是1，这体现了“语言表达能力”的差别。 多层次抽象 用一位的加法“间接操作”可以实现普通加法操作； 加法操作又可以作为一步操作用在更复杂的“间接操作”中。 实际上现在计算机内部电路能提供的操作远不只是那几个最简单的“直接”操作。 内部与外部 问题7: 区分“内部与外部”对于让计算机“什么都能干有什么意义? 问题8： 现在你能回答“计算机究竟能做什么”了吗？ 也许可以这样回答： 计算机本身做不了什么，但在人的“指挥”下，计算机似乎什么都能做，因为“间接”有无限的“想象空间”。 问题9： 我们如何“指挥”？ 写程序？ 学会了“语言”就会写程序吗？ Part II Problem-Solving in general 我们如何解题? George Polya: “How to Solve It?” Understanding the problem: “What you are given and what you are supposed to figure out” Devising a plan: “How will you attack the problem?” Carrying out the plan: Solve the problem. Looking back: check the result, and… 问题10: 计算机能帮我们做什么? 我们如何解题, 用计算机? 计算机如何理解问题? 输入是什么? 输出是什么? 如何针对计算机制定计划? 什么样的”计划”可能在计算机上实现? 什么样的形式才能让计算机知道该怎么做? 执行计划 – “计算机解题” 只有这个才真正是计算机做的! 回头看 为什么结果是正确的? 效率能提高吗? 问题11: 怎样才能让计算机帮到我们? 一个例子 – “渡河问题” 问题：人、狼、羊、菜用一条只能同时载两位的小船渡河，“狼