我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:藏宝阁 > 第一代语言 >

第一章 程序设计基础知识

归档日期:07-30       文本归类:第一代语言      文章编辑:爱尚语录

  第一章 程序设计基础知识_管理学_高等教育_教育专区。c语言谭浩强教材课件

  第一章 程序设计基础知识 1.1 程序与程序语言 . 1.1.1 语言 . . 1、计算机语言 是人与计算机进行交流的方式,有其符合数学规范的 单词、句子和含义的定义。 2、 语言的发展 第一代:机器语言 ——二进制代码,计算机母语 第二代:汇编语言——用符号表示的计算机指令 ——面向计算机的语言 面向计算机的语言 第三代: 高级语言——采用完全符号化的描述,用类 似自然语言的形式来描述对问题的处理过程,用数学 表达式的形式来描述对数据的处理过程,Pascal, C等, 要求人告诉计算机怎样做, ——面向过程的语言 面向过程的语言 第四代: 非结构化语言——Visual C++,Delphi,VB, C++ Build, C#, JAVA等。 要求人告诉计算机 做什么, ——面向对象的语言 面向对象的语言 第五代: 智能化语言——PROLOG 面向过程的语言是程序设计的基础 1.1.2 程序设计 . . 1 程序 计算机是一种具有内部存储能力的自动、高效的电子 设备,其本质的使命就是执行指令所规定的操作。 程序= 程序={ 指令 },是用计算机语言对来所要解决问题 中数据以及处理问题的方法和步骤所做的完整而准确的 描述。 ——这个描述过程称为程序设计 这个描述过程称为程序设计 程序 = 算法 + 语言 + 数据结构 语言工具和环境 1/4时间 具体步骤、设计方法 3/4时间 *程序设计如同建房子= 设计图纸 + 具体施工 + 材料 2 程序设计步骤 ⑴ 分析问题,建立数学模型 将解题过程归纳为一系列的数学表达式 ⑵ 确定数据结构和算法 确定存放数据的内部结构,解决问题的方法和步骤 ⑶ 编制程序 用某种计算机语言把问题的解决方案严格的书写出来。 ⑷ 调试程序 在计算机上用实际的输入数据对编好的程序进行测试。 3 程序涉及方面 数据结构、算法、编程语言和程序设计方法 1.2 算法和算法的表示 1.2.1 算法的概念 1 算法 是为解决一个特定的问题所采取的确定的有限的步骤。 例1:解数学题——解题的计算步骤和过程。 例2:演唱歌曲——歌谱,它规定了歌唱家如何唱歌,先 唱什么,后唱什么,唱什么音阶,什么音符……。 例3:制作写字台——加工顺序:从桌腿→桌面→抽屉→ 组装的过程。 2 计算机算法 告诉计算机如何一步步进行操作,直至解决问题的具 体步骤。包含:数值计算和非数值计算 包含: 包含 3 设计算法的思维方法 例1—1 有黑和蓝两个墨水瓶,但却错把黑墨水装在了蓝墨水瓶子 1 里,而蓝墨水错装在了黑墨水瓶子里,要求将其互换。 算法分析:这是一个非数值运算问题。因为两个瓶子的墨水不 能直接交换,所以一问题的关键是需要引入第三个墨水瓶。设 第三个墨水瓶为白色,其交换步骤如下: ①将黑瓶中的蓝墨水装人白瓶中; ②将蓝版中的黑墨水装入黑瓶中; ③将白瓶中的蓝墨水装入蓝瓶中; ④交换结束。 [例] 猴子吃桃问题:有一堆桃子不知数目,猴子第一天吃掉一半, 觉得不过瘾,又多吃了一只,第二天照此办理,吃掉剩下桃子的 一半另加一个,天天如此,到第十天早上,猴子发现只剩一只桃 子了,问这堆桃子原来有多少个? 假设每天有an(n=1…10)只桃子,而我们可以看出,a1, a2, . .,a10 之间存在一个简单的关系: a9= 2 * ( a10+ 1 ) a8= 2 * ( a9+ 1 ) ┇ a1= 2 * ( a2+ 1 ) 也就是:ai= 2 * ( ai + 1+1) (i=9,8,7,6,...,1) 这就是此题的数学模型。 再考察上面从a9,a8直至a1的计算过程,这其实是一个递推过程 ,这种递推的方法在计算机解题中经常用到。另一方面,这九步 运算从形式上完全一样,不同的只是ai的下标而已。 由此,我们引入循环的处理方法,并统一用a0表示前一天的 桃子数,a1表示后一天的桃子数,将算法改写如下: 1) a 1=1; {第1 0天的桃子数,a1的初值} i = 9。{计数器初值为9} 2) a 0= 2 * ( a1+ 1 )。{计算当天的桃子数} 3) a 1= a0。{将当天的桃子数作为下一次计算的初值} 4) i=i-1。 5) 若i = 1,转2 )。 6) 输出a0的值。 其中2 )~5 )步循环执行9次。 这就是一个从具体到抽象的过程,具体方法是: 1) 弄清如果由人来做,应该采取哪些步骤。 2) 对这些步骤进行归纳整理,抽象出数学模型。 3) 对其中的重复步骤,通过使用相同变量等方式求得形式的统一 ,然后简练地用循环解决。 例1—3 给定两个正整数m和n (m≧n),求它们的最大公约数。 算法分析:用辗转相除法(也称欧几里德算法)求解。 被除数 除数→ n 例:设m=35,n=15 商 m … 余数→ r 若r=0,前个非0的r即是 若r不为0 2 3 15 35 5 15 30 15 5 0 ① ② 则:最大公约数为5 算法可以描述如下: ①将两个正整数存放到变量m和n中,保证m不小于n; ②求余数:计算m除以n,将所得余数存放到变量r中; ③判断余数是否为0:若余数为0则执行第⑤步,否则执行第④步: ④更新被除数和余数:将n的储存放到m中,将r的值存放到n中, 并转向第②步继续循环执行; ⑤输出n的当前值,算法结束。 4.算法的两要素 . 4.1 两要素:基本功能操作 + 控制结构 两要素: 4.2 计算机的基本功能操作包括以下四个方面: (1)逻辑运算:与、或、非; (2)算术运算:加、减、乘、除; (3)数据比较:大于、小于、等于、不等于、大于等于 (4)数据传送:输入、输出、赋值。 4.3 算法的控制结构决定了算法的执行顺序,包括: 顺序结构、分支结构、循环结构。 1.2.2 算法的基本特征 (1)有穷性:一个算法必须在执行有限个操作步骤后终止; (2)确定性:算法中每一步的含义必须是确切的,不可出现任何二 义性; (3)有效性:算法中的每一步操作都应该能有效执行,一个不可执 行的操作是无效的,如一个数被0除的操作就是无效的,应避免。 (4)有零个或多个输入:这里的输入是指在算法开始之前所需要的 初始数据。例如,例l—1的算法中有2个输入,即需要输人a和b两个 初始数据,而例1—2的算法中则需要输入四个初始数据。有些特殊 算法也可以没有输入。 (5)有一个或多个输出:所谓输出是指与输入有某种特定关系的量, 在一个完整的算法中至少会有一个输出。如上述三个例子中都有输 出。试想若例1—3中没有“输出n的当前值”这一步,则该算法将 毫无意义。 1.2.3 算法的表示 原则上说,算法可以用任何形式的语言和符号来描述.通常有 自然语言、程序语百、流程图、NS图、PAD团、伪代码等。第一节 中的三个例子就是用自然语言来表示算法, 流程图是最早提出的用图形表示算法的工具,具有直观性强、 便于阅读等特点;NS图和PAD图符合结构化程序设计要求,是软件 工程中强调使用的图形工具。 1.流程图符号 由美国国家标准化协会ANSI规定了一些常用的符号. 或 (a) 流程线:表示算法的执行方向 (b) 注释框:表示对算法中的某操作或某部分操 作所作的必要的备注说明。 或 (c) 连接点:表示不同地方的流程图的连接。 (d) 起止框:用以表示算法的开始 或结束。 (e) 输入/输出框:表示算法的输 入和输出操作。 (f) 处理框:算法中各种计算和赋 值的操作均以处理框加以表示。 (g) 判断框:表示算法中的条件判 断操作。 2.用流程图表示算法 例1-1 例1-2 例1-3 1.2.4 几种常用算法介绍 1.枚举法(穷举法) 首先根据问题的部分条件预估答案的范围,然后在此范围内对所 有可能的情况进行逐一验证,直到全部情况均通过了验证为比。若 某个情况使验证符合题目的全部条件,则该情况为本题的一个答案; 若全部情况验证结果均不符合题目的全部条件,则说明该题无答案。 例题1.鸡翁—,值钱五;母鸡一,值钱三;雏鸡三,值钱一;百 钱买百鸡,翁、母、雏各几何? 这就是列方程:x十Y十z=100 5x十3Y十z=100 据题意可知,x , y , z的范围一定是0到100的正整数,则最简单 的解题方法是假设一组 x , y , z 值,直接带入方程组求解,即在各 个变量的取值范围内不断变化 x , y , z 全部可能的组合,若满足方 程组则是一组解。 利用枚举法解题需要以下步骤: (1) 分析题目,确定答案的大致范围。 (2) 确定列举方法。常用的列举方法有:顺序列举,排列列举和 组合列举。 (3) 作试验,直到遍历所有情况。 (4) 试验完后可能找到与题目要求完全一致的一组或多组答案, 也可能没找到答案,即证明题目无答案。 枚举法的特点是算法简单,容易理解,但运算量较大。对于可确 定取值范围但又找不到其它更好的算法时,就可以用枚举法。通常 枚举法用来解决“有几种组合”、“是否存在”、求解不定方程等 类型的问题。 利用枚举法没计算法大多以循环控制结构实现 利用枚举法没计算法大多以循环控制结构实现。 循环控制结构 2.迭代法 是一种数值近似求解的方法,特点是:把一个复杂问题的求解过 程转化为相对简单的迭代算式,然后重复执行这个简单的算式,直 到得到最终解。 迭代法有精确迭代法和近似迭代法。所谓精确选代是指算法本身 提供了问题的精确解;如对N个数求和、求均值、求方差等,这些 问题都适合使用精确迭代法解决。 例l—5 计算 s=1十2+3+4十……+100 其迭代方法如下: 首先确定迭代变量 s 的初始值为0; 其次确定迭代公式 s+i→s; 当i分别取值1,2,3,4,…,100时,重复计算迭代公式 s+i→s,迭代 100次后,即可求出 s 的精确值。 流程图表示见书 P11 页 迭代法通常用于数值运算的求解问题 3.递推和递归法 这是程序设计中常用的两种算法,都是利用某些公式的递推性。 最常见的例子是计算级数,—般给出数列后项与前项的递推公式, 要求计算数列通项。 例如: (1) f1(n)=2+fl(n—1),f1(1)=1 f1(n)={1.3,5,7,…} ——这是首项为l公差为2的等差数列(等差级数)。 (2) f2(n)=2 × f2(n一1),f2(1)=1 ——这是首项为1公比为2的等比数列。 (3) f3(n)=n×f3(n一1),f3(1)=1 ——这个数列的通项f3(n)=n!。 (4) f4(n)=f4(n—1)+f4(n一2),f4(1)=1,f4(2)=1; ——这就是有名的斐波那契数列。 特点:在数列的未知项与已知项之间存在着一定关系,借助于已 知项和这一关系,就可逐项求出未知项。 计算数列通常用递推和递归两种算法。 ①递推法:是指利用递推公式,由简到繁逐次迭代求解。 例1—7 求n! 设n=15。 ∵ n! =1 ×2 × …… × n,其算法存在如下递推过程: f(0)=0!=l f(1)=1!=1×0!=1 f(2)=2!=2×1! =2 f(3)=3!=3×2!=6 …… f(n)=n!=n×(n-1)!=n × f(n-1) 结论:递推法的关键是找到进行递推的通项公式 ② 递归法:利用递推公式,由繁化简,用简单的问题和已知的 操作运算来解决复杂的问题。 f(1)=l f(n)=f(n一1) × n 将所一个式子从n到n—1、再到n—2逐步递推化简得到: f(n)=f(n—1) × n=f(n—2) ×(n—1) × n =…=f(1)×2×3×…×n (n>1) 每次化简,自变量减1,但要多乘一个因子,在化简的每一步, f(n-1),f(n-2),…等仍为未知量,直到化简为f(1),因f(1)已知,f(n)便 可由一个式子求乘法得到,这个计算算过程不是直接的,它包含两 个过程: ⑴ 由繁到简的递推化简; ⑵ 由已知值f(1)经乘法运算回归到所求值。 递归特征: 递归特征:如果一个过程直接或间接地有限次数地调用了它自身, 则称这个该过程是递归的。其关键 关键是必须有一个递归终止条件,即 关键 要有递归出口。 例求n! ③ 递归与递推的对比 ⑴ 递推是从已知的初始条件出发,逐次递推出最后所求的值,一 般可利用循环结构实现,比较简单。 ⑵ 递归是从需要求解的函数本身出发,逐次上溯调用其本身的求 解过程,直到递归的出口,然后再从里向外倒推回来,得到最终的 值。它要求语言具有反复自我调用于程序的能力(用递归子程序实 现)。 ⑶ 一般说来,一个递推算法总可以转换为—个递归算法。 4.分治法 在求解一个复杂问题时,应尽可能地把这个问题分解为较小部分, 找出各部分的解,然后再把各部分的解组合成整个问题的解,这就 是所谓的分治法。(子程序的设计理念) 常用于解决非数值运算问题,如数据检索、快速分类选择等问题 的算法中被广泛应用。 1.3 结构化程序设计方法 具有良好的可读性、可靠性、可维护性和良好的结构的高质量 程序,高效率的编程过程是每位程序设计工作者追求的目标,要做 到这一点,就必须掌握正确的程序设计方法和技术。 1.3.1 程序的三种基本结构 为了避免在传统流程图中用“很随意”的流程线来描述程序的转 移功能。而导致的程序结构杂乱无章,提出了程序的三种基本结构。 即:程序的顺序、选择和循环三种控制流程 程序的顺序、 程序的顺序 1.顺序结构 表示程序中的各操作是按照它们出现的先 后顺序执行的,其特点 特点是:程序从入口点a开 特点 始,按顺序执行所有操作,直到出口点b处, 所以称为顺序结构。 2.选择结构 表示程序的处理步骤出现了 分支,它需要根据某一特定的 条件选择其中的一个分支执行。 (a) 单选则 (b) 双选择 (c) 多选择 3.循环结构 表示程序反复执行某个或某些操作(即需要循环执行的部分),直 到某条件为假(或为真)时才可终止循环。 最主要的是:什么情况下执行循环?哪些 操作需要循环执行? 当型循环:先判断,后执行。即当满足给 定的条件时执行循环体,并且在循环终端处 流程自动返回到循环入口;如果条件不满足, 则退出循环体直接到达流程出口处。 直到型循环:先执行,后判断。即直接执 行循环体,在循环终端处判断条计,如果条 件不满足,返回入口处继续执行循环体,直 到条件为真时再退出循环到达流程出口处。 1.3.3 结构化程序设计方法 主要包括: ① 只采用三种基本的程序控制结构来编制程序,从而使程序具有 良好的结构; ② 程序设计自顶而下; ③ 用结构化程序设计流程图表示算法。 1、结构化程序设计特征 (1) 以三种基本结构的组合来描述程序; (2) 整个程序采用模块化结构; (3) 有限制地使用转移语句,且只限于在一个结构内部跳转,不 允许从个结构跳到另一个结构,这样可缩小程序的静态结构与动态 执行过程之间的差异,使人们能正确理解程序的功能; (4) 以控制结构为单位,每个结构只有一个入口和一个出口,各 单位之间接口简单,逻辑清晰; (5) 用结构化程序设计语言书写程序。 2、自项而下的设计方法 结构化程序设计的总体思想是采用模块化结构,自顶而下,逐 步求精。 3、程序设计的风格 程序设计风格从一定意义上讲就是一种个人编写程序时的习惯。 (1)语句形式化。准确,无二义性。 (2)程序一致性。保持程序中的各部分风格一致,文档格式一致; (3)结构规范化。程序结构、数据结构、甚至软件的体系结构要符 合结构化程序设计原则。 (4)适当使用注释。 (5)标识符贴近实际。程序中数据、变量和函数等的命名原则应选 择有实际意义标识符,以易于识别和理解。例如:表示电压和电流 的变量名尽量使用v和i,而不要用a和b。要避免使用类似aa、bb等 无直观意义的变量名。 程序设计风格举例,如有A和B两个小程序如下: 本章小结 本章介绍的基本内容有: ① 语言、程序和程序设计; 语言是交流的工具,程序是指令的集合.而程序设计就是用计算 机语言对所要解决的问题进行完整而准确的描述过程。一个完整的 程序应该涉及到以下四个方面的问题:数据结构、算法、编程语吉、 程序设计方法。 程序设计过程的四个步骤是: ⑴ 分析问题,建立数学模型; ⑵ 确定数据结构和算法; ——确定解决问题的方案 ⑶ 编制程序; ——用程序语言把这个解决方案严格的描述出来 ⑷ 测试程序。 ——计算机上测试这个程序 ② 算法、算法设计和算法的表示; 常用算法:迭代法、枚举法、递归法等, 注意设计算法和编写程序要分开考虑,当你还没有学习程序语言 时,就学会针对一些简单问题设计算法,这是学习程序设计入门的 好方法。 ③ 程序结构、结构化程序和程序风格。 程序的结构化技术是程序设计的基本技术,它使得程序在逻辑上 层次分明、结构清晰、易读、易维护,从而提高程序质量和开发效 率:采用结构化程序设计方法,并且用流程图表示算法足必须的。 将算法转换成程序代码,并注意程序风格,这都是编写代码时要注 意的问题。 作业:1. 第一和第二大题做在书上 2. 第三大题的 1, 5, 7, 8

本文链接:http://kuenergyclub.com/diyidaiyuyan/794.html