当前位置:首页 >> 学科竞赛 >>

NOI初级教程


目录
1、 前言 2、 计算机基础知识 3、 算法及其描述 4、 初次使用 TURBO-PASCAL(Free Pascal) 5、 顺序结构程序设计 6、 分支结构程序设计 7、 循环结构程序设计 8、 分支与循环应用加深 9、 字符串与数组 10、枚举算法入门 11、数组应用举例 12、过程与函数的简单使用

第一章 前言 一、有关 NOI 的

几个问题
1. 什么是 NOI? NOI 就是 National Olympiad in Informatics,即全国信息学奥林匹克,它 的分区联赛相当于数学的全国高中联赛, 物理上的全国复赛和化学上的全国 初赛。分区联赛分为初赛和复赛,初赛为笔试,复赛为上机编程。复赛从 2001 年开始已经改为由全国统一评奖, 有的省市也把复赛成绩作为选拔 NOI 选手的重要依据。自 1995 年开始举办,是一项全国性的奥林匹克学科竞赛 活动,是全国中学生五大学科奥林匹克活动之一,其它四项是数学、物理、 化学、生物。每年一届,初赛定于每年的十月份最后一个星期六的下午,复 赛一般在每年的十一月份最后一个星期六或十二月份第一个星期六。 初赛和 复赛都是全国统一试题, 统一时间考试。 初赛以地级市为单位进行组织考试, 以书面考试形式进行,时间两小时。复赛以省为单位,根据初赛参赛人数, 选取 5%以内的人参加复赛,根据成绩由高到低评选出省一、二、三等奖。 初赛一般考察计算机基本知识, 基本数学能力和基本程序设计知识和能 力。初赛试题的类型一般有:选择题(基础知识) ,数学题(一般是推公式) , 写程序运行结果题,编程知识(考察范围不定,考过数据结构,算法复杂度 等)和程序填空。 复赛是上机编程,一般是 3 个小时,4 个编程题目。初中组复赛一般是 键盘输入,屏幕输出(有点落后了) ,而高中组则是文件输入、输出。内容 涉及到搜索、动态规划、简单的图论算法以及一些数学技巧。难度虽不大, 但建议初学者不要眼光太高, 尽力把自己有把握的题目做正确就可以了, 不 要花很多精力想难题。记住:信息学竞赛从不会给“过程分” ,如果程序没 有编完或者没有调试通过, 除了你运气好撞到几分之外, 几乎可以肯定该题 你将得 0 分。至于全国竞赛 NOI,相当于数理化的冬令营比赛,每个省有 3~4 名选手参加,选出国家集训队员 20 名左右,大家不要把它和分区联赛 搞混淆了, 其中的优秀学生参加国家队的集训, 并最终选出四名同学组成国 家队参加国际比赛(IOI) 。江苏省这几年活动开展得比较广泛,都是组织两 个代表队参加全国竞赛。 2、 “信息学”学的是什么? 信息学学习内容主要有以下几个方面: (1)掌握一种结构化的程序设计语言; (2)计算机相关基础知识; (3)初等组合,这是信息学解题的思维方式; (4)图论,主要是基础概念方面的,用于理解算法;
2

(5)数学问题,这类题目考的是数学思维,其中有一部分是考创造能 力的; (6)培养分析问题、解决问题的能力。 3、学习过程中要注意什么问题? 第一,要认清自己的位置。也就是根据自己的学习目的,判断自己是什 么水平,经过努力能到达什么水平。 第二, 要能熟练的掌握自己使用的编程语言。 常常看到有人问一些很简 单的语法问题什么的, 其实这些东西都应是基础的知识, 只需要翻翻书或看 看系统的帮助就可以弄懂的。如果连编程语言都不了解,又怎么能够编程 呢?这里说的编程语言指的是标准的程序设计语言, 例如 PASCAL, C/C++。 而一些集成开发环境(IDE)并不属于这个范围,例如 DELPHI,VB,VC 等。 第三,把一些基础打好,这个非常重要。所谓基础,就是一些基本的算 法,例如:求最小公倍数,高精度,排序,递归,回溯等。 第四,提高正确率。其实第三点说的“打好”基础的意思就是:对于基 础的题目,一定要争取百分百正确!简单的题目一定不能丢分,很难的题目 不要花太多时间,能拿分就可以了。当然,这些建议是对于入门者来说的。 在开始使用编程语言后, 你会发现, 程序中不能错一点点, 哪怕是一个标点, 少一个或多一个,要么是语法不正确,不能运行,要么是另外一个含义,得 不到你想要的结果。 因此提高正确率其实首先是要细心加耐心, 在此基础上 再全面地考虑问题,得到较多的分数。 附注:程序的三种错误 1. 语法错误 就是不符合语言的基本规则,编译时不能通过。 2. 语义错误 程序虽然编译能通过,但是方法不正确或考虑得不全 面。 3. 语用错误 用户在使用程序时的错误,一个好的程序要有好的用户 界面,尽量避免用户在使用上的错误。对于信息学奥林匹克竞赛的 程序来说, 这一点主要是要注意输入、 输出的格式符合题目的要求。 第五,要懂得利用网络资源。学会在网络上收集资料,国内有许多学校 和部门都办了相关网站或网页,如我校的网站www.ntzx.net.cn中的在线辅导 中专门有信息学奥林匹克栏目。 当然有许多网页是大同小异。 但是有一点要 注意:不要沉溺在网络上。网络能帮助你学习许多知识,也会使一些人荒废 时间,得不偿失。 4、用什么编程语言,什么 IDE 好? 编程语言主要在以下几类: BASIC :如果你是编程初学者,那么 BASIC 是最适合的,但是由于大 部分这类语言不是结构化的,不适合搞信息学。
3

PASCAL:这个是最适合初学者学习的,因为这种语言和 BASIC 一样 简单易学,而且现在国内中学生的竞赛资料都是用 PASCAL 写的。 C/C++ :大学生基本都用这个的,参加 ACM(大学生程序设计竞赛) 必学语言。C/C++里面有一些概念可能不太容易被初学编程的中学生接受, 而且如果用得不熟练是很容易出错的。 不过, 学过 PASCAL 的人要学 C/C++ 是很容易的,编程语言的学习是触类旁通的。 有人曾经戏称 PASCAL 语言是艺术性的语言,C 语言是独具匠心的语 言,一个是艺术家用的,另一个是匠人用的,当然这话有点过分。 IDE: PASCAL:建议初学者使用 Turbo Pascal 7.0 或者 Borland Pascal 7.0,要 对调试的基本操作熟悉。以后到了高层次的竞赛,例如 NOI,是需要 free Pascal 的,而且是 Linux 下的,现在有许多版本的 Free Pascal 在 Windows 下也可以使用,你可以从相关网站下载。不过虽然 IDE 变了,但是用几天 就会熟悉的了。至于 DELPHI 这种基本语法跟 Pascal 相似的可视化编程工 具,有点大材小用的感觉。 C/C++ :GCC 是首选,Turbo C++ 3.0 也不错。 选择什么 IDE 没有本质上的差别,关键是要看写什么程序,对复赛来 说,江苏省从 2002 年开始高中组建议使用 Free Pascal,有时也会出现一些 问题, 如 FreePascal 可以充分使用系统内存, 而一般的 TP 变量只能用 64KB, 这样会造成选择不同的 IDE 出现不公平的现象,因此有的比赛指明程序变 量最大使用内存的大小,以体现公平。

二、分区联赛特点和历史回顾
从 1995 年第一届分区联赛开始,已经比较成熟了。题目的难度和考查 范围从总体来说是逐年增加。 初赛主要是靠平时的积累。 其中选择题部分各 年差别比较大,考查的范围很不相同。坦白地说,初赛的题目水平并不是很 高,虽然题目有时看起来不大规范,不过从另一方面讲,在选拔复赛选手的 角度讲,初赛题目还是比较成功的。只要基础好(选择题和填空题) ,有耐 心(完善程序)和细心(写运行结果) ,初赛一般都能得到高分。 至于复赛, 全是上机完成。

三、备战 NOI 初赛策略
初赛考的知识点, 大纲无非是计算机基本常识、 基本操作和程序设计基 本知识。选择题考查的是知识,而填空、问题解决题更加重视能力的考查。 一般说来,选择题是不需要单独准备的,也无从准备,只要多用心积累就可 以了。到是问题解决题目比较固定,大家应当做做以前的题目。写运行结果 需要多做题目, 培养良好的程序阅读和分析能力, 而完善程序最好总结一下
4

以前题目常常要你填出来的语句类型。 这个每年都差不多的, 想不出来是可 以回忆一下有哪些可能填的语句,再放到程序里面看是否合适。 (一) 、选择题 一般它们是比较容易得分的,一共 30 分,不可错过。从 2003 年起增加 了多项选择题, 选择题的分数也增加了一些。 但是选择题考查的知识范围比 较广,得全分的也只是很少的同学。近几年来,初赛的考查范围有了很大的 变化,越来越紧跟潮流了。这是好事情,不过需要大家有比较广泛的知识, 包括计算机硬件,软件,网络,数据结构(例如栈,队列,排序算法) ,程 序设计语言以及一些基本的数学知识和技巧(例如排列组合) 。 (二) 、填空与问题解决题(称之为解答题) 这部分题目对数学要求要高一点,往往考查的是代数变形、数列(一般 是考递推) ,也考查一些算法和数据结构知识。建议大家多花一点时间做, 尽量做对。 下面是前几年相关初赛题: 1、 数组 A[30..100,20..100]以行优先的方式存储,每个元素占 8 个字节,且已 知 A[40 ,30]的地址为 2000,则 A[60,90]的地址为:_________________ 如果以列优先存储,则为:_________________ [说明]:本题考查了数据结构中数组存储方式,行优先就是先存储满一 行后再存储下一行, 而二维数组一般是第一个下标表示行、 第二个下标表示 列,行优先可以进行如下的运算: A[40,31]----A[40,100] 70 个元素; A[41,20]----A[41,100] 81 个元素; A[42,20]----A[42,100] 81 个元素; 满 19 行, 19*81 个 ?? 元素 A[59,20]----A[59,100] 81 个元素; A[60,20]----A[60,89] 70 个元素。 所以行优先方式下 A[60,90]的存储地址为: A[40,30]的存储地址+(70+19*81+70)*8 同样可以得到列优先方式下 A[60,90]的存储地址为: A[40,30]的存储地址+(60+59*71+30)*8 2、设栈 S 的初始状态为空,现有 6 个元素组成的序列{1,3,5,7,9,11},对该序列 在 S 栈上依次进行如下操作(从序列中的 1 开始,出栈后不在进栈):进栈,出栈, 进栈,进栈, 进栈,进栈,出栈,进栈,问出栈的元素序列是:_________,栈顶指针 的值为______栈顶元素为:___________________ [说明]:考查了数据结构中的栈,只要熟悉栈的进出规则——“先进后
5

出” ,操作起来并不难。 3、把中缀表达式写成后缀及前缀表达式 (1) (P+Q)*(A-B)/((C+D)/(E-F))-G 后:_________________前:_________________ (2) A-C*D+B/E*(D/A) 后:_________________前:_________________ 4、根据后缀表达式,写出前缀及中缀表达式 ABC/DE+GH-/*+ 前:_________________中:_________________ [说明]:这两题考查了数据结构中的表达式树。 5、用一个字节来表示整数,最高位用作符号位(1 为正,0 为负),其他位表示数 值: (1) 、这样的表示法称为原码表示法,表示数的范围为:_________________ (2) 、原码表示法,将出现_________________有两种表示 (3) 、实际上计算机中是用补码表示数,其表示范围为:_________________ [说明]:考查了数的原码,补码表示形式,知道了原码就是直接二十进制的 转化,补码是反码的基础上加 1,而补码只对非正数应用。 6、已知 N*N 个数据成方阵排列: A11 A12 A13 ... A1n A21 A22 A23 ... A2n ... An1 An2 An3 ... Ann 已知 Aij=Aji, ( 1 ) 、 将 A11,A21,A22,A31,A32,A33... 存 储 到 一 维 数 组 A(1),A(2),A(3)...A(K) 给出 i,j 写出求 K 的表达式:_________________ (2) 、 将 A11,A12,...A1n,A22,A23,...A2n,A33... Ann 存 储 到 一 维 数 组 A(1),A(2),A(3)...A(K), 给出 i,j 写出求 K 的表达式:_________________ 7、已知一个数列 U1,U2,U3...Un...,往往可以找到一个最小的 K 值和 K 个数 a1,a2,..,ak, 使 得 数 列 从 某 项 开 始 都 满 足 :U(n+k)=a1*U(n+k-1) + a2*U(n+k-2)+... + akUn ( 式 A) 例 如 数 列 1,1,2,3,5... 可 以 发 现 : 当 K=2,a1=1,a2=1 时,从第 3 项起(N>=1)满足:U(n+2)=U(n+1) + Un 试对数列 1^3 ,2^3 ,3^3 ,...,N^3,...,求 K 和 a1,a2,...ak,使得式 A 成立.
6

[说明]:这两题实质是考数学。 8、 给出一棵二叉树的中序遍历:DBGEACHFI 与后序遍历:DGEBHIFCA,画出 此二叉树。 [说明]:考查你对二叉树遍历的基本了解。 9、给出二叉树的前序遍历与后序遍历,能确定一棵二叉树吗,举例说明。 [说明]:同样考查你对二叉树遍历的基本了解,其实由前序和后序遍历的结 果不能确定二叉树的结构。 10、下面是一个利用完全二叉树特性,用顺序表来存储的一个二叉树,结点数 据为字符型(结点层次从小到大,同一层从左到右顺序存储,#表示空结点,@表 示存储数据结束) 结点 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 数据 A B C # # D E # # # # # G F @ 画出对应的二叉树: [说明]:考查了数据结构中的二叉树 11、用邻接矩阵表示有向图(图略) [说明]:考查了数据结构中的图的表示 12、 根据 Nocomachns 定理,任何一个正整数 n 的立方一定可以表示成 n 个连续的奇数的和。 例如: 13=1 23=3+5 33=7+9+11 43=13+15+17+19 在这里,若将每一个式中的最小奇数称为 X,那么当给出 n 之后,请写出 X 与 n 之间的关系表达式:___ [说明]:其实是考代数 12、某班有 50 名学生,每位学生发一张调查卡,上写 a,b,c 三本书的书名, 将读过的书打“*” ,结果统计数字如下: 只读 a 者 8 人;只读 b 者 4 人;只读 c 者 3 人;全部读过的有 2 人;读 过 a,b 两本书的有 4 人;读过 a,c 两本书的有 2 人;读过 b,c 两本书的有 3 人。 (1)读过 a 的人数是( ) 。
7

(2)一本书也没读过的人数是( ) 。 [说明]:考查逻辑推理的能力,数学好的小学生大概都可以做。 (三) 、写运行结果 这是初赛分数占比例最大的部分, 是同学得分最多的地方也是部分同学 失分最多的地方。 一般做这类题目的核心是找程序目的, 即这个程序想干什么。 迄今为止 考过的题目还没有“乱写”的,总有一点“写作目的”的。抓住了它,不仅 得出答案变得很容易了, 而且对自己的结果也会比较有信心。 写程序运行结 果大纲规定是必考的。试卷中给出的程序并不复杂,语句的含义容易明白, 因此悟性好的选手总是很快就能体会到程序的设计思路并得出正确的答案, 而机械模仿计算机硬算出结果的同学往往做得很慢,而且容易失误。 有部分同学在读懂了程序的意思后结果却写错了, 主要原因是没有把握 住“临界点” ,即条件的具体限定,循环的起始点、结束点等等,往往是多 算一个点或少算一个点。 另外一个就是要注意输出格式, 因为写程序运行结果的题一般只有输出 语句才有输出结果,如果读懂了却将格式写错了得不到分数那是最可惜的 了。 1.(1999 年分区联赛) Program excpl; var x,y,y1,jk,j1,g,e:Integer; a:array[1..20] of 0..9; begin x:=3465; y:=264; jk:=20; for j1:=1 to 20 do a[j1]:=0; while y<>0 do begin y1:=y mod 10; y:=y div 10; while y1<>0 do begin g:=x; for e:=Jk downto 1 do begin g:=g+a[e]; a[e]:=g mod 10; g:=g div 10 end; y1:=y1-1
8

end; jk:=jk-1 end; j1:=1; while a[j1]=0 do j1:=j1+1; for Jk:=j1 to 20 do write(a[jk]:4); writeln end. 程序不长,但是有一定的难度。高手最多半分钟就看懂了程序的意思, 但初学者往往算了很久得出了结果却是错的。 下面我们还是先以一个初学者 的身份分析一下这个程序。记住,不要一开始就模拟电脑来一个个语句“执 行” 。 分析程序一般从以下几点入手: 1、变量 首先是变量的名字。 可惜分区联赛题目中的变量不是 I 就是 J, 很讨厌。 I 和 J 一般作为循环计数器, 没有什么意思,因此不要管它了。然后要看变 量在程序的哪里出现过, 着重看它与其他变量的相互引用关系, 猜测它的作 用。例如上题。x 只在 g:=x 中出现,暂时不要管它,因为它很可能只是一 个初始数据。y 有三处:1) while y<>0 do 2) y1:=y mod 10; 3) y:=y div 10; 很明显,y 每次少了最后一位数字,把这位数字给了 y1。有经验的选手应该 体会到了什么,不过我们继续。现在我们知道了:y 对程序的作用是:每次 提供最后一位给 y1,即 y1 每次的值依次是:4,6,2 y1: 1)while y1<>0 do 2)y1=y1-1 很明显就是一个循环嘛!循环 y1 次! jk: 1)for e:=jk downto 1 do 2)jk:=jk-1 jk 作为循环初始值,居然一次比一次少...其原因有待进一步分析。 j1: 1)for j1:=1 to 20 do a[j1]:=0; 2)j1:=1; 3)while a[j1]=0 do j1:=j1+1; 4)for Jk:=j1 to 20 do write(a[jk]:4); 显然,j1 和其它变量没有什么联系。1)是初始化,2)3)4)是输出数组 a g: 出现的位置是几层循环之内了,应该很重要!一会儿再分析!
9

e: 作为循环变量,没有什么意思。 通过变量分析,我们知道了:x,y 是数据,y 每次提供最后一位给 y1, 循环 y1 次。j1 和 g 的作用有待分析。 2、程序结构 我们把程序分成几块。 1)x:=3465; y:=264; jk:=20; for j1:=1 to 20 do a[j1]:=0; 初始化。不要管它。 2)while y<>0 do begin y1:=y mod 10; y:=y div 10; while y1<>0 do begin << g:=x; for e:=Jk downto 1 do begin g:=g+a[e]; a[e]:=g mod 10; g:=g div 10 end; >> y1:=y1-1 end; jk:=jk-1 end; 3) j1:=1; while a[j1]=0 do j1:=j1+1; for Jk:=j1 to 20 do write(a[jk]:4); writeln 输出结果,也不要管它。 块 2 最重要。它的思想是:每次取 Y 的最第位 y1,执行<<>>y1 次,每 次把 jk 减一。现在最重要的是<<>>中的在干什么。注意到最后输出的 a[], 要留意 a[]的变化!a[e]总是取个位(g mod 10),g 每次少一位,和 a[e-1](别 忘了 e 在循环!)相加...难道是...高精度加法???它执行了 y1 次,y1 每次 都是 y 的个位...对了。程序就是在做 x*y 所以答案就是 3465*264=914760 再看它的输出格式,输出的应该是:___9___1___4___7___6___0 其实有经验的话,看到 g 这个变量名和 g:=g+a[e]; a[e]:=g mod 10;这几 个标志句子。就可以一下子知道程序的用意了。
10

<< >>中只有 6 行,你可以模拟电脑“执行”几个语句在找规律。方法 是:把循环“展开” ,再写一个变量值表,即:语句执行后变量情况: g:=x; g:=g+a[e]; g=x+a[e]; a[e]:=g mod 10; a[e]:=x+a[e]的个位 g:=g div 10; g=(x+a[e])的前几位 g:=g+a[e-1]; g=(x+a[e])的前几位+a[e-1]; a[e-1]:=g mod 10; a[e-1]=a[e-1]+(x+a[e])的进位 …… (四)完善程序 这部分题目得分率似乎不高。 许多同学有这样的感觉, 这道题如果纯粹 作为一个编程题, 自己还能写出程序, 但是试题中必须要根据它所设定的算 法来实现, 通常的感觉是不知道程序中要你做什么, 不能读懂它的算法基本 思想。对于这一类题目,往往要先多读几遍题意,理解要实现什么,然后是 理程序中的数据结构、变量含义,最后才去考虑填什么语句。 这类试题常常让大家填的是: 1、初始化(i:=0; j:=0; for i:=1 to n do a[i]:=0 之类的) 2、一些明显的动作: (1) 结果没有储存在需要的地方。 (2) 累加器没有做加法 (3) 输出 3、关键动作。在算法描述中出现的比较关键的步骤。例如交换排序程序的 “交换”操作等很明显需要完成的操作。分析方法和写运行结果类似,注意 分析变量和程序结构,理解变量和模块的作用是解题的关键。 以 2003 年初赛题为例(初中组第二题、高中组第一题) : “翻硬币” [题意]: 有 M 枚硬币堆在一起, 从上面开始先一次将一枚翻过来, 再一次将两枚 一起翻过来??最后将 M 枚一起翻过来, 再从上面开始第一次将上面一枚翻 过来, 一次将上面两枚一起翻过来??直到最后还有所有 M 枚全部正面朝上 为止。要求总的翻硬币次数。 [说明]: 这道题如果纯粹作为一个编程题,大家可能会用“模拟法”写出相关程 序,设置一个标志数组,模拟这个过程,每翻一次都检查一下是否是全部正 面朝上, 最后输出翻的次数就可以。 问题是题中给出的程序不是用这种方法, 而是用的数学推导关系, 也就是说要求你找出翻的总次数跟 M 的关系。 在短
11

的时间内找出这样的规律很难, 因此此题得分率很低, 几乎没有同学当场能 做出。 [程序清单]: program program42; var m:integer; function solve(m:integer):longint; var i,t,d:longint; flag:boolean; begin if m=1 then ________(1)__________ else begin d:=2*m+1; t:=2; i:=1; flag:=false; repeat if t=1 then begin solve:=i*m; flag:=true; end else if t=_______(2)_________ then begin solve:=____________(3)______; flag:=true;end else __________(4)____________; i:=i+1; until flag; end; end; begin read(m); if (m>0) and (m<2000) then writeln(________(5)______); end. [分析]: 仔细阅读和分析题意, 可以能够填出第一个和第五个, 因为只有一枚时 要翻两次,而主程序中没有引用函数,在输出时直接引用。问题是其它三个 如何填,在短时间内很难找出相关数学关系,如果有一台电脑,先写出模拟 法的程序,运算出 m 不同数值时的对应结果,再从中找出关系还好些,初 赛的性质决定了只能由人工来模拟计算机工作,找出其中的规律。 从 solve 函数中可以看出分成了 M=1 和 M>1 两种大的情况,在 M>1 的情况下,结果的不同与 t 有关,程序中根据 t 分为三种情况,其中 t=1 时 的结果已经给出(为 i*m) ,而另外两种情况是要求你自己完成的,其中一 种情况是能够决定翻的次数的, 而整个程序中没有看到对 t 进行处理的语句,
12

所以要完成的任务一是:t 为另一值时所确定的翻硬币的次数,任务二是:t 为其它情况时对 t 的处理, 这个处理的赋值语句肯定与 m 有关。 仔细看一看 程序,其中又引进了一个变量 d,它的值是 2*m+1,已有的代码中也没有用 到这个变量,可以猜想给 t 赋值的表达式肯定是一个跟 d 有关的式子。 如果能结合“模拟法”程序运行得出的结果,比较结果跟 i 、m 的关 系,就能方便地找出规律(通项公式) 。 以下是 m 为不同值时,相关几个变量跟结果的关系: m=3 d=7 2*m=6 重复 t:=t*2 mod d 运算,直到 t=1 或 t=2*m i 1 2 3 t 2 4 1 solve=i*m=9 m=4 d=9 2*m=8 i 1 2 3 t 2 4 8 solve=i*m-1=3*4-1=11 m=5 d=11 2*m=10 i 1 2 3 4 5 t 2 4 8 5 10

solve=i*m-1=5*5-1=24

m=6 d=13 2*m=12 i 1 2 3 4 5 6 t 2 4 8 3 6 12 solve:=i*m-1=6*6-1=35 m=7 d=15 i 1 2 t 2 4 ..... m=15 d=31 i 1 2 t 2 4 2*m=14 3 4 8 1

solve:=i*m=4*m=28

2*m=30 3 4 5 8 16 1 solve:=i*m=5*15=75

m=16 d=33 2*m=32 i 1 2 3 4 5 t 2 4 8 16 32

solve:=i*m-1=5*16-1=79

m=30 d=61 2*m=60 i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
13

t 2 4 8 16 32 3 6 12 24 48 35 9 18 36 11 22 44 27 54 47 33 5 10 20 40 19 38 15 30 60 solve:=I*m-1=899 所以本题应填的结果为: (1) solve:=2 (2) 2*m (3) i*m-1 (4) t:=2*t mod d (5) solve(m) 综上所述,初赛还是有一定的难度的,但是只要基础打牢,系统训练 过的同学正常发挥应该能拿到 50 以上的分数的。 至于复赛题型与内容,在后续的内容里再向大家介绍。

14

附: 全国青少年信息学(计算机)奥林匹克分区联赛竞赛大纲(修改稿) 1.试题知识范围: 初赛内容与要求 1.计算机和信息社会(信息社会的主要特征、计算机的主要特征、数字通信网 络的主要特征、数字化) 2.信息输入输出基本原理(信息交换环境、文字图形多媒体信息输入输出方式) 3.信息的表示与处理(信息编码、微处理部件 MPU、内存储结构、指令,程序, 和存储程序原理、程序的三种基本控制结构) 4.信息的存储、组织与管理(存储介质、存储器结构、文件管理、数据库管理) 5.信息系统组成及互连网的基本知识(计算机构成原理、槽和端口的部件间可 扩展互连方式、层次式的互连结构、互联网络、TCP/IP 协议、HTTP 协议、 WEB 应用的主要方式和特点) 6.人机交互界面的基本概念(窗口系统、人和计算机交流信息的途径(文本及 交互操作) ) 7.信息技术的新发展、新特点、新应用等。 1. Windows 和 LINUX 的基本操作知识 2. 互联网的基本使用常识 (网上浏览、搜索和查询等) 3. 常用的工具软件使用(文字编辑、电子邮件收发等) 数 据 结 构 程 序 设 计 1.程序语言中基本数据类型(字符、整数、长整数、浮点) 2. 浮点运算中的精度和数值比较 3.一维数组(串)与线性表 4.记录类型(PASCAL)/ 结构类型(C) 1.结构化程序设计的基本概念 2.阅读理解程序的基本能力 3.具有将简单问题抽象成适合计算机解决的模型的基本能力 4.具有针对模型设计简单算法的基本能力 5.程序流程描述(自然语言/伪码/NS 图/其他) 6.程序设计语言(PASCAL/C/C++,2003 年仍允许 BASIC) 1.初等算法(计数、统计、数学运算等) 2.排序算法(冒泡法、插入排序、合并排序、快速排序) 3.查找(顺序查找、二分法) 4.回溯算法

计 算 机 的

基 本 常 识

计 算 机 的

基 本 操 作

程 序 设 计 的 基 本 知 识

基本算法 处 理

15

复赛内容与要求 在初赛的内容上增加以下内容: 数 据 结 构 1.指针类型 2.多维数组 3.单链表及循环链表 4.二叉树 5.文件操作(从文本文件中读入数据,并输出到文本文件中)

程 序 设 计

1.算法的实现能力 2.程序调试基本能力 3.设计测试数据的基本能力 4.程序的时间复杂度和空间复杂度的估计

算 法 处 理

1.离散数学知识的应用(如排列组合、简单图论、数理逻辑) 2.分治思想 3.模拟法 4.贪心法 5.简单搜索算法(深度优先 广度优先)搜索中的剪枝 6.动态规划的思想及基本算法

2.比赛中使用的程序设计语言是: 2003 年:初赛:BASIC、PASCAL 或 C/C++; 复赛:BASIC、PASCAL 或 C/C++。 2004 年:初赛:BASIC、PASCAL 或 C/C++ 复赛:PASCAL 或 C/C++。 2005 年及之后:初赛:PASCAL 或 C/C++ 复赛:PASCAL 或 C/C++。

16

第二章
一、二进制数

计算机基础知识

计算机内信息的存储、运算等主要通过二进制。 二进制的特点:只有两个基本数字 0 和 1;逢二进一位。 二进制的优点:因为它只有两个基本数字 0 和 1,所以容易物理实现。 所谓物理实现, 指的是通过不同的物理状态来表示不同的数字。 如在计算机 的内部,对于 0 和 1 可以通过高电平(电压稍高一点的电流)和低电平(电 压稍低一点的电流)来表示。又如在软磁盘上存放一个 0 或 1,可以通过磁 性的强弱来表示。 二进制的缺点: 读写不方便。 有时又引进八进制或十六进制来方便描述。 因为 8 是 2 的 3 次方,所以三位二进制跟一位八进制相对应;同样四位二 进制跟一位十六进制相对应。八进制有 8 个基本数字:01234567,它的特点 是逢八进一位。而十六进制的有十六个基本数字:0123456789ABCDEF,它 的特点是逢十六进一位。下面是几种进制的对照表: 十进制 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 二进制 0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000 10001 10010 10011 10100 八进制 0 1 2 3 4 5 6 7 10 11 12 13 14 15 16 17 20 21 22 23 24 十六进制 0 1 2 3 4 5 6 7 8 9 A B C D E F 10 11 12 13 14

我们知道十进制的每一位的权代表的是十的若干次方,不同进制的数, 基数不同,其每位上所代表的值大小也不同,我们称之为“权” 。
17

①十进制数,逢十进一。如(219)10=2*102+1*101+9*100 ②二进制数,逢二进一。如(11010)2=1*24+1*23+0*22+1*21+0*20=26 ③八进制数,逢八进一。如(273)8=2*82+7*81+3*80=187 ④十六进制数,逢十六进一。如(27B)16=2*162+7*161+11*160=635 从以上的计算中可以看到:进制不同,基数不同,每位上权值大小也不 同,数值大小也不相同。 将十进制数转换为任意进制数的基本方法为: 将十进制数除以所定的进 制数反向取余,如将十进制数 39 转为二进制数: 2 | 39 2 | 19 ??1 2 | 9 ??1 2 | 4 ??1 2 | 2 ??0 2 | 1 ??0 2 0 ??1 39(10)=100111(2) 39=32+4+2+1=100111(2) 又如将 245 转为八进制:245(10)=365(8) 8 | 245 8 | 30 ??5 8 | 3 ??6 8 0 ??3 对于十进制小数转为其他进制的小数, 则是不断将小数部分乘以进制数 取整,作为转换后的小数部分,直到为零或精确到小数点后第几位。如 0.35(10)=0.01011(2), 0.125(10)=0.001(2) 任意进制数转为十进制数的基本方法是按权展开求和, 前面①②③④例 子已说明。

二、信息代码及 ASCII 码
信息在计算机内存储或运算是通过二进制来实现的, 计算机本身并不要 求你按什么规律来将信息转换为什么代码, 只有你给出对应规律就行。 也就 是说谁都可以来定义代码, 但如果这样各自乱定义没有统一的规定, 对于计 算机与计算机之间的信息交换就不能保证了。 国际上统一使用美国信息交换标准代码 ASCII 码。ASCII 码用八位的二 进制表示,基本的 ASCII 字符集共 128(2 的 7 次方)个,其二进制代码最 高位为 0,如“A”对的编码为 01000001(2) ,相当于十进制 65。中国汉字 编码用两个字节表示,为了区别一般编码,其最高位设为 1。汉字国标区位 码 GB2312-80 又称区位码,共分 94 个区,两位的区号和两位的位号惟一确 定一个汉字或符号,01 到 15 区为符号区,16 到 55 区为一级汉字(以拼音
18

为序)共 3755 个,56 以后的二级汉字(以部首为序)共 3008 个。 其它常见的代码有 BCD 码等(四位二进制只取前面的 4 位从而方便地 跟十进制对应起来) 。

三、原码、反码、补码
对于正数, 在计算机内部都是采用原码表示的, 即原来是什么就表示成 相应的二进制数。一般第一位为符号位。 如+65,对应的二进制数是 1000001,加上符号位为 01000001。 对于负数或 0 可能用补码表示。补码是在反码的基础上加上 1。而反码 就是取反的操作,将 0 变为 1,1 变为 0。 由于采用了补码,使 0 的表示唯一了。 (问题:如果都是用原码表示,0 的两种表示是什么?)

四、其它一些计算机基础知识
1.计算机的产生与发展 1946 年世界上第一台电子计算机——埃尼阿克(ENIAC)于美国产生。 计算机的发展经历了四代:第一代电子管计算机、第二代晶体管计算机、第 三代中小规模集成电路计算机、第四代大规模和超大规模集成电路计算机。 我国从 1956 年开始电子计算机的科研与教学工作,1983 年 12 月成功 地研制成功每秒运行 1 亿次以上的“银河”巨型计算机。1992 年 11 月研制 成功每秒运行 10 亿次的“银河Ⅱ”巨型计算机,1997 年又研制成功每秒运 行 130 亿次的“银河Ⅲ”巨型计算机。 2.计算机系统及其工作原理 (1)计算机系统组成 计算机系统由硬件和软件两部分组成。 硬件指计算机的各种元器件; 软 件指程序的有关的文档资料。 主要硬件: ①输入设备 常见的有键盘、鼠标、扫描仪等。 ②输出设备 常见的有显示器、打印机、绘图仪等。 ③中央处理器 CPU 它包括运算器和控制器,运算器进行算术运算和逻 辑运算, 控制器是计算机的指挥系统, 它的操作过程是取指令——分 析指令——执行指令,循环执行。 ④存储器 具有记忆功能的物理器件,用于存储信息,存储器分为内存 和外存。内存是半导体存储器,它分为只读存储器(ROM) 、随机存储 器(RAM)和高速缓存(cache) ,一般所说的计算机内存大小是指 RAM 的大小,如 128MB、64MB、32MB 等。外存现在主要有磁性存储器(软 盘和硬盘、磁带等)和光电存储器(光盘等) ,它们可以作为永久性
19

存储器。存储器的两个重要技术指标:存取速度和存储容量,内存的 存取速度快,与 CPU 速度相匹配,软盘的存取速度慢。存储容量是指 存储信息量的大小,它用字节(Byte)作为基本单位,1 个字节用 8 位二进制 (Bit) 表示 ( 即 1Byte=8bit) , 1KB=1024B , 1MB=1024KB , 1GB=1024MB??。 计算机的软件: 分为系统软件和应用软件。 系统软件是管理和使用计算机的软件, 主要 有操作系统软件如 Windows95/98/2000/NT、DOS、UNIX 等,其中 Windows 系列是多任务可视化图形界面,而 DOS 是字符命令格式的单任务的操作系 统。应用软件是为了某个应用目的而编写的软件,主要有辅助教学软件、辅 助设计软件、文字处理软件、工具软件以及其它的应用软件。 (2) 计算机的工作原理 到目前为止,电子计算机的工件原理均采用冯.诺依曼的存储程序思想, 其工作过程如下图: (控制器发出控制信号控制其它器件工作)

输入输出设备

内存储器

运算器

控制器 程序中的数据、指令都采用数字化编码方式,保存在存储器中,程序中 的指令必须是属于这台机器的指令系统。 (3)计算机病毒:是一种程序,是人为设计的具有破坏性的程序。 3、DOS 的常用命令及其应用 (1)文件 文件是指记录在存储介质(如磁盘、光盘等)上的一组相关信息的集合。 文件夹(又称子目录) 将文件人为地分组存放,每一组给定一个名字, 则称这个组为文件夹。 文件的基本操作有建立、存储、复制、删除、重命名、移动、建立子目 录(文件夹) 、删除子目录(文件夹) 、进入子目录(文件夹) 、退出子目录 (文件夹) 。 (2) 内部命令 是指当 DOS 启动后, 计算机引导程序将系统以及常用的命令处理模块驻 留在计算机的内存中。 常用的内部命令有: 目录类 DIR(显示文件目录)、MD,CD,RD(建立、进入、删除子目录) 。 文件类 COPY (拷贝) 、 DEL (删除) 、 TYPE (显示内容) 、 REN (或 RENAME
20

改名) 功能类 CLS(清屏) 、TIME(查或改系统时间) 、DATE(查或改系统日期) 、 VER(查有关版本信息)等。 (3) 外部命令 存储在外存储器上的 DOS 可执行文件(扩展名为 COM、EXE 或 BAT 的) ,当用户使用外部命令时,计算机就从外存调入内存,当执行完命令, 就自动从内存中退出。常用的外部命令有: FORMAT (格式化磁盘) 、 DISKCOPY(磁盘拷贝)等。 4.Windows 基本知识 系统资源与资源管理器,文件与文件夹 运行程序:窗口执行、命令执行(可执行文件 exe 、com、 bat) 、不可直 接执行文件(要其它可执行系统的支持或提供给其它程序使用) 。 文件的类型:主要通过扩展名来区别,如.pas 表示 PASCAL 的源文件。 5.网络的基本知识 (1) 概念 将地理位置不同的计算机用通信手段连接起来,并共同遵守一定的协 议, 共享计算机的软、 硬件资源。 因特网是网络的集合, 是全球最大的网络。 (2) 网络类型 网络分为局域网(局限于某个范围内的网络连接)和广域网(跨地区的 范围广的网络,因特网是覆盖全球的广域网) 。 (3) 因特网提供的服务主要功能有: 信息浏览(WWW) 文件传输(FTP) 发送电子邮件(E-mail) 电子公告牌(BBS) 远程登录(telnet) 电子商务 网址的结构 如http://www.sina.com.cn 其是 http:// ——超文本浏览协议 www.sina——表示主机域名 com——网络机构域名,这里是商业网,其它的如 net、 gov 等 cn——地区域名,这里是中国域名,其它如 hk 为香港、 tw 为台湾, 不加地区域名的为国际域名。 电子邮件地址:如 yueking121@163.com 这里 yueking121 是用户名, @是分隔符号,163 是主机名。 网络内容比较多,请参见本章后阅读材料。 6.Linux 操作系统 是一种免费的操作系统,使用越来广泛,详见阅读材料。 7.汉字输入方法
21

汉字的输入方法很多,大体分为:流水码(序码) 、音码、形码、音形 码。 流水码: 区位码、 电报码、 通讯密码等均属于流水码, 优点是重码少 (几 乎没有重码),缺点是难于记忆。其中区位码比较早的有 GB2013/80,每个 汉字或符号均对应一个四位数,前两位为区号,后两位为位号。如“、 ”的 区位码为 “0102” 。 前 15 个区为基本符号, 16-55 区为一级汉字 (常用汉字) , 根据拼音的顺序排列,56 区以后为二级汉字(不常用的汉字) ,按部首的顺 序排列。 音码:以汉语拼音作为编码输入汉字,优点是大多数人都易于掌握,但 同音字多,重码率高,影响输入的速度。 形码:以汉字的字形进行编码,编码的规则比较多,难于记忆,要经过 训练才能较好地掌握,一般重码很少,能达到较高的速度。 音形码:将音码和形码结合起来,减少重码率,提高汉字输入速度。

五、计算机语言
计算机语言是人与计算机进行交流的一种工具,通过它可以编写程序, 让计算机完成交给它的系列任务。 计算机语言分为机器语言、汇编语言、高级语言。 机器语言是计算机唯一能够直接识别的语言, 无论是操作符和操作数都 是由 0 和 1 组成的, 其优点是简单, 执行效率高, 缺点是读写起来很不方便, 且通用性差,不同的计算机其机器语言也不一样。 汇编语言是机器语言的符号化, 只是增加了可读性, 但仍然是通用性不 强, 编程时要对相应机器有所了解, 换句话说就是要有一定的计算机专业基 础才能写出程序。不同类型、不同档次的计算机其汇编语言也不一样的。 由于机器语言和汇编语言都是针对机器而言的, 汲及到底层的操作, 有 人把它称为低级语言。 而直接面向应用的是高级语言, 只要用户能够确定好 算法, 不需要对机器了解多少就能够写出程序, 且高级语言都跟自然语言比 较接近(几乎都是英语) 。一般所说的程序设计语言都是指的高级语言。高 级语言很多,常见的有 BASIC、PASCAL、C、FORTRAN 等。 由于计算机能直接执行的只有机器语言, 所以其它语言写的程序都要有 一个“翻译”的过程。这种翻译分为两种:解释方式和编译方式。 解释方式就是一边翻译一边执行, 下一次执行时还要翻译, 还要依赖于 程序系统。 编译方式是将整个程序翻译成机器能够执行的代码, 以后只要执行这个 翻译好的代码就行了,不要重新翻译了。在 Turbo Pascal 7.0 里,运行程 序前会自动编译,一般情况下会在磁盘里生成一个同主名的 exe(可执行) 文件。

22

[阅读材料]:
一、网络基础知识
1、网络的概念:计算机网络(Network)是将处在 不同地理位置 且相互独立 的 计算机 或 设备, 通过 传输介质 和 网络设备 按照特定的 结构 和 协 议 相互连接起来, 利用 网络操作系统 进行管理和控制, 从而实现 信息传 输 和 资源共享 的一种信息系统。 2、网络的发展: ARPAnet ARPAnet (高级研究计划署网络, Advanced Research Projects Agency net) 是世界上第一个计算机网络, 出现在 20 世纪 60 年代后期, 由美国国防部资 助。其第一个节点于 1969 年在加利福利亚大学洛杉矶分校安装,最终发展 成为今天的 Internet。 我国 Internet 的发展 1987 年 9 月下旬,钱天白教授发出我国第一封电子邮件“越过长城, 通向世界” ,揭开了中国人使用 Internet 的序幕。 3、网络的分类: (1)按照地理范围分类 局域网 (Local Area Network, LAN) 覆盖范围一般不超过数十公里,通常是一幢建筑物内、相邻的几幢建筑 物之间或者是一个园区的网络。 广域网 (Wide Area Network, WAN) 覆盖范围通常为数百公里到数千公里,甚至数万公里,可以是一个地区 或一个国家,甚至世界几大洲或整个地球。 城域网 (Metropolitan Area Network, MAN) 覆盖的地理范围介于局域网和广域网之间,通常为数十公里到数百公里 的一座城市内。 (2)按照管理方式分类 对等网 (Peer to Peer) 通常是由很少几台计算机组成的工作组。对等网采用分散管理的方式, 网络中的每台计算机既作为客户机又可作为服务器来工作, 每个用户都管理 自己机器上的资源。 客户机/服务器网 (Client/Server) 网络的管理工作集中在运行特殊网络操作系统服务器软件的计算机上进
23

行,这台计算机被称为服务器,它可以验证用户名和密码的信息,处理客户 机的请求。 而网络中其余的计算机则不需要进行管理, 而是将请求通过转发 器(Redirector)发给服务器。 (3)按照数据传输方式分类 广播网络 (Broadcasting Network) 网络中的计算机或设备通过一条共享的通信介质进行数据传播,所有节 点都会收到任何节点发出的数据信息。这种传输方式主要应用于局域网中。 广播网络中有三种传输类型:单播、组播和广播。 点对点网络 (Point to Point Network) 网络中的计算机或设备通过单独的链路进行数据传输,并且两个节点间 都可能会有多条单独的链路。这种传播方式主要应用于广域网中。 4、网络拓扑结构:总线拓扑、星形拓扑、环形拓扑、网状拓扑、混合拓扑、 蜂窝拓扑

二、协议和参考模型
1、什么是协议: 协议是网络中计算机或设备之间进行通信的一系列规则的集合。 协议示例,以发送消息“HELLOSTUDENTS” 为例: 0 1 4 H E L L O S T U D E N T S 常用协议有:IP、TCP、HTTP、POP3、SMTP 2、分层结构的优点: 各层间相互独立,某一层的变化不会影响其他层 促进标准化工作 使网络易于实现和维护 3、分层结构的工作原理: 纵向通信 在分层结构中, 低层服务为高层服务提供服务, 高层服务使用低层服务 提供的服务。 横向通信 分层结构中,对应的分层协同工作,以保证能够成功的完成通信。 4、OSI 参考模型

24

具体 7 层 应用层 Application 表示层 Presentation 会话层 Session 传输层 Transport 网络层 Network 数据链路层 Data Link 物理层 Physical

数据格式

功能与连接方式 网络服务与使用者应 用程序间的一个接口 数据表示、数据安全、 数据压缩 建立、管理和终止会话

典型设备

数据组织成数据 段(Segment)

用一个寻址机制来标 识一个特定的应用程 序(端口号) 分 割 和 重 新 组 合 基于网络层地址 (IP 地 数据包(Packet) 址)进行不同网络系统 间的路径选择 将比特信息封装 通过使用接收系统的 成数据帧 (Frame) 硬 件 地 址 或 物 理 地 址 来寻址 传输比特(bit)流 建立、维护和取消物理 连接

路由器 网卡、网桥、 交换机 中继器和集线 器

5、TCP/IP 参考模型的各层: 第 1 层:网络接口层(Network Interface) 对应 OSI 物理层和数据链路层并实现与它们相同的功能,其中包括 LAN 和 WAN 的技术细节。这一层也称为主机到网络层(Host-to-Network)。 第 2 层:互联网络层(internet) 互联网络层的目的是运送数据包,将数据从任何在相连的网络上送 到目的地, 而不在乎走的是哪个路径或网络。 管理这层的特定协议称为互联 网络协议(IP)。最佳的路径选定和数据包交换都发生在这层。 第 3 层:传输层(Transport) 传输层负责处理有关服务质量等事项, 如可靠度、 流量控制和错误校正。 该层可以提供不同服务质量、 不同可靠性保证的传输服务, 并且协议发送端 和目标端的传输速度差异。这一层也称为主机到主机层(Host-to-Host)。 第 4 层:应用层(Application) 应用层包括会话层和表示层的功能,用来建立应用层来处理高层协议、 有关表达、编码和会话控制。TCP/IP 将所有应用程序相关的内容都归为一 层,并保证为下层适当的将数据封装成数据包。 6、协议栈 什么是协议栈: 在网络中,为了完成通信,必须使用多层上的多种协议。这些协议按照
25

层次顺序组合在一起, 构成了协议栈(Protocol Stack), 也称为协议族(Protocol Suite)。 常用的协议栈 :TCP/IP、IPX/SPX、AppleTalk TCP/IP 协议栈: 通常所说的协议并不是一个单独的协议,它往往是由多个协议组成的, 并且随着时代的发展而发展的。下面是 TCP/IP 协议栈主要包括的协议: OSI Name Server 5-7 File Transfer 4 3 ARP TCP RARP FDDI IP ATM NFS UDP ICMP X.25 3 2 HTTP 协议 SMTP FTP SNMP 4 TCP/IP

2

IEEE802.2(3,4,5,6) SLIP PPP

1

三、IP 地 址
1、什么是 IP 地址: IP 地址是 TCP/IP 网络中的主机(或称为节 点)的惟一地址。 IP 地址是网 络层的逻辑地址。 2、为什么要使用 IP 地址: 方便管理和使用,弥补了 MAC 地址的离散。 3、IP 地址的格式: IP 地址是一组 32 位长的二进制数字,用点分十进制表示。 4、IP 地址的组成: 网络地址+主机地址
26

地址 类型 A B C D E

引导 位 0 10 110 1110 1111

W 的范围 1-126 128-191 192-223 224-239 240-

地址结 可用网络地址 构 数 网 . 主 . 126(27-1-1) 主.主 网 . 网 . 16384(214) 主.主 网 . 网 . 2097152(221) 网.主 组播地址 研究和实验用地址

可用主机地址数
16777214(224-2) 65534(216-2) 254(28-2)

5、子网 子网(Subnet)是在 TCP/IP 网络上,用路由器连接的网段。 同一子网内的 IP 地址必须具有相同的网络地址。 6、子网掩码(Subnet Mask): 子网掩码用来确定 IP 地址中的网络地址部分。其格式与 IP 地址相同, 也是一组 32 位的二进制数。 子网掩码中为“1”的部分所对应是 IP 地址中的网络地址部分,为“0” 的部分所对应是 IP 地址中的主机地址部分。 举例 IP 地址:192.168.100.100 255.255.255.0 子网掩码 192.168.100.0 则网络地址为 缺省的子网掩码: A 类地址:255.0.0.0 (前 1 个 8 位组是网络地址) B 类地址:255.255.0.0 (前 2 个 8 位组是网络地址) C 类地址:255.255.255.0 (前 3 个 8 位组是网络地址) 7、专网 IP 和公网 IP: 专网 IP(供企业内部使用) 1 个 A 类地址:10.0.0.0/8 16 个 B 类地址:172.16.0.0/12 256 个 C 类地址:192.168.0.0/16 公网 IP(供 Internet 使用):要申请并付一定的费用才能使用或动态分配 8、IP 地址的分配原则: 只有 A、B、C 三类地址可以分配给计算机和网络设备; 网络地址的第一个数字不能为 127,保留用来测试连接; 网络地址不能全为 0,也不能全为 255:全为 0 没有网络,全为 255 用
27

作子网掩码 主机地址中不能全为 0,也不能全为 255:主机地址全为 0 用来表示网 络地址,全为 255 用作广播; 网络地址相同主机地址必须惟一 不 能 使 用 的 IP : 0.0.0.0 、 255.255.255.255 、 127.x.x.x 、 A.0.0.0 、 A.255.255.255、B.B.0.0、B.B.255.255、C.C.C.0、C.C.C.255。

四、Internet 接入方案
1、Internet 服务: 电子邮件 (SMTP 和 POP)、 Web 服务 (HTTP)、 新闻(NNTP)、 文件传输(FTP)、 远程终端(Telnet) 2、统一资源定位符:URL(Uniform Resource Locator) http://www.ntzx.net.cn/noiweb/noi.htm 使用的协议 (http://) 完整域名 (www.ntzx.net.cn) 服务器上的文件路径 (/noiweb/noi.htm) 3、接入方案: Modem 接入 ISDN 接入:综合业务数字网(Intergrated Servers Digital Network) ADSL 接入:铜质电话线缆,语音和数据一同传输

五、Linux 部分
1、 什么是 Linux ? Linux 是一个功能强大的操作系统, 同时它是一个自由软件, 是免费的、 源代码开放的。 编制它的目的是建立不受任何商品化软件权制约的、 全世界 都能自由使用的 Unix 兼容产品。 2、Linux 系统的组成: Linux 内核、Linux Shell、Linux 文件系统 Linux 实用工具。 内核,Shell 和文件系统一起形成了基本的操作系统结构。 3、Linux 文件系统 文件系统是文件存放在磁盘等存储设备上的组织方法, 主要体现在对文 件和目录的组织上。Linux 采用统一的树型结构的文件系统,在 Linux 文件 系统下可以切换目录、访问文件 设置目录和文件的权限、设置文件的共享等。 Linux 支持多种类型的文件系统。
28

4、学习 Linux 之前应该掌握的概念 (1)磁盘及分区 : 一块硬盘可以分为一个主分区和若干个扩展分区(逻辑分区) ,Linux 操作系统可以安装在任何地方,因此许多机器可以做成多个 windows 系统 及 Linux 多启动。 在 Liunx 下没有盘符的概念,不管是什么存储盘,在它里面都是一样对 待的,系统里只有从根目录往下一层层的目录,一个盘可以多个目录,一个 目录也可能会跨多个盘。 (2)理解 Linux 文件系统标准: /:根目录,系统中所有的目录都是从根目录开始。 /bin: 存放常用命令。 /boot: 引导核心的程序目录 /dev: 外部设备名 /etc: (etcetera)系统管理所要的配置文件和子目录 /home :存放用户主目录的地方, 一般是/home/用户名。 其他目录有 ftp、 httpd、 samba 等。 /lib: (library)系统基本的动态链接库 /lost+found /opt :optional(可以选择的) /proc: 虚拟系统,是由系统初起时内存中产生的 /root:超级用户默认的主目录; /sbin:系统管理员使用的系统管理程序; /tmp: 存放各程序执行时所产生的临时文件; /usr: 占空间最大的目录, 用户的很多应用程序和文件几乎全在这个目录中; /var:存放一些系统记录文件和配置文件; (3)掌握 Linux 下设备的使用方法 配置名称 /dev/had,/dev/hdb /dev/hdc,/dev/hdd /dev/sda,/dev/sdb /dev/scd0,/dev/scd1 说 明 IDE I 的 Master/Slave 硬盘/光盘 IDE II 的 Master/Slave 硬盘/光盘 第一,第二个 SCSI 硬盘 第一,第二个 SCSI 光驱

(4)理解 LILO 和 GRUB 的用途: LILO 全称为 LInux LOader GRUB 全称为 GRand Unified Boot loader 是位于硬盘引导扇区的一个小程序,是引导 Linux 系统内核的最常见的方
29

式; 可以用来引导多个操作系统;可以同时支持多个不同的系统内核映像; 为每个系统内核映像提供了密码保护; 支持位于不同磁盘和分区中的引导扇区、映象文件和启动映像; (5)普通用户与超级用户:$,# 普通用户可以在其权限许可的范围内使用系统资源, 而超级用户 (用户 名为 root)不仅可以使用系统中的所有资源而且可以管理系统资源。 (6)工作方式:字符工作方式和图形工作方式 5、Linux 的安装和初步使用 (1)安装 Linux 前的准备(了解) 了解 Linux 支持的硬件 光盘启动安装不需要任何准备 本地硬盘安装和网络安装需要制作启动盘: Boot.img 、 Bootnet.img 、 Pcmcia.img 制作安装启动盘:Dos:需要 Dosutils/rawrite.exe 和 image/boot.img Linux:dd if=boot.img of=/dev/fd0 bs=1440k 准备空闲的硬盘或分区 :使用 PQ Magic 或使用 fips (2)系统使用初步 普通用户和超级用户 登录与注销系统:登录系统( login) 、注销登录( logout 或 exit) 注:系统中任何用户均可使用 系统关机和重启的方法:关机( halt) 、重新启动( Reboot ) 注:只有超级用户可用 熟悉 Linux 的目录结构: 文件的类型:普通文件(文本文件、二进制文件、可执行程序、声音图像文 件) 目录文件 链接文件(硬链接、软链接) 特殊文件 设备文件(/dev/ttys1:标准终端 /dev/hda:第一块 IDE 硬盘) 管道文件 ls –l 时显示的文件类型: -:普通文件 d:目录文件 l:链接文件 b:块设备文件 c:字符设备文件
30

p:管道文件 使用 ls –l / 命令进行查看,了解目录结构: /usr /etc /dev /lib /home /var /bin /sbin 了解图形工作环境 学会获得系统帮助 6、Linux 常用命令 (1)命令规则、路径和文件 命令规则:命令动词 [参数] [操作对象] 路径:绝对路径、相对路径 文件:命名规则 文件通配符:* 匹配多个字符 ?匹配单个字符 [abc] 匹配 abc 中任意一个字符 [!abc] 匹配 abc 之外的任意一个字符 (2)文件目录操作命令 ls touch cp mv rm ln ls ----list 列文件或目录 用法:ls 参数: -a:显示所有文件,包括隐藏文件 -l:以长格式显示 -F:附加文件类别信息 -d:显示目录 -t:按修改时间先后显示 -R:显示目录及下级子目录结构 范例: ls –a ls –alR ls –F touch: 生成一个空文件或修改文件的时间 范例: touch * :将当前目录下所有文件时间修改为当前系统时间 touch –d 20010602 test:将文件 test 的时间修改为 20010602 touch test2:如果 abc 存在,则修改为当前系统时间,如果不存在,则生成 一个为当前时间的空文件 cp – copy file 用法:cp –afpx source target
31

-a:尽可能保持文件的结构和属性 -p:保持原始文件日期 -f :如果目标文件已经存在,则覆盖它 -i :提示是否覆盖现有的普通目标文件 -R:包含子目录 范例: cp ls.txt mydir1 cp –a mydir1 mydir2 cp /etc/syslog.conf ./ cp -a /etc/sound/ /home/so/ mv – move file 用法:mv –b source target -b:给被覆盖的文件建立一个备份 范例: mv abc bcd mv abc mydir/ rm – remove rm –irf 文件或目录 i:交互模式 r:删除目录及以下所有内容 f:强制删除 注意:Root 用户在删除文件时要特别小心、权限问题 cat more less head tail cat:输出文本文件内容(文本文件合并) 范例: cat tt.txt cat txta txtb > txt more:按页显示文件 范例:more tt.txt less:按页显示文件,可以使用翻页键 范例:less tt.txt head:显示文件的前?行 范例:head –20 /etc/passwd

mv

-b abc mydir/

32

tail:显示文件的后?行 范例:tail –20 /etc/passwd pwd cd mkdir rmdir cd – change directory 用法:cd [目录] 作用:切换路径 范例:cd .. cd / pwd – print work directory 用法:pwd 作用:显示当前工作目录 范例:配合 cd 创建和删除目录 mkdir 用法: mkdir 目录名 作用:创建目录新的目录 范例:mkdir abc rmdir 用法: rmdir 目录名 作用:删除空目录 范例:rmdir abc

tail +20 /etc/passwd

cd ../usr

find grep find 作用:查找文件或目录 用法:find 查找路径 匹配条件 动作 常用匹配条件 name ‘字符串’ lname ‘字符串’ user 用户名 group 组名 perm xxxx links n atime n mtime n grep 功能:在文件中查找匹配的字符串 格式:grep [参数] “待查字符串” 文件 例子: grep ‘abc’ myfile grep ‘abc’ *
33

grep -B 4 ‘abc’ * grep -2 ‘abc’ *.txt tar gzip compress 压缩与解压缩-常用压缩工具 gzip,gunzip .gz zip,unzip .zip tar .tar compress .Z bzip2 .bz2 sort paste sort:将文本文件排序 范例 sort passwd sort –n test :将 test 按照数字大小排序 sort test1 test2 test3:将文件 test1,test2,test3 的内容联合排序 paste:将不同文件合并 范例:paste test1 test2 > test3 (3)信息显示命令 dmesg 显示机器引导时内核显示的状态信息 file :测试文件类型 stat:显示文件访问、修改、变更时间、大小、属主和组以及许可模式等信 息 范例: stat abc.txt who w :查看其他登录的用户 who 和 w 使用范例 who who -wi w whoami:查看登录用户自己的信息 hostname:查看主机名 uname:显示系统信息 du:报告指定的文件(目录)已使用的磁盘空间的总量 df:报告文件系统磁盘空间的使用情况 free:查看当前内存和交换空间的使用情况

34

(4)用户通信与网络命令 write:向另外一个用户发信息。以 CTRL+D 作为结束 使用举例 : $ write webmaster wall:向所有用户广播信息。 格式:wall [message] [文件名] $ wall Happy new year! mesg:是否接受其它用户发来的信息 mesg [y|n] talk:适用于双向通信的工具 ,格式:talk 用户名 mail:字符界面下的 MUA 格式:mail [选项] [用户地址] 使用:阅读邮件 {mail ( h f )} 发送邮件 {mail username@domain} 删除邮件 {mail ( d u )} 保存邮件到文件 {mail ( s n filename)} 保存到 {mail ( s n+filename)} 将信的内容保存邮件到文件或文件夹(w) 从文件中读取邮件 {mail -f filename} 从文件夹中读取邮件 {mail -f +filename} 回复邮件 {mail ( r n)} ftp:客户端程序,常用子命令: open close asc bin dir/mdir ls pwd cd get/put mget/mput newer delete/mdelete mkdir/rmdir rename lcd !cmd system bye/quit help/? lynx:字符界面的浏览器 (5) 其他命令: clear:清屏 wc:文本文件中单词的计数(word count) date:显示和更改系统日期 cal:显示日历 su:切换登录用户 passwd:更改用户密码 help:用于查看 Linux 内置命令的帮助信息 man:列出指定命令的帮助手册 7、Shell 的高级使用
35

(1)重定向: 标准输入、输出:Study、 Stout、Stderr 输出重定向:> 、>> 错误输出重定向:2> 、&> 输入重定向:< 、<<!????! (2)管道:将一个命令的输出传送给令一个命令,作为另一个命令的输入 使用方法:命令 1|命令 2|命令 3??|命令 n 使用举例:$ ls –Rl /etc |more $ cat /etc/passwd | wc $ cat /etc/passwd | grep lrj $ ps –aux |tail +2 |more (3)命令替换 `cmd`或$(cmd) 例如:$wall `date` $cd `pwd` (4)命令执行顺序:命令间隔符说明 ; 用;间隔的各命令按顺序依次执行 && 前后命令的执行存在“逻辑与”关系,只有&&前面的命令执行成功 后,它后面的命令才被执行 || 前后命令的执行存在“逻辑或”关系,只有||前面的命令执行失败后, 它后面的命令才被执行 几个命令间隔符同时出现在同一个命令行上时,其优先级为: ;的优 先级最低 ||和&&具有相同的优先级 ,同优先级,按从左到右的结合原则 执行命令行 ,使用()可以组合命令行中的命令,改变执行顺序。 命令的多种执行顺序举例: $ date ;pwd 顺序执行 date 和 pwd 命令。 $ mail jjh < message && rm message 若文件 message 被 mail 发送出去,就把它删除,否则不删除。 $ write jjh < report || mail jjh < report 若对方拒绝对话,就将信息发送到他的信箱里。 $ date ; cat file |wc 只有 cat 命令的信息通过管道送给 wc 命令。 $ (date; cat file) |wc date 和 cat 命令的信息都通过管道送给 wc 命令。

36

8、磁盘和文件系统管理 (1)什么是文件系统? 文件系统是指存放在某个已格式化的存储介质上 (如: 软盘、 硬盘、 CDROM) 的、 能被操作系统管理的一组文件, 以及实施管理所需的一些数据结构的总 体。 Linux 的文件系统是树形结构的。 (2)磁盘分区(fdisk) fdisk 命令的子命令: m:显示帮助(命令清单) a:激活分区的可引导标志 l:列出可选的分区类型 n:添加新分区 d:删除已经存在的分区 p:显示分区表 t:改变分区的文件系统类型 w:写分区表 q:退出 (3)创建文件系统 # mkfs –t ext3 –c /dev/hda2 # mkfs –c /dev/hda2 -t:指定文件系统类型 -c:建立文件系统前先检测有无坏块 # mkfs –t ext2 –c /dev/sda1 # mkfs –t vfat –c /dev/hdb2 (4)挂装和卸装文件系统 # mount –t ext3 /dev/sdb1 /opt # mount –t vfat /dev/hda6 /mnt/win # mount /mnt/cdrom # mount /mnt/floppy # mount 注意:挂装目录必须存在 Linux 专门提供了挂装目录/mnt 不要在挂装目录下进行挂装操作 将软盘或光盘放入驱动器后在实施挂装操作 卸载前不要取出软盘或光盘 不能在同一个目录下挂装两个文件系统
37

# umount /mnt/cdrom # umount /mnt/floppy # umount /dev/hda6 # umount /dev/sdb1 # umount /opt 注意:不能在挂装目录下进行卸载操作 (5)文件系统管理的常用命令 df: 显示文件系统的统计数据 du: 显示硬盘使用情况 ln: 创建链接文件 find :查找文件 dd: 文件拷贝(diskdump) ,将指定的输入文件拷贝到输出文件上去 几个参数 if:输入文件 of:输出文件 bs:块字节大小 count: 块数

[练习]:
1.将下列十进制数转为二进制数、八进制数和十六进制数 123(10)=____________(2)=_______(8)=______(16) 768(10)=____________(2)=_______(8)=______(16) 45 (10)=____________(2)=_______(8)=______(16) 513(10)=____________(2)=_______(8)=______(16) 12.125(10)=____________(2)=_______(8)=______(16) 2.TURBO-PASCAL 系统中整型变量(数)用两个字节来存储,那么整型变量 (数)可以表示的最大数是多少?最小数是多少?长整型变量(数)用 4 个字节来存储,那么长整型可以表示的范围是多少? 提示:正数或 0 用原码表示,负数则是用补码表示,第一位为符号位(也就 是说为 0 或为 1 分别表示正数或负数) ,其它都是具体的数字。 3.某张 CDROM 盘的容量为 670MB,那么它可以存放多少个基本字符? 如果一本书约 20 万个基本字符,那么一张盘可以存放多少本这样的书 (全为基本字符的书)? 现在有许多人喜欢将买回来的书扫描后保存在电脑里。如果扫描一本 书,每页纸扫描后成一个文件,该文件节约方式存储大约要 10KB,那么一
38

本 400 页的书要多大的存储空间?700MB 的 CDROM 大概可以存储这样的书多 少本? 学校图书馆有藏书 20 万本 (平均每本 400 页) , 如果请你来帮助扫描保 存,你先计算一下,大概要多大的存储空间?如果再刻录到光盘上,刻一份 大约要多少张光盘(假设每张 700MB)? 4.TURBO-PASCAL 系统用 64KB 来存放变量,那么它最多可以定义多少个整 型变量? 5.选择题(每题有且只有一个正确答案) (1) 下列两组命令前者为 ms-dos 命令,后者为 linux 命令,两者作用基 本不相同的一组是: a、dir ls b、md mkdir c、type ps d、copy cp (2) 某子网中有一主机地址为 192.168.100.10, 则该子网的网络地址可能为: a、192.0.0.1 b、192.168.10.0 c、198.168.100.1 d、192.168.100.0 (3)网络中常说的 URL 代表的是: a、Universal Resource Locator b、Uniform Repository Link c、Uniform Referral Location d、Uniform Resource Locator (4)IP4 中 B 类 IP 地址可标识的网络数量是: a、214 b、215 c、216

d、221

[分析与解答]:
1. 进制转换 (1) 123(10)=111101(2)=173(8)=7B(16) (2) 768(10)=1100000000(2)=1400(8)=300(16) (3) 45(10)=101101(2)=55(8)=2D(16) (4) 513(10)=1000000001(2)=1001(8)=201(16) (5) 12.125(10)=1100.001(2)=14.1(8)=C.2(16) 2. 整型数最大为 32767(2 -1) ,最小数为-32768(-2 ) ; 31 31 长整型数最大为 2147483647(2 -1) ,最小数为-2147483648(-2 ) 。
39
15 15

3. 基本字符存储时占用一个字节, 而 670MB=670*1024*1024B=702545920B, 所以一张光盘可以存储 702545920 个基本字符。 因 702545920/200000 整数部分为:3512,所以一张光盘大约可存储 这样的书 3512 本。 扫描的一本书存储约需的空间为:10KB*400=4000KB,而 700MB 的光 盘存储空间为 700*1024KB,所以可存储这样的书为:700*1024/4000,约等 于 179 本。 4. 一个整型变量占用两个字节,所以 64KB 可以存储的整型变量个数为: 1024*64/2=32768。 5. 选择题 (1) 选 C,因为 A 组为显示文件目录,B 组为建目录,D 组为复制文件, 而 C 组中 type 命令在 DOS 中为显示文件内容, ps 在 Linux 里为显示进程号。 (2)选 D,因为网络地址的主机地址部分全为 0,去除 A 和 C,而一个网段 内的 IP 地址具有相同的网络地址,B 选的地址的第三部分为 10,排除 B。 (3)Uniform Resource Locator ,在 Internet 的 WWW 服务程序上用于指定 信息位置的表示方法,所以选择 D。 (4)选择 A,因为 B 类地址一般用前 16 位二进制来表示网络地址,而前 两位固定为 10,所以网络地址的数量最多为 2 的 14 次方。

40

第三章 算法及其描述
一、程序与算法
计算机程序是指能使计算机完成特定任务并且计算机能够执行的指令 的有序集合。一般所说的程序都是指计算机程序。 算法是解决问题的步骤和方法, 我们所说的算法特指用计算机解决问题 的方法。 例 3-1 如何确定一个正整数是否是质数。 [分析]: 质数也叫素数,其定义是:除了 1 和它本身外,不能被其它正整数整除 的且大小 1 的整数。在后面的许多程序中都要用到判定是否是质数的算法。 判定的方法也比较多,这里我们直接从它定义出发,得出一种算法。 [算法]: (1) 输入一个正整数 A(告诉计算机要判定哪个数) ; (2) B=2; (3) 当 A 不能被 B 整除时将 B 的值增加 1; (4) 如果 B=A(说明 2 到 N-1 都不能整除 A) ,则 A 是质数,否则不是。 [程序描述]: 使用 Turbo-Pascal 写出上面算法的程序如下 program eg3_1; var a,b:integer; begin readln(a); b:=2; while a mod b>0 do b:=b+1; if b=a then writeln('Yes!') else writeln('No!'); end.

二、程序的优点(为什么要用程序来解决问题)
计算机程序执行起来速度快、准确,减少了复杂的人工运算。更大的优 点是通用性,可以解决一类问题,如上面的判定一个数是否是质数,程序对 于所有的自然数都适用(当然是在程序所允许的数据范围之内的自然数) 。 当然并不是所有的问题都可以通过程序来解决的, 如 “如何实现世界和 平”之类的问题就不是通过计算机就可以实现的。 总之,通过程序可以充分发挥计算机高速、准确的优点,通过计算机来
41

解决一类相关问题。

三、算法的三种结构
1. 顺序结构: 自上而下一步步地执行,不重复也不少一步; 2. 分支结构: 根据条件的是否成立选择不同的分支去执行, 有可能是单个分支或多个 分支。单个分支的情况如“如果成绩大于等于 90 则为优秀” 。两个分支的情 况如“如果成绩大于等 60 则为合格否则为不合格” 。多个分支的情况如“成 绩在 90-100 间的为优秀, 80-90 为良好, 70-80 为一般, 60-70 为及格??” 。 3. 循环结构: 某一程序段要连续重复执行若干次, 从而构成循环。 有效的循环一般有 “当型循环”和“直到型循环” ,许多程序设计语言还有“计数循环” ,一般 用在事先知道循环次数的情况下使用。

四、算法的三种描述方法
1.自然语言描述 主要是通过文字或数学式子来进行描述解决问题的过程,第一步做什 么,第二步做什么?? 2.流程图描述 主要有两种模式,框图和结构化流程图(N-S 图) 。 (1)框图

A 满足 条件 不满足

B

A

B

图 3-1 图 3-2

42

A 满足 条件

A 不满足 条件

不满足 图 3-3

满足 图 3-4

图 3-3 表示的结构称为“当型”循环。当给定的条件满足时执行 A 块, 否则不执行 A 块而直接跳到下面部分执行。 图 3-4 表示的结构称为 “直到型” 循环, 它的含义是:执行 A 块直到满足给定的条件为止(满足了条件就不再执 行 A 块)。 这两种循环的区别是:当型循环是先判断(条件)再执行, 而直到型 循环是先执行后判断。 以上三种基本结构可以派生出其它形式的结构。 由这三种基本结构所构 成的算法可以处理任何复杂的问题。 所谓结构化程序就是由这三种基本结构 所组成的程序。 可以看到,三种基本结构都具有以下特点: ① 有一个入口。 ② 有一个出口。 ③ 结构中每一部分都应当有被执行到的机会,也就是说,每一部分都 应当有一条从入口到出口的路径通过它(至少通过一次)。 ④ 没有死循环(无终止的循环)。 结构化程序要求每一基本结构具有单入口和单出口的性质是十分重要 的, 这是为了便于保证和验证程序的正确性。 设计程序时一个结构一个结构 地顺序写下来,整个程序结构如同一串珠子一样顺序清楚,层次分明。在需 要修改程序时, 可以将某一基本结构单独孤立出来进行修改, 由于单入口单 出口的性质,不致影响到其它的基本结构。 (2) 结构化流程图(N-S 图) 在结构化程序设计中,使用一种“结构化流程图” ,所谓流程图是用图 形来表示程序设计的方法, 它采用一些几何图形来代表各种性质的操作, 是 程序设计中广泛使用的一种辅助设计手段。 结构化流程图是美国 I.Nassi 和 B.Schneiderman 两人在 1973 年提出的方法的基础上形成的, 因此也称为 N-S 结构化流程图,它的基本成分有以下三种:

43

(1) 一条简单的指令,用一个矩形框来表示,见图 3-5 (在框内写一条简单的指令) 图 3-5 顺序结构可以表示如图 3-6 执行 A 块 执行 B 块 图 3-6 如交换两个变量的值的过程就是顺序结构。见图 3-7 输入 X,Y X Y → Z → X

Z → Y 输出 X,Y 图 3-7 交换变量 (2)判断选择结构用图 3-8 形式的框图表示: 满足条 满足 执行 A 块 图 3-8 (3)循环结构用图 3-10 和图 3-11 形式的框图表示。 图 3-10 表示的是当型循 环,图 3-11 表示的是直到型循环。 当条件满足 执行循环中的指令 图 3-10 件否? 不满足 执行 B 块

执行循环中的指令 直到条件满足 图 3-11

44

3、程序描述 如果一个算法如果交给计算机去执行, 最终是要通过程序来描述。 选择 不同的语言,基于相同的算法,程序描述也不相同,但基本上差不多,虽然 不同的计算机语言有不同的语法规则, 但是因为算法一样, 条件与赋值等描 述也是大同小异。 无论程序多么复杂, 无非是由三种基本结构组成的, 整个程序看起来是 一个顺序的结果, 中间可能有分支或循环 (有的是递归, 后面专门介绍递归, 它也可以看成是一种循环) 。

五、算法的多样性
同一个问题可能会有不同的解决方法, 也就是说可能有不同的算法, 就 如同“一题多解”一样。有的算法效率高一些,有的算法效率低一些,有的 算法好理解一些, 有的算法难理解些。 评价算法的好坏也有几种不同的标准, 大家可以阅读相关材料来加深理解算法的评估。 正是因为算法的多样性, 才 有了各种类型的基本算法, 我们今后学习的主要内容就是在掌握了基本编程 工具的基础上学习一些基本算法及其应用。 例 3-2 求若干个数中的最大数。 [分析]: 要求出若干个数中的最大数, 可以先假设某一个数最大, 其它的数依次 跟它进行比较, 从而找出最大数; 也可以两两比较, 去掉小的, 再两两比较, 去掉小的,直到剩下一个数为止;或者先第一个跟第二个比,将大的放到第 二个, 再将第二个跟第三个比, 将大的放到第三个??最后两个数进行比较, 将大的放到最后一个,最后一个数就是最大数。 [方法 1]: “擂台比武”法 基本思路:设置“擂台” ,在程序中用一个变量来存储最大的数,先假 设最大数就是第一个数, 然后从第二个数到最后一个数重复做: 如果这个数 比当前的最大数还要大,就取而代之,留在“擂台” 。最后“擂台”上的数 就是最大数。 自然语言描述: (1) 输入数字的个数 N; (2) 输入 N 个数字; (3) 假设最大数 MAX 为第一个数; (4) 从第二个数到第 N 个数重复做: 如果这个数比 MAX 大,那么 MAX 等于这个数 (5) 输出最大数 MAX。

45

N-S 图描述:

输入 n,读入 n 个数放进 a[1],a[2]到 a[n]里 Max:=a[1];I:=1; I:=I+1 a[I]>max? yes Max:=a[I] 直到 I=N 输出 Max [方法 2]:比较相邻两数,大者后移 自然语言描述: (1) 输入 n 和 n 个数; (2) I 从第 1 个数到第 N-1 个数重复做 如果第 I 个数比第 I+1 个数大那么交换这两个数的位置 (3) 输出最后一个数(最大数) N-S 图描述: no

输入 n,读入 n 个数放进 a[1],a[2]到 a[n]里 I:=0; I:=I+1 a[I]>a[I+1]? yes 交换 a[I],a[I+1] 直到 I=N-1 输出 a[n] [思考与提高]: no

46

上面这两种方法都适合用循环来解决, 排序也正是基于这样的思想重复 找指定的数中的最大数或最小数。 但是当数据量比较大时, 比较的次数相对 较多,可以采用“分而治之”的思想,算法上叫“分治法” 。如要求 100 个 当中的最大数, 先分别找出前 50 个中的最大数和后 50 个当中的最大数, 再 比较这两个最大数,取其中大的。50 个数当中如何找出最大的数呢?再将 它分为找前 25 个和后 25 个数,??,直到剩下一个数。由此得到第三种算 法。 [算法 3]:分治法 自然语言描述: (1) 定义一个找最大数的函数 maxnum(left,right); 如果 left=right 那么最大数 maxnum 就是当前数 否则 middle=(left+right)/2; 最大数 maxnum 等于 maxnum(left,middle), maxnum(middle+1,right)中较大的数。 (2) 输入 N 和 N 个数; (3) 调用函数 maxnum(1,N)计算并输出 1 到 N 个数中最大的数。 程序描述: program example3_2_3; var n,i:integer; a:array[1..10000] of integer; function maxnum(left,right:integer):integer; var middle,m1,m2:integer; begin if left=right then maxnum:=a[left] else begin middle:=(left+right) div 2; m1:=maxnum(left,middle); m2:=maxnum(middle+1,right); if m1>m2 then maxnum:=m1 else maxnum:=m2; end end; begin readln(n); for i:=1 to n do read(a[i]); writeln('max=',maxnum(1,n));
47

end. [思考与提高]: 也可以针对第二种算法用分治的思想来设计算法,如共有 100 个数, 先将第 1 个数和第 51 个数比,大者放第 1 个;将第 2 个数和第 52 个数比, 大者放第 2 个;??第 50 个数和第 100 个数比,大者放第 50 个。这样做下 来最大数肯定在前面 50 个数里。 再在 50 个数中重复上过程, 得到最大数在 前 25 个里??在前面 13 个里、在前面 7 个里、在前面 4 个里、在前面 2 个里,在第一个里。

[练习]:
写出解决下列问题的算法(用自然语言和流程图描述) : 1. 求两个自然数 M、N 的最大公约数。 2. 如果银行的存款年利率为 2%, 那么存入一定量的钱在银行多少年后本息 才能翻倍? 3. “筛选法”求一定范围内的质数是一种高效的方法,其基本方法是先将 1 排除在外,从 2 开始,将其后的所有的 2 的倍数“筛去” ;再到下一个 没有被“筛去”的数,将其后所有的倍数“筛去”??直到某个数结束, 合理选择这个结束的数可以减少“筛选”的次数。最后没有被“筛去” 的数就是质数。 [提示]: 检测 N 是否是质数,可以从 2 检测到 N-1,这是检测最多的。也可以检 测到 N 的一半,还可继续缩小,只要检测到 N 的算法平方根。 “筛选法”每 次都是用质数来检测, 因此最后只要检测到不大于 N 的算术平方根的质数就 行了。 4. 求和:S=1+1/2+1/3+??1/10000

[习题分析与讲解]:
1.求最大公约数 [算法 1] 从大到小依次检测 基本思路:i 从一个数开始,当 I 不能同时整除两个数时,将它的值减
48

1,因此循环束时 I 能同时整除两个数且是最大的,说明它就是两个数的最 大公约数。 自然语言描述: (1) 输入两个正整数 m,n(假设 m<=n,如果不是交换一下即可); (2) I 初值为 m; (3) 当 I 不能同时整除 M 和 N 时将 I 的值减少 1; (4) 输出最大公约数 I。 N-S 图描述: 输入 m,n i:=m 当 (m mod I>0) 或(n mod i>0)时 I:=I-1 输出 I [思考与提高]: 这种算法的原理比较简单, 但是检验的次数可能比较多, 如当两个数的 最大公约数为 1 时,需要检测的次数为 M。可以从数学的角度来思考,如果 I 是 M、N 的最大公约数,且设 M<=N,那么 M、N-M 的最大公约数的最大公约 数也是 I,如果 N-M=0,说明最大公约数就是 M,否则取 M 为原来 M、N-M 中 较小的一个,N 取 M、N-M 中较大的一个,重复上述过程。以 M=36,N=78 为 例,运算过程如下: 78-36=42; 42-36=6; 36-6=30; 30-6=24; 24-6=18; 18-6=12; 12-6=6 6-6=0; 所以最大公约数就是 6,从而得到第二种算法,这种方法运算 和比较了 8 次,比起从 36 开始往下检测要检测 31 次省得多。 [算法 2]:反复取大的减小的,直到两者相等
49

自然语言描述: (1) 输入 M、N(假设 M<=N) ; (2) 重复做以下内容: I 等于 N-M; M 取原来 M、I 中较小者; N 取原来 M、I 中较大者。 直到 M=N (3) 输出最大公约数 M(或 N,因为此时 M=N) 。 N-S 图描述: 输入 m,n I:=n-m M 取 M,I 中较大者 N 取 M、I 中较小者 直到 M=N 输出 M [思考与提高]: 相减时可以不考虑中间过程 M、N 的大小,可以用如下的方法来做: (1) R=M;当 M>=N 则反复做 R=M-N; (2) M=N; N=R (3) 如果 N>0 再从(1)开始做。 同样以 M=36、N=78 为例: 第一次做(1) 、 (2)步骤相当于交换 M、N 的值,M=78,N=36; 第二次做(1) 、 (2)步骤后的结果为:M=36,N=6 第三次做(1) 、 (2)步骤后的结果为:M=6,N=0 由此得到最大公约数为 6。 大家都知道, 除法是减法的重复运算, 反复相减求差的过程相当于 求余数的过程, 所以我们可以用求余法求两个数的最大公约数, 由此得 到第三种算法。 [算法 3] 辗展相除求余数,直到余数为 0 自然语言描述:
50

(1) 输入两个正整数 M,N; (2) 重复做以下步骤:R=M MOD N;M=N;N=R; 直到 R=0; (3) 输出最大公约数 M。 N-S 图描述 输入 m,n R:=M MOD N M:=N; N:=R; 直到 R=0 输出 M [思考与提高]: 如果不用直到型循环,用当型循环,先判断再执行,因为在判断之前要 先求余数,所以循环体中要先调整 M、N,再继续求数,而且最后输出余数 时不是 M,而是 N,思考一下这是为什么,如果仍然是 M,结果又如何? N-S 图如下: 输入 m,n R:=m mod n 当 R>0 时重复做 M:=n; n:=r; r:=m mod n 输出 n

2、利息计算 基本思路:不管存入银行多少钱,其利率是一样的,所以可以将原存入 的钱数设为 1,然后一年一年地计算(就是所谓的“利滚利” ) ,如第一年后 为 1.02,第二年后为 1.02*1.02,??,直到乘积大于或等于 2 时结束。 自然语言描述:
51

(1) 初始化,钱数 a 为 1;年数 b 为 0; (2) 重复做以下内容:a=a*1.02;b=b+1; 直到 a>=2; (3) 输出年数 b。 N-S 图描述: a:=1;b:=0 a:=a*1.02; b:=b+1 直到 a>=2 输出 b

[思考与提高]: 上面是通过“直到型循环”来实现的,也可以通过“当型循环”来做, 只不过条件跟上述结束的条件相反, 因为一个是描述结束的条件、 一个是描 述执行的条件。 大部分循环都是如此, 有些可通还要调整循环体中某些执行 的顺序,在今后的程序设计过程中经常会碰到类似的问题。 “当型循环”N-S 图描述如下: a:=1;b:=0; 当 a<2 时 a:=a*1.02; b:=b+1; 输出 b 3、 “筛选法”求质数 自然语言描述: (1) 输入 N; (2) 先假设 2 到 N 都是质数; (3) I 从 2 到 N 的算术平方根重复做 如果 I 是质数,那么 J 从 2 到 N/J 重复做:将 I*J 置为合数; (4) 输出 2 到 N 间所有的质数。

52

N-S 图描述: 输入 n,将 a[2]]到 a[n]置为 0(表示是质数) I 从 2 到 N 的算法平方根做 a[I]=0? Yes J 从 2 到 N DIV I 做 A[I*j]:=1; I 从 2 到 N 重复做 A[I]=0? Yes 输出 I 4、求分数和 自然语言描述: (1) 和 S 为 1,分母 I 为 1; (2) 当 I<10000 时重复做:I 的值增加 1,S 的值增加 1/I; (3) 输出 S。 N-S 图描述: S:=1;i:=1; 当 i<10000 时重复做 i:=i+1; s:=s+1/I; 输出 s [思考与提高]: 上面的算法描述中,S 和 I 的初值都是 1,而重复做的是内容是先将 I 的值增加 1,然后再将 S 的值增加 1/I。如果重复做的内容是先将 S 的值增 加 1/I,然后再将 I 的值增加 1,那么 S 的初值要为 0,重复做的条件是 I<10001。 NO no

53

第四章

使用 TURBO-PASCAL7.0 系统

一、进入 TURBO-PASCAL7.0 系统
双击桌面 PASCAL 系统的快捷方式(如 TPX 等) ,或从其它方式进入(如 从“我的电脑”里找出相应程序所在的位置然后进入) 。 例 4_1 在 Turbo Pascal 编辑系统下输入下面的程序(9-9 乘法表) : program example4_1; var i,j:integer; begin for i:=1 to 9 do begin for j:=1 to i do write(i*j:4); writeln; end; readln end. 输入正确后保存,文件名为 eg4_1.pas,保存时扩展名可以不加,系统 会自动添加 pas 扩展名,不正确进行相应编辑直到正确。 基本的编辑键介绍: 上下左右箭头:移动光标 Home 光标移到行头 End 光标移到行尾 PageUp 上一页 PageDown 下一页 Insert 插入/改写状态切换 Delete 删除当前字符 Backspace 删除前一字符 Ctrl + PageUp 移到文件头 Ctrl + PageDown 移到文件尾 Ctrl + Y 删除当前行 要求熟悉菜单:File,Edit,Run 等项目。选取菜单可以用鼠标直接点 也可以按 F10 键,再用上下左右键移动到相关项目。 运行程序(run)——点击菜单项目或 Ctrl+F9 。 编译程序(compile)——点击菜单项目或 Alt+F9 。
54

一般的 TP 系统可以设置成运行程序的同时先编译成可执行文件。 退出系统后运行刚才编译好的程序, 注意刚才保存的位置, 到相应文件 夹里找 eg4.exe 文件,这个文件可以直接执行。

二、系统简介
目前使用得比较多的 PASCAL 系统主要有三种:Turbo Pascal、Borland Pascal、Free Pascal,前两种基本上没有大的差别,这里主要是介绍前两种 的使用,有关安装程序可以从网上下载,然后进行安装。安装完后,相应目 录里(如\TP\BIN)里会有两个执行主文件:Turbo.exe、tpx .exe ,其中后 者只能在 windows 下执行,但是两者的编辑界面、菜单等几乎是相同的。 一般进入系统后,屏幕上方是菜单栏,中间的编辑栏(用户的程序在 此显示、编辑) ,最下面是常用的功能快捷键提示: F1:help F2:Save F3:open Alt + F9:compile F9:make Alt+F10:local menu 相关功能都可以在菜单里找到,菜单分为这样几类: File Edit Search Run Compile Debug Tools Options Window Help, 下面分别介绍几个常用的菜 单项目。 1.File 文件操作类 New :新建,在新的编辑窗口中新建一个文件 Open F3 :打开,查找并找开一个文件 Save: 存盘,保存当前活动编辑窗口的文件 Save as: 另存为,将当前文件换名或换路径保存 Save all:保存所有,保存所有修改过的文件 Change dir…:改变默认目录 Dos shell:暂时退回到 DOS 命令状态,键入 exit 再返回 Exit Alt + X : 退出系统 2.Edit 编辑类 Undo Alt+ Backspace :撤销,撤销最近的编辑操作 Redo :恢复,恢复刚撤销的操作 Cut Shift + Del :剪切 Copy Ctrl + Ins :复制 Paste Shift +Ins :粘贴 Clear Ctrl + Del :清除 Show clipboard :显示剪贴板内容 3.Search 查找类
55

Find… 查找 Replace… 替换 Search again 再次查找(替换) 4.Run 运行类 Run Ctrl + F9 :运行,执行当前编辑的文件 Step over F8 :不跟踪过程的单步调试 Trace into F7 :跟踪,单步调试(一行一行地执行) Goto cursor F4 :执行调试到光标处 Program reset Ctrl + F2 :取消当前调试并初始化调试器 5.Compile 编译类 compile Alt + F9 :编译,将 pas 源程序编译成可执行文件 exe Make F9 :只编译更新的源文件 Build:全部编译主文件及调用的所有单元 6.Debug 调试类 Watch 打开“观察”窗口,常用来观察相关变量或表达式运行状态下的值 Output 打开“输出”窗口,与编辑窗口在同一屏幕下看输出情况 User screen Alt + F5 切换到用户运行全屏幕状态,按任意键返回 Add watch… Ctrl + F7 增加“观察”表达式 7.Tools 工具类 Go to next Alt + F8 到下一个位置 Go to previous Alt + F7 到前一个位置 8.Options 选项类 这一类菜单是让用户进行相关设置, 包括: Compiler… 、 Memory sizes….、 Directories…、 Browser… 、 Environment 等 9.Windows 窗口类 Close all 关闭所有窗口 Size/Move Ctrl + F5 调整窗口尺寸/移动窗口 Zoom F5 放大(最大化)或还原当前活动窗口 Next F6 到下一窗口 Previous Shift + F6 到前一窗口 Close Alt + F3 关闭当前窗口 List… Alt + O 窗口列表
56

10. Help 帮助类 Index Shift + F1 索引 Topic search Ctrl + F1 主题查找 Prevopis topic Alt + F1 到上一次帮助主题窗口

三.PASCAL 程序介绍
例 4-1 要求输入的程序就是一个完整的 PASCAL 程序,它是由程序头、 说明部分和程序体三部分组成。 程序头:program 部分,表明程序的名字(跟文件名不是一回事) ,没 有太大的实际意义, 往往只是表明程序的主要作用, 一般跟注释部分结合使 用, 说明此程序做什么的, 用了什么主要算法等, 一个程序可以没有程序头。 说明部分:说明程序中用到的常量、变量、过程或函数等。在 pascal 程序中用的量必须先说明后使用,如常量的说明通过 const,变量的说明通 过 var,常见的变量类型有 integer(整数),real(实数),char(字符、1 个字 符),string(字符串,一般要指明长度),boolean(布尔型,值为真 ture 或假 false)等。标准 PASCAL 程序说明部分可以有标号说明、常量说明、自定 义类型说明(包括枚举、子界等) 、变量说明、过程或函数说明,说明符分 别是:Lable、const、type、var、procedure 或 function,如果程序中有多种 说明,要注意说明的顺序,一般是 label?const?type?var?procedure 或 function。这个顺序有它的原因的,在以后的使用中会体会到的。 程序体:begin 和 end. 部分的内容,程序中每一个语句与语句之间通过 分号来间隔。 一个最简单的程序必须由 begin 开始、end . 结束,中间可以什么都没 有, 也能执行, 只不过没有什么结果, 因为其中没有什么要计算机做的语句。

四、turbo-pascal 处理的对象
1、常数 就是系统不通过运算就能知道结果的值,它可以是数值型如 123、5E+6 等,也可以是字符型的如’hello!’,等等。 其中上面的 5E+6 类似于数学上的科学计数法,表示 5*106。 2、 常量与变量 常量和变量都是通过名字来相互区别的。 常量是值不变的量, 它通过一个名字来标识, 通常是程序中常用到的一 些量,它的值不变,一般在程序中要多次使用到,从名字上就可以知道它的 含义, 如果要改变这个值只要在说明部分改动就行了, 不必在程序中一个一 个地去改。
57

变量就是值可以变化的量,一个没有变量的程序是没有太大意义的, 正因为程序中使用了变量,才可以记录数据的变化、进行相关处理,否则再 高档的计算机也只是一个低级的计算器 (因为现在稍好一点的计算器也有编 程使用变量的功能) 。 常量和变量的名字都是有一定的规则的,首先要保证唯一性,可以简 单地用一些字母(不区分大小写) ,也可以是一些单词或拼音字母表示特定 的含义,增加可读性,但是中间不能有空格。 常量的说明如: Const p=3.1415926; {其实系统内部有一个常量 pi,可以不要定义} Xm=’Nantong Middle School’; 变量的说明如: Var name: string[8]; a, b, c: integer; x, y, z: real; 这里的 const、var 都是系统的保留字,分别用来说明常量、变量。在程 序的说明部分,常量的说明顺序往往先于变量的说明。因为常量先说明了, 在后面的其它部分的说明中就可以用到它。如: const max=100; {定义一个常量 max,表示最大值,它的值固定为 100} var a,b:0..max; {变量 a 和 b 的值只能在 0 到 max 之间,max 的值已在常量 中说明, 如果没有先说明这个常量, 系统编译时会出错} ?? 3、 内部函数与内部过程 系统已定义好了可以直接使用的函数或过程, 通过名字来引用, 大部分 有参数,如 int(x)—求 X 的整数部分。我们使用的一般语句也都可以看作是 turbo-pascal 的内部过程。函数与过程的主要区别是前者都有返回值,而后 者却不一定, 它执行相应的处理, 过程可以象语句一样使用, 而函数却不行, 只能出现在表达式中。 4、 保留字与标准标识符 系统定义好的字符组合,有一定的含义,一般来说用户不能再使用了, 以免产生二义性。 对于用户来说,哪些字符组合不能再用呢?进入 TP 系统后你会发现, 输入的程序中有些字符的颜色会自动变成白色, 有些是黄色??凡是白色的 都是系统定义好的、不能另外拿来作为常量、变量、函数、过程等的名字, 它们称为保留字。 而黄色的当中,有一部分是用户自己定义的,也有是系统定义的(如 read、write、writeln 等) ,它们是可以让用户来重新定义的,不过一般不要
58

这样使用。 因此一般所说的保留字就是在编辑窗口能够自动变成白色的字符 串, 而其它的一些系统定义的语句等可以看作是系统的过程或函数, 称为标 准标识符。 系统的保留字主要有: and array begin case const div do downto else end file for function goto if in label mod nil not of or packed procedure program record repeat set then to type until var while with 系统预定义的标识符(标准标识符)主要有: 标准常量:false maxint true 标准类型:boolean char integer real text 标准文件:input output 标准函数:abs arctan chr cos eof eoln exp ln odd ord pred round sin sqr sqrt succ trunc 标准过程:dispose get new pack page put read readln rest rewrite unpack write writeln 系统预定义的标识符用户还是可以重新定义的, 但不提倡这样使用, 下 面是一个重新定义 write 的示例: program example4_2; {redefine procedure write} procedure write(x:integer); begin writeln(x); end; begin write(5); write(6); end. 程序中将 write 定义成与 writeln 类似的功能,只不过,它只能输出整型 数,其它类型的它不能输出。如果不重新定义,也就是说没有 procedure 这 个过程说明部分,主程序中 write(5);write(6)运行输出的结果是:56,而有了 重新的定义后,将输出两行,第一行是 5、第二行是 6。 5、表达式 程序在进行处理时要用到各种各样的式子, 称为表达式。 所谓表达式就 是通过括号() 、运算符将一些量连在一起形成的式子。这些量可以是各种 类型的,可以是常量、变量、常数、函数等。 表达式有好几种类型,不同类型的表达式有自己的运算符号。
59

(1) 算术表达式 通过算术运算符+,-,*,/, div,mod 进行运算。 6 种算术运算符的说明表 运算符 操作数类型 Integer, real +(加) Integer, real - (减) Integer, real * (乘) Integer, real / (实数除) Integer div (整数除) Integer Mod (求余)

运算结果类型 Integer, real Integer, real Integer, real Real Integer Integer

如: 2*2 (操作数 2 和 2 都是整型,结果为整型数=4) 2*3.1 (操作数有一个是实型数,所以结果为实型数=6.2) 4/2 (运算符为实数除,结果为实型数,即使能够整除结果仍为实型数) 6.0/2.0 (结果为实型数 3.0) 15 div 5 (整除结果为 3) 16 div 3 (整除结果为 5) -21 div 2 (整除结果为-10) 21.0 div 3 是一个错误的表达式,因为 21.0 是一个实型数不能进行整除运算 15 mod 3 (求余结果为 0) 16 mod 3 (求余结果为 1) -21 mod 2 (求余结果为-1) 算术运算符的运算次序: 括号> 函数 > * / div mod > + 下面是结合变量、函数、括号等有关算术表达式的示例: (a+b)/(a-b) (-b+sqrt(b*b-4*a*c))/(2*a) 2*pi*r pi*r*r (2) 、字符表达式 有关字符(串)操作的表达式,运算符有“+” (相连运算)等。 如:’nan’+’tong’ 结果为 ‘nantong’ ‘yue’+’king’结果为’yueking’
60

(3) 、关系表达式与逻辑表达式 描述大小、 相等或不等关系的表达式称为关系表达式, 对关系表达式再 进行与或非运算的称为逻辑表达式。运算符主要有 =,>,<,>=,<=,<>,and, or, not 等,它的结果(值)只可能是两种即 False 或 True。 如: a+b>=c {等同于 not (a+b<c)} (a>b) and (b>c) {类似于数学上的 a>b>c,注意这里两个关系表达 式用括号括起来, 因为它们的运算级别比 and 低, 如果不用的话变成了 a > b and b >c,先进行 b and b 运算,跟数学上的 a>b>c 意义大不一样了} not f {f 为布尔型的变量} not (a>b) {等同于 a<=b} 3=2 {结果恒为 false,因为它不可能成立}

五、Turbo-Pascal 系统处理内容的补充说明
1.基本字符集 字母(26 个字母,大小写均可) ; 十进制数字; 专用字符:+-*/=<>.,():;^@{}$# 还有一些复合符号也当作专用符号,如>=、<=、<>、:=等。 2.标识符 标识符用以标记名字。程序中用到许多名字,有些名字为保留字,如 program, const, var, begin, end 等;有些名字也是由系统规定的,用来预定义 的类型、常数、变量、过程、函数、单元等,称为标准标识符;其余的则由 程序员根据程序要求自行选定的名字,对程序、常数、变量、标号、类型、 过程、函数、记录字段、单元等,均要取定相应的名字。 标识符的基本规则是:必须由一个英文字母或下划线开头,后面可跟 英文字母、数字和下划线的任意组合。标识符中的英文字母不区分大小写。 一个标识符的长度不能超过 127, 如果超过 63 个字符只有前 63 个字符有效。 3.标准标量类型 (1) .整型表 要 求 能 记 住 的 两 个 常 量 : maxint=32767{ 最 大 的 整 数 } 、 maxLongint=2147483647 {最大的长整数} 类型 取值范围 占字节数 格式 shortint -127..127 1 带符号 8 位 integer -32768..32767 2 带符号 16 位 longint –2147483648..2147483647 4 带符号 32 位
61

Byte Word

0..255 0..65535

1 2

无符号 8 位 无符号 16 位

上表所列类型都是基本类型,可以用来进行变量值的说明等等。它们 的取值范围是由占用字节数和格式决定的,如 byte 类型为一个字节的无符 号数,最小为二进制的 00000000,最大为二进制的 11111111,对应的十进 制数范围就是 0 到 255。

(2) .实型表 类型 Real Single Double Extended Comp 取值范围 2.9*10^-39~1.7*10^38 1.5*10^-45~3.4*10^38 5.0*10^-324~1.7*10^308 1.9*10^-4951~1.1*10^4932 –2^63+1~2^63-1 字节数 6 4 8 10 8 有效位数 7~8 11~12 15~16 19~20 19~20

(3) .布尔型(boolean:英国数学家的名字) 它的值只有两个:false 、true。用来标明逻辑值成立或不成立、真或假。 (4) .字符型(char) :只能是一个字符,字符的值也有大小,大小是由这 个字符的 ASCII 码值决定的。 4.注释、常数定义和变量说明 (1)注释 通过{}引起来,增加程序的可读性,一般不执行,在许多 pascal 系统中也可以用一个乘号*后面跟注释内容。 (2)常量定义 格式:const <常量名>=<常量> 如 const DayPerWeek=7; Limit=255; Max=1024; FirstChar=’A’; (3) 变量说明 如 var radius: integer; diameter: real; 常量名和变量名跟前面所说的标识符的定义一样,要由一个英文字母开头, 中间不能有空格, 并且不区分大小写, 书写时根据各人习惯适当地将一些字
62

母写为大写以增加程序的可读性,但对程序的执行没有什么影响。 5.枚举类型与子界类型 有时候在程序中要定义一些量是在指定的范围内的数据,这些个体的数 据可能是标准类型的也可能不是标准类型的, 在 Pascal 系统中是通过枚举类 型、子界类型来描述这种类型的数据。 这里只作简单说明, 在后续的内容中将详细地说明, 它们都属于自定义 类型,在 Pascal 系统中自定义类型都是通过 type 在程序说明部分优于变量 先进行说明。 (1) .枚举类型 枚举类型定义了一个有序的值的集合, 这些值通过枚举描述性标识符的 方法来指示的,它的一般形式为: type 类型标识符=(标识符 1,标识符 2??标识符 n) ; 其中 type 是保留字,下面可以跟若干个上述形式的类型定义。 如:type color = (red,blue,green,yellow,purple); sax = (male,female); suit = (club,diamond,hert,spade); day = (Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday); switch = (off,on); 定义了五个枚举类型 color, sax, suit, day, switch 以及它们各自的所能取到的 值,如果接着有变量说明: var MyFavorColor:color; Yoursax:sax; Playcard:suit; Today,yesterday,tomorrow:day; Status:switch; 都是可以的, 它们只能取相应的值, 也可以直接在变量说明时采用枚举类型, 如:var color:(red,blue,green,yellow,purple); 枚举类型是有序的,如上面说明了 color 以后便有下面的大小或顺序关 系:red<blue<green<yellow<purple。 (2) .子界类型 所谓子界是指有限的一定范围内数据,从起始边界到终止边界。有对 于有序类型,可以用子界来说明。 如: type age=12..18; {指定 age 是在 12 到 18 之间的整数}
63

var yourage: age; 也可以直接写为 var yourage: 12..18; 再如下面的程序: program example4_3; type letters='A'..'z'; var c:letters; begin for c:='A' to 'z' do if (c<='Z') or (c>='a') then write(c); writeln; end. 程序中定义了枚举类型 letters,它是 A 到 z 之间的字符,其中还包括 Z 到 a 之间的几个非字母的字符,因此程序中结此进行了判定再输出, 程序的 运行结果就是: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz 6.一些常用的预定义的标准函数 任何一种高级语言系统都带有许多内容函数, 提供给用户使用。 所谓函 数其实是一些程序段,它能进行相关处理并返回值。 函数代表一种处理,给出一个或多个原始数据,通过函数的加工处理, 可以得到一个结果。原始数据称为自变量,也称为参数,结果称为因变量。 每个函数都有一个名称, 函数处理时只要调用函数名并按自变量个数、 顺序、 类型和含义将原始数据代入就可以了。 有些特殊函数可能没有自变量, 或者 可以用也可以不用,如随机函数等,绝大部分都是有自变量的。 Pascal 定义了丰富的标准函数, 用户可以从系统的帮助中去查看相关函 数的说明、使用及例子。看帮助时一个关键字标题后跟 function 的说明它是 函数。 灵活地使用系统函数可以提高程序的效率, 减少你的代码书写, 快速实 现你的要求。 如字符串与数值的变换, 如果你自己写程序时可能要相当长的 一段代码, 直接使用内部函数或过程就可以直接实现。 一般的函数都有自变 量,用户只要记住函数名和它的形式,就可以直接引用。 另外用户也可以自定义函数来使用。 对于自定义函数请见“过程与函数”的有关章节。 系统的函数有这样几类: 算术函数,进行相关数值运算的一类函数。 标准函数,判定奇数、取前趋后继等。
64

转换函数,进行格式间的转换变化。 字符串函数,有关字符串操作的函数,后续章节中介绍。 其它实用函数,包括文件、记录、指针等等,后续章节中介绍。 (1) .算术函数 标识符 Abs Arctan Cos Exp Frac Int Ln Pi Random Random Sin Sqr Sqrt 自变量类型 整型或实型 实型或整型) 实型(或整型) 实型 实型(或整型) 实型(或整型) 实型(或整型) 无自变量 无自变量 Word 实型(或整型) 整型或实型 实型(或整型) 意义 绝对值 abs(-1)=1 反正切 余弦 (或整型) 小数部分 整数部分 自然对数 圆周率 [0,1]间的随机数 [0,自变量]间随机整数 正弦 平方 平方根 结果类型 同自变量类型 实型 实型 指数 实型 实型 实型 实型 实数 word 实型 同自变量类型 实型

(2) .标准函数 标识符 Odd Pred Succ 自变量类型 整型 离散类型 离散类型 意义 判奇数 前趋 后继 结果类型 布尔型 同自变量类型 同自变量类型

(3) .转换函数 标识符 自变量类型 Chr Byte Ord 离散类型 Round 实型 Trunc 实型 Upcase 字符型 函数运算结果示例: abs(-42)=42 abs(-7.49)=7.49 sqr(2)=4 sqrt(4)=2 pred(2005)=2004

意义 自变量为序号的字符 自变量对应的序号 舍入 截取取整 小写字母转为大写

结果类型 字符型 longint longint longint 字符型

{取绝对值} {平方与算术平方根} {前趋,根据自变量类型确定}
65

round(3.7)=4 trunc(3.7)=3 {四舍五入和截尾取整运算} ord(‘A’)=65 ord(‘a’)=97 chr(97)=’a’ {字符与序号的对应} upcase(‘x’)=’X’ upcase(‘?’)=’?’ {小写转换为大写} ord(False)=0 {有序类型的都有序号} random(256)=0~255 之间的一个随机整数 {随机生成一个数} 函数 frac 与 int 有如下的关系: frac(x)=x-int(x)

[思考与练习]:
1. 上机进入 pascal 系统,编辑调试一个小的程序,观看程序的运行结果, 并以 ex1_1.pas 为文件名存盘。 program my_first_program; var name:string; begin write(‘Enter your name:’); readln(name); writeln(‘Hello! ‘,name); readln; end. 2.计算下列表达式的值 (1)10/2+2 (3)35 div 5 mod 5 (5)(3+5-abs(3-5)) div 2 (7)trunc(17/3) (9)chr(ord(succ(‘a’)) 3.写出下列算术式子的表达式 (1) |a-b|+(5c-r2)0.5 (2) ax2+bx+c (3) (a+b)(c-d) (e+f)(x-y) (4) 2x3-3x2+5x-6

(2)35/5*4 (4)(3+5+abs(3-5)) div 2 (6)sqr(ord(‘Z’)-ord(‘A’)) (8)int(17/3) (10) ord(upcase(‘d’))-ord(‘E’)

66

4.选择题 (1) Pascal 编译程序的过程是指: A. Pascal 程序的机器语言版本 B. 一组机器语言指令 C. 将源程序翻译成目标程序,即由 pas 文件到 exe 文件 D. 系统提供的一个基本软件 (2) 每个 Pascal 程序都发须有: A. 程序头 B. 程序标题 C. 变量说明部分 D. 注释部分 E. 程序体 (3)Pascal 程序的执行部分是指 A. 程序体 B. 程序说明部分和语句部分 C. 语句 D. 整个程序 (4)在 TP 系统中下列哪个量在系统定义中有专门的常量表示 A. 最大整数 B. 最大实数 C. 最小整数 D. 最小实数 (5) 标准 PASCAL 程序说明部分正确顺序是: A. lable?const?var?type B. var?const?lable?type C. lable?const?type?var D. const?var?type?lable (6)下列不是保留字的是: A.sum B. program C. div

D. var

(7) 下列函数的结果是整数类型的是: A. chr(65) B. ord(true) C. pred(true)

D.odd(3)

67

(8) 将数字 8 转换为一个字符“8”的表达式为: A. chr(8) B. ord(‘8’)-ord(‘0’) C. chr(8+ord(‘0’)) D.chr(ord(8)) (9) 表达式 365 div 30 mod 7 的值为: A. 3 B. 4 C. 5 D. 6 (10)正确的关系表达式是: A. a<b<c B. not ((a <b) and (b<c)) C. a=35 and b=’b’ D. 35>34>33 5.思考题 (1) (2) (3) (4) (5)

常量和变量的命名规则都一样,它们有什么本质的不同? Pascal 源程序的基本结构和各部分的作用是什么? 类型与数据是什么关系? 与数据类型有关的标准标识符是什么? 系统定义的常量名用户可以在程序中重新定义吗?输入下面的 程序看是否能通过。 const pi=3.14; {pi 原是系统定义的圆周率常量} var r,s:real; begin readln(r); s:=pi*r*r; writeln(s:10:2); end.

[参考答案]: 1.输出 Hello ############

{#表示运行时输入的字符}

2.写表达式的值 (1) 7.0 {说明:/是实数除,虽然可以整除,结果还是实数形式,这里写为 7.0 就 是 表 示 结 果 是 实 数 , 程 序 输 出 时 如 果 不 指 定 格 式 , 如 语 句 : writeln(35/5),输出 7.0000000000E00 这样的形式,表示 7*100 ,下同} (2) 28.0 (3) 2 (4) 5 (5)3 (6)625 (7)5 (8) 5.0 {说明:虽然 int(x)和 trunc(x)函数都是取整运算,但是返回的值 的类型却不一样,int(x)将 x 的小数部分去除但结果的类型仍然是实型,而 trunc(x)将 x 的小数部分去除后返回的是整型(长整型)} (9) b {说明 ord(x) 和 chr(x)函数是一对相反的函数,本表达式直接返回
68

的是字母“a”的后继} (10)-1 {说明:upcase(x)函数将字母转换为大写的格式,而英文字母的序 号(ASCII 码值)是根据字典顺序编排的,D 在 E 前面一个,所以 D 的序 号减去 E 的序号结果为-1} 3、写表达式 (1) (2) (3) (4) abs(a-b)+sqrt(5*c-r*r) a*x*x+b*x+c (a+b)*(c-d) / ((e+f)*(x-y)) 2*x*x*x-3*x*x+5*x-6

4、选择题 (1)C (2)E (3)B(4)A (5) C (6) A (7) B (8) B (9) C (10) B 5、思考题 (1) 本质区别是:常量的值不能改变,而变量的值可以改变。需要 补充说明的是程序中自定义的常量说明顺序比较优先,一般在 最前面(除了标号说明之外) ,而变量的说明相对在说明部分的 后面,只在过程与函数说明的前面。 (2) PASCAL 的程序分为三个部分:程序头、说明部分、程序体, 程序头只是标明程序,说明部分指明程序中要用到的一些量, 包括自定义的类型、常量、变量、函数、过程等,其中自定义 的函数、过程等在主程序引用时是要执行的,而程序体是程序 的主要执行部分。 (3) 每一个数据都属于一定的数据类型,有些类型之间可以相互转 化,并且有一定的兼容性,如给实型的变量赋值可以用整型, 系统会自动转换。 (4) 与类型有关的标准标识符主要有: integer, longint,byte,word, real, boolean, char, string 等。 (5) 系统定义的常量名用户可以在程序中重新定义,还有一些标准 函数等都可以重新定义,这种情况一般少用。因此上程序可以 运行。再如下程序重新定义了 maxinteger,也可以执行: const maxinteger=30000; begin writeln(maxinteger); end. 一般来说用户没有必要将系统保留的常量重新定义。另外系统
69

有一些标准函数或过程,用户也可以重新定义。如系统函数里 有 int(x),它能取 X 的整数部分,返回一个小数部分为 0 的实 数,如果我们要将它定义为跟 trunc(x)一新的功能(返回的是整 数形式) ,可以作如下定义: function int(x:real):longint; begin int:=trunc(x); end; 这样在程序里再调用 int(x)函数时返回的就是一个整数了。 如有这样的主程序: begin writeln( int(3.14)) end. 运行结果就是 3。

70

第五章 顺序结构的程序设计
一、输入与输出语句
1.read/readln 读取数据 格式:read(变量) 或 read(变量 1,变量 2,??) readln(变量) 或 readln(变量 1,变量 2,??) 功能:在运行程序时读入相应数据给指定变量,直到读入的数据满足为止, 这里所说的满足有两个方面的含义,一是类型的一致,二是数据的满足。 Readln 跟 read 不同的地方就是它执行完后将到下一行。 例:read(a,b,c) ; 根据事先定义的类型由用户在运行程序时输入相应的数据给 a,b,c,也可 分开写成三个 read 语句:read(a);read(b);read(c)。 readln(a,b,c); 与 read(a,b,c)不同是读完数据后另起一行,如果将它分为三 个语句 readln(a); readln(b); readln(c)执行时可能读入的数据跟原来不一样, 自己上机去试试吧! readln; 空读语句, 一般起到让程序运行时停止由用户回车后继续或跨过 一行中其余的数据,保证下一个读语句从下一行头一个数据开始读取。 2.write/writeln 输出语句 语句功能:输出指定表达式的值。 如 wirte(a),write(‘Jiangshu’); 分别输出 a 的值和 Jiangshu (1)场宽 在输出项后用“:数字”指明输出的宽度。 如 write(5:6),则输出: 5 {5 的前面有 5 个空格,整个输出项占 6 个字符的位置} 对于实数类型的还可以通过“:数字 1:数字 2”指明输出数字的宽度 和小数点后的位数。 如:write(1.2:10:5) 将输出: 1.50000 {整个输出项占 10 个字符位置,整数部分占 4 位,小数点 1 位,小数 部分 5 位,其中整数部分不足的在高位补空,小数部分不足在后面补 0} 如果指定的宽度比原输出项应有的宽度小呢? 对于整数或字符等类型的,将自动调整到最小所要的宽度,如 write(‘ABCD’:2)仍将输出 ABCD。 对于实数,小数部分会取自定的位数,将尾部去除(四舍五入) ,并自 动适应到最少的宽度。 [思考]:
71

如何对小数点后指定位进行四舍五入? [解答]: 一种方法是直接指定输出小数点后指定的位数, 如对于变量 a 要保留到 小数点后第三位并考虑四舍五入, 可以直接写为 write(a:0:3)。 这种方法跟系 统的设置有关,也就是说这样不能保证任何时候都正确。 可以对指定位加 5 后从这位始截尾。 如要求对实型变量 a 要求精确到小 数点后两位,对小数点后第三位进行四舍五入,可以用这样的输出语句 write(a+0.005:0:2)。一般来说对于变量的处理,可以先按这种方法(即相应 位加 5 后再去尾)通过赋值语句进行处理,输出时不进行处理,只是直接输 出就行了。 (2)writeln 跟 wirte 的区别 writeln 语句在输出完指定内容后另起一行,write 只管输出除非真满一 行后才另起一行。 空的 wirteln 起到一个输出空行的作用,如果它前面有 write 语句,则在 其它输出空行(可能不满一行) ,保证下一个输出另起一行。在程序中经常 用一个空的 writeln 语句起换行的作用。 (3) 一个语句多个输出项 一个 write 或 writeln 中可以有多个输出项,各项之间用逗号间隔。 如 write(1,2,3); 它与三个 write 语句作用一样:write(1);write(2);write(3); 再如 writeln(1,2,3); 输出 123 后换行。 与它等同的分开写的形式为:write(1);write(2);writeln(3);

二、赋值语句(:=)
格式:变量名:=表达式 功能:将表达式的值计算出来赋给相应的变量。 不管什么计算机语言, 赋值语句都是最基本最常用的语句, 通过它给变 量赋值来进行各种运算、处理。 如 a:=10*5; {a 的值为 50} a:=a+1;{将 a 的值增加 1,常用此语句来进行计数} s:=s+a; {将 s 的值增加 a,常用类似的累加语句来进行求和} t:=t*a; {将 t 的值变为原来的 a 后倍,常用类似的语句来进行累乘} 例 5_1.交换两个数值型变量 a 和 b 的值 [分析与算法选择]: 要交换两个变量的值,可以联想起现实世界中交换两个容器 A 和 B 中
72

所装的东西,一般要先引进一个空的容器 C,先将一个容器(如 A)里的倒 入 C,再将另一个容器 B 的倒入 A,最后将 C 的倒入 B,从而实现 A、B 容器内容的互换。 [方法 1]:引进第三个变量 c:=a; a:=b; b:=c; [思考与提高]: 考虑到两个变量都是数值型的, 而变量的特点跟现实世界中的物品又不 一样,变量的值赋定后,如果不改变它,系统会一直记住这个值的,不管这 个值使用了多少次。 因此也可以不引进第三个变量, 而是先将两个变量的值 先合并起来放到其中一个变量里 (如 A) , 此时另一个变量 B 还是原来的值。 要使 B 的值变量合并前 A 的值只要将和减去 B 的值就行了,这样做以后, A 还是原来两数的和,B 的值已是原来 A 的值了。再用 A 减 B,得到的结 果给 A,这样 A 的值变为原来 B 的值了,从而实现了两个数值型变量的交 换。对于其它类型的变量,也可以模仿这种方法,不过要烦一些。 [方法 2]:先合并后分开 a:=a+b; {如原来 a=3,b=5,执行此语句后 a=8,b=5} b:=a-b; {执行此语句后 a=8,b=3} a:=a-b; {执行此语句后 a=5,b=3} 还有其它一些办法,但都没有上面的两种方法通用。如可先乘再除, 这种方法对于有一个变量为 0 的情况就不正确了。也可能会出现除数为 0 的情况。 例 5_2.计算四个变量的乘积 [分析与算法选择]: 一般的计算,可以直接用一个表达式将运算结果给一个变量就行了。 如果变量的个数不确定, 或者说变量的个数很多, 此时用一个表达式就不方 便了,可行的方法是来一个就算一个,直到全部的都算好结束。在后面的循 环中常用这种方法。 [参考程序]: program example5_2; var t:longint; a,b,c,d:integer; begin write(‘Enter integer a,b,c,d:’); readln(a,b,c,d);
73

t:=1; t:=t*a; t:=t*b; t:=t*c; t:=t*d; writeln(‘a*b*c*c=’,t); end. [补充说明]: 累加时,存放累加值的变量初值一般为 0;而累乘时必须将相应变量的 初值赋为 1。如上述程序中 t 的初值为 1,如果没有这句,系统默认的初值 为 0,那么乘下来结果也是 0。

[练习]:
1.写出下列程序的运行结果 (1)program ex5_1_1; var a:integer; b:real; c:char; d:boolean; begin a:=1234; b:=1234.5678; c:='%'; d:=true; writeln(a,a:5,a:10,a:0); writeln(b,b:12:5,' ',b:0:0); writeln(c,c:5); writeln(d,d:5); writeln('end':5); end. (2)program ex5_1_2; var a,b:integer; begin write('Input a,b(integer):');
74

readln(a,b); writeln('max=',(a+b+abs(a-b)) div 2); writeln('min=',(a+b-abs(a-b)) div 2); end. run Input a,b(integer):1234 4321 输出: 2、编写程序 (1) 输入三角形的三边,输出三角形的面积(假设这三边一定能构成三角 形) 。 计算三角形面积的公式: p:=(a+b+c)/2 s:=sqrt(p*(p-a)*(p-b)*(p-c)) (2) 用随机函数产生指定范围内的数(可能是整数,也可能是小数位确定的 小数) 提示: random 函数不加自变量时是随机产生一个纯小数(最小的情况是 0) ; 要产生指定范围内的数,要先确定这个范围内一共有多少个数(设为 n) ,再考虑最小数(设为 m) ,如果是小数先当整数来考虑,最后再来除或 乘一个 10 的若干次方。 如要产生一个两位数,因为两位数一共有 90 个,random*90 产生的是 0-90 之间的数,截尾后变成的整数范围是 0-89,再加上最小数 10,产生的 就是任意的两位数了: trunc(random*90)+10。也可以写成 random(90)+10 要求编程实现: 产生 10.00 到 99.99 之间任意的两位整数带两位小数。

[参考答案]:
1.阅读程序 第一题 1234 1234 12341234 1.2345678000E+03 1234.56780 1235 % % TRUE TRUE end 第二题 4321
75

1234 5、 编写程序 第一题参考程序 program ex5_21; var a,b,c,p,s:real; begin write('Input a,b,c:'); readln(a,b,c); p:=(a+b+c)/2; s:=sqrt(p*(p-a)*(p-b)*(p-c)); writeln('s=',s:10:2); end. [说明]:此程序运行时可能会碰到无解的情况,如输入 2 4 7,程序会有这 样的提示: “Error 207: Invalid floating point operation.”提示你错 误号和相关的错误信息, “无效的实数操作” 是因为对负数进行开平方运算。 换句话说就是这个程序不能保征对输入的所有数据都有效, 对于不能构成三 角形的三条边长不进行运算,这需要一个判断,下一章内容。 第二题参考程序 program ex5_22 Var a:integer; begin randomize; a:=trunc(random*9000)+1000; writeln(a div 100,’.’,a div 10 mod 10,a mod 10);{ writeln(a/100:5:2);} end.

76

第六章
一.复合语句

分支结构的程序设计

1.为什么要用复合语句 在程序中有时候要将多个语句结合起来作为一个整体,象一个语句一样 来使用。这时就要用到复合语句,用 begin 和 end 将多个语句结合在一起。 2.格式: begin 语句 1; 语句 2; ?? 语句 N; end; {说明:end 前的最后一个分号可以不写,也可以写,相当于其后是一 个空语句。} 其效果跟普通的语句一样,也就是将多个语句合并成一个语句来使用, 特别是在后面的条件语句或循环语句里执行的是多个语句要像一个语句一 样时就必须要使用复合语句。

二.条件语句(if---then---else)
格式 1:一个分支 if 条件 then 语句; 格式 2:两个分支 if 条件 then 语句 1 else 语句 2; 注意 else 前没有分号,否则会出错。 (思考这是为什么?) 1.条件的描述 在使用条件语句时主要的难点就是条件的描述和满足条件或不满足条 件时要执行的语句的描述。 条件通过布尔表达式来描述。 例:条件语句与自然语言描述的对比 (1)if a>1 then a:=a-1 else a:=a+1; 如果 a 大于 1 那么将 a 的值减少 1,否则将 a 的值增加 1 (2)if (a>b) and (b>c) then s:=(a-b)*(b-c); 如果 a 大于 b 并且 b 大于 c,那么 s 的值为(a-b)乘以(b-c)
77

(3)if (a>0) or (b>0) then s:=a+b; 如果 a>0 或者 b>0,那么 s 的值等于 a+b (4)if f then t:=t+1; {这里 f 为布尔型的变量} 如果 f 成立即等于 true,那么 t 的值增加 1 2.语句的选择 满足条件时执行什么、不满足条件时执行什么要先搞清楚。 当满足条件时或不满足条件时执行的是多个语句时要使用复合语句的格 式。当然单个语句也使用复合语句的格式也不会错,只不过多此一举而已, 并不影响程序的执行,有时先这样写是为了后来的扩充。 例:条件语句与自然语言描述 if a<0 then begin a:=a+1; s:=s+1; end; 如果 a 小于 0,那么执行两部分: (1)a 的值增加 1; (2)s 的值增加 1。

五.多分支语句 case {有时也叫多路分支}
1.格式: case 表达式 of 值 1: 语句 1; 值 2: 语句 2; ?? [else 语句] end; 2.示例 (1) 两个分支的情况,还不如直接用条件语句 case random(Maxint) mod 2 of 0: writeln(‘Even digit’); 1: writeln(‘Odd digit.’); end; {等同于 if random(maxint) mod 2=0 then writeln(‘Even digit.’) else writeln(‘Odd digit.’);} 根据随机产生的非负整数情况来确定 偶数时:输出‘Even digit’; 奇数时:输出‘Odd digit.’ (2)根据字符型变量 ch 的值来确定不同的执行
78

case ch of ‘A’..’Z’,’a’..’z’: writeln(ch,’ is an identifier character.’); ‘0’..’9’: writeln(ch,’ is a decimal digit.’); else writeln(ch,’ is a special character.’); end; {等同于: if ((ch>=’A’) and (ch<=’Z’)) or ( (ch>=’a’) and (ch<=’z’)) then writeln(ch,’ is an identifier character.’) else if (ch>=’0’) and (ch<=’9’) then writeln(ch,’ is a decimal digit.’) else writeln(ch,’ is a special character.’); } 3.使用注意点 当有 else 部分时它上面的语句的最后一行可以有分号也可以没有分号, 这点跟 if-then-else 不一样; case 语句结构中最后要有一个 end 作为结尾; 其 中的语句可以是单语句也可以是复合语句。

[练习]:
1、编程输入三角形的三条边长,输出三角形的面积,如果不能构成三角形 输出错误信息。 2、输入三个整数,按由大到小的顺序输出。 设三个数为 a,b,c,一种方法可以用条件的并列,列举出可能有的 6 种情况。另一种方法是用条件的嵌套,从而输出结果。 3.编写程序输入年份和月份,输出这个月的天数。 4.编程求解一元二次方程,输入三个系数,输出解或无解。 5.编一个随机产生一个 100 以内的四则运算题,要求先输出这个四则运算 的式子, 这个四则运算的式子要能确保第一个数不小于第二个数, 如果是除 法的话要能确保能够整除, 然后让用户输入结果, 如果输入的结果正确则输 出“Right!”否则输出“Error!” 。

79

[分析与参考程序]:
1.[分析与提示]: 对于输入的三条边长, 首先判定能不能构成三角形, 不能构成则输出提 示信息: “error” ,否则(能构成三角形)则求解面积并输出。 [参考程序]: program sjxmj; var a,b,c,p,s:real; begin readln(a,b,c); if (a+b>c) and (a+c>b) and (b+c>a) then begin p:=(a+b+c)/2; s:=sqrt(p*(p-a)*(p-b)*(p-c)); writeln(‘s=’,s:10:2); end else writeln(‘error!’); end. 2.[方法 1]: program sgs1;{条件的并列} var a,b,c:integer; begin readln(a,b,c); if (a>b) and (b>c) then writeln(a,b,c); if (a>c) and (c>b) then writeln(a,c,b); if (b>a) and (a>c) then writeln(b,a,c); if (b>c) and (c>a) then writeln(b,c,a); if (c>a) and (a>b) then writeln(c,a,b); if (c>b) and (b>a) then writeln(c,b,a); end. [方法 2]: program sgs2;{条件的嵌套} var a,b,c:integer; begin readln(a,b,c); if a>b then if b>c then writeln(a,b,c) else if c>a then writeln(c,a,b) else writeln(a,c,b)
80

else if a>c then writeln(b,a,c) else if c>b then writeln(c,b,a) else writeln(b,c a) end. [思考与提高]: 采用条件的嵌套,你一定要理清楚一层与一层之间的关系,不能乱套, 否则自己也不清楚到底错在什么地方。 用并列虽然看起来重复, 结构却很清 晰,不容易出错。你可以自行选择到底用并列还是嵌套。有时嵌套是不可避 免的,这时只能先理顺再使用。 另外在使用嵌套的时候要注意有“否则”的情况(else 部分) : “else 跟 if—then 的配对”跟“右括号跟左括的配对”是一样的。在条件的嵌套结构 当某些条件语句要用到 else 而有些又用不到的时候,建议不用 else 的条件 语句也用上 else,后面什么也不跟就行,标明对于这个条件语句它的整体已 经结束,后面再有 else 部分跟它无关,这样这不会引起 else 配对错误。 3.[分析]: 一年中有十二个月, 其它十一个月的天数基本固定的, 只有二月份的天 数是特殊的。根据万年历算出闰年的 2 月的天数,每 400 年中只能有 97 个 闰年??闰年(二月 29 天的两种情况) : (1) 年份能被 4 整除不能被 100 整除 (2) 年份能被 400 整除。 [参考程序]: program calendar; var year:1701..2200; month:1..12; day:integer; begin readln(year, month); case month of 1,3,5,7,8,10,12: day:=31; {大月 31 天} 4,6,9,11:day:=30; {小月 30 天} 2: if (year mod 4=0) and (year mod 100<>0) or (year mod 400=0) then day:=29 else day:=28; {二月份的情况} end; writeln(‘days=’,day); end. [思考与提高]:
81

你可以修改程序,将程序先输出年份和月份(用英文表示) ,然后再输 出这个月的天数。还是用 case 语句,如: case month of 1:write(‘Jan.’); 2:write(‘Feb.’); ……. 12:write(‘Dec.’); end; 如果给出具体的日期, 你能通过程序算出这天是星期几吗?你可以先参 考某一天是星期几,然后进行运算,同样要考虑到闰年的情况。 4.[分析与提示]: 一元二次方程可以写为形如 ax2+bx+c=0,其中 a,b,c 是系数,要求 X 的 解,由于输入的系数各种可能都有,所以对各种情况要考虑周全。 如果 a<>0 那么方程是二次方程 如果 b*b-4*a*c>0 那么 方程有两个实数解: x1:=(-b+sqrt(b*b-4*a*c)/(2*a) x2:=(-b-sqrt(b*b-4*a*c)/(2*a) 否则(即 b*b-4*a*c 不大于 0) 如果 b*b-4*a*c=0, 那么方程有两个相同的解 x=-b/(2*a) 否则(即 b*b-4*a*c 小于 0) 无实数解(虚数解暂不考虑) 否则(即 a=0) 如果 b<>0,那么方程是一次方程,有一个解:x:=-c/b 否则(即 b=0) 如果 c=0(即 a=0,b=0,c=0),那么有无数解 否则 (即 a=b,b=0,c<>0)无解。 Pascal 程序的基本结构为: If a<>0 then if b*b-4*a*c>=0 then begin…..end Else….. Else If b<>0 then …. Else if c=0 then ….. else …..; [参考程序]: program ex6_4; var a,b,c,d,x1,x2:real;
82

begin write('Input a,b,c:'); readln(a,b,c); if a=0 then if b=0 then if c=0 then writeln('Wushujie!') else writeln('Wujie!') else writeln('x=',-c/b:10:4) else begin d:=b*b-4*a*c; if d>=0 then begin x1:=(-b+sqrt(d))/(2*a); x2:=(-b-sqrt(d))/(2*a); writeln('x1=',x1:10:4); writeln('x2=',x2:10:4); end else writeln('Wujie!'); end; end. 5.[分析与提示]: 用随机函数来产生四则运算的操作数和操作符,其中操作数都是 100 以 内的整数,所以可以直接用 random(100)就行了,如果第一个数比第二个数 小则交换两个数。而操作符(运算符)只有四种可能,因此先用随机函数产 生出 0-3 间的数,再根据产生的是什么数来确定是“+、-、*、/” 。其中对于 除法运算要考虑除数不能为 0,再要考虑能整除,所以先进行整除运算,得 到一个结果,再将第一个数变为除数乘以商。 [参考程序]: program ex6_5; var a,b,c,j,k:integer; f:char; begin randomize; a:=random(100); b:=random(100); c:=random(4); if a<b then begin a:=a+b; b:=a-b; a:=a-b; end; case c of 0: begin f:='+'; j:=a+b;end; 1: begin f:='-'; j:=a-b;end;
83

2: begin f:='*'; j:=a*b;end; 3: begin f:='/'; if b=0 then b:=2; j:=a div b; a:=j*b; end; end; write(a,f,b,'='); readln(k); if k=j then writeln('right!') else writeln('error!'); end. [思考与提高]: 这道程序可以给小学低年级的学生使用, 当成一个随机出题的工具来使 用,但是这里有明显的几个缺陷:一是乘法可能不适合口算,因此可以在程 序中作相应修改,当是乘法时如果第二个数太大(如超过 10)便作相应变 换(如整除 10 等) 。二是运行一次程序只能出一道题,每做一次就要重新运 行一次,最好能够一次出多道题,并且能够判分,这样就更实用了,相关的 程序在学习了下一章内容后再做。

84

第七章 循环结构的程序设计
许多处理过程中有连续的重复,这时候如果还是一句句地重复写的话, 既麻烦又累赘, 当要重复成千上万次时, 这种重复的书写几乎是不可能实现 的。直接简便的方法是用循环语句来实现循环。 一.While 语句与当型循环 1.格式: while 布尔表达式 do 语句; 2.说明: 格式中 while 和 do 都是保留字,布尔表达式表示条件,它的描述跟条 件语句里的条件描述是一样的。 Do 后面的语句可以是单一语句也可以是复合语句,称为循环体。只要 布尔表达式成立时(即值为 TRUE 时)就执行循环体,如此反复直到布尔 表达式不成立(值为 FALSE)时停止。如果一开始就为布尔表达式就不成 立(值为 FALSE) ,那么循环体一次也不执行。 例 7_1:输出 1 到 100 的算术平方根。 [分析]: 计算一个数的算术平方根可以用一个函数 sqrt(i),其中的 I 从 1 一直变 化到 100,通过循环来实现。 [程序清单]: program ssqrt; var i:integer; begin i:=1; while i<=100 do begin writeln(‘Squrare root of’, i, ‘ is ‘, sqrt(i):8:4); i:=i+1; end; end. [思考与提高]: 上面程序中 I 的初值为 1,在循环体中,先是输出 I 的算术平方根再将 I 的值增加 1,所以最后循环结束时 I 的值是 101,while 的条件也要写成 I<=100 或写为 I<101,如果写成 I<100,那么在 I=99 时满足循环的条件, 先输出 99 的算术平方根,然后 I 的值增加 1 变为 100,此时不满足循环的 条件了,所以便结束循环,结果 100 的算术平方根没有输出。因此我们在用
85

循环时一定要把握好控制循环的边界条件, 不能随便扩大边界也不能随便缩 小边界。 另一种写法:i 的初值为 0,条件的描述及循环体的相关语句的顺序都 要作调整: i:=0; while i<100 do begin i:=i+1; writeln(??); end; [注意]: 在 while 循环体中一定要有相应的语句使布尔表达式的值可能为 false, 否则就会构成死循环。 3、循环的强制终止 一般来说,只要循环的条件及循环体描述得当,循环都能顺利结束, 不会产生死循环的。 有时在程序运行中会有一些特殊的情况, 需要终止当前 循环的执行, 如果将这个条件写到循环体外有不太方便, 这时可以使用 break 来强制终止当前循环的执行。

二、Repeat 语句与直到型循环
1.格式: repeat 语句; 语句; ??; 语句; until 布尔表达式; 2. 说明 格式中 repeat 和 until 都是保留字,其间的语句构成循环体,最后一个 语句的分号可以省略;until 后的布尔表达式表示条件,描述的是循环结束 的条件。 3. 功能 反复执行循环体直到布尔表达式的值为 true 时为止。 4.示例: 上例的程序段可写为: begin
86

i:=1; repeat writeln(‘Square root of ‘, i, ‘ is ‘,sqrt(i):8:4); i:=i+1; until i>100; end. 5.While 与 Repeat 语句对比 while 和 repeat 语句一般情况下可以相互替换。它们的主要区别是: while 是先判断后执行,而 repeat 是先执行后判断,因此 while 语句的 循环体有可能一次也不执行,而 repeat 语句至少执行一次; 前者是当条件满足时执行,而后者是当条件不满足时执行; 前者的循环体是复合语句时要用 begin、end,而后者却不一定要用。

三、for 语句与计数循环
1.格式: (1)for 变量标识符:=初值表达式 to 终值表达式 do 语句; 从小到大执行的格式 (2)for 变量标识符:=初值表达式 downto 终值表达式 do 语句; 从大到小执行的格式 2.说明 格式中的 for,to,downto,do 都是保留字, to 一般用在升序的计数,而 downto 用在降序的计数。变量标识符在这里称作是控制变量,必须是离散 (有序)数据类型,如: for i:=1 to 100 do …. for ch:=’a’ to ‘z’ do…. 3.示例 上面的例子用 for 语句写出的程序段为: for i:=1 to 100 do wirteln(‘Square root of ‘ ,i,’ is’, sqrt(i):8:4); 也可以写成: for i:=100 downto 1 do wirteln(‘Square root of ‘ ,101-i,’ is’, sqrt(101-i):8:4); for 语句的形式简单,但它也有一定的局限性,主要是控制变量的值不 能随意变化,每次只能取其后继(用 to 的情况)或前趋(用 downto 的情况) , 另一限制是控制变量只能用简单的有序的离散量, 且循环次数已定, 不能象 while 或 repeat 那样通过布尔表达式来控制循环的操作。 例 7_2:用 for 语句计算前 N(N>1)个自然数中所有偶数的和。
87

[分析]: 判定偶数可有多种方法, 也可以不用判定而直接去构造偶数, 由此得 到更多的方法。 [方法 1]: 构造偶数,1 到 n 之间的偶数有 N DIV 2 个,所以从第一个构造到最 后一个偶数,并将它加到存储和的变量中。 sum:=0; for counter:=1 to n div 2 do sum:=sum+2*counter; [方法 2]: 对 1 到 n 中任一个自然数进行检测, 如果它除以 2 的余数为 0 表明它是 偶数,则将其加到和中。 for counter:=1 to n do if counter mod 2=0 then sum:=sum+counter; [方法 3]: 用标准函数 odd(x),判定是否是奇数,如果不是奇数说明它是偶数。 for counter:=1 to n do if not odd(counter) then sum:=sum+counter; [方法 4]: 在方法 1 中是构造偶数相加,也可以先相加,再考虑偶数的情况,如 10 以内的偶数为 2、4、6、8、10,将它们标明序号为 1、2、3、4、5,序号为 原数的一半, 因此只要求出序号的和, 再将序号的和乘以 2 便得到偶数的和。 For counter:=1 to n div 2 do sum:=sum+counter; Counter:=counter*2; 注意:一般情况下不允许在 for 语句的循环体中改变控制变量的值。 四.多重循环(循环的嵌套) 当程序中要用到多个循环时,如果这些循环是并列的关系,那么它们 彼此之间的控制变量不相互影响。 而当一个循环的循环体中又有循环时,这就是循环的嵌套,称为多重 循环。如前面要大家输入的“输出九九乘法表”程序。 例 7_3:编写程序输出如下的字母塔:

88

A ABA ABCBA ……………. ABCD……DCBA [分析]: 此题有两个关键: 一是确定每一行前导空格符的数目; 二是按一定规律 输出英文大写字母,共 26 行。应能保证最后一行前导空格数目至少为 0, 设最后一行的前面空格数为 10 个,那么倒数第二行前面的空格数为 11,倒 数第三行的数目为 12??,如果控制输出行的字符变量为 c,则空格数为: ord(‘Z’)-ord(c)+10 [程序清单]: program lettertower; var ch,c:char; begin for c:=’A’ to ‘Z’ do begin write(‘ ‘:ord(‘Z’)-ord(c)+10); {输出空格数} for ch:=’A’ to c do write(ch); {输出一行的左半部分} for ch:=pred(c) downto ‘A’ do write(ch); {输出一行的右半部分} writeln; {换行} end; end. [思考与提高]: 上面整个程序是个两重循环, 而外循环的循环体是两个并列的循环, 因 此虽然程序中有三个 for 语句,但只是两重循环。 而程序中输出一行时是通过两个循环来实现的, 能不能通过一个循环来 实现呢?用字符型变量来控制循环不太方便, 可以用整型变量来控制循环列 方便一些,相应的程序段如下: for I:=1 to 26 do begin write(‘’:36-I); for j:=1-I to I-1 do write(chr(64+I-abs(j))); writeln; end;

89

五.不建议使用的 goto 语句及标号
如果在程序中要自由跳转,可使用:goto 标号; 标号要在程序的说明部分先说明。 1. 标号说明 Lable 语句标号 [,语句标号] 如:label one,two 在程序体中有 one: 和 two: 开始的程序段,其它地方就可以通过 goto one 或 goto two 来转到指定的地方 one 或 two。 2.为什么不建议使用 label 和 goto? 虽然在程序中用 goto 语句可以给程序设计带来方便,但如果程序中使 用 goto 语句将会破坏结构化的程序结构,它完全可以通过条件、循环等来 替代。当一个程序中多处使用 goto 语句时,很容易引起交叉错误,阅读起 来也很麻烦。因此建议大家不用或尽量少用 goto 语句。

[练习]:
一、阅读程序题,写出程序运行结果 1.program ex7_1_1; var i,j:integer; begin for i:=1 to 10 do begin for j:=1 to 10 do if i>j then write(1) else write(0); writeln; end end. 2.program ex7_1_2; var i,j:integer; begin for i:=3 to 9 do begin for j:=2 to i-1 do write(i mod j=0:10); writeln
90

end end. 二、完成程序题,将程序补充完整完成指定的任务 1.求 100 以内所有质数的和。 [变量说明]:h 存放所有质数的和;I、j 为循环检测变量 [程序清单]: program ex7_2_1; var i,j,h:integer; begin __________(1)________; for i:=3 to 100 do begin j:=2; while (i mod j>0) and (j<i) do j:=j+1; if _____(2)_______ then h:=____(3)_______; end; writeln(h) end. 2. 输出四位数以内(包括四位数)是一个质数的完全平方数的数,并输出 总的个数。 [变量说明]: n 存放符合条件的数的个数;I、j 是循环检测变量;K 存放完全平方数。 [程序清单]: program ex7_2_2; var i,j,k,n:integer; begin n:=0; for i:=2 to 99 do begin k:=____(1)_____; j:=2; while (i mod j>0) and (j<i) do j:=j+1; if _____(2)_______ then begin write(________(3)________:5); ______(4)_______;
91

end end; writeln; writeln('Count=',n); end. 三、编写程序题 1.编写输出“右三角的九九乘法表”的程序: 1 2 3 4 5 6 7 8 9 4 6 8 10 12 14 16 18 9 12 15 18 21 24 27 16 20 24 28 32 36 25 30 35 40 45 36 42 48 54 49 56 63 64 72 81 2. 输出“字母菱形” 其中菱形的行数为 2*n-1(1<=n<=26) ,n 由键盘输入。 [样例]: 输入 3 输入 2 输出 A ABA A 输出 A ABA ABCBA ABA A

3. 编写一个猜数字的程序,你想一个 1000 以内的自然数,程序运行后计 算机给出它猜的数,你根据这个数键盘输入相应字符,告诉它大了(输 入 G)或小了(输入 L)或对了(输入 R) ,只要你都是用一个数作为标 准并且输入正确,计算机 10 次以内肯定能猜出你所想的数。 4. 编程实现:计算机随机出十道 100 以内的四则运算题给用户运算,如果 用户输入正确就提示“Right”否则提示“Error” 。 [要求]: 如果是减法第一个数要比第二个数大;
92

如果是乘法,第二个数不超过 10; 如果是除法, 第二个数不超过 10 也不为 0, 第一个数不小于第二个数并 且能被第二个数整除。

[分析与参考解答]:
一.阅读程序题 1. 0000000000 1000000000 1100000000 1110000000 1111000000 1111100000 1111110000 1111111000 1111111100 1111111110 2. FALSE TRUE FALSE TRUE FALSE TRUE FALSE

FALSE FALSE TRUE FALSE FALSE TRUE

FALSE FALSE FALSE TRUE FALSE

FALSE FALSE FALSE FALSE

FALSE FALSE FALSE

FALSE FALSE

FALSE

二、完成程序题 1. (1) h:=2 (2) j=i 2.(1) i*i (2) j=i (3) k

(3)h+I (4) n:=n+1

三、编写程序题 1.通过两重循环来实现程序,注意循环的初值和终值 program ex7_3_1; var i,j:integer; begin
93

for i:=1 to 9 do begin write('':i*3); for j:=i to 9 do write(i*j:3); writeln; end; end. 如果内循环纯粹表示输出的第几项,那么第 I 行第 J 项的输出内容为 I*(j-1+I),相应程序段如下: for I:=1 to 9 do begin write(‘’:I*3); for j:=1 to 10-I do write(I*(j+I-1):3); writeln end; 2.程序中用两重循环来实现,外循环控制行,内循环控制列,两次使用了 诸如 1-n 到 n-1 的形式,使四个部分统一起来。 program ex7_3_2; var n,i,j,k:integer; begin readln(n); for i:=1-n to n-1 do begin k:=n-abs(i); write('':36-k); for j:=1-k to k-1 do write(chr(64+k-abs(j))); writeln; end; end. 3.采用了二分法来猜数字,因为 1000 以内的数都不超过 2 的 10 次方,所 以不超过 10 次就可以猜出。 program ex7_3_3; var a,b,n:integer; c:char; begin a:=0; b:=1024; n:=0;
94

repeat writeln((a+b) div 2); write('Please Enter G,L or R ( > < =):'); readln(c); c:=upcase(c); if (c='G') or (c='>') then b:=(a+b) div 2; if (c='L') or (c='<') then a:=(a+b) div 2; n:=n+1; until (c='R') or (c='=') or (n>10); if n>10 then writeln('You are wrong!') else writeln('Your number is:',(a+b) div 2); readln end. 4. 用一个循环来重复执行 10 次产生四则运算并让用户输入的过程, 而四则 运算符根据随机产生的 0、1、2、3 确定加、减、乘、除。 program ex7_3_4; var a,b,c,j,k,n:integer; f:char; begin randomize; for n:=1 to 10 do begin a:=random(100); b:=random(100); c:=random(4); if a<b then begin a:=a+b; b:=a-b; a:=a-b; end; case c of 0: begin f:='+'; j:=a+b;end; 1: begin f:='-'; j:=a-b;end; 2: begin f:='*'; if b>10 do b:=random(10); j:=a*b; end; 3: begin f:='/'; while (b=0) or (b>10) do b:=random(9)+1; j:=a div b; a:=j*b; end;
95

end; write(a,f,b,'='); read(k); if k=j then writeln('right!') else writeln('error!'); end; end.

96

第八章 条件和循环语句应用
一、相关要点:
1.无论是条件语句还是循环语句的 while 和 repeat/until 中的条件描述都 有是通过布尔表达式来实现的。 许多同学对布尔表达式不熟悉, 其实就是值 只可能是真或假的表达式。 一般有关数值型的变量或表达式, 在判断其值的 大小或范围时,都是通过描述它们大小、相等或不等的关系的,因此有些语 言的教材也称之为关系表达式。在 if 语句中满足条件(即布尔表达式值为 真 true) ,时执行的是 then 后的语句。While 循环是当条件满足时才执行循 环体,而 repeat 是执行循环体直到条件满足时才结束,前者描述的是执行的 条件,后者描述的是结束执行的条件。 2.If 语句中当满足条件或不满足条件要执行的是一组语句时,一定要用 复合语句的格式,否则只认为第一个语句是满足条件或不满足条件要执行 的。While…do 后面的循环体和 for….do 后面的循环体也是一样。复合语句 的 begin 和 end 是配对使用的,不能跟其它的 end 混淆起来。其它有 end 的 语句是:case…end,而整个程序体是由 begin 开始,end.结束,注意整个程 序结束 end 后的点号不能少。 3.在一个程序中条件语句和循环语句都可能有并列或嵌套,并列一般容 易理解,嵌套一定要把握住一层一层之间的关系。对于循环的嵌套来说,内 层的循环体执行的次数一般是内外层循环次数的相乘关系。

二、例程
例 8_1.键盘输入一个正数 n(n>2) ,判定 n 是否是素数。 [分析与算法选择]: 判定一个数是否是素数可以有多种方法,我们希望尽可能地少判定一 些, 也希望算法实现容易些。 在算法确定的情况下, 用循环语句来重复判定, 几种循环语句都可以选择,一般来说 while 与 repeat 更方便一些,用 for 循 环要么会在已经得出不是素数的情况下仍然继续判定,要么增加 break 语句 来终止循环。 [程序清单]: 程序 1 while 循环 program example8_1a; var n,i:integer; begin
97

readln(n); i:=2; while (i<=sqrt(n)) and (n mod i>0) do i:=i+1; if i>sqrt(n) then writeln('Yes') else writeln('No'); end. 程序 2 repeat 循环 program example8_1b; var n,i:integer; begin readln(n); i:=1; repeat i:=i+1; until (i>sqrt(n)) or (n mod i=0); if i>sqrt(n) then writeln('YES') else writeln('NO'); end. 程序 3 for 循环 program example8_1c; var n,i:integer; f:boolean; begin readln(n); f:=true; for i:=2 to trunc(sqrt(n)) do if n mod i=0 then begin f:=false; break; end; if f then writeln('YES') else writeln('NO'); end. 例 8_2.鸡兔同笼问题,输入总头数 t 和总脚数 j(2t<=j<=4j,且 j 是偶数) 输出各自的头数(t1,t2) 。 [分析与算法选择]: 如果作为一个数学题,用方程组就可以方便解决,或者根据自己解方
98

程组得到的式子, 根据输入的头数和脚数直接输出鸡和兔各自的头数。 因为 本题正好可以作为确定方程组来解,如果是不确定方程,就麻烦些了。 我们只要根据鸡和兔脚数与头数的关系,用循环来检验可能的解,对 于不确定方程,这种方法更方便,且可找出所有可能的解。 [程序清单]: program example8_2 var t,j,t1,t2:integer; begin readln(t,j); for t1:=0 to t do begin t2:=t-t1; if t1*2+t2*4=j then writeln(‘Ji=’,t1,’ Tu=’,t2); end; end. [运行示例]: 输入:40 100 输出:Ji=30 Tu=10 例 3、编程输出规则图案 * *** ***** ******* ********* *********** [分析与算法选择]: 对于平面规则图案的输出,一般用一个两重循环来实现,在实现时我 们主要从以下几个方面来考虑: 1. 有多少行,一般用外循环来控制; 2. 每一行的起始位置跟行有什么关系,通常是用 write(‘’:有关行的表 达式)的形式来控制输出的空格数; 3. 每一行有多少个输出项(列) ,用内循环来控制输出; 4. 具体一个输出项跟行、列有什么关系,直接输出相关输出项有关行 和列的表达式。 本题中要输出的图案是 6 行,每行的个数不定,其中第一行的 1 个, 第二行为三个??,可以从中归纳出第 I 行为 2*I-1 个。 第一行的起始位置为 6,第二行的起始位置为 5,第三行的起始位置为
99

4??,从中可以归纳出第 I 行的起始位置为 7-I,换句话说就是在前面要先 输出 6-I 个空格。 [程序清单]: program exampl8_3; var I,j:integer; begin for I:=1 to 6 do {一共 6 行} begin write(‘’:6-I); {每一行先输出的输出空格数} for j:=1 to 2*I-1 do write(‘*’); {每一行输出的个数与内容} writeln; {换行} end; end.

练习: 编写程序 1.输入两个自然数 M,N,输出它们的最大公约数和最小公倍数。 2. 编程输出规则数字图形。 (1) 111111111 (2)1 (3) 6 22222222 12 56 33333333 123 456 44444444 1234 3456 55555555 12345 23456 66666666 123456 123456 (4) 1 (5)12345654321 121 123454321 12321 1234321 1234321 12321 123454321 121 12345654321 1

100

(6)

1 121 12321 1234321 123454321 12345654321 123454321 1234321 12321 121 1

[部分参考程序]: program ex8_1; var m,n,m1,n1,r:integer; begin readln(m,n); m1:=m;n1:=n; r:=0; repeat r:=m1 mod n1; m1:=n1; n1:=r; until r=0; writeln(‘Max=’,m1); writeln(‘Min=’,m div m1*n) ; end. program ex2_1; var i,j:integer; begin for i:=1 to 6 do begin for j:=1 to 6 do write(i); writeln; end; end. program ex2_3; var i,j:integer; begin
101

for i:=1 to 6 do begin write(‘’:6-i); for j:=7-i to 6 do write(j); writeln; end; end. program ex2_4; var i,j:integer; begin for i:=1 to 6 do begin write(‘’:30-i); for j:=1-i to i-1 do write(i-abs(j)); writeln; end; end. program ex2_5; var i,j:integer; begin for i:=6 downto 1 do begin write(‘’:30-i); for j:=1-i to i-1 do write(i-abs(j)); writeln; end; end. program ex2_6; var i,j,k:integer; begin for i:=-5 to 5 do begin k:=6-abs(i); write(‘’:30-k); for j:=1-k to k-1 do write(k-abs(j)); end; end.

writeln;

102

第九章 字符串和数组
Turbo-pascal 的数据类型分为三种类型:简单类型、构造类型、指针类 型。前面介绍的整型、实型、布尔型以及枚举类型等都是简单类型,而构造 类型有字符串、数组、记录、集合、文件类型。描述一个构造类型特征的是 其成分的类型和它的构造方法。 因此对于构造类型, 主要去考虑如何构造即 其构造方法。指针类型是一种特殊的数据类型,它涉及到动态存储分配。

一、字符串类型定义和变量说明
1.定义 type 变量标识符=string[常数]; 还可以使用不带字符串最大长度(即不用方括号)的字符串定义,此时 取时大长度的缺省值 255,形式为:type 变量标识符=string; 例:type class=string[10]; name=string[20]; address=string; 定义了三个字符串类型,最大长度为别是 10,20,255。 2.字符串变量说明 字符串变量与简单类型变量说明一样,有两种形式:一是先写字符串 类型定义, 后用其进行变量说明; 二是直接将字符串类型写于变量说明之中。 曾上例子可以写出如下的字符串类型变量说明: var class1, class2: class; myname, yourname,hisname: name; heraddress: address; 也可以直接说明: var class1, class2: string[10]; myname, yourname, hisname: string[20]; heraddress: string; 3.字符串长度 为了记录一个字符串的实际长度即有效字符的长度,系统在所有字符 串变量前保留一个不可见字符,称它为长度字节,因此 turbo-pascal 编译器 为每一字符串变量在内存中所分配的字节数 (一个字符占一个字节) 是其长 度加 1。在长度字节中存放的是这样一个字符:其相应的 ASCII 序数值为该
103

字符串变量的当前实际长度。由于系统允许对一个字符串变量进行整体访 问, 也可以对字符串变量中的各个字符逐个地访问, 第二种访问应指定某字 符在字符串中的位置即下标, 如 myname[1]表示字符串变量 myname 的第一 个字符,myname[2]表示第二个字符,依次类推。因此可用 myname[0]表示 在长度字节中所存放的字符,而字符串的实际长度可用 ord(myname[0])求 得。 也可以直接用系统函数来求字符串的长度,如 length(myname)。 4.字符串与字符 字符串变量和字符类型 char 相兼容,可把 char 视作长度为 1 的字符串 类型,因而它们在字符串表达式计值时可混合使用。如‘A’可看作是字符, 也可视为字符串。 但字符串类型和字符类型在内存中的存储形式不同。 另外 允许长度为 0 的空串{此时字符串的存储仍然要一个字节,用来存放其长度 字符},但字符类型必须也只能有一个字符。 5.字符串的常数定义与类型常数定义 可将任意字符串定义成一个常数标识符,以供程序各处引用。字符串 常数定义的一般形式为: const 常数标识符=字符串常数; 其中字符串常数是用单引号括起的字符串序列。如: const heading=’Difference between string variable and string typed constant’; splitline=’-------------------------------------------------------------------------’; 分别以常数标识符 heading 表示一个表头信息,splitline 表示分隔线。 字符串类型常数定义要规定字符串类型及所取的初始值,形式为: const 类型标识符:字符串类型=字符串常数; 如:const Password:string[7]=’private’; TrueString:string[5]=’yes’; FalseString:string[5]=’no’; SchoolName:string[4]=’NTZX’; NewLine:string[2]=#13#10; {通常通过“#数字”描述无法输入的字符, 其中数字为相应字符对应的 ASCII 码值}

二.字符串表达式和赋值语句
1.字符串表达式 通过字符串运算符将字符串常数、 字符串变量、 字符串函数等组成起来 的式子就是字符串表达式, 由字符串表达式进行运算可形成新的字符串。 运
104

算符主要是+,用来进行字符串的连接。如: 说明了常数 const pas=’pascal’ 就可以有以下的字符串表达式: ‘Turbo’+pas+’ is better than ‘+’standard ‘+pas 字符串连接的结果还是字符串,如果串和长度超过 255,则超过的字符 将被截去。 可使用关系运算符=,<,>,<=,>=,<>比较任意两个字符串的大小,这些运 算符的优先级别比连接符“+”号低,要注意这点,该加括号的地方要加括 号。关系运算符用于字符串操作时,其结果还是为布尔值,在比较两个字符 串时,两者自左向右逐个比较相对应字符的 ASCII 码值,只有当两个字符 串长度相等且对应字符完全相同时才认为这两个字符串相等。 如果两个字符 串长度不等, 但短字符串与长字符串前面的字符逐个相等, 则认为短字符串 小于长字符串。字符串的比较大小其实就是比较字符的 ASCII 码值的大小, 有点跟字典顺序相似。 2.字符串赋值语句 赋值语句可应用于字符串类型,它表示计算右部字符串表达式的值, 并将结果赋予左部字符串变量。 允许以字符串变量中某一个字符位置赋值即 此时实际上是字符的赋值。如: var hisname:string[15]; ………….. hisname:=’Mr.’+’ Yueking’ 又如:var s1:string[20]; ………. For i:=1 to 20 do s1[i]:=chr(64+i);

三、数组
在代数上我们常常这样写:a1,a2….ai….a100(0<i<101),通过 i 来指明具 体的 ai,如 i=10 时代表 a10,在 pascal 语言里我们也希望能够类似地描述。 从前面的变量名里我们已经知道,a1,a2..ai 彼此之间是相互独立的,并没有 必然的联系。如要象代数上那样,可以使用数组。 数组其实是一组相同值类型的变量的集合,这些变量共用一个名,彼 此之间通过下标来区别。如定义了数组 a,它的下标可以从 1 到 100,那么 就可以直接通过 a[i]来指明第 i 个量,如 i=10,a[i]指的是 a[10]。 1.数组的说明 可以先通过 type 标识符=array[下标范围] of 值类型; 然后再在变量说明里引用。
105

如:type array1=array[1..100] of integer; var a,b:array1; 也可以直接在变量说明里说明: 变量名:array[下标范围] of 值类型; 如:var a,b:array[1..100] of integer; 描述下标范围一般通过离散(有序)类型,如从一个整数到另一个整数, 或者从一个字符到另一个字符等。如: var a:array[-5..5] of integer; c:array[1..20] of char; d:array[‘a’..’z’] of integer; 2.数组的使用 刚才我们已从代数上使用说明了数组使用的优点,特别是要保存的量 比较多且这些量之间又有某种联系。 如要将若干数重新根据由大到小或由小 到大的顺序排序时,这些数都是要保留的,只是位置换了而已,此时用数组 变可以实现。后面我们会专门介绍排序的算法的。 例 9_1:让计算机随机产生 100 个 0 到 1000 之间的整数,输出其中最大的 数。 [分析与算法选择]: 随机产生数可以用其 random 函数, 产生的 100 个数依次存放在 a[1]到 a[100] 里。选最大数时可用“擂台比武”的思想,假设最大数放在变量 max 里, 如果 a[i]比 max 大,则取而代之,i 从 1 到 100 重复此操作。 [程序清单]: program maxdigit; var a:array[1..100] of integer; i,max:integer; begin randomize; for i:=1 to 100 do a[i]:=random(1000); max:=a[1]; for i:=2 to 100 do if a[i]>max then max:=a[i]; writeln(‘Max=’,max); end. 例 9_2 键盘输入 40 个 5 位以下的整数,最后分批输出其中的奇数和偶数。 [分析与算法选择]: 判定一个数是奇数或偶数比较简单,如果不是要分批输出可以一边输
106

入一边判定,现在要分批输入所以输入跟输出的过程要分开,输入的 40 个 数要先存放起来,通过数组很方便。 [程序清单]: program digit; var a:array[1..40] of integer; i:integer; begin for i:=1 to 40 do read(a[i]); writeln; for i:=1 to 40 do if odd(a[i]) then write(a[i]:5); writeln; for i:=1 to 40 do if not odd(a[i]) then write(a[i]:5); writeln; end.

[练习]:
1、最简单的打字练习程序 计算机随机出 50 个字母(大写、小写的都可能有) ,在屏幕上显示出这 50 个字母, 然后等待用户输入, 最后计算机根据用户输入的字符给出一个得分 (输对一个字符得 2 分) 。 提示:52 个字符都有可能产生, ‘A’到‘Z’的 ASCII 值 65 到 90,而‘a’ 到‘z’的 ASCII 值为 97 到 122。 如果随机产生的数据放在变量 S 里,那么有: if s<27 then …ord(64+s) else …..ord(96+s-26) 2、四则运算 让计算机随机产生 10 道 100 以内的四则运算题(要求运算的数及运算 的结果都是在 0-100 之间,如果是除法运算要保证能整除) 。 程序要能将十道题保存, 且能保存用户的答题情况, 最终输出用户的得 分,如果用户对某道题 5 次都没有答对,最后要将这道题重新显示出来。 [分析与提示]: 对于一道题目的产生,可以用随机函数产生两个操作数和操作符,如果 用二维数组来保存所有产生的题目,可以这样: t[1..10 表示题号,1..4,为 1 时表示第一个操作数,为 2 时表示第二个操
107

作数,为 3 时表示操作符对应的序号如 1234 分别表示+-*/ ,为 4 时表示正 确的结果] 如 t[5,1]=48 t[5,2]=6, t[5,3]=4 , t[5,4]=8 表示第 5 题为:48/6=8 对于用户的答题情况,可以另外开辟一个数组来存放每一题几次答对的 (1-5 表示 1 到 5 次答对的,为 6 表示 5 次都没有答对) ,也可以加到 T 数 组中来,如用 t[I,5]表示第 I 题用户答题情况。 对于操作符,可以先定义一个字符串常量‘+-*/’ ,然后根据值直接从 中取。 CONST OP:STRING[4]=‘+-*/’ ; 如上面有关 48/6 的式子的输出可以写为: write(t[5,1], op[t[5,3]], t[5,2], ’=’ ); program ex9_2; const op:string[4]='+-*/'; var t:array[1..10,1..5] of integer; i,j,k,m,f,fs:integer; begin randomize; for i:=1 to 10 do begin j:=random(99)+1; k:=random(99)+1; f:=random(4)+1; if j<k then begin m:=j;j:=k;k:=m;end; if f=3 then if k>10 then k:=k div 10+1; if f=4 then begin k:=k div 10+1; j:=j div k*k; end; case f of 1: m:=j+k; 2: m:=j-k; 3: m:=j*k; 4: m:=j div k; end; t[i,1]:=j; t[i,2]:=k; t[i,3]:=f; t[i,4]:=m; end; for i:=1 to 10 do begin j:=1; repeat write('Number ',i,':',t[i,1],op[t[i,3]],t[i,2],'=');readln(k); j:=j+1;
108

until (k=t[i,4]) or (j=6); if k=t[i,4] then begin j:=j-1; fs:=fs+10-(j-1)*2; end; t[i,5]:=j; end; writeln('Defen=',fs); for i:=1 to 10 do if t[i,5]=6 then writeln('Number',i,':',t[i,1],op[t[i,3]],t[i,2],'=',t[i,4]); end.

109

第十章 枚举算法入门
一、什么是枚举
“枚”就是一个一个地做。 “举”就是列举。枚举就是一个一个地列 举。应用到程序中,枚举有许多表现形式,比如把所有的组合都扫描一遍, 找出符合要求的组合。举个简单的例子,找素数。1 什么都不是,2 是素数, 3 是,4 不是,5 是??,如此把所有的自然数(当然是不可能的,只能尽 量多)都找一遍,就能找出所有的素数(如果可能的话)。 可以这么说,枚举是最简单,最基础,也是最没效率的算法。枚举拥有 很多优点,以致于他能够活到现在而不被淘汰。首先,枚举有超级无敌准确 性,只要时间足够,正确的枚举得出的结论是绝对正确的。其次,枚举拥有 天下第一全面性,因为它是对所有方案的全面搜索,所以,它能够得出所有 的解。

二、例程
例 10_1 找偶数。 [程序要求]: 找出 30000 以内所有的偶数,一个个地输出来。 [分析与算法选择]: 从 0 开始到 30000 一个个地看是否是偶数,如果是则直接输出。 [参考程序]: program example10_1; var i:integer; begin for i:=0 to 30000 do {为什么要 30000 呢? integer 类型是从 32767 到+32767 之间的整数。 如果你要再大一点,可以用 longint 类型的 } if i mod 2=0 then write (i:8); {i mod 2 表示 i 给 2 除之后的余数,如 9 mod 2=1,5 mod 7=5} end. 完了, 就是这么简单, 也许不用说你就知道是什么意思, 就是把 0-30000 之间的整数都找一次, 如果它能够被 2 整除, 就输出来, 如果不能就不输出。 例 10_2 求出给定的一个自然数 n 以内的素数。 [分析与算法选择]:
110

一个整数 n 如果是素数那它有什么特征?哦, 它只能够被 1 还有它本身整除。 所以除了 1 和 n 之外,其它的从 2 到 n-1 之间的整数,都必须不能整除 n。 那么我们就取一个 n,造一个循环语句,判断从 2 到 n-1 之间的整数中,有 没有能整除 n 的,有的话,哪怕只有一个,那 n 都不是素数。懂了吗?上面 那个方法, 确实有许多可以偷懒的地方, 编程的一个大原则就是能有多懒就 要多懒(当然是要在正确的前提下了。 )还是不要叫懒吧,叫它优化,一个 程序的效率, 就取决于算法的好坏, 一个好的高效率的算法和一个低效率的 算法,所需要的时间相差很大,有时是一个只要几秒而另一个却要几千年。 下面是对枚举范围的逐步缩小: 1、比 n 的平方根还大的整数,当然不能整除 n。所以,这一部分我们不 用管它。 2、如果从 2 到 n 的算术平方根取整后得到的整数(这个整数用 Pascal 表 达式描述为 trunc (sqrt(n)), 注意用的是 trunc 函数而不是 int 函数) 之间有一 个数能整除 n, 那我们对 n 的判断就应该结束了, 而没必要再判断下面的数。 3、你想一下如果一个数不能被 2 整除,那它还能够被 4,被 6,被 8 等 等的 2 的倍数整除吗?当然不能。所以,我们又得出了一个结论。只要一个 数 n 不能被所有的从 2 到 trunc(sqrt(n))之间的素数整除, 那它就一定是素数。 这样,我们就把这个问题的算法,优化了不少,下面给出了第二种情况的 程序, 自己写出其它两种情况相关的程序。 值得一提的是第三个优化的方法 所涉及的数据结构略微复杂了一点, 如果初学者能力不足, 那只用前面两个 优化的方法也行。 [程序清单]: program meiju;{枚举法求 N 以内素数} const n=8; {假设 n 为 8,其它的值也一样} var i,j,k:integer; begin write(2); for i:=3 to n do begin j:=2; k:=trunc(sqrt(i)); while (j<=k) and (i mod j>0) do j:=j+1; if j>k then write(i:4); end; writeln; end.

111

三、小结
枚举就是在全集中的元素一个一个拿出来试, 有点象小孩数糖果, 由于 它的运算量相对较大, 所以, 我们应该注意尽可能地限制一些无谓运算的出 现, 这是搜索所要求的最重要的技巧, 以后我们还会陆续地介绍其他一些减 少运算量的方法。 大部分情况下枚举算法的实现主要通过循环来完成, 确定好检查范围和 检查条件, 然后用循环根据这个范围来检查, 当符合检查条件时就进行相关 处理。

习题:编写程序
1、发奖品问题 [问题描述]: 学校某班里要表彰 5 位学生,老师要将 5 件互不相同的奖品发给这 5 位同学。一共有哪几种不同的发法? [输出格式]: 先输出每一种奖品分发法,具体一种分法由一个五位数构成,如 12345 表示第一个同学发第 1 件奖品, 第二个同学发第 2 个奖品, 第三个同学发第 3 个奖品??,也就是第 I 个数字表示第 I 个同学发的是某个奖品。 最后再输出总的分法数量。 2、百钱买百鸡问题: [问题描述]: 有一个人有一百块钱, 打算买一百只鸡。 到市场一看, 大鸡三块钱一只, 小鸡一块钱三只,不大不小的鸡两块钱一个。现在,请你编一程序,帮他计 划一下,怎么样买法,才能刚好用一百块钱买一百只鸡? [输出格式]: 先输出所有可能的买法,最后输出总的买法数。 3、各位数字之和为 8 [问题描述]: 每一个数都可以求出它各位数字的和,如一个自然数为 123,那么它的 各位数字之和为:1+2+3=6。 现在要求你求出 32767 以内的正整数中各位数字和为 8 的所有数, 并统 计其个数。 [输出格式]:
112

先从小到大以一行输出十个符合条件的数的方式输出所有符合条件的 数。如第一行为:8 17 26 35 44 53 71 80 。 最后一行输出符合条件的数的个数。 4、农场主的篱笆 [问题描述]: 农场主有 100 块 1 米的正方形篱笆, 他想用这些篱笆搭一个一面靠墙的 长方形圈,想使圈的面积最大应如何搭建?请你邦他编程解决。

分析与解答:
第一题: 此题类似于全排列问题(全排列问题在后面的中级本里有专门的章 节,它有好几种实现方法),也就是 1 到 5 如何编排到五个位置, 用枚举法是一种方法,每个人拿的奖品都可能是 1 到 5,通过五重 循环来检测,当 5 个人当中没有奖品重复的时候就是一种分法。 [参考程序]: program ex10_1; var i,j,k,m,n:1..5; t:integer; begin t:=0; for i:=1 to 5 do for j:=1 to 5 do for k:=1 to 5 do for m:=1 to 5 do for n:=1 to 5 do if (i-j)*(i-k)*(i-m)*(i-n)*(j-k)*(j-m)*(j-n)*(k-m)*(k-n)*(m-n)<>0 then begin
113

write(i,j,k,m,n,'':5); t:=t+1; end; writeln('Total=',t); end.

第二题 这是一个标准的枚举算法,分别用三个变量表示大鸡、小鸡、不大 不小的鸡的只数,对各种鸡可能的只数进行检测,如果它们的总数为 100 只,并且总钱数是 100 就符合条件。 program buy; var a,b,c,s:integer; begin s:=0; for a:=0 to 33 do {大鸡只数的范围} for b:=0 to 50 do {中鸡只数的范围} if a*3+b*2<=100 then {如果此时钱数不超过 100,加此条件可以缩小 检测范围,从而提高速度,不加此条件也可以} begin c:=(100-a*3-b*2)*3; {从钱数方面来考虑,100 元用剩下的全买小鸡} if a+b+c=100 then {在花 100 元钱的情况下如果买了 100 只鸡} begin s:=s+1; {买法数增加 1} writeln(‘big=’,a,’ no big& no little=’,b,’ little=’,c); {输出一种买鸡方案} end; end; writeln(‘total=’,s); end. 也可以从钱数开始考虑, 用三个变量分别表示买三种鸡的钱数, 只不过 买大鸡的钱数是 3 的倍数, 买中鸡的钱数是 2 的倍数, 而买小鸡的钱数只要 是整数就行。 progarm buy2; var a,b,c:integer; s:integer; begin s:=0; for a:=0 to 100 do for b:=0 to 100-a do if (a mod 3=0) and (b mod 2=0) then begin c:=100-a-b;
114

if a div 3+b div2+c*3=100 then begin writeln(a div 3:4,b div 2:4,c*3:4); s:=s+1; end; end; writeln(‘total=’,s); end. 第三题 用枚举的办法是将 1 到最大的整型数列举出来, 判定它的各位数字之和 是否是 8,如果是则输出,并将统计其个数的变量增加 1。 [参考程序]: program ex10_3; var i,j,k,h,t:integer; begin for i:=1 to 32767 do begin j:=i; h:=0; {先用一个变量 j 记录 I 的值,对 j 进行拆分,如果对 I 直接进行拆分会影响循环的执行。 另外每一次求各位数字之和前都要将记录 和的变量清 0, 否则也会影响结果, 因此变量的初值很重要, 自己体会这点} while j>0 do {对 j 进行拆分,求它各位数字的和} begin h:=h+j mod 10; {将 j 的个位数加到 h 里} j:=j div 10; {j 去除个位数形成新的数} end; if h=8 then {如果和为 8 那么输出当前检测的数并计数} begin write(i:8); t:=t+1; end; end; writeln; writeln('Total=',t); end. 第四题 将各种“围法”列举出来,一个个地计算其面积,挑出其中面积最大的 一种方法。而选最大的方法就是所谓的“擂台比武”的方法,设一个变量来 存储最大的面积,初始值为 0,如果某种方法比它的值大就取而代之,最后 所有的方法列举完,它的值就是最大的。设靠墙的两边长 a,则对着墙的边 长 b 为 100-2*a,a 的范围最小为 1 最大为 49,从而确定了枚举的范围。 [参考程序]:
115

program ex10_4; var a,b,max,maxa,maxb:integer; begin for a:=1 to 49 do begin b:=100-a*2; if a*b>max then begin max:=a*b; maxa:=a;maxb:=b;end; end; writeln('The max_square=',max); writeln('The three side is:',maxa:5,maxb:5,maxa:5); end. [运行结果]: The max_square=1250 The three side is: 25

50

25

[思考与提高]: 上面的程序中如果一个围法比当前的最大面积还要大, 就记录了三个变 量的值, 其实对于边长只要记住一个边的长就行了, 输出时再用一个表达式 输出其它边的长。自己修改程序。

116

第十一章 数组应用例程
前面介绍过字符串与数组,其实字符串可以理解为一种特殊类型的数 组:一维的字符型数组,它的使用可数组差不多,但是它们还是有许多不同 的, 如字符串在固定有第 0 个字符其 ASCII 码值等于字符串的长度, 而一维 字符型数组只能在其定义的下标范围内使用。 数组可以有多维的,如要存放 60 个学生每人 8 项数据,可以定义如下 的二维数组: var xs:array[1..60,1..8] of integer; 说明了 xs 是一个二维的数组变量,第一个下标可以从 1 用到 60,第二 个下标可以从 1 用到 8。有了如上的说明,那么下面的引用在程序中都是合 法的:xs[1,8],sx[5,1],sx[60,2],s[I,j]等。 有了数组以后,许多算法就可以实现了。 例 11-1.编写程序,计算并输出 2 的各次负幂表,只要求求得 2 的负 100 次方的精确表示。 [分析]: 根据要求写出 2 的负整数次方,用符号^表示幂次(方) ,容易写出: 2^(-1)=0.5 2^(-2)=0.25 2^(-3)=0.125 2^(-4)=0.0625 2^(-5)=0.03125 2^(-6)=0.015625 ?? 如果用 real 型变量存放计算结果, 由于 turbo-pascal 系统对于一个 real 型数据至多能精确到 11 位到 12 位有效数字,从而对于如: 2^(-30)=0.000000000931322574615478515625 就不能将它精确地表示出来,即使是 extended 类型也没有用,我们希望所 输出的 2 的负整数次方的精确表示,让计算机象人一样来进行计算与存贮 数据,这便是算法里所说的“高精度运算” 。如果能找出一定的数学规律使 计算机运行程序花的时间更少 (虽然计算机运行速度快, 但还是要花时间的, 好的算法与差的算法运行时间相差很多的) ,那是更好的。 一般来说,对于一个问题,首先要能保证其算法的正确性,其次再去考 虑算法的优化,考虑如何提高效率。 2 的负整数次方都是通过十进制小数的形式来表示的,由前面的几个 2 的负整数次方的式子可以知道,小数位数跟负整数次方的整数相同,如 2 的负 5 次方为 0.03125,小数点后共 5 位,第 i 位用 d[i]表示有: d[1]=0,d[2]=3,d[3]=1,d[4]=2,d[5]=5 现在要求 2 的负 6 次方,可用 2 的负 5 次方再除 2,可设法对 2 的负 5 次方从 i=1 起逐位相除。 对于每一个十进制小数, 被 2 除可能出现两种情况: 能被 2 整除或不能被 2 整除。取其商数作为该位新的数值,而将余数(0 或 1)保留并“进位”到下一位十进制数位的运算,根据这一原理,可逐位
117

求得 2^(-6)的数值: d[1]=0,d[2]=1,d[3]=5,d[4]=6,d[5]=2,d[6]=5 因此, 求 2 的各次负幂所选择的算法是在上一次所求得的基础上逐位相 除,余数进位。实际上最后一位不计算就能知道它永远是 5。 因为本题最多求到 2 的负 100 次方,帮可说明一个一维数组变量,它 的数组元素个数是 100,每个数组元素用以存放一位十进制数,另外在列表 输出 2 的各个负整数次方时,只要输出相应位就行了。 [程序清单]: program NegPower; const max=100; var i,k,r,n:integer; d:array[1..max] of 0..9; begin writeln('2^(-1)=0.5’); d[1]:=5; for k:=2 to max do begin write('2^(-',k,')=0.'); r:=0; for i:=1 to k-1 do begin r:=r*10+d[i]; d[i]:=r div 2; r:=r mod 2; write(chr(d[i]+ord(‘0’))); end; d[k]:=5; write(‘5’) end; end. 例 11-2.编写程序实现 m 阶魔方阵,设 m 为奇数。 [分析]: 魔方阵是这样一个方阵,由 1,2,3,4??m*m 组成,其行、列、对角 线元素之和均为常数,比如 m=3 时的方阵为: 4 3 8 9 5 1 和数=15 2 7 6 m=5 时的魔方阵可以为: 11 10 4 23 17 18 12 6 5 24 25 19 13 7 1 2 21 20 14 8
118

9 3 22 16 15 仔细观察上两个方阵可以找出如下的数字“走”的规律:首先将 1 放置 在第(m+1)/2行、第m列的位置上。要放的数增加 1,将上一数放的 位置行号和列号都增加 1,如果增加后超过边界了(即大于 m 了) ,则相应 的超边界的行号或列号变为 1,由新的行号和列号确定的新位置就是新数要 放的位置,但有时会有“撞车”的现象,也就是该位置上已放过数字了,此 时不能再放了, 怎么办?不好走就退回原地再换个方向吧, 哪个方向好呢? 就是左转了,因为这种情况下一般好象是左边空的。 (左转的办法是行号不 变,列号减 1,此时要不要考虑出界的情况呢?按理应考虑出界的情况的, 不过我试了好几个数据都没有发现这种情况, 为安全起见, 还是加个判定吧) 上面这个填数过和直到 m*m 填完为止。 [程序清单]: program mf; const max=25; var m,i,j,k,t1,t2:integer; a:array[1..max,1..max] of integer; begin while (m<3) or (m mod 2=0) do readln(m); i:=(m+1) div 2; j:=m; k:=0; {初始化} while k<m*m do begin k:=k+1; a[i,j]:=k; {填数} t1:=i; t2:=j; {为了能精确地退回,先记住当前的位置 I,J} i:=i+1; {行增 1} j:=j+1; {列增 1} if i>m then i:=1; {出界处理} if j>m then j:=1; {出界处理} if a[i,j]>0 then {撞车处理} begin i:=t1; j:=t2-1; if j<1 then j:=m; {出界处理} end; end; for i:=1 to m do begin for j:=1 to m do write(a[i,j]:3);
119

writeln; end; end. [思考与提高]: 有些同学可能习惯从第一行的中间开始填数字 1,其结果跟上面的方法 本质上是一样的,只要通过旋转就可以得到上面的程序运行结果。因此 1 从 4 个边上开始填应是相同的。 填的过程不同的是行、 列变化的不同以及碰 到撞车时转向的不同。 这种排列数字魔方的方法的正确性有待于从数学上来证明。 如果你用枚 举的办法找出符合要求的结果就不需证明。 用枚举算法时关键是如何缩小枚 举的范围,因为 1 到 m*m 的数字组合是很多的,不可能一一枚举过去,如最 小的 m 为 3 时 1 到 9 的排列就有 9! 种, 就要用长整型的变量来控制, 当 m=5 或更大时枚举量已是一个天文数字了。 所以要考虑如何分组, 将其分为若干 组,每组的和都是相同的(为 m*(1+m*m)/2) 。感兴趣的话可以试试这种方 法。 例 11-3:用筛选法求 10000 以内的素数。 [分析]: 素数从 2 开始,先假设从 2 到 n(这里 n=10000)全是素数,可以定义 一个标记数组,这个数组的值可以用布尔型的(结果为 TURE 或 FALSE) ,也 可以用 0、1 两种数值来表示是否是素数的状态(有没有被删除) 。 先从 2 开始将其中 2 的倍数筛去(不包括 2 自己,即删除 2 的 2 倍、3 倍、??n div 2 倍) ; 再往后找出第一个素数(即第一个没有被删除的数,如 2 后是 3)再筛 去它的倍数(2 倍、3 倍、??、n div 3 倍) ; ?? 一直到以 n 的算术平方根(100)以内的素数为基数筛选结束为止。 最后输出没有被删除的数。 由于程序中是用两个标记数值来记录是否被删除的状态, 对于重复删除 的情况(如 6 既被 2 删除又被 3 删除) ,只是将其值改为表示删除的值,多 次赋值并不影响结果。 [程序清单]: program Find_Prime; var a:array[2..10000] of 0..1; i,j:integer; begin for i:=2 to 10000 do a[i]:=1; {先假设全为素数} for i:=2 to 100 do {以从 2 到 100 之间的素数为基数开始筛} if a[i]=1 then for j:=2 to 10000 div i do a[i*j]:=0;
120

for i:=2 to 10000 do if a[i]=1 then write(i:5); writeln; end. 例 11-4 自然数的高精度加法 [问题描述]: 有两个自然数,其位数不超过 200 位,要求求出它们的和。 [输入]: 两个字符串 s1,s2,分别表示两个相加的自然数。 [输出]: 两个自然数相加的结果。 [样例]: 输入 123456789987654321 98765432100123456789 输出 123456789987654321+98765432100123456789=98888888890111111110 [分析与算法选择]: 对于输入的两个字符串, 要将其每一位转换成相应的数字, 并且要按位 对齐相加,并考虑进位因素,结果存入到一个数组里。 先来解决第一个问题: 如何将一个字符转成相应的数字。 我们知道每一 个基本字符都有一个对应的 ASCII 码值,对于‘0’ 、 ‘1’ 、??‘9’这十个 字符,它们的 ASCII 码值是连续的。如果你能记住‘0’的 ASCII 码值最好 了,记不住也不要紧,对于一个基本数字字符要将其转换为数字,用这样的 表达式就行了:ord(ch)-ord(‘0’)。 [程序清单]: program example11_4; var s1,s2,t:string; a:array[1..520] of integer; i,j,len1,len2:integer; begin readln(s1); readln(s2); write(s1,'+',s2,'='); len1:=length(s1); len2:=length(s2); if len1<len2 then begin t:=s1; s1:=s2; s2:=t; len1:=len2; len2:=length(s2); end;
121

for i:=1 to len2 do a[i]:=ord(s1[len1-i+1])+ord(s2[len2-i+1])-2*ord('0'); for i:=len2+1 to len1 do a[i]:=ord(s1[len1-i+1])-ord('0'); for i:=1 to len1 do begin a[i+1]:=a[i+1]+a[i] div 10; a[i]:=a[i] mod 10; end; j:=len1+1; if a[j]=0 then j:=j-1; for i:=j downto 1 do write(a[i]); writeln end.

[练习]:
第一部分 阅读程序写出运行结果 1. 2. 第二部分 完成程序 第三部分 编写程序 1.编程输出若干行的杨辉三角形: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 ?????????????? 先用二维数组实现,再考虑如何用一维数组来实现。 [提示]: 先为考虑输出格式,只看原始数据如下: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1
122

?? 如用二维数组 a[i,j]来存放结果,i 表示行号(第几行) 、j 表示列号 (这一行的第几个元素) 。找出规律: a[i,j]:=a[i-1,j-1]+a[i-1,j] (j>1 且 j<i 时) a[i,j]:=1 (j=1 或 j=i 时) 这样用循环来求出各位上的数字,最考虑输出格式。 用一维数组可以节省存储空间,计算一个就输出一个,但要注意顺序。 [提高]: 如果用二维数组来存储数据,但是其中一个下标(如第一个下标)只用 1 和 2,1 表示上一行的数据,2 表示当前行的数据,程序应如何写? a[2,i]:=a[1,i-1]+a[1,i]; 当输出完一行后就将当前行变为上一行,为下一行计算做准备: a[1]:=a[2] 在许多程序设计的过程中, 如果数组开得太大, 可能会超过指定内存的 大小,在这种情况下要考虑数据本身的特点,不一定要全都保存,上述方法 是一种比较好的方法。 2.编写一程序,对输入的十进制数,转换为等价的二、八、十六进制数并 输出转换结果。 [输入样例]:65535 [输出样例]: 65535(10)=1111111111111111(2) 65535(10)=177777(8) 65535(10)=FFFF(16) 3.对于阶乘函数,即使自变量很小,其值也会相当大,如: 10!=3528800;25!=15511210043330985987000000 如果用 integer 型数来表示阶乘,最多只可以表示到 7! ,用 longint 类型 最多只能到 12! 。请你设计一个程序,当输入一个正整数 N(1<N<100)时, 输出 N!的精确表示。 4.输入两个自然数 m、n(1<=m,n<=10 ) ,输出 m/n 的结果,要求精确到小数 点后 50 位,并考虑到四舍五入的因素。 [输入样例]: 2 3 [输出样例]: 2/3=0.666666666666666666666666666666666666666666666666667 [提高]: (1) 如果输入的自然数有可能超过长整型范围,在 200 位以内,并要求 相除结果有 250 位有效数字,程序应如何写? (2) 如果输入的不一定是自然数,只保证是正数,而且这两个数的位数
9

123

在 200 位以内,要求保留 250 个有效数字,程序如何写? 5.键盘输入两个自然数 m、n(1<=m,n<=10 ) ,输出 m*n 的结果。 [输入样例]: 123456789 987654321 [输出样例]: 123456789*987654321=121932631112635269 [提高] (1)如果输入的自然数可以超过长整型范围,程序应如何写? (2)如果输入的不一定是自然数,有可能是带小数位的数,程序应该如何 写? 6. “半蛇形数字三角形” 编程输出如下所示的“蛇形数字三角形” 。 要求: 输入一个自然数 n(n<30) ,表示行数; 第一行有 n 个数字,第二行有 n-1 个,??第 n 行只有一个数字; 第一行第一个为 1,以后的走向是从右上到左下,直到这样的走向不能 再进行结束。 另外要求用两种方法来完成程序: 方法 1:用二维数组来存放结果,也说是说先用模拟的方法将结果求出,再 用循环输出; 方法 2:不用数组,直接找规律输出,也就是说找出行列与输出结果之间的 关系,直接通过两重循环输出。 n=9 1 2 4 7 11 16 22 29 37 3 5 8 12 17 23 30 38 6 9 13 18 24 31 39 10 14 19 25 32 40 15 20 26 33 41 21 27 34 42 28 35 43 36 44 45 [第三部分参考程序]: 第一题 方法 1:
124
9

使用二维数组来存放杨辉三角形数据 program ex11_1; var a:array[1..20,1..20] of integer; i,j,n:integer; begin readln(n); a[1,1]:=1; for i:=2 to n do begin a[i,1]:=1;a[i,i]:=1; {第一行的第一个数和最后一个数都是 1} for j:=2 to i-1 do a[i,j]:=a[i-1,j]+a[i-1,j-1]; {第 I 行的第 j 个数等于上一行的同一列与上一行的前一列的数之和} end; {输出部分} for i:=1 to n do begin write('':30-2*i); {考虑到输出效果, 如果每一项占 4 列这里便是 2*I} for j:=1 to i do write(a[i,j]:4); writeln; end; end. 第一题方法 2:用一个一维数组 用一维数组来处理数据, 每算出一行杨辉三角形的数据便输出, 请注意 思考为什么要从右边向左边处理,如果从左边向右边处理会是什么结果? program ex11_1a; var a:array[1..20] of integer; i,j,n:integer; begin readln(n); for i:=1 to n do begin a[i]:=1; write('':30-2*i); for j:=i-1 downto 2 do a[j]:=a[j]+a[j-1]; for j:=1 to i do write(a[j]:4); writeln; end;
125

end. 第 1 题方法 3:二维数组尽可能小 program ex11_1b; var a:array[1..2,1..20] of integer; i,j,n:integer; begin readln(n); for i:=1 to n do begin a[2,1]:=1;a[2,i]:=1; write('':30-2*i); for j:=2 to i-1 do a[2,j]:=a[1,j]+a[1,j-1]; for j:=1 to i do begin write(a[2,j]:4);a[1,j]:=a[2,j];end; writeln; end; end. 数组值变换时可以直接用 a[2]:=a[1]; program ex11_1c; var a:array[1..2,0..20] of integer; i,j,n:integer; begin readln(n);a[1,1]:=1; {一定要给出一个初始值,否则输出的全是 0} for i:=1 to n do begin write('':30-2*i); for j:=1 to i do begin a[2,j]:=a[1,j]+a[1,j-1]; write(a[2,j]:4) end; writeln; a[1]:=a[2]; end; end. 二维数组一个下标的范围是 1 到 2 相当于两个一维数组 program ex11_1d; var a,b:array[0..20] of integer; {a 表示上一行数据,b 表示当前行数据} i,j,n:integer; begin readln(n); a[1]:=1;
126

for i:=1 to n do begin write('':30-2*i); for j:=1 to i do begin b[j]:=a[j]+a[j-1]; write(b[j]:4) end; writeln; a:=b; end; end. 第2题 program ex11_2; const h:string='0123456789ABCDEF'; {定义字符串常量及数组常量} b:array[1..3] of byte=(2,8,16); var c:array[1..32] of integer; m,n:longint; i,j:integer; begin write('Input a number:');readln(n); for i:=1 to 3 do begin m:=n; j:=0; while m>0 do begin j:=j+1; c[j]:=m mod b[i]; m:=m div b[i]; end; write(n,'(10)='); for m:=j downto 1 do write(h[c[m]+1]); writeln('(',b[i],')'); end; end. 第 2 题方法 2 :适合更多进制的转换 program ex11_2a; const b:array[1..4] of byte=(2,8,16,24); {依次转换为 2、4、16、24 进制,这只是一个示例,转换为其它进制的也一 样,只要在这里作修改就行了} var c:array[1..32] of integer;
127

m,n:longint; i,j:integer; begin write('Input a number:');readln(n); for i:=1 to 4 do begin m:=n; j:=0; while m>0 do begin j:=j+1; c[j]:=m mod b[i]; m:=m div b[i]; end; write(n,'(10)='); for m:=j downto 1 do if c[m]<10 then write(c[m]) else write(chr(55+c[m])); writeln('(',b[i],')'); end; end. 第3题 program ex11_3; var a,b:array[1..30000] of byte; {a 数组存放阶乘结果, b 数组存放中间结果, 因为相乘时是拆为一位一位的, 如果不用中间数组来存放,结果将受影响,如 1234*23 分为 1234*3 和 1234*20 两个步骤,如果 a 数组存放的是 1234,相乘结果仍放在 a 里,那么 只能保证第一步 1234*3,第二步*20 时便不是原来的结果了} n,i,j,t,len,s:integer; {n 就是所求阶乘 n!的原始数据,I、j 控制循环,t 临时存放 I 的值,将其 拆这一位一位的跟(I-1) !的结果相乘,len 存放结果的位数,s 存放相乘 时的偏移位数} begin readln(n); len:=1; a[1]:=1; {初始值,1!=1,此时长度为 1} for i:=2 to n do {依次求 2 到 n 的阶乘} begin t:=i;s:=0; {t 临时存放 I 的值,开始时偏移位为 0} while t>0 do {将 t 拆分为一位一位地跟(I-1) !相乘} begin for j:=1 to len do b[j+s]:=a[j]*(t mod 10)+b[j+s]; for j:=1 to len+s do begin
128

b[j+1]:=b[j+1]+b[j] div 10; b[j]:=b[j] mod 10; end; t:=t div 10; s:=s+1; end; len:=len+s; while b[len]=0 do len:=len-1; for j:=1 to len do begin a[j]:=b[j]; b[j]:=0;end; end; write(n,'!='); for j:=len downto 1 do write(a[j]); writeln; end. 第 3 题方法 2: 不考虑求阶乘的 n 太大(3000 以内均合适) ,这样就没有必要将每个乘 数拆分下来再进行相乘, 而是直接跟原来的乘积相乘就行了, 因为原来的乘 积已进行了进位处理,每一位都是 0 到 9 的数,乘积仍然是整数范围。 program ex11_3a; var a,b:array[1..15000] of integer; i,j,n,len:integer; begin writeln('Input n(1<n<3100):'); readln(n); a[1]:=1; len:=1; {先给出 1 的阶乘为 1,有效位数是 1} for i:=2 to n do {依次求出 2 到 n 的阶乘} begin for j:=1 to len do a[j]:=a[j]*i; len:=len+2; for j:=1 to len do {进位处理} begin a[j+1]:=a[j+1]+a[j] div 10; a[j]:=a[j] mod 10; end; len:=len+1; while a[len]=0 do len:=len-1; end;
129

write(n,'!='); for j:=len downto 1 do write(a[j]); writeln; end. 第 4 题 简单的高精度除法 m/n 可以直接通过除法进行运算,反复做的内容执行的是: (1) 求整除结果 对余数 r 乘以 10 整除除数, 并将整除结果保存在数组元 素里,余数初始值为给定的被除数对除数求余的结果。a[I]:=r*10 div n (2)求新余数 r:=r*10 mod n 直到算到第 51 位(指定精确到 50 位,要根据 51 位的值来确定四舍五入) 最后再考虑进位的情况。 [参考程序]: program ex11_4; var m,n,r:longint; i,j:integer; a:array[1..51] of byte; begin readln(m,n); write(m,'/',n,'='); r:=m mod n; m:=m div n;{先求出整数部分和余数} for i:=1 to 51 do begin a[i]:=r*10 div n; r:=r*10 mod n; end; if a[51]>=5 then {考虑最后的四舍五入向上进位的情况} begin a[50]:=a[50]+1; j:=50; while (a[j]=10) and (j>1) do begin a[j]:=0; j:=j-1; a[j]:=a[j]+1; end; end; if a[1]=10 then begin m:=m+1;a[1]:=0;end;{长整型范围内的不会有这 种情况的,因为 m/n 循环节的长度不超过 9 位} write(m,'.'); for i:=1 to 50 do write(a[i]);
130

writeln; end. [程序 2]: 两个 200 位以内的自数数相除,结果保留 250 位有效数字 program ex11_4a; var s1,s2:string; {存放原始相除的两数} a,b:array[0..250] of integer; m:array[1..9] of string; {存放除数的 1-9 倍结果} i,j,k,n,len1,len2,ws,q0:integer; t1,t2:string; {分步除时两个临时变量} begin readln(s1); readln(s2); len1:=length(s1); len2:=length(s2); if s1<s2 then q0:=1; {首次除时位数相同却不够,这样结果的整数位便 达不到 len1-len2+1,而是少一位,这里用变量 q0=1 表示这种情况} {以下先求出除数的 1 到 9 倍结果,仍以字符串保存} m[1]:=s2; k:=len2; for i:=2 to 9 do begin for j:=1 to k do b[j]:=ord(m[i-1][k+1-j])+ord(m[1][k+1-j])-2*ord('0'); for j:=1 to k do begin b[j+1]:=b[j+1]+b[j] div 10; b[j]:=b[j] mod 10; end; if b[k+1]>0 then begin k:=k+1; m[1]:='0'+m[1]; end; m[i]:=''; for j:=1 to k do m[i]:=chr(b[j]+ord('0'))+m[i]; end; if m[1][1]='0' then delete(m[1],1,1); {以下以分步相除:} k:=len2; i:=0; while i<250 do begin inc(i); {变量 i 值增加 1} if length(s1)>k then {如果被除数位数超过除数} begin t1:=copy(s1,1,k); {取出被除数跟除数相同的位数个数字}
131

delete(s1,1,k); {去除被除数部分数字} if t1<s2 then {虽然位数相同但是不够除的情况} begin t1:=t1+s1[1]; {增加一位后肯定够除了} delete(s1,1,1); end; end else {被除数位数小于除数的位数时} begin t1:=s1;s1:=''; {先取出被除数的所有位} while ((t1<s2) and (length(t1)=k)) or (length(t1)<k) do {位数相同但被除数仍小于除数或被除数位数小于除

相关文章:
NOI初级教程
NOI初级教程_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档NOI初级教程_学科竞赛_高中教育_教育专区。目录 1、 前言 2、 计算机基础知识 3、...
全国信息学奥赛NOI培训教程(Pascal 2016)
全国信息学奥赛 NOI 培训教程 全国信息学奥赛 NOI 培训教程 (Pascal 2016) 目录计算机基础知识 ---6 第一章 计算机基础常识 第二章 操作系统简介 第三章 计算机...
Pascal基本教程(2014学生版)
Pascal基本教程(2014学生版)_数学_初中教育_教育专区。名师文件辅导,效果明显,配...IOI(国际奥林 匹克信息学竞赛)把 Pascal 语言作为三种程序设计语言之一, NOI(...
Pascal基本教程(2014学生版)
Pascal基本教程(2014学生版)_学科竞赛_小学教育_教育专区。Pascal 基本教程 第1...IOI(国际奥林匹克信息学竞赛)把 Pascal 语言作为三种程序设计语言之一, NOI(...
广州话初级
粤语学习教程2-提高课(学... 30页 1下载券 广州话拼音方案 2页 免费 广东...noi6 laa3 我等你很久了 你快 D 去啦 nei5 faai3 D heoi3 laa1 你听...
泰语入门
TU NOI DAI MAI? 【土(怒诶)帯买】 泰语入门:泰语常用语-快点、慢点、轻点...泰语基础+基本发音规律 6页 免费 泰语入门基础教程 2页 免费 ©...
C语言入门必做习题100例(五)
(NOI'95.1_2) 在一个园形操场的四周摆放 N 堆石子(N≤100), 现要将...<css css.shtml' target='_blank' title = 'div 视频教程'>div class="td...
非常好的学习程序的网址
//www.jzsx.com/noi/11-3.asp 中山纪念中学信息学竞赛教程 http://www.kogle.net/ Kogle.Net 信息学奥林匹克总站 http://noi.stinfo.net/index0.asp ...
越南语学习入门
mot lan gap go, da dinh menh do, oi duyen so da an bay,cho cho toi dc noi ra khi trong long anh co em... vi may ta ko the danh chu ...
初中化学上册教学视频(完全版整理)
from=my 构 ( 一 ) 构 ( 二 ) 第四单元 自然界的水课题 1 爱护水资源 爱护水资源 1 http://v.ku6.com/show/4ykVcKC0pO0uWcyvNoiqlQ...html?from...
更多相关标签:
瑜伽视频教程初级 | 瑜伽视频教程初级全套 | 网页制作初级教程 | 肚皮舞初级教程 | 左轮吉他初级入门教程 | 减肥瑜伽初级教程 | 初级摄影教程 | 瑜伽球视频教程初级 |