《算法与程序设计计算机是如何解决问题的(V3.0).ppt》由会员分享，可在线阅读，更多相关《算法与程序设计计算机是如何解决问题的(V3.0).ppt（51页珍藏版）》请在金锄头文库上搜索。
1、算法与程序设计算法与程序设计北大附中北大附中李冬梅李冬梅算法与程序设计算法与程序设计研究什么研究什么 算法与程序设计算法与程序设计是研究如何用计算是研究如何用计算机来解决实际问题。即计算机进行问机来解决实际问题。即计算机进行问题求解。题求解。例如例如 （1）出一个）出一个100万以内的一个正整数让万以内的一个正整数让计算机猜，计算机只能提出不超计算机猜，计算机只能提出不超20个问个问题，针对每个问题的回答只有题，针对每个问题的回答只有“是是”或或“否否”，计算机能在计算机能在20次内猜中吗？次内猜中吗？若能猜中，用什么方法？若能猜中，用什么方法？例如例如 （2）有一大堆）有一大堆CD杂乱无章地
2、摆放在杂乱无章地摆放在CD架上，请计算机按字母顺序将架上，请计算机按字母顺序将CD排列排列在在CD架上。架上。例如例如 （3）请计算机查找到本）请计算机查找到本.拉登的下落。拉登的下落。例如例如 （4）请计算机编游戏。）请计算机编游戏。例如例如 （5）请计算机为汽车检查故障）请计算机为汽车检查故障。 例如例如 （6）一个推销员要走访他的销售区中的）一个推销员要走访他的销售区中的每个城市，为了提高效率，他想找到一每个城市，为了提高效率，他想找到一条路线，在返回起点前，每个城市去一条路线，在返回起点前，每个城市去一次且只去一次，这样的线路有吗？如果次且只去一次，这样的线路有吗？如果有，计算机可以帮
3、助找出来吗？有，计算机可以帮助找出来吗？计算机是如何解决问题的计算机是如何解决问题的首先搞清楚计算机能干什么首先搞清楚计算机能干什么要知道计算机能干什么？要知道计算机能干什么？先要知道计算机是什么？先要知道计算机是什么？计算机包括什么计算机包括什么 软件？软件？硬件？硬件？计算机软件是干什么的？计算机软件是干什么的？计算机硬件又能干什么的？计算机硬件又能干什么的？最终是哪件在干活？最终是哪件在干活？主板主板主板主板CPU内存内存集成电路（芯片）集成电路（芯片）集成电路集成电路集成电路是嵌入了多个门的硅片。集成电路是嵌入了多个门的硅片。这些硅片被封装在塑料或陶瓷里，边缘有引这些硅片被封装在塑料或
4、陶瓷里，边缘有引脚可以焊接在电路板上或插入适合的插槽里。脚可以焊接在电路板上或插入适合的插槽里。每个引脚连接着一个门的输入或输出，每个引脚连接着一个门的输入或输出，也可能是电源或地线。也可能是电源或地线。集成电路是根据它们所包含的门数分类的，集成电路是根据它们所包含的门数分类的，这些分类也反映了电子技术的发展历史。这些分类也反映了电子技术的发展历史。集成电路集成电路缩写缩写名称名称门数量门数量SSI小规模集成电路110MSI中规模集成电路10100LSI大规模集成电路100100000VLSI超大规模集成电路100000计算机硬件能干什么计算机硬件能干什么 计算机硬件可以显示数字计算机硬件可以
5、显示数字0，1晶体管电路晶体管电路晶体管电路晶体管电路晶体管电路晶体管电路非门非门电路图表示符号真值表与门与门电路图表示符号真值表或门或门真值表表示符号电路图异或门异或门真值表表示符号电路图非门与门或门异或门半加器半加器组合电路组合电路测试位相等的组合电路测试位相等的组合电路abOUT多路复合器多路复合器basout单个位的多路复合器单个位的多路复合器单个位的多路复合器单个位的多路复合器000010001110000100110000100000100111100000000000000000000000001100001100001001110000111000000100000000000
6、0011111000011000001100000001100000010010000111000001000000110000000000001100100000001101111111100000000000110000000000000000000111111110001100011000000RAM（内存）计算机硬件能干什么计算机硬件能干什么 计算机可以保存数字计算机可以保存数字二进制二进制二进制二进制0 01 1101011111001001011011111111111111111十进制十进制十进制十进制0 01 1223 34 455255255计算机能干什么计算机能干什么 计算
7、机可以保存符号计算机可以保存符号计算机可以保存符号计算机可以保存符号字符 ASCII码 字符 ASCII码 字符 空格 ！ # $ % & ( ) * + , - . / 0 1 2 3 4 5 6 7 8 9 : ; ? 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089 090 091 092 093 094 095 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z _ 096 09
8、7 098 099 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 、 a b c d e f g h i j k l m n o p q r s t u v w x y z | 主机主机主机主机中央处理器中央处理器中央处理器中央处理器（CPUCPU）控制器控制器控制器控制器算术逻辑部件算术逻辑部件算术逻辑部件算术逻辑部件内存储器内存储器内存储器内存储器输入输入输入输入设备设备设备设备输入输入输入输入设备设备设备设备辅助
9、存辅助存辅助存辅助存储设备储设备储设备储设备011011000011011000011011000011011000计算机体系结构（冯计算机体系结构（冯计算机体系结构（冯计算机体系结构（冯. .诺伊曼体系结构）诺伊曼体系结构）诺伊曼体系结构）诺伊曼体系结构） 让计算机在屏幕上写一个让计算机在屏幕上写一个“Hello”指令：指令：写写“Hello”计算机硬件不懂，但中国人能懂计算机硬件不懂，但中国人能懂指令：指令：writeHello计算机硬件不懂，但某一种计算机计算机硬件不懂，但某一种计算机高级程序设计语言能懂高级程序设计语言能懂指令：指令：writeHwriteewritelwritelwr
10、iteo计算机硬件不懂，但某一种计算机计算机硬件不懂，但某一种计算机高级程序设计语言能懂高级程序设计语言能懂指令：指令：CHAROC#/H/,iCHAROC#/e/,iCHAROC#/l/,iCHAROC#/l/,iCHAROC#/o/,iSTOP计算机硬件不懂，某一种汇编语计算机硬件不懂，某一种汇编语言能懂，大多数人看不懂言能懂，大多数人看不懂指令指令11100000000000000100100011100000000000000110010111100000000000000110110011100000000000000110110011100000000000000110111100
11、000000计算机硬件懂了，某一种机器语言能计算机硬件懂了，某一种机器语言能懂，但一般人看不懂了懂，但一般人看不懂了计算机的硬件指令计算机的硬件指令其实，计算机可以执行的指令非常有其实，计算机可以执行的指令非常有限，控制器可以识别、限，控制器可以识别、ALU(算术算术/逻逻辑运算单元辑运算单元)可以执行的指令也就可以执行的指令也就100多条，其中还有很多是重复指令，比多条，其中还有很多是重复指令，比如，不同类型的数据通常有不同的如，不同类型的数据通常有不同的ADD指令。指令。我们让计算机做的每一件事都必须简我们让计算机做的每一件事都必须简化为这些最简单的、硬件级的指令。化为这些最简单的、硬件级
12、的指令。计算机总是以非常快的速度孜孜不倦计算机总是以非常快的速度孜孜不倦地执行着它们的简单任务。地执行着它们的简单任务。如果我们知道如何把一个复杂的操作如果我们知道如何把一个复杂的操作解释为一序列原始的硬件级指令，那解释为一序列原始的硬件级指令，那么，每次想完成复杂的任务时，只要么，每次想完成复杂的任务时，只要指导计算机执行这个序列即可。指导计算机执行这个序列即可。一旦指导计算机执行复杂的操作后，一旦指导计算机执行复杂的操作后，就可以用它们来描述更复杂的操作和就可以用它们来描述更复杂的操作和任务，这就是算法与程序设计的任务。任务，这就是算法与程序设计的任务。就是要把需要计算机处理就是要把需要计
13、算机处理的复杂任的复杂任务转换为简单的指令务转换为简单的指令算法与程序设计算法与程序设计当我们用当我们用WORD写一篇论文时，计写一篇论文时，计算机能为你执行数千个操作，从识别算机能为你执行数千个操作，从识别敲入的字母到拼写检查，为了让计算敲入的字母到拼写检查，为了让计算机处理所有这些事情，每个操作都必机处理所有这些事情，每个操作都必须转换成一序列原始的硬件级指令。须转换成一序列原始的硬件级指令。但这些工作不可能每次都让程序员但这些工作不可能每次都让程序员去做，只要第一次告诉计算机如何做，去做，只要第一次告诉计算机如何做，以后计算机就可以自己翻译了。以后计算机就可以自己翻译了。汇编指令举例汇编
14、指令举例助记符对应的机器指令的操作码含义STOP00000000 停止执行 LOADA00000001 把操作数载入寄存器A ADDA00000011 把操作数加到寄存器A 汇编语言与汇编器汇编语言与汇编器汇编语言汇编语言汇编语言汇编语言指令序列指令序列指令序列指令序列机器语言机器语言机器语言机器语言指令序列指令序列指令序列指令序列汇编器汇编器汇编器汇编器输入输入输入输入输出输出输出输出高级语言与编译器高级语言与编译器高级语言高级语言高级语言高级语言指令序列指令序列指令序列指令序列机器语言机器语言机器语言机器语言指令序列指令序列指令序列指令序列编译器编译器编译器编译器输入输入输入输入输出输出输
15、出输出计算机如何解决问题计算机如何解决问题 （1）分析问题）分析问题（2）找到解决问题的方法）找到解决问题的方法（3）把方法用有限的步骤描述出来，且每一）把方法用有限的步骤描述出来，且每一步骤都可以通过某种计算机语言实现。步骤都可以通过某种计算机语言实现。（4）用某种计算机程序设计语言描述解决问）用某种计算机程序设计语言描述解决问题的方案。题的方案。（5）上机调试）上机调试算法什么是算法呢？什么是算法呢？就是解决问题的一种精确、系统的方法。就是解决问题的一种精确、系统的方法。算法为了写出具体的、计算机可以执行的为了写出具体的、计算机可以执行的算法，算法要满足算法，算法要满足5条：条：一定的输入一定的输入一定的输出一定的输出确定性确定性有效性有效性有限性有限性
