第二章程序设计概念

第二章程序设计概念解决问题的一般概念日常生活问题的解决A.明确问题B.理解问题C.寻找备选方案D.从备选方案列表中找出最好的解决方案E.列出所选择的解决方案的指令F.评价解决方案计算机中的问题计算机并不能解决人类所面临所有问题1算法问题：主要执行非常困难和耗时的数据计算，如微分问题，地球轨迹，10000名字排序2启发式问题:人工智能领域，下象棋，打牌1算法方案：可以通过一系列明确的动作来解决.2启发式方案:需具有相应的知识和经验，经过不断的尝试和失败才能达到最终目标。1计算型如数学计算过程，大多数学问题都是计算型2

逻辑型如包含关系或逻辑处理的问题3反复型反复执行一组数学型或逻辑型指令的问题，大多启发式问题都属于反复型。计算机解决问题的类型计算机解决问题的基本过程：

分析问题设计算法调试程序编写程序检测结果解决问题的难点：

人计算机编写指令算法计算机解决的任何问题都可以通过按特定顺序执行一系列操作来完成，对操作的描述就是算法（Algorithm）。算法包括了执行的操作和执行操作的顺序。李开复：算法的力量

算法是计算机科学领域最重要的基石之一，但却受到了国内一些程序员的冷落。许多学生看到一些公司在招聘时要求的编程语言五花八门就产生了一种误解，认为学计算机就是学各种编程语言，或者认为，学习最新的语言、技术、标准就是最好的铺路方法。其实大家都被这些公司误导了。编程语言虽然该学，但是学习计算机算法和理论更重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法和理论，例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等等。整天赶时髦的人最后只懂得招式，没有功力，是不可能成为高手的。用流程图表示求解下列问题的算法。

求1~100的积YN开始结束1=>i1=>productProduct*i=>producti+1=>ii<=100输出product开始结束1=>i0=>sumsum+i=>sumi+1=>ii<=100YN输出sum计算机中表示的算法：一个逐步的指令序列，用来描述怎样执行操作以产生期望的结果。算法体现了解决问题的步骤，一旦选定算法，就要用计算机语言编写程序（生成代码）。

把算法翻译成计算机认识的命令程序程序是为完成一项特定任务而用计算机语言编写的一组指令序列。编写程序就是指示计算机完成特定的任务或解决特定的问题。程序就是计算机的驾驶员操作码

操作数

数据传送指令数据处理指令程序控制指令输入输出指令

其它指令

IfGoto……＋－×÷AndOr……CPU内存I/O设备主机对计算机的硬件进行管理等指令

结构分类指令：用来规定计算机的一个基本操作的二进制代码。#include<iostream>usingnamespacestd;intmain(){inti=1,sum=0;do{sum=sum+i;i=i+1;}while(i<=100);cout<<sum<<endl;return0;}C语言编写的程序开始结束1=>i0=>sumsum+i=>sumi+1=>ii<=100YN算法的流程图#include<iostream>usingnamespacestd;intmain(){inti=1,product=1;do{product=product*i;i=i+1;}while(i<=100);cout<<product<<endl;return0;}#include<iostream>usingnamespacestd;intmain(){inti=1,sum=0;do{sum=sum+i;i=i+1;}while(i<=100);cout<<sum<<endl;return0;}求积求和不是所有的算法都能编写成计算机可执行的程序。计算机算法特征：有穷性、确定性、有零个或多个输入、有一个或多个输出、有效性。计算机不能容忍算法的多义性。程序员的难点？广大的学生上网成瘾如患绝症。编写程序的前期工作1、分析问题a.确定期望的输出b.确定输入项目c.列出相关输入和输出的公式d.执行手工计算2.选择一个全面解决问题的算法3.编写程序4.测试例如：圆的周长C可由公式C=2πr确定，其中π值3.1415，r是圆的半径。利用这个公式，计算半径是65.0m的圆的周长。a.确定期望的输出:圆的周长b.确定输入项目：半径c.列出相关输入和输出的公式：C=2πrd.执行手工计算：给一个半径，用该公式计算开始结束设置半径r值为2周长C=2πr

输出周长#include<iostream>usingnamespacestd;intmain(){floatr,C;//声明输入和输出项目r=65.0;//设置半径的值

C=2*3.1415*r;//计算周长（输出）

cout<<“圆的周长：”<<C<<endl;return0;}编写程序好的程序设计方法才能写出优秀的代码。把选择好的算法翻译成C语言的过程称为程序设计。程序设计方法

一、结构化程序设计方法二、面向对象的方法结构化程序设计方法程序的目的：用于数学计算主要工作：设计求解问题的过程缺点：对于庞大、复杂的程序难以开发和维护设计思路自顶向下、逐步求精。采用模块分解与功能抽象，自顶向下、分而治之。程序结构：按功能划分为若干个基本模块，形成一个树状结构。各模块间的关系尽可能简单，功能上相对独立；每一模块内部均是由顺序、选择和循环三种基本结构组成。其模块化实现的具体方法是使用子程序。优点：有效地将一个较复杂的程序系统设计任务分解成许多易于控制和处理的子任务，便于开发和维护。缺点：可重用性差、数据安全性差、难以开发大型软件和图形界面的应用软件把数据和处理数据的过程分离为相互独立的实体。当数据结构改变时，所有相关的处理过程都要进行相应的修改。每一种相对于老问题的新方法都要带来额外的开销。图形用户界面的应用程序，很难用过程来描述和实现，开发和维护也都很困难。面向对象的方法将数据及对数据的操作方法封装在一起，作为一个相互依存、不可分离的整体——对象。对同类型对象抽象出其共性，形成类。类通过一个简单的外部接口，与外界发生关系。对象与对象之间通过消息进行通讯。优点：程序模块间的关系更为简单，程序模块的独立性、数据的安全性就有了良好的保障。通过继承与多态性，可以大大提高程序的可重用性，使得软件的开发和维护都更为方便。根据程序设计方法选择合适的程序设计语言

计算机语言的发展第一台可编程的计算机是1822年由英国物理学家和数学家CharlesBabbage（查尔斯．巴比奇）发明的，AdaByron(艾达．拜伦）为这台机器开发过一组指令。可惜，这台机器没有完成。但可编程的机器的概念诞生了。Ada

Auausta伯爵夫人，(诗人拜伦之女)第一位计算机程序员巴贝奇，CharlesBabbage(1792～1871)

英国数学家。1792年12月26日生于英国德文郡，1871年10月18日卒于伦敦。巴贝奇于1810年入剑桥大学学习，后为该校数学教授。1816年被选为英国皇家学会会员。1812年巴贝奇开始研究差分机，1822年制成一台可以运转的小型样机。它是一台专用的加法机，在计算过程中不用人干预便可自动进行计算。巴贝奇在1832年提出了分析机的设想，把程序控制引入计算机。但是由于当时技术和经费等原因未能研制成功。

1834年，Charles

Babbage发明解析机（Analytical

Engine），首度提出近似现代电脑组织的观念。虽因机器结构太复杂，非当时技术所能制造。但解析机的设计理念和Babbage的程式构想，却开启了近代计算机的先河。

1937年，美国科学家制造了一台机器（称为ABC），但需要人配合才能执行指令。1939年，宾夕法尼亚大学的约翰．马茨里（JohnW．Mauchly)博士开始研制一种称为电子数字积分计算机ENIIAC(ElectricalNumericalIntegratorandComputer),直到1946年才完成。

第一台电子计算机

（ENIAC,ElectronicNumericalIntegratorAndCalculator）5000次加法/秒重量28吨占地170m218800只电子管1500个继电器功率150KW计算机语言的分类计算机语言机器语言低级语言高级语言汇编语言C,C++,DELPHI已知基本工资（basepay)和加班工资(overpay)，计算总工资(pays)。我们的算法：basepay+overpay=>pays机器编码：11000000000000000000010000000000101111000000000000000010000000000011汇编（不同机器类型，编码不同）:LOADbasepayADDoverpaySTOREpays高级语言编码（C语言源代码）pays=basepay+overpay;机器语言由计算机硬件系统可以识别的二进制指令组成的语言称为机器语言。汇编语言将机器指令映射为一些可以被人读懂的助记符，如ADD、SUB等。机器语言由计算机硬件系统可以识别的二进制指令组成的语言称为机器语言。汇编语言将机器指令映射为一些可以被人读懂的助记符，如ADD、SUB等。计算机发展的初期，软件工程师们只能用机器语言来编写程序。这一阶段，在人类的自然语言和计算机编程语言之间存在着巨大的鸿沟。机器语言由计算机硬件系统可以识别的二进制指令组成的语言称为机器语言。汇编语言将机器指令映射为一些可以被人读懂的助记符，如ADD、SUB等。计算机发展的初期，软件工程师们只能用机器语言来编写程序。这一阶段，在人类的自然语言和计算机编程语言之间存在着巨大的鸿沟。此时编程语言与人类自然语言间的鸿沟略有缩小，但仍与人类的思维相差甚远。因为它的抽象层次太低，程序员需要考虑大量的机器细节。高级语言屏蔽了机器的细节，提高了语言的抽象层次，程序中可以采用具有一定涵义的数据命名和容易理解的执行语句。这使得在书写程序时可以联系到程序所描述的具体事物。IBMForTranPascalAdaCC++Jave高级语言屏蔽了机器的细节，提高了语言的抽象层次，程序中可以采用具有一定涵义的数据命名和容易理解的执行语句。这使得在书写程序时可以联系到程序所描述的具体事物。C是面向过程的高级语言C++是面向对象的高级语言

计算机同人类解决问题一样，必须了解问题域，找出问题中相关的数据、未组织要素、已组织要素、信息，这些信息和数据是计算机解决问题的工具，是处理过程中用到的数据。在解决问题时，计算机首先要把问题中所需要的数据和要执行的程序存储到计算机的内存（主存储器）中。

存储器的种类存储器是计算机的记忆部件，负责存储程序和数据。存储器分两大类：主存储器(内存)和辅助存储器(外存)。主存储器采用的是半导体存储器，其特点是：存取数据速度快，可随机存取，体积小，功耗低。内存容量有限。主存储器(内存)又分为随机存储器RAM和只读存储器ROM。ROM（ReadOnlyMemory）主要用来存放固定不变的程序、数据系统软件，如BIOS程序。这种存储器中的信息只能读出而不能随意写入。断电后所存数据不会改变（具有非易失性）。RAM(RandomAccessMemory)是一种随机访问的可读写存储器。在计算机断电后RAM中的信息会丢失（具有易失性）。RAM存储器分为：静态RAM和动态RAM。程序执行时，程序和数据都存储在RAM中。CPUCPU内部结构Cache计算机的存储程序工作原理

计算机利用主存储器（主存）存放需执行的程序，中央处理器依次从主存中取出每一条指令，并经过分析后加以执行，直到全部指令执行完成。不论指令还是数据,若想存入计算机中,都必须采用二进制编码形式,在二进制系统中只有两个数0和1,即便是多媒体信息(声音、图形等)也必须转换成二进制的形式,才能存入计算机.二进制概念128瓦32瓦64瓦16瓦8瓦4瓦1瓦2瓦11111000二进制数制，由18世纪德国数理哲学大师莱布尼兹发现。二进制具有以下优势:1.易于物理实现:因为具有二种稳定状态的物理器件是很多的,如门电路的导通与截止,电压的高与低,而它们恰好对应表示1和0两个符号。假如采用十进制,要制造具有十种稳定状态的物理电路,那是非常困难的。2.二进制数运算简单：数学推导证明,对R进制的算术求和、求积规则各有R(R+1)/2种。如采用十进制,就有55种求和与求积的运算规则;而二进制仅各有三种,因而简化了运算器等物理器件的设计。3.机器可靠性高：由于电压的高低,电流的有无等都是一种质的变化,两种状态分明，所以基2码的传递抗干扰能力强,鉴别信息的可靠性高。4.通用性强：基2码不仅成功地运用于数值信息编码(二进制),而且适用于各种非数值信息的数字化编码。特别是仅有的二个符号0和1正好与逻辑命题的两个值“真”与“假”相对应,从而为计算机实现逻辑运算和逻辑判断提供了方便。十进制 R=10，数字集0,1,2,3,4,5,6,7,8,9二进制 R=2，数字集0,1八进制 R=8，数字集0,1,2,3,4,5,6,7十六进制R=16，数字集0,…,9,A,B,C,D,E,F其他进制日常生活中我们最熟悉十进制数据，但在与计算机打交道时，会接触到二进制、八进制、十六进制系统，但无论哪种数制,其共同之处都是进位记数制。

内部存储器的作用是存放执行的程序和程序中需要使用的数据，是整个数据存储和变换的枢纽。存储器由一个个大小相同的存储单元组成，每个存储单元由8位二进制位组成。为了区分和访问不同的存储单元，系统为每一个存储单元分配了惟一的编号，称为存储单元的地址。存储单元内存放的是数据。CPU对存储器可以读（取）也可以写（存）数据.……0110101010110110存放内容地址0001000200030004……FFFEFFFF存储器的逻辑结构存储器的容量

存储器的每个存储单元可以存放8位二进制，称为一个字节(Byte)，字节是访问内存的最小单位。字节是存储的基本单元，二进制位则是计算机对数据操作的最小单位。位与字节的关系？从物理上看，一个位（bit）就是一个既能开又能关的开关，开用0表示，关用1表示。单一的bit限制了其可用性，因此，所有的计算机都把bit组合起来形成一个更大的单元，即字节（Byte）。存储单位位（Bit）：度量数据的最小单位字节（Byte）：最常用的基本单位K字节 1K=1024byteM（兆）字节 1M=1024KG（吉）字节 1G=1024MT（太）字节 1T=1024Gb7b6b5b4b3b2b1b0计算机如何存储数据计算机将数据存储在内存的存储单元（字节）中。不同类型的数据占用的存储单元数不同。

一个位能表现什么值？一个字节能够表示多少个不同的位模式？字长：字长是指计算机能直接处理的二进制信息的位数。字长是由CPU内部的寄存器、加法器和数据总线的位数决定的。字长越长，精度越高，速度越快，但价格也越高。当前微机字长有16位，32位，高档微机的字长是64位。主频：指时钟脉冲发生器在单位时间(s)内发出的脉冲数。频率越高，计算机的处理信息的速度也越快。主频的单位是兆赫兹(MHz，GHz)。存储容量:(1)内存容量。指内存储器能够存储信息的总字节数。容量越大，运行速度越快。内存储器容量大小，受限于CPU的地址总线。(2)外存容量。指外存储器所能容纳的总字节数。数据以二进制形式存储

汉字编码GB国标码：中文内码之一，代表中文简化字，在中国大陆广泛使用，影响所及，使用量渐见普及。国标码是指国家标准信息交换用汉字编码（GB2312-80标准）。国标码是指1980年中国制定的用于不同的具有汉字处理功能的计算机系统间交换汉字信息时使用的编码。国际码是二字节码,用两个七位二进制数编码表示一个汉字。目前国标码收入6763个汉字,其中一级汉字（最常用）3755个,二级汉字3008个,另外还包括682个西文字符、图符。音频、视频、图形、图像数值数据整型数据：二进制编码原码：商除2取余，逆序排列，最高位是符号位，整数是0，负数是1.反码：原码的各个位取反，符号位除外补码：反码最末位加11+1=01+0=10+1=10+0=0整数以补码形式存储。正整数：原码，反码，补码一样.例如：+15（用一个字节表示）原码：00001111符号位数值位+15（用一个字节表示）原码：00001111反码：00001111补码：00001111正整数的原码、反码、补码一样负整数：例如-15（一个字节表示）原码：10001111反码：11110000补码：11110001以补码形式存储二进制转换为十进制00010101=24+22+20=+21必须是原码才能转为真值.1110000=2-1+2-2+2-3=0.87511001100，计算出对应的十进制数求出原码：对补码除符号位外各个位求反，最末位加111001100对应的原码是：10110100真值：-52浮点数的存储浮点数转换为二进制一、整数部分：商除2取余，商为0结束，余数逆序排列；二、小数部分：乘2取整，积为0结束，整数部分顺序排列。例如：单精度浮点数120.5的二进制原码表示：

1111000.1浮点数120.5用二进制表示为：1111000.1用二进制的科学计数法表示为1.1110001*26任何一个数的科学计数法表示都为1.xxx*2n

尾数部分就可以表示为xxxx,不保存小数点前面的1，所以23位的尾数部分，可以表示的精度却变成了24位。

对于指数部分，因为指数可正可负，8位的指数位能表示的指数范围就应该为:-127～128，指数部分的存储采用移位存储，即存储的数据为元数据加上127，8位指数位全是数值位，数值范围：0～255如指数是6，实际存储的是133的二进制.

单精度浮点数120.5的存储方式如下所示:01000010111100001000000000000符号位指数位尾数位12.651.原码：1100.101001100110011001102.科学计数：1.10010100110011001100110*233.尾数用补码表示：100101001100110011001104.指数：3+127=130,130的原码：100000101内存中：010000010110010100110011001100110符号位指数位：指数没有符号位尾数位-0.0121.原码：0.000000110001002.科学计数：1.1000100*2-73.尾数:10001004.指数：-7+127=120,120的原码:01111000内存中：1011110001000100符号位指数位：指数没有符号位尾数位如果给出内存中一段单精度存储的数据，如何知道该数据的十进制数值呢？如给出如下内存数据：0100001011101101000000000000首先分段：01000010111011010000000000000000根据我们的计算方式，可以计算出，这样一组数据表示为:1.1101101*26=1110110.1=120.5符号位指数位尾数位给出以下数的二进制存储形式：25-3018.7-18.7给出以下整数的十进制存储形式：00111110001110101011111000111010给出以下浮点数的十进制存储形式：0111001000001110001110001100110011110010000011100011100011001100在程序中如何表示数据呢？#include<iostream>usingnamespacestd;intmain(){floatr,C;//声明输入和输出项目r=65.0;//设置半径的值

C=2*3.1415*r;//计算周长（输出）

cout<<“圆的周长：”<<C<<endl;return0;}floatr,C;//r,C就表示数据r,C在程序中称为变量。程序中用变量和常量来表示数据。程序员必须给使用的每个变量命名。变量变量名、变量值、变量标识的内存单元：

sudent_score

注：一些在问题中值经常变动的数据可以定义成变量,如商品的价格,账户上的余额.89内存单元变量名(不能变）变量值(可变，在程序运行时）变量名和变量值的区别：变量名是一个标签，计算机根据变量名找到相应的内存地址，然后把这个地址中存放的内容---变量值取出来进行处理.因计算机只用名访址，所以必须保证变量名的一致性。在程序中，通过变量名来访问数据，每个变量名都与一个特定的内存单元联系起来，每个内存单元一次只能存放一个数值。

对于程序员来说，变量最关键的作用是什么？存储单元和内存单元的区别？变量所标识的内存单元可以被刷新。刷新的含义是什么？常量常量：常量是一种固定的字符或数值，在整个指令运行过程中都不能改变，在编程语言中，可以给常量命名，这时，常量就有了内存地址和名字,在程序执行过程中，常量会被赋值，且该值不能再改变，可通过名字访问它.常数是常量的一种表示，直接使用，如89,8.7

3.1415926

PI

常量名(不能变）常量值(不能变）内存单元注：一些在问题中值不变的数据可以定义成常量,如，圆周率的值，一个公司薪水系统中公司的名字.计算机中的常量和变量常量变量规则：不能改变例子：值值常量命名