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

pascal语法讲义-第七讲


百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

第七讲 数组与字符串
一、一维静态数组
我们先来思考一个问题。 例题 1.4.2.1.1:读入 3 个数,将之倒序输出。 想必这个程序对大家来说没有难度。 program p1_4_2_1_1(input,output); var a,b,c:longint; b

egin readln(a,b,c); writeln(c,' ',b,' ',a); readln(); end. 下面我们来思考一个升级版的问题: 例题 1.4.2.1.2:读入 1000 个数,将之倒序输出。 这个程序对于大家来说肯定也是可以搞定的, 只不过相对而言比 较麻烦,这里我们提供一个生成该程序源文件的程序。 program p1_4_2_1_2_producer(input,output); var i:longint; begin assign(output,'p1_4_2_1_2.pas'); rewrite(output); writeln('program p1_4_2_1_2(input,output);');
第 1 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

write('var '); for i:=1 to 999 do write('a',i,','); writeln('a1000:longint;'); writeln('begin'); write('readln('); for i:=1 to 999 do write('a',i,','); writeln('a1000);'); write('writeln('); for i:=1000 downto 2 do write('a',i,','); writeln('a1);'); writeln('readln();'); writeln('end.'); close(output); end. 这里使用了一定文件的知识,如果把 assign、rewrite、 close 三行略去的话,大家应该可以看得懂。有兴趣的同学可以把这个程序 放到 Free Pascal 编译器中编译、执行一下,然后看看生成的文件 ( “p1_4_2_1_2.pas” ) , 再把生成文件放到 Free Pascal 中编译一下。 很容易,我们发现,这个程序是相当长的。 有 14.4KB 的代码量,这显然不符合我们的期望。 下面我们再看一个题目。 例题 1.4.2.1.3: 读入一行数 (1<个数<1 ? 105 ) , 将之倒序输出。
第 2 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

假设个数为 n,我们来思考一下。如果说按照我们已学的内容, 我们可以求出 n 的值, 也可以根据已知的 n 的大小生成如 p1_4_2_1_2 的程序,但是我们既要知道 n 的大小,又要倒序输出,只输入一遍, 明显是不可能的。 另外, 将 Free Pascal 的编译器附在软件之中发行, 明显是不合理的。 俗话说, “穷则变, 变则通, 通则久” , 既然目前我们遇到了瓶颈, 我们就需要转变一种想法——Pascal 是否为我们提供了一种更易于 操作的解决方案呢?事实上,更为简易的解决方案在 Pascal 中是存 在的,Pascal 为我们提供了一种构造类型——数组,就可以完成这 一任务。 例如,例题 1.4.2.1.2 可以这样写: program p1_4_2_1_2(input,output); type arr=array [1..1000] of longint; var i:longint; a:arr; begin for i:=1 to 1000 do read(a[i]); readln(); for i:=1000 downto 1 do write(a[i],' '); writeln(); readln(); end.
第 3 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

而例题 1.4.2.1.3 可以这样写: program p1_4_2_1_3(input,output); type arr=array [1..1000000] var i,n:longint; a:arr; begin i:=0; while not(eoln()) do begin inc(i); read(a[i]); end; readln(); n:=i; for i:=n downto 1 do write(a[i],' '); writeln(); readln(); end. 很明显,使用了数组的程序有以下好处: 1、简洁、易于理解 2、便于修改、维护 3、使得程序可以不直接借助 asm 实现一些功能
第 4 页,共 45 页

of longint;

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

首先,我们来简单的介绍一下数组。 所谓数组,就是相同数据类型的元素按一定顺序排列的集合,就 是把有限个类型相同的变量用一个名字命名, 然后用编号区分他们的 变量的集合,这个名字称为数组名,编号称为下标。组成数组的各个 变量称为数组的分量,也称为数组的元素,有时也称为下标变量。 一维数组是由数字组成的以单纯的排序结构排列的结构单一的 数组,所以上面两个程序所使用的,是一维数组。 静态数组是在声明时已经确定子数组大小的数组, 即数组元素的 个数固定不变 (声明数组, 就是声明数组名、 维数、 类型、 数组大小) , 所以以上两个程序中的数组,均为静态数组。另外,值得注意的是, 静态数组的每个元素在内存上的存储地址是连续的。 下面我们来详细介绍一下有关一维数组的操作。 1)说明部分的说明方式 数组是一种构造类型,与枚举、子界一样,需要类型定义: type <自定义类型标识符>=array [<下标类型>] of <元素类型> 值得注意的是,这里的下标类型必须是顺序类型,包括整型、字 符型、枚举型、子界型、布尔型,但不能是其他类型,例如实型、字 符串类型等。对于元素类型没有太多要求,只需要符合先定义,后使 用之原则。 以下的定义是合法的: type a=array [integer] of ^integer; //指针数组,数组下标类型为整型,元素类型为指针类型
第 5 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

type b=array [boolean] of set of 0..9; //集合数组,数组下标类型为布尔型,元素类型为集合类型 type c=array ['a'..'c'] of record x,y:longint; end; //记录数组,数组下标类型为字符类型的子界型,元素类型为记 录类型 type d=array [(red,green,blue)] of file; //文件数组,数组下标类型为枚举类型,元素类型为文件类型 但是,这种定义是非法的,因为实型不是顺序类型: type e=array [3.1 .. 5.6] of longint; 然而,我们最常使用的一种定义仍然是 type arr=array [1..maxn] of longint; 或 type arr=array [0..maxn+1] of longint; //maxn 为用户自定义的一个常量。 定义了类型, 就可以定义变量, 与其他构造类型 (如枚举、 子界) 相同,我们可以这样定义: var x:a; //a 是已经定义过的数组类型 当然,如同枚举、子界一样,我们也可以将类型说明和变量说明 并在一起写,从而省略去定义类型标识符的部分,在某些特定情况下 减少代码量,虽然这样不被推荐: var y:array [1..100] of longint;
第 6 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

2)程序体的使用方式 从标程 p1_4_2_1_2 和 p1_4_2_1_3 中, 我们可以看到数组元素的 调用方式: <数组变量标识符>[<下标表达式>] 例如 a[1],b[true],c['a'],d[red]等(这里的 a,b,c,d 为数 组变量标识符,而非类型标识符) ,而这些数组元素的类型即为数组 定义中的元素类型。这里值得注意的是,[]内的下标表达式类型必须 与说明部分所定义的类型一致。 下面我们用一道例题来详细解释其用法: 例题 1.4.2.1.4:读入一行数,将之全部+1,再倒序输出。 program p1_4_2_1_4(input,output); var a:array [shortint] of longint; i:longint; begin i:=0; while not(eoln()) do begin inc(i); read(a[i]); inc(a[i]); end; readln();
第 7 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

for i:=i downto 1 do write(a[i],' '); writeln(); readln(); end. 数组是不能整体读入、输出的。 例如对于本程序的 a 数组,以下语句是非法的: “readln(a);” 、 “write(a);” 。 但是数组是可以整体赋值的,例如“a:=b;”前提条件是 a 数组 与 b 数组类型一致。事实上,数组还可以整体初始化,例如,将数组 a 整体赋值为 0,我们可以这么写: fillchar(a,sizeof(a),0); 这里的 fillchar、 sizeof 都是编译器在 system 单元中定义好的, 无需我们自行定义。 另外,关于数组的一些已定义的函数过程,我们主要介绍以下几 个:(这里以 Free Pascal 为准,Turbo Pascal 中的参数类型 longint 统一为 word)
1 SizeOf : function (var x):longint; ○
E A

简单的说其作用就是返回一个对象或者类型所占的内存字节数 (就像我们从参数表中看到的,其实 sizeof 不只能用于数组,也可 以用于其他类型,包括标准类型、构造类型等等,甚至是文件类型, 有兴趣的同学可以自己试试) 。
第 8 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

2 FillChar : procedure(var X; Count: Longint; value) ○
E A A

它的功能是, 把指定变量 X 在内存段中所占的前 Count 个字节赋 为相同的值 value, 其中 value 是填充的值,只能是 Byte、Char 或 Boolean 等单字节类型的值。 下面通过表格简单的讲解一下 fillchar 整体赋值的结果(第一 列为数组 a 的元素类型,其余列数中的值表示 fillchar 后每一个元 素的值)。 fillchar(a,sizeof(a),x) arrtype boolean char shortint byte integer word longint single x=0 false #0 0 0 0 0 0 0 x=1 true #1 1 1 257 257 16843009 2.36942782761724E-0038 x=255 true ‘ ’ -1 255 -1 65535 -1 -1

也能用于其他数据类型。 事实上,fillchar 不只可以用于数组,
3 FillByte : procedure(var X; Count: Longint; value) ○
E A A

类似于 fillchar
4 FillWord : procedure(var X; Count: Longint; value) ○
E A A

对一个内存块, 每 Word 字节数, 赋值一次, 赋值内容为 Value,
第 9 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

一共赋值 Count 次。但是,count 就不再是 sizeof(a)了,而要变成 a div 2。有兴趣的同学可以思考一下,为什么要 div 2?
5 FillDWord : procedure(var X; Count: Longint; value) ○
E A A

Dword 意思是占用 4 个字节的整型,具体来讲可以是常用的 longint 类型。同样的,count 要变成 sizeof(a) div 4。想想,这 又是为什么? 备注:有关整体赋值的更多内容,我们将在本书的第三卷进行深 入、详细讨论。 其实,正如同标准类型的变量的初始化一样,数组变量的初始化 也是可以在定义部分说明的,例如: var a:array [1..5] of longint=(1,2,3,4,5); 或 type arr=array [1..5] of longint; var a:arr=(1,2,3,4,5); 但是,括号里的数字个数必须与元素个数相等。例如下面的定义 就是错误的: var a:array [1..5] of longint=(1,2,3,4); 事实上, 数组也可以作为一个常量, 我们称之为常量数组。 例如: const a:array [1..5] of longint=(1,2,3,4,5); 当然也可以这样写: type arr=array [1..5] of longint; const a:arr=(1,2,3,4,5);
第 10 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

自然,这种写法是错误的: const a:array [1..5] of longint=(1,2,3,4); 3)压缩数组 在某些教科书上,在 Pascal 中,有一个 packed 关键字,它的作 用,是为我们节省空间。 例如,数组 a 定义为 var a:array [1..10000] of char; 占用 10000 个字长,而说明改为紧缩方式: var a:packed array [1..10000] of char; 在 16 位微机中,就只占用 5000 个字长,在 32 位微机中,只占 用 2500 个字长。 但事实上,根据编者的实验结果,packed 的添加并不影响编译 结果,自然也不影响占用字长。

TP7 亦然,有兴趣的同学可以自己去做个试验。
第 11 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

4)一维静态数组的常见基本操作
1 移动 ○
E A A

将数组 a 的第 p 个元素移至第 q 位(q>p),将 p,q 间的所有元素 依次向前平移一位。



p-1

p

p+1

p+2



q-1

q

q+1



算法描述: 首先将 a[p]的值保存在 temp 中,然后将 a[i]{i in [p..q-1]} 的值附为 a[i+1],最后将 a[q]的值赋为 temp。 对应程序段如下 temp:=a[p]; for i:=p to q-1 do a[i]:=a[i+1]; a[q]:=temp; 有兴趣的同学可以列举一串数,自己模拟一下,验证是否正确。 当然,事实上,这段程序可以使用标准过程 move 来实现。 思考: 1.如果是 p>q, 然后将 p,q 间的所有元素都向后平移一格, 那么这段程序应该怎么写? 2.思考下面方法能否实现移动,为什么? for i:=p to q-1 do change(a[i],a[i+1]);//change 表示交换 a[i],a[i+1]的值
第 12 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

2 查找 ○
E A A

对于给定的数组 a,求值为 x 的元素所在的位置,如果有,输出 所有的 x 的值,如果没有,输出“No Solution” 。 算法描述: flag:boolean 初值为 false。从起始位置找到终点位置,如果找 到了,输出后,将 flag 的值修改为 true。最后若 flag 仍为 false, 则认为无解,输出“No Solution” 。 对应程序段: flag:=false; for i:=1 to n do if a[i]=x then begin writeln(i); flag:=true; end; if not(flag) then writeln(' No Solution'); 思考: 1.如果说只需要搜索到一个位置就结束或者说保证数组里只出 现一次 x 的话, 程序可以怎么写? (提示: for+break 或 repeat/while 皆可)如果说使用 goto 语句,能否避免掉 flag?试试看! 2.本题的时间复杂度为 O(n),若保证数组单调递增或递减,有 O(log n)的算法吗?
第 13 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

3 插入 ○
E A A

思考:假设有一数组 a,我要在第 p 个位置插入一个值 x,怎么 办? 提示:现将第 p 到最后一个位置的数向后平移一格,再行插入,
1 来写一写。 可以参见 ○ 4 删除 ○
E A

思考:假设有一数组 a,我要删除第 p 个位置的数,怎么办? 提示:只要将第 p+1 到最后一个位置的数向前平移一格即可。
5 排序 ○
E A A

已有某一数组 a,求一方法将其按从小到大顺序排列。 例如: 4 3 输出结果为 1 2 2 3 4 5 6 7 7 2 2 6 5 1

方法一(选择排序法): 选择排序(Selection sort)是一种简单直观的排序算法。它的 工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个 元素,存放在序列的起始位置,直到全部待排序的数据元素排完。 简单点来说:对比数组中前一个元素跟后一个元素的大小,如果 后面的元素比前面的元素小则用一个变量 k 来记住他的位置, 接着第 二次比较,前面“后一个元素”现变成了“前一个元素” ,继续跟他 的“后一个元素”进行比较如果后面的元素比他要小则用变量 k 记住
第 14 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

它在数组中的位置(下标),等到循环结束的时候,我们应该找到了最 小的那个数的下标了,然后进行判断,如果这个元素的下标不是第一 个元素的下标,就让第一个元素跟他交换一下值,这样就找到整个数 组中最小的数了。然后找到数组中第二小的数,让他跟数组中第二个 元素交换一下值,以此类推。 下面是对应程序段: for i:=1 to n-1 do for j:=i+1 to n do if a[i]>a[j] then change(a[i],a[j]); 方法二(冒泡排序法) : 冒泡排序(Bubble Sort) ,是一种计算机科学领域的较简单的排 序算法。 它重复地走访过要排序的数列,一次比较两个元素,如果他们的 顺序错误就把他们交换过来。 走访数列的工作是重复地进行直到没有 再需要交换,也就是说该数列已经排序完成。 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到 数列的顶端,故名。 冒泡排序算法的运作如下: 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 对每一对相邻元素作同样的工作, 从开始第一对到结尾的最后一 对。在这一点,最后的元素应该会是最大的数。
第 15 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

针对所有的元素重复以上的步骤,除了最后一个。 持续每次对越来越少的元素重复上面的步骤, 直到没有任何一对 数字需要比较。 下面是对应程序段: for i:=n downto 2 do for j:=1 to i-1 do if a[j]>a[j+1] then change(a[j],a[j+1]) 思考: 1.如果要从大到小排,应该怎么写? 2.上面给出的两个程序段能够完成排序的原因是什么?试着给 出简单的证明。 3.能否基于上面两个程序段进行一定的修改,以提升效率? 4.回忆自己打麻将时从摸牌到码牌的过程 (没有玩过麻将的同学 可以参考打扑克时从发牌到整理的过程) ,想想自己是如何使本无规 律的麻将牌按照顺序排列的, 试着使用这种原理探索一种上面并未提 及的排序方法。 5.我们提供的两种排序方法以及你根据麻将牌推导的排序方法 时间复杂度均为 O(2 ), 而在 1.2.1.1 中我们还提及了 BOGO 排序 (猴 你们能自行提出其他的排序方法吗?看看,是否有 O(nlogn)的排序 法?有更低的吗?
第 16 页,共 45 页

子排序) ,这种排序方法的时间复杂度为 O(n*n!)。聪明的读者们,

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

6.假定在待排序的记录序列中, 存在多个具有相同的关键字的记 录,若经过排序,这些记录的相对次序保持不变,即在原序列中, a[i]=a[j],且 a[i]在 a[j]之前,而在排序后的序列中,a[i]仍在 a[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。想想, 上面给出的两种排序方法和你自己推出的排序方法,哪些是稳定的, 哪些是不稳定的? 7. 比较算法(Comparison sort)是排序算法的一种,通过一个 抽象的内容比较操作(通常是“小于或等于”操作)来确定两个元素 中哪个应该放在序列前面。 该算法的唯一要求就是操作数满足全序关 系:如果 a≤b 并且 b≤c 那么 a≤c(传递性) 。对于 a 或 b,要不 a ≤b,要不 b≤a(完全性) 。对于 a≤b 并且 b≤a 这种情况,a 和 b 都 有可能被排在前面。这时输入的顺序就会决定最后的顺序。比较排序 类似于将未贴标签的砝码用天平将按质量大小进行排序, 并且除了用 天平测量两个砝码的质量之外不能用其他方法。我们提出的插入、冒 泡、以及读者通过麻将牌导出的方法均为基于比较的排序法,思考是 否有不基于比较的排序法? 8.有人说基于比较的排序法时间复杂度的下限为 O(nlogn),想 想, 这么说有道理吗?能不能举出一个反例呢?为什么?试着给予证 明。 事实上,排序的算法还有很多,选择、冒泡只是其中相对而言嘴 最简单的两种排序法,其时间复杂度也是相当高的。有关排序,我们 将在本书第二卷进行详细的讨论。
第 17 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

5)一维静态数组的综合应用 例题 1.4.2.1.4:同余问题(SameMod) 【题目描述】 小明在纸上随手写下了 N 个正整数。 他想要知道能否存在一个大 于 1 的整数 M,使得这 N 个数除以 M 的余数都相同。 从小到大依次输出符合条件的所有 M。 【输入】 第一行一个整数 N,表示小明写下的正整数个数。 接下来一行,N 个整数 a[i],每两个数中间用一个空格分开,表 示小明写下的第 i 个数。保证所有数都不相同。 【输出】 从小到大依次输出所有符合条件的整数 M,中间用空格分隔。数 据保证至少存在一个这样的 M。 【输入样例 1】 【输出样例 1】 【样例 1 解释】 【输入样例 2】 【输出样例 2】 【样例 2 解释】 【数据范围】 60%的数据,1<=a[i]<=10,000 100%的数据,2<=n<=100,1<=a[i]<=1,000,000,000。
第 18 页,共 45 页

3 6 34 38 2 4 三个数都能被 2 整数;除以 4 都余 2。 5 5 17 23 14 83 3 这 5 个数除以 3 都余 2。

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

program p1_4_2_1_4(input,output); var min,n,i,j,ans:longint; a:array[0..100] of longint; function gcd(a, b:longint):longint; begin if b=0 then gcd:=a else gcd:=gcd(b,a mod b); end;//定义求最大公约数的函数:gcd begin readln(n); ans:=0; min:=maxlongint; for i:=1 to n do begin read(a[i]); if a[i]<min then min:=a[i]; end; if a[1]<>min then begin a[1]:=a[1]+a[2]; a[2]:=a[1]-a[2]; a[1]:=a[1]-a[2];
第 19 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

end; for i:=1 to n do a[i]:=a[i]-min; for i:=2 to n do if a[i]<>0 then begin if a[i]>ans then begin a[i]:=a[i]+ans; ans:=a[i]-ans; a[i]:=a[i]-ans; end; ans:=gcd(ans,a[i]); end; j:=0; for i:=1 to round(sqrt(ans)) do if ans mod i=0 then begin inc(j); a[j]:=i; end; for i:=1 to j do
第 20 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

if a[i]<>1 then write(a[i],' '); n:=round(sqrt(ans)); for i:=j downto 1 do if a[i]<>n then write(ans div a[i],' '); writeln(); readln(); end. 这里定义了一个函数 gcd(),用来求最大公因数。对于自定义函 数的详细研究,我们将在 1.5.1 中进行详细研究。 例题 1.4.2.1.5:高精度加法 由于计算机的存储字节有限, 所以不能完整表示一个很大整数的 精确值,这时候就得用到其他的方法,称之为高精度算法。高精度乘 法,实际上,就是模拟加法的过程。像小学的笔算过程。 program p1_4_2_1_5(input,output); var a,b,c:array[1..1000000]of integer; l2,i,l1,l:longint; ch:char; begin l1:=0; l2:=0;
第 21 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

fillchar(c,sizeof(c),0); while not(eoln()) do begin inc(l1); read(ch); a[l1]:=ord(ch)-48; end; readln(); while not(eoln()) do begin inc(l2); read(ch); b[l2]:=ord(ch)-48; end; readln(); for i:=1 to l1 div 2 do begin a[i]:=a[i] xor a[l1+1-i]; a[l1+1-i]:=a[i] xor a[l1+1-i]; a[i]:=a[i] xor a[l1+1-i]; end; for i:=1 to l2 div 2 do
第 22 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

begin b[i]:=b[i] xor b[l2+1-i]; b[l2+1-i]:=b[i] xor b[l2+1-i]; b[i]:= b[i] xor b[l2+1-i]; end; if l1>l2 then l:=l1 else l:=l2; for i:=1 to l do begin c[i]:=a[i]+b[i]+c[i]; if c[i]>=10 then begin c[i]:=c[i] mod 10; c[i+1]:=c[i+1]+1; end; end; if c[l+1]>0 then l:=l+1; for i:=l downto 1 do write(c[i]); readln(); end. 同理, 可以编写高精度其他的运算, 有兴趣的同学可以自己试试。
第 23 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

例题 1.4.2.1.6:步步高升(Step by Step) 【问题描述】 春节的时候 TENSHI 去逛花市。她来到一个卖盆竹的摊位,看到 一盆叫做“步步高升”的盆竹。 “步步高升,步步高升……”学习就 是要一步一步来,不能急,要打好基础。在稳固的基础上才谈得上步 步高升!TENSHI 若有所思。她看到这盆东西好意头,于是想买下。 谁知一问价钱, “不贵不贵,才***RMB。 ”TENSHI 差点没昏倒,囊 中羞涩嘛。但是 TENSHI 还是很想买下来,于是她就在一旁观察。观 察了一段时间,她发现这个卖盆竹的人和别人杀价很有规律。设此人 第 i 次报价为 Wi 元,那么他第 i+1 次报的价格为 Wi-A 或 Wi -B。 到了最后,TENSHI 以 Z 元成交,高高兴兴的回家去了。 【任 务】

求 TENSHI 把盆竹的价格由 W1 元杀到 Z 元的方法总数。 【输入格式】 输入文件第一行有两个正整数 W1 和 Z。 第二行有两个正整数 A 和 B。 【输出格式】 将方法总数输出,只有一行。 注意:结果不超过 MAXLONGINT 【数据范围】 10 ≤ W1 ≤106,1 ≤ Z ≤ 106 ,Z < W1 2 ≤ A 、B ≤ 10000,A≠B
第 24 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

program p1_4_2_1_6(input,output); var t:array [1..10000000] of longint; w1,a,b,z,i:longint; begin fillchar(t,sizeof(t),0); readln(w1,z); readln(a,b); t[w1]:=1; for i:=w1-1 downto z do t[i]:=t[i+a]+t[i+b]; writeln(t[z]); readln(); end. 这道题所使用算法的思想, 是动态规划, 具体而言, 是线性动规。 有关动态规划思想的具体阐述,我们将在第二卷中给出。

二、动态数组
动态数组(Dynamic Array)没有固定的大小和长度。当对动态 数组进行赋值或者是将其传递给 SetLength 过程时, 动态数组所占用 的内存将会被重新分配。 声明一个动态数组类型的语法格式如下所示。 type <类型名称> = array of <基础类型>; 相对于静态数组,在 array 和 of 之间的[<下标类型>]没有了。 其下标的默认索引值是从 0 开始的。在 32 位平台上,一个动态数组
第 25 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

类型的变量占用 4 个字节的内存, 并包含了一个指向动态分配的数组 的指针。动态数组类型的变量实际上是一个隐式的指针,并且使用了 与长字符串类型相同的引用计算技术来进行管理。 关于动态数组的使用,我们将在本书 1.6.1 指针部分详细介绍。

三、二维数组
在 1.4.2.1 中,我们说过数组的元素类型是任意的。可能就会有 同学思考这样一个问题:如果一个数组的元素类型是另一个数组,那 么这会是什么? 例如: type arr=array [1..1000] of array [1..1000] of longint; 那么,这个 arr 类型是什么东西呢? 这就是二维数组。 例题 1.4.2.3.1:打印杨辉三角前 10 行。 program p1_4_2_3_1(input,output); const n=11; var a:array [1..n] of array [1..n] of longint; i,j:longint; begin fillchar(a,sizeof(a),0); for i:=1 to n do a[i][1]:=1; for i:=1 to n do
第 26 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

for j:=2 to i do a[i][j]:=a[i-1][j-1]+a[i-1][j]; for i:=1 to n do begin for j:=1 to (n-i) div 2 do write(' ':6); if odd(n-i) then write(' ':3); for j:=1 to i do write(a[i][j]:6); writeln(); end; readln(); end. 事实上,Pascal 为二维数组提供了一种简易的写法: array [<下标类型 1>,<下标类型 2>] of <基类型> 值得注意的是,这种定义方法与下面的写法是等效的: array [<下标类型 1>] of array [<下标类型 2>] of <基类型> 在 Pascal 中,不要求下标类型 1 与下标类型 2 为同一类型,甚 至不需要类型相容。也就是说,下面的写法是合法的: array [char,boolean] of longint 这与下面的写法等效: array [char] of array [boolean] of longint 事实上,Pascal 在二维数组的引用上,也提供了类似的更为简
第 27 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

易的解决方法,这使得 Pascal 更为人性化。 简单而言,在程序体中可以这样引用二维数组的一个元素: <数组名>[<下标一>,<下标 2>] 这与下面的写法等效: <数组名>[<下标 1>][<下标 2>] 例如,a[1][true]可以改写为 a[1,true],这两种写法等效。 例题 1.4.2.3.2:数字三角形(IOI1994) The Triangle Time Limit: 1000MS 【Description】 Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right. 【Input】 Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.
第 28 页,共 45 页

Memory Limit: 10000K

Figure 1

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

【Output】 Your program is to write to standard output. The highest sum is written as an integer. 【Sample Input】 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 【Sample Output】 30 这道题来自于 IOI1994,这道题的推出标志着动态规划思想正式 进入 OI。作为动态规划的 OI 首秀,数字三角形,这一道树状动规的 基础题深入人心,直到 2012 年,数字三角形仍出现在 NOIP 普及组初 赛的试题中 (NOIP2012 普及组初赛第三大题阅读程序写结果第三题) , 虽然 NOIP 的初赛题并没有使用动规算法而是递归,然而状态转移方 程已经给出。 下面是样例程序
program p1_4_2_3_2(input,output); var n,i,j,ans:integer; a,f:array[1..500,1..500]of longint;
第 29 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

begin readln(n); for i:=1 to n do begin for j:=1 to i do read(a[i][j]); readln; end; f[1][1]:=a[1][1]; for i:=2 to n do begin f[i,1]:=f[i-1,1]+a[i,j]; f[i,i]:=f[i-1,i-1]+a[i,i]; for j:=2 to i-1 do if f[i-1,j-1]<f[i-1,j] then f[i,j]:=f[i-1,j]+a[i,j] else f[i,j]:=f[i-1,j-1]+a[i,j]; end; ans:=f[n,1]; for j:=2 to n do if f[n,j]>ans then ans:=f[n,j]; for j:=1 to n do f[n,j]:=a[n,j]; for i:=n-1 downto 1 do
第 30 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

for j:=1 to i do if f[i+1,j]<f[i+1,j+1] then f[i,j]:=f[i+1,j+1]+a[i,j] else f[i,j]:=f[i+1,j]+a[i,j]; writeln(f[1][1]); readln(); end.

事实上,这道题也可以只使用一个二维数组,有兴趣的同学可以 试试。 例题 1.4.2.3.3:背包问题 有 N 件物品和一个容量为 V 的背包。 第 i 件物品的重量是 w[i], 价值是 v[i]。求解将哪些物品装入背包可使这些物品的重量总和不 超过背包容量,且价值总和最大。 背包问题(Knapsack problem)是一种组合优化的问题。问题可以 描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的 总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称 来源于如何选择最合适的物品放置于给定背包中。 相似问题经常出现 在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。 也可以将背包问题描述为决定性问题, 即在总重量不超过 W 的前提下, 总价值是否能达到 V?它是在 1978 年由 Merkel 和 Hellman 提出的。 下面介绍一种常见方法。 用子问题定义状态:即 f[i][v]表示前 i 件物品恰放入一个容量 为 v 的背包可以获得的最大价值。则其状态转移方程便是:
第 31 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

f[i][v]=max{f[i-1][v], f[i-1][v-w[i]]+v[i]} 。这个方程非常重 要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以 有必要将它详细解释一下: “将前 i 件物品放入容量为 v 的背包中” 这个子问题,若只考虑第 i 件物品的策略(放或不放) ,那么就可以 转化为一个只牵扯前 i-1 件物品的问题。如果不放第 i 件物品,那么 问题就转化为“前 i-1 件物品放入容量为 v 的背包中” ,价值为 f[i-1][v];如果放第 i 件物品,那么问题就转化为“前 i-1 件物品 放入剩下的容量为 v-w[i]的背包中” ,此时能获得的最大价值就是 f [i-1][v-w[i]]再加上通过放入第 i 件物品获得的价值 v[i]。 注意 f[v]有意义当且仅当存在一个前 i 件物品的子集,其费用 总和为 v。 所以按照这个方程递推完毕后, 最终的答案并不一定是 f[N] [V],而是 f[N][0..V]的最大值。如果将状态的定义中的“恰”字去 掉, 在转移方程中就要再加入一项 f[v-1], 这样就可以保证 f[N] [V] 就是最后的答案。至于为什么这样就可以,由读者自己来体会了。 这种方法时间和空间复杂度均为 O(N*V)。事实上,这种算法已 经做到了时间复杂度最优,但是在空间复杂度上仍可优化至 O(V), 也就是说可以用一个一维数组而不是二维数组来实现, 具体方法希望 由读者在阅读完本程序后思考并给出。 program p1_4_2_3_3(input,output); var i,j,v,n:longint; c,w:array[0..1000] of longint; f:array [0..1000,0..10000] of longint;
第 32 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; begin readln(n,v); fillchar(f,sizeof(f),0); for i:=1 to n do readln(c[i],w[i]); for i:=1 to n do for j:=1 to v do f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+j[i]); writeln(f[n,v]); readln(); end. 事实上,背包问题还有很多变种,有关背包动规的详细内容,详 见本书第二卷。 例题 1.4.2.3.4:矩阵乘法 二维数组可以用来模拟矩阵,那么我们能不能使用 Pascal 来计 算矩阵的乘法呢?答案当然是肯定的。为简便起见,我们让两个矩阵 均为 n*n。
第 33 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

program p1_4_2_3_4(input,output); var n,i,j,k:longint; a,b,ans:array[0..101,0..101]of longint; begin fillchar(ans,sizeof(ans),0); readln(n); for i:=1 to n do for j:=1 to n do read(a[i,j]); for i:=1 to n do for j:=1 to n do read(b[i,j]); for i:=1 to n do begin for j:=1 to n do begin for k:=1 to n do ans[i,j]:=ans[i,j]+a[i,k]*b[k,j]; write(ans[i,j],' '); end; writeln(); end;
第 34 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

readln(); end. 思考:为什么是“read(a[i,j])”而不是“read(a[j,i])”?尝 试着用线性代数公式A × = ( × ) 来说明。

另 外 , 能 否 将 “ ans[i,j]:=ans[i,j]+a[i,k]*b[k,j] ” 改 成

“ans[i,j]:=ans[i,j]+a[k,j]*b[i,k]”?为什么? 还有,能否借助已学的 Pascal 二维数组知识完成求 n 阶行列式 的程序?有兴趣的同学可以试试。 最后,有兴趣的同学可以借助已学内容,结合高斯消元法等线代 知识,编写如求逆矩阵、求秩等其他线代操作的程序。

四、多维数组
我们研究了数组的数组,并给予了它“二维数组”的名字。同样 的,我们可以将它扩展到三维、四维、甚至 n 维,其定义、使用方法 与二维数组一致。 具体来说,可以这样定义: array [<下标类型 1>,<下标类型 2>,…,<下标类型 n>] of 基类型 可以这样使用: a[i1,i2,i3,…,in] 其下标类型等要求与二维数组完全一致,这里就不再赘述。 事实上,我们把二维及以上的数组统称为多维数组。 鉴于超过二维的, 尤其是超过三维的多维数组无论在实际编程还 是奥林匹克竞赛中都基本不用,所以这里就不多讨论了。
第 35 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

五、字符串
首先,我们来看一看下面这种数据类型: type st=packed array [1..255] of char; 对,这就是一个普普通通的紧缩字符数组。但是,Pascal 为我 们提供了字符数组一些特殊的使用方法。 (1)允许字符数组的直接读写 我们知道,普通数组不能进行直接的读(read)和写(write),但 事实上,字符数组可以。 有兴趣的同学可以把下面的程序导入 Free Pascal 编译器中,编 译,执行一下。 program p1_4_2_5_1(input,output); type st=array [1..500] of char; var s:st; begin readln(s); writeln(s); readln(); end. 我们可以看到,通过 readln 命令,改程序将读入的字符与 s 的 字符进行了一一对应赋值,而短缺的部分,均赋值为空格。 (2)允许整体赋值 有兴趣的同学可以把下面的程序导入 Free Pascal 编译器,执行
第 36 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

一下试试看。 program p1_4_2_5_2(input,output); type st=array [1..500] of char; var s:st; begin s:='Pascal'; writeln(s); readln(); end. 与 readln 命令相同,缺省部分用空格补齐。 (3)提供了一种字符数组运算: '+' 有兴趣的同学可以把下面这段程序导入 Free Pascal 编译器,执 行一下。 program p1_4_2_5_3(input,output); type st=packed array [1..100] of char; st2=packed array [1..255] of char; var s1,s2:st;s:st2; begin s1:='Turbo'; s2:='Pascal'; s:=s1+s2; writeln(s);
第 37 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

readln(); end. 我们看到,两个字符数组连起来了。 (4)提供了六种关系运算:'>'、'<'、'>='、'<='、'='、'<>' 在关系比较时,无论两个字符数组长度是否相同,从左到右按照 其 ASCII 码值逐一进行比较。当两个字符的 ASCII 值不等时,便可比 出大小(ASCII 码大的字符数组“大” ) 。若短字符数组和长字符数组 的左边字符都相等时,长数组比段数组大。有关关系运算的程序,有 兴趣的同学可以自行依照前面三段程序来写。 有同学可能说了,既然 Pascal 都能这么人性化了,能不能把字 符数组的大量空格给解决了? 答案是肯定的。 事实上, Pascal 为我们提供了一种数据类型——字符串 string。 下面我们首先来介绍一下字符串的定义: var <自定义变量标识符>:string[<长度>]; (<长度>∈{x∈N|0<x<256}) 这个长度表示字符串的最大长度。当[<长度>]部分缺省时,表示 最大长度为 255。 字符串继承了字符数组的全部附加功能, 只是短却的部分并不会 由空格来补齐。有兴趣的同学可以自己编个程序试验一下。下面我们 主要介绍 system 单元中字符串的几个常用函数、 过程。 当然, system 单元不需要在 uses 部分说明。下面进行列举:
第 38 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

1、length

function (st:string):byte;

返回字符串的长度,即字符串中字符的个数,其结果为整型。 2、pos function (st1,st2:string):byte;

功能为在 s2 串中查找出现 s1 串的起始位置, 找到则返回第一个 位置的值,否则返回 0。 3、str procedure (value:variant;var st:string);

value 可以为整型,也可以为实型。 将数 value 转化为字符串 st。 4、val procedure (st:string;var value;var code:byte)

value 是变参,可以为整型,也可为实型。 将字符串 st 转化为数 value, code 存储 errorlevel: 若未出错, 则为 0,若出错,则 code 返回第一个错误的值。例如 st ‘-3.2’ ‘23a1’ value -3.2 0 code 0 3

事实上,code 可以省略,即 val(st,value) 5、copy function (st:string;pos,len:byte):string;

从 st 串的第 pos 个位置开始截取长度为 len 的字符串。 6、delete procedure (var st:string;pos,len:byte);

从 st 的第 pos 个位置开始删除长度为 len 的字串。 7、insert procedure (var s:string;d:string;pos:byte);

在 s 的第 pos 个位置插入字符串 d
第 39 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

8、concat 可以看做是

function(s1,s2,…,sn):string; s1+s2+…+sn

下面我们看一道例题。 例题 1.4.2.5.4: (NOIP2013 普及组)记数问题(count) 【描述】 试计算在区间 1 到 n 的所有整数中 , 数字 x(0 ≤ x ≤ 9)共 出现了多少次? 例如,在 1 到 11 中,即在 1、2、3、4、5、6、7、8、9、10、 11 中,数字 1 出现了 4 次。 【输入】 输入共 1 行,包含 2 个整数 n、x,之间用一个空格隔开 【输出】 输出共 1 行,包含一个整数,表示 x 出现的次数。 program p1_4_2_5_4(input,output); var n,i,j,total:longint; x:integer; st:string; begin readln(n,x); total:=0; for i:=1 to n do begin
第 40 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

str(i,st); for j:=1 to length(st) do if st[j]=chr(x+48) then inc(total); end; writeln(total); readln(); end. 既然 string 这么好用,那么一定有同学要问了,有没有什么办 法突破 255 的限制?答案是肯定的。 事实上, Pascal 为我们提供了两类长字符串: AnsiString 和 UnicodeString,这两种长字符串的长度几乎可以仅限于可用内存的 大小。 (备注:以下内容摘自叶叶《Delphi XE4 语言指南》 ) AnsiString 类型代表了一个动态分配的字符串,其最大长度仅 限于可用内存的大小。一个 AnsiString 类型的变量实际上是一个隐 式的指针,该指针指向了一个包含了字符串信息的结构。当变量为空 时,也就是说包含了零长度的字符串时,对应的指针为 nil 不使用额 外的内存来保存字符串。当变量非空时,对应的指针指向一个动态分 配的包含字符串值的内存块。这个内存块是在堆(heap)上分配的, 但是对它的管理是完全自动的,不需要使用到用户代码。一个 AnsiString 类型的结构包含了一个 32 位的长度指示、一个 32 位的
第 41 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

引用计数、 一个 16 位的数据长度用于表示每个字符所占用的字节数、 以及一个 16 位的代码页。 一个 AnsiString 类型代表了一个单字节字符串。对于单字节字 符集(single-byte character set,SBCS) ,字符串中的每个字节代 表了一个字符。 对于多字节字符集 (multibyte character set, MBCS) , 虽然每个元素仍然是一个字节, 但是一个字符可能需要使用一个到多 个字节来表示。多字节字符集,特别是双字节字符集(double-byte character set,DBCS) ,被广泛的应用于亚洲语言,例如汉字。一个 AnsiString 类型的字符串可以包含 MBCS 字符。 AnsiString 类型的索引是从 1 开始的。索引多字节字符串是不 可靠的, 因为 S[i]代表 S 中的第 i 个字节, 但不一定是第 i 个字符。 第 i 个字节可能是一个字符,也可能是一个字符中的一部分。但是, 标准的 AnsiString 字符串处理函数支持多字节字符串,它可以根据 当前的区域设置对多字节字符串进行处理。通常情况下,多字节函数 的名称以 “Ansi”开始。 例如, StrPos 的多字节版本是 AnsiStrPos。 对多字节字符的支持依赖于操作系统和基于当前的区域设置。 因为 AnsiString 类型的变量是一个指针,所以两个或两个以上 的变量可以引用相同的值而不需要使用额外的内存。 编译器利用这一 点来节约资源并且提高赋值的执行速度。每当一个 AnsiString 类型 的变量被消毁或赋于新值时,旧的字符串值(变量的原值)的引用计 数将会被递减, 同时新的字符串值 (如果有) 的引用计数将会被递增。 如果一个字符串值的引用计数达到零, 那么它所占用的内存就会被释
第 42 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

放。这个过程被称为引用计算(reference counting) 。当使用索引 改变字符串中的某个字符值时,如果这个字符串的引用计数大于 1, 那么这个字符串将会被重新拷贝。 这被称为写时拷贝 (copy-on-write) 语义。 UnicodeString 类型是默认的字符串类型,代表了一个动态分配 的 Unicode 字符串,其最大长度仅限于可用内存的大小。在 Unicode 字符集中,每个字符使用一个到多个字节来表示。Unicode 有多种转 换格式, 使用不同转换格式的相同字符编码可以很容易的进行相互转 换。常用的 Unicode 格式有如下三种。 一、 对于 UTF-8, 每个字符可以使用 1 至 4 个字节来表示。 在 UTF-8 中,前 128 个 Unicode 字符对应于 US-ASCII 字符。 二、UTF-16 是另一种常用的 Unicode 编码,其中每个字符使用 2 个或 4 个字节来表示。 在基本多文种平面中的字符使用 2 个字节来表 示,其余的字符以代理对的方式使用 4 个字节来表示。 三、UTF-32 中的每个字符使用 4 个字节来表示。 Windows 平台支持单字节字符串、多字节字符串、以及 Unicode 字符串。Windows 操作系统支持 UTF-16。关于 Unicode 标准的详细介 绍请参考其官方网站[7]。 UnicodeString 类型使用了与 AnsiString 类型完全一样的内部 结构。但是,UnicodeString 中的字符使用 UTF-16 进行编码。由于 UnicodeString 类型和 AnsiString 类型使用了相同的结构,所以它 们的功能非常的相似。当一个 UnicodeString 类型的变量为空时,它
第 43 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

不占用额外的内存。当这个变量非空时,对应的指针指向一个动态分 配的包含字符串值的内存块。 这个内存块的管理对用户来说是 “透明” 的。UnicodeString 类型的变量使用了引用计数,两个或两个以上的 变量可以引用相同的值而不需要使用额外的内存。可以对 UnicodeString 类型的实例进行索引。 索引从 1 开始, 正如 AnsiString 类型一样。 UnicodeString 类型与其他所有的字符串类型都是赋值兼容的。 但是,在 AnsiString 类型与 UnicodeString 类型之间进行赋值时, 需要进行适当的向上或向下的转换。注意,将一个 UnicodeString 类 型赋值给一个 AnsiString 类型是不推荐的, 这可能会导致数据丢失。 在 Delphi 中也可以通过 WideChar 类型、 PWideChar 类型和 WideString 类型来支持 Unicode 的字符和字符串。 关于使用 Unicode 的 更 多 信 息 请 参 考 《 Unicode in RAD Studio 》 和 《 Enabling Applications for Unicode》 。 上面介绍的两种字符串类型, AnsiString 类型和 UnicodeString 类型,统称为长字符串类型(long string type) 。目前默认的长字 符串类型是 UnicodeString 类型,它使用了与 AnsiString 类型相同 的引用计数。为了与旧的代码相兼容,可能需要使用 AnsiString 类 型。 在 32 位平台上, 一个长字符串类型的变量占用 4 个字节的内存, 并包含了一个指向动态分配的字符串的指针。与此有关的内容,我们 将在本书的第三卷进行详细解释。
第 44 页,共 45 页

百度 Pascal 吧公开培训教材-Pascal 培训课程普及讲义-第七讲

六、逻辑电路
逻辑电路是一种离散信号的传递和处理,以二进制为原理、实现 数字信号逻辑运算和操作的电路。分组合逻辑电路和时序逻辑电路。 前者由最基本的“与门”电路、 “或门”电路和“非门”电路组成, 其输出值仅依赖于其输入变量的当前值, 与输入变量的过去值无关— 即不具记忆和存储功能;后者也由上述基本逻辑门电路组成,但存在 反馈回路—它的输出值不仅依赖于输入变量的当前值, 也依赖于输入 变量的过去值。 由于只分高、 低电平, 抗干扰力强, 精度和保密性佳。 广泛应用于计算机、数字控制、通信、自动化和仪表等方面。最基本 的有与电路、或电路和非电路。 逻辑门可以用电阻、电容、二极管、三极管等分立原件构成,成 为分立元件门。 也可以将门电路的所有器件及连接导线制作在同一块 半导体基片上,构成集成逻辑门电路。 简单的逻辑门可由晶体管组成。 这些晶体管的组合可以使代表两 种信号的高低电平在通过它们之后产生高电平或者低电平的信号 高、低电平可以分别代表逻辑上的“真”与“假”或二进制当中 的 1 和 0,从而实现逻辑运算。常见的逻辑门包括“与”门, “或” 门, “非”门, “异或”门(也称:互斥或)等等。 逻辑门可以组合使用实现更为复杂的逻辑运算。 事实上,这就是当年最早的计算机的组成原理,有兴趣的同学可 以课后再查阅与之有关的一些资料以扩充自己对于计算机原理的认 知。
第 45 页,共 45 页


相关文章:
语法讲义第七讲虚拟语气
语法讲义第七讲虚拟语气 隐藏>> 语法讲 义虚拟语气 第七讲第一.虚拟语气应用范围概述虚拟语气用来表示一种假设的情况或主观的愿望, 是一种表示非真实 情况或主观...
完整的Pascal讲义(word)
完整的Pascal讲义(word)_IT认证_资格考试/认证_教育...如果程 序有语法错误,则会在程序窗口的第一行处...第六、七行总宽度与前四行一样。 参与程序如下:...
PASCAL语法基础-答案
Pascal 语法基础习题 第一题:下列哪些常量是对的,哪些是错误的,错在哪? Const...第七题:编写一个程序,输入两个实数 a,b,求 a,b 的乘积。(尤其当 a,b ...
PASCAL讲义
PASCAL讲义_IT/计算机_专业资料。编程必备第...如果程序有语法错误,则会在程序窗口的第一行处显示...以上程序的运行结果为: A=51B=35C=16 七、带格式...
pascal语法
pascal语法_经济学_高等教育_教育专区。DELPHI语言pascal 语法 2005 年 1 月 27 日 09:45 作者:不详 来源:中国烟机备件网 第一章,pascal 介绍 一,pascal 的基...
Pascal语法小结
Pascal 语法小结请同学们牢记:计算机的实质是对存储器中(容器)的数据进行修改。不能被计算机语 言的语法所迷惑。对一个程序要一眼就看到本质,找到程序中最关键的...
语法讲义第三讲名词
语法第五讲代词 语法讲义第五讲虚拟语气 语法讲义第七讲虚拟语气 语法讲义第八...语法讲义名词 第三讲名词定义: 名词是表示人,事物,地点或抽象概念的名称。 名词...
初三下学期冲刺中考系列讲义(第七讲)
初三下学期冲刺中考系列讲义(第七讲)_中考_初中教育_教育专区。初三下学期冲刺中考系列讲义(第七讲)第一部分 语法+字词综合运用 语法专题——被动语态考点① 中考...
PASCAL语法分析
Pascal 语言的语法分析器 基于文档最下面词法分析器写的 #include<iostream> #include<cstring> #include<fstream> #include<sstream> #include<string> using ...
Pascal语法小全
Pascal语法小全_其它语言学习_外语学习_教育专区。Pascal 语法小全 OBJECTPASCALPROGRAMING(WRITEDBYC.Y.CATTENTIONSYSTEMDEVELOPMENTCO,.) 1.标记(TOKEN) 1.1特别...
更多相关标签:
pascal语法 | pascalscript语法 | pascal基本语法 | pascal语法分析器 | pascal语言语法 | pascal if then 语法 | pascalscript乘法语法 | free pascal 语法 |