算法与程序设计计算机是如何解决问题的(V3.0).ppt

算法与程序设计,北大附中 李冬梅,算法与程序设计研究什么,算法与程序设计是研究如何用计算机来解决实际问题。即计算机进行问题求解。,例如,（1）出一个100万以内的一个正整数让计算机猜，计算机只能提出不超20个问题，针对每个问题的回答只有“是”或“否”， 计算机能在20次内猜中吗？若能猜中，用什么方法？,例如,（2）有一大堆CD杂乱无章地摆放在CD架上，请计算机按字母顺序将CD排列在CD架上。,例如,（3）请计算机查找到本.拉登的下落。,例如,（4）请计算机编游戏。,例如,（5）请计算机为汽车检查故障。,例如,（6）一个推销员要走访他的销售区中的每个城市，为了提高效率，他想找到一条路线，在返回起点前，每个城市去一次且只去一次，这样的线路有吗？如果有，计算机可以帮助找出来吗？,计算机是如何解决问题的,首先搞清楚计算机能干什么,要知道计算机能干什么？先要知道计算机是什么？,计算机包括什么,软件？ 硬件？ 计算机软件是干什么的？ 计算机硬件又能干什么的？ 最终是哪件在干活？,主板,主板,CPU,内存,集成电路（芯片）,集成电路,集成电路是嵌入了多个门的硅片。 这些硅片被封装在塑料或陶瓷里，边缘有引脚可以焊接在电路板上或插入适合的插槽里。 每个引脚连接着一个门的输入或输出，也可能是电源或地线。 集成电路是根据它们所包含的门数分类的，这些分类也反映了电子技术的发展历史。,集成电路,计算机硬件能干什么,计算机硬件可以显示数字0，1,晶体管电路,晶体管电路,晶体管电路,非门,电路图,表示符号,真值表,与门,电路图,表示符号,真值表,或门,真值表,表示符号,电路图,异或门,真值表,表示符号,电路图,非门,与门,或门,异或门,半加器,组合电路,测试位相等的组合电路,a,b,OUT,多路复合器,b,a,s,out,单个位的多路复合器,RAM（内存）,计算机硬件能干什么,计算机可以保存数字,二进制 0 1 10 11 100 101 11111111,十进制 0 1 2 3 4 5 255,计算机能干什么,计算机可以保存符号,控制器,算术逻辑部件,内存储器,输入 设备,输入 设备,辅助存 储设备,计算机体系结构（冯.诺伊曼体系结构）,让计算机在屏幕上写一个“Hello”,指令： 写“Hello” 计算机硬件不懂，但中国人能懂,指令： write “Hello“ 计算机硬件不懂，但某一种计算机高级程序设计语言能懂,指令： write “H“ write “e“ write “l“ write “l“ write “o“ 计算机硬件不懂，但某一种计算机高级程序设计语言能懂,指令：CHARO C#/H/,i CHARO C#/e/,i CHARO C#/l/,i CHARO C#/l/,i CHARO C#/o/,i STOP 计算机硬件不懂，某一种汇编语言能懂，大多数人看不懂,指令 11100000 0000000001001000 11100000 0000000001100101 11100000 0000000001101100 11100000 0000000001101100 11100000 0000000001101111 00000000 计算机硬件懂了，某一种机器语言能懂，但一般人看不懂了,计算机的硬件指令,其实，计算机可以执行的指令非常有限，控制器可以识别、ALU(算术/逻辑运算单元)可以执行的指令也就100多条，其中还有很多是重复指令，比如，不同类型的数据通常有不同的ADD指令。 我们让计算机做的每一件事都必须简化为这些最简单的、硬件级的指令。,计算机总是以非常快的速度孜孜不倦地执行着它们的简单任务。 如果我们知道如何把一个复杂的操作解释为一序列原始的硬件级指令，那么，每次想完成复杂的任务时，只要指导计算机执行这个序列即可。 一旦指导计算机执行复杂的操作后，就可以用它们来描述更复杂的操作和任务，这就是算法与程序设计的任务。,就是要把需要计算机处理 的复杂任务转换为简单的指令,算法与程序设计,当我们用WORD写一篇论文时，计算机能为你执行数千个操作，从识别敲入的字母到拼写检查，为了让计算机处理所有这些事情，每个操作都必须转换成一序列原始的硬件级指令。 但这些工作不可能每次都让程序员去做，只要第一次告诉计算机如何做，以后计算机就可以自己翻译了。,汇编指令举例,汇编语言与汇编器,汇编语言 指令序列,机器语言 指令序列,汇编器,高级语言与编译器,高级语言 指令序列,机器语言 指令序列,编译器,计算机如何解决问题,（1）分析问题 （2）找到解决问题的方法 （3）把方法用有限的步骤描述出来，且每一步骤都可以通过某种计算机语言实现。 （4）用某种计算机程序设计语言描