当前位置:首页 >> 学科竞赛 >> 第六章数组

第六章数组


第6章
6.1 问题导引与分析





到目前为止,我们所接触的变量类型(除文件类型外)为简单数据类型,其特点是 对单一的变量进行数据处理和操作。在解决实际问题时,常需要处理大量的数据,如对 1000 个学生的成绩排序、对一批数据进行各种处理等问题,如果用简单变量来存储这些 数据,要用到大量的简单变量,无

论从存储还是处理都很不现实。Pascal 语言引入了数 组类型,能方便地解决批量数据处理问题。 数组是程序设计中最常用的结构数据类型,用来描述由固定数目的同一类型的元素 组成的数据结构。 从形式上看, Pascal 语言数组元素书写格式为: 变量名[下标 1, 下标 2, 下标 3, ??], 数组的每个元素和下标相关联,根据下标指示数组的元素。 只有一个下标的变量集合称为一维数组。 如:a[1],a[2],a[3],a[4],a[5],??,俗称 a 数组。 使用数组的方便之处在于数组的下标可以用变量来表示,如上述的 a 数组元素可以 写成 a[i]形式,通过灵活控制下标变量 i,达到对数组元素进行批量处理和操作的目的。 6.1.1 问题导引 选票统计(Votes)

问题 6.1

【问题描述】 国际运动协会组织了一个评选 N 佳运动员的活动,评选方式很特殊,先由网民投票 选举,各国的网民可以任选自己喜爱的运动员,然后从中选出得票高于 100 万张的运动 员 N 个,对他们用 1 到 N 进行编号,重新投票,根据不同的得票值,颁发不同的奖项, 现在组织者想知道重新投票后,这 N 个运动员的票数,请你帮他完成。 【输入格式】 第一行,一个数,表示 N 个运动员; (1≤N≤1000) 第二行开始为一组以空格隔开的选票,选票值为 1 到 N 间的数,以-1 为数据结束标 志。选票数量不超出长型范围。 【输出格式】 按编号顺序输出编号和票数。 【输入样例】 3 3 1 2 3 2 1 2 3 1 2 2 1 3 3 1 2 3 3 -1 【输出样例】 15 26 37

1

问题 6.2

质数(prime.pas)

【问题描述】 求 1 到 N 间的质数。 【输入格式】 一个数 N。 (1<N<1000000) 【输出格式】 以空格隔开的质数。 【输入样例】 10 【输出样例】 2357 问题 6.3 查找(Find)

【问题描述】 中考成绩出来了,许多考生想知道自己成绩排名情况,于是考试委员会找到了你, 让你帮助完成一个成绩查找程序,考生只要输入成绩,即可知道其排名及同名次的人有 多少。 【输入格式】 第一行一个数 N; 第二行一个数 K; 第三行开始 N 个以空格隔开的从大到小排列的所有学生中考成绩。接着 K 个待查找 的考生成绩。 【输出格式】 K 行,每行为一个待查找的考生的名次、同名次的人数、比考生高分的人数。查找 不到输出“fail!。 ” 【输入样例】 10 2 580 570 565 564 564 534 534 534 520 520 564 520 【输出样例】 423 628 6.1.2 问题分析

分析问题 6.1 对于选票统计问题,如果用人工来统计会是如何统计呢?通常的一种方法是,先写 上每个人选的标识符,如:本题中用编号标识,然后一边唱票,一边在对应人的标识符
2

的下方打上增加票数的标志,如:用“正”字,每增加一票,增加“正”字的一个笔划, 当唱票完毕,统计一下每个人选得到的“正”字的笔划数即为每个人选的票数。然而, 本题中,N 值可以达到 1000,且每人的得票值很大,人工完成统计是不可能的,但人工 的统计方法是可以借鉴的,将人工的统计方法转换为算法,描述如下。 算法描述: 1. 开辟每个人选的票数值存放空间; 2. 读入参选人数 N 值; 3. 读入第一张投票号 X; 4. 当 X<>-1 时,即读票未结束,反复执行下列操作: (1) 对应 X 号人选的票数加 1; (2) 读入下一张投票号 X; 5. 当读完投票,输出参选人的票数。 分析问题 6.2 关于质数判断问题,在第四章的例 4.4 中做过讨论。其算法思想基于数学对质数的 定义,因此,在例 4.4 基础上,我们比较容易得到求 1~N 之间的质数的一种算法,描述 如下。 1. 读入 N; 2. 输出质数 2; 3. 对 3~N 间的每个数进行质数判定,为质数的输出。 该算法的时间复杂度为 O(n2),当 N 比较大时,需要一定时间才能出解。 变换角度分析,2 是质数,2 的倍数一定不是质数,这些数就无需进行质数判定, 同理,3 是质数,3 的倍数一定不是质数,??。于是,先把 N 个自然数按次序排列起 来,1 不是质数,也不是合数,要划去。第二个数 2 是质数留下来,而把 2 后面所有能 被 2 整除的数都划去。2 后面第一个没划去的数是 3,把 3 留下,再把 3 后面所有能被 3 整除的数都划去。3 后面第一个没划去的数是 5,把 5 留下,再把 5 后面所有能被 5 整 除的数都划去。这样一直做下去,就会把不超过 N 的全部合数都筛掉,留下的就是不超 过 N 的全部质数。 这种按顺序输出质数的同时,将质数的倍数筛去的算法,称为筛法。用筛法求质数 是一种比较快的算法,算法时间复杂度为 O(n2)。 这里用到一个名词:算法复杂度。算法复杂度包括时间复杂度和空间、复杂度,时 间复杂度指执行算法所需的时间(执行多少次赋值、比较等操作) ,空间复杂度指执行算 法需要消耗多少存储空间。算法的时间和空间复杂度是算法设计和选择一个很重要的考 量参数。 分析问题 6.3 由于给出的原始数据是有序的,在读入数据过程中可以得到的有效信息有: 1.当读入数与前一个数不同时,名次增 1;
3

2.当读入数与前一个数相同时,相同分数人数增 1,累计到当前的人数增 1。 因此,为了方便后面的查找,先进行预处理,扫描数据,按从大到小的顺序记下每 个不同数据的名次、相同人数、累计人数。在经过预处理后的有序数据中实现查找并输 出。 最简单的查找方式为,按顺序查找,找到相同的成绩或找不到后输出。这种查找方 式称之为顺序查找,显然,在数据量比较大的情况下,顺序查找的效率是比较低的。 寻求提高效率算法的突破口之一,充分利用问题给予的条件,本问题中给出了一个 非常重要的条件就是,数据是有序的。这里引入如何在有序数中快速查找数据的算法---二分查找法。 二分查找算法思想:将 N 个元素分别分成个数大致相同的两半,取中间数 a[n/2], 如果 x=a[n/2],则找到 x,算法终止,如果 x<a[n/2],则在 a[n]的左半部分继续查找 x,如 果 x>a[n/2], 则在 a[n]的右半部分继续查找, 接下去查找的数据范围为上一次数据范围的 一半,继续执行此算法。 例:在有序序列[05 中查找数据 21 和 85。 [05 13 19 21 37 56 64 75 80 88 92] 13 19 21 37 56 64 75 80 88 92]

[05

13

19

21

37]

56

64

75

80

88

92

05

13

19

[21

37]

56

64

75

80

88

92

查找 K=21 的过程(查找成功) [05 13 19 21 37 56 64 75 80 88 92]

05

13

19

21

37

56

[64

75

80

88

92]

05

13

19

21

37

56

64

75

80

[88

92]

05

13

19

21

37

56

64

75

80

[88

92]

查找 K=85 的过程(查找失败) 二分查找算法的时间复杂度为 O(Log2(N))。

4

6.1.3

解决方案 1. 如何定义和存储批量数据; 2. 如何根据需要直接找到批量数据中的某一个数据。 通过对数组的学习和灵活使用,将有效解决批量数据处理等问题。 一维数组 一维数组的定义

为实现问题 6.1、问题 6.2 和问题 6.3 的算法,需要先解决以下几个问题:

6.2 6.2.1

当数组中每一个元素只带有一个下标时,称为一维数组。 PASCAL 语言中,定义数组可以采用以下几种方式。 1.在说明部分的 TYPE 区中定义数组类型,然后再在 VAR 区中说明数组,形式如 下: TYPE 数组类型标识符=array [下标类型] of 元素类型; 下标类型必须是一个顺序类型, 其作用是指定数组下标的编制方式和下标取值范围。 基类型规定了数组元素的类型和性质,可以是 integer,char,real,boolean 等。 例如: TYPE sample=array [1..10]of integer; {有 10 个元素的一维数组} VAR a,b: sample; 在说明部分的 TYPE 区中,由用户定义了一个名为 sample 的数组类型,在 VAR 区部 分说明了 a 和 b 为 sample 类型的数组。 2. 直接在 VAR 区中定义数组 VAR 数组名:array [下标类型] of 元素类型; 例如: VAR a,b: array [1..10]of integer; 3.数组的常量定义 CONST 数组名:array [下标类型] of 元素类型=(逗号隔开的数据) ; 逗号隔开的数据个数要与下标类型定义数组元素个数相一致。 数据类型和元素类型 相一致.

5

例如: (1)const a:array[1..3] of integer=(3,4,5); (2)const Hexadecimal : array[0..15] of char = (‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’, ‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’); 或者: Hexadecimal : array[0..15] of char = ‘0123456789ABCDEF’; 当在说明部分定义了一个数组之后,PASCAL 编译程序为所定义的数组在内存空间开 辟一串连续的存储单元。 例如: TYPE color=(red,yellow,blue,while,black); rowtype=array[1..8] of real; coltype=array[‘A’..’E’] of integer; colortype=array[color] of CHAR; VAR a: rowtype; b: coltype; c: colortype; 以上程序段定义了 a、b、c 三个数组,它们在内存中的排列如下图示意。

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

a[8]

a 数组的存储结构

b[‘A’]

b[‘B’]

b[‘C’]

b[‘D’]

b[‘E’]

b 数组的存储结构

c[red]

c[yellow] c[blue]

c[while]

c[black]

c 数组的存储结构 6.2.2 一维数组的引用

当定义了一个数组,数组中的各个元素就共享一个数组名(即为数组变量名) ,元素 之间通过不同的下标进行区别。对数组的操作归根到底就是对数组元素的操作。 一维数组元素的引用格式为: 数组名[下标表达式]
6

说明: (1)下标表达式值的类型,必须与数组类型定义中的下标类型完全一致,并且不允 许超越所定义的下标上界和下界。 (2)数组是一个整体,数组名是一个整体的标识,对数组进行操作,即对其元素操 作。数组元素可以像同类型的普通变量那样使用。 例如: a[3]:=34; read(a[4]); 例如: VAR a,b,c:array[1..100] of integer; begin ?? c:=a;a:=b;b:=c; ?? end. 在上面程序中,a,b,c 三个数组类型完全一致,c:=a;a:=b;b:=c 实现了 a,b 两个数组所 有元素的交换。 例 6.1 按顺序从键盘输入 50 个整数,将这 50 个数逆序输出,并求位于读入顺序 为偶数位上的整数之和。 问题分析: 本题所做的事就是能够按需求自由地输出和处理输入的数据,由于数据元素个数比 较多,为了方便灵活使用数据,设计一个数组存放输入的数据,每个数据按读入顺序保 存在对应数组元素的下标变量中,这样,将这 50 个数逆序输出问题就转化为控制数组 下标值从 50 变化到 1 的问题,求位于读入顺序为偶数位上的整数之和就转化为求数组 元素下标值为偶数的问题。 算法描述: 1. 定义一个下标范围为[1..50]的数组; 2. 按顺序读入数据,存放在相应的数组下标变量中; 3. 利用循环语句控制数组下标值从 50 变化到 1,输出数组元素; 4. 利用循环语句控制数组下标值从 1 变化到 50,累加下标值为偶数的元素和; 5. 输出累加和。 程序设计: program exam6_1; var a:array [1..50] of integer; i:integer;
7

对数组 a 中下标值为 3 的下标变量赋以 34 的值。 读入一个数存储到下标变量 a[4]元素中。

(3)特殊地,如果两个数组类型一致,它们之间可以整个数组元素进行赋值。

s:longint; begin for i:=1 to 50 do read(a[i]); writeln; s:=0; for i:=1 to 50 do if I mod 2=0 then s:=s+a[I]; writeln('s=',s); end. 针对具体的问题,可以给数组下标变量赋予定的物理意义,方便算法的设计和实 现。如:例 6.1 中,数组下标变量表示第几位上的数组元素,利用循环变量有序地控 制下标变量的变化,达到自如选择数组元素解决问题的目的。 一维数组的应用 实现问题 6.1 算法程序。 //求数组偶数位上的元素值和 //读入数据存放在数组中 //逆序输出数组元素值

for i:=50 downto 1 do write(a[i],' ');

6.2.3

例6.2

设 a 数组用于存放每个运动员的票数,由于参选运动员最多 1000,因此,a 数组元 素个数设计为 1000 个。 赋予数组下标变量物理意义为动员编号标识符。 即 a[x]表示编号为 X 运动员的票数。 当读入数 X,则 X 运动员票数加 1,表示为 a[x]:=a[x]+1,程序实现如下。 Program votes; var a:array[1..1000] of longint; n,x:longint; begin assign(input,'votes.in'); reset(input); assign(output,'votes.out'); rewrite(output); fillchar(a,sizeof(a),0); //表示将数组 a 的所有元素数赋为 0 readln(n); read(x); begin inc(a[x]); read(x); end; for i:=1 to n do
8

{读入参选人数} {读入第一张票}

while x<>-1 do {编号为 X 的运动员票数加 1} {读入选票}

writeln(i, ' ', a[i]); close(input); close(output); end. 例6.3

{按编号顺序输出每个参选运动员有编号和选票}

实现问题 6.2 程序设计。

使用筛法思想求质数算法描述如下: 1.定义布尔型数组 a,数组元质 a[i]表示数 i 是否为质数,由于 FreePascal 布尔型数 组默认的初值为 false,设当 i 为合数时,a[i]值为 true; 2.读入数据范围 n; 3.循环控制数组下标值 i 从 2 变化到 sqrt(n),实现下列操作: 如果当前 i 的数组元素为质数,从数组中筛 去该元素的所有倍数的元素,即 a[i*j]:=true; 4.取出未被筛去的 a 数组元素存放入 p 数组中; 5.输出 p 数组元素。 程序设计: Program prime; var a:array[0..1000000]of boolean;//质数标志数组 p:array[0..500000]of longint; //用于记录质数 pn,n,i,j:longint; begin assign(input,'prime.in'); reset(input); assign(output,'prime.out'); rewrite(output); readln(n); for i:=2 to trunc(sqrt(n)) do //将 sqrt(n)内的质数的倍数筛去 begin if not a[i] then for j:=2 to n div i do a[i*j]:=true; end; for i:=2 to n do //将未被筛去的数存入 p 数组中 if not a[i] then begin inc(pn); p[pn]:=i; end;
9

for i:=1 to pn-1 do write(p[i], ' '); writeln(p[pn]); close(input); close(output); end.

//输出质数

在上述算法程序实现中,每次筛去当前获取的质数的倍数,可能存在某些数被重复 筛的现象。如:N=25 时,6 数字即被 2 筛去也被 3 重复筛。如何做到不重复筛呢?筛数 的原则是筛去质数的连续倍数,在扫描 i 是否为质数过程中,i 是连续数,程序实现方式 可充分利用 i,每次筛去已生成的质数 i 的倍数,直到 i 扫描完。 Program prime; var a:array[0..1000000]of boolean; p:array[0..500000]of longint; pn,n,i,j:longint; begin assign(input,'prime.in'); reset(input); assign(output,'prime.out'); rewrite(output); readln(n); for i:=2 to n do begin if not a[i] then //当前数为质数,记录质数 begin inc(pn); p[pn]:=i; end; for j:=1 to pn do //筛去 p 数组中质数和当前 i 组成 的倍数的数 begin if i*p[j]>n then break; a[i*p[j]]:=true; end; end; for i:=1 to pn-1 do write(p[i], ' '); writeln(p[pn]); close(input);
10

//倍数>n 跳出循环 //如果 i 是某个质数的倍数,则跳出循环

//倍数为合数标志

if i mod p[j]=0 then break;

close(output); end. 例6.4 实现问题 6.3 程序设计。

利用二分查找法实现成绩查找算法描述如下: 1.设数组 a 用于存放不同的分数值,b 用于存放相同分数的人数,s 用于存放高于 此分数的人数。数组下标表示名次。 2.预处理,从高到低读入分数,统计相同分数的人数和高于本分数的人数,统计不 同分人数 p; 3.读入需要查找的成绩 x,二分查找成绩; 4.设变量 l、r、mid 表示指针,分别指向左端、右端和中间数据,初值为 l:=1; r:=p; mid:=(l + r) div 2; 5.如果 r>l 反复执行下列操作: (1)如果 a[mid]=x,退出循环,执行输出; (2)如果 a[mid]>x,说明 x 值位于 mid 到 r 之间,改变左指针为 l:=mid+1; (3)如果 a[mid]<x,说明 x 值位于 l 到 mid 之间,改变右指针为 r:=mid-1; (4)继续二分,让 mid:=(l+r) div 2; 6.判断退出循环时,a[mid]的值是否为查找值,是,输出名次、相同分数的人数和 高于本分数的人数,不是,输出查找不到该分数。 程序设计: Program Find; var a,b,s:array[0..100000]of longint; n,k,i,l,r,mid,p,x:longint; begin assign(input,'find.in'); reset(input); assign(output,'find.out'); rewrite(output); readln(n); readln(k); for i:=1 to n do begin read(x); if a[p]=x then {读入数与前一个数相同,相同分数人数加 1,大等于本分数 的人数 1 } begin inc(b[p]); inc(s[p]);
11

end else begin //读入数与前一个数相同 //名次加 1 //存储分数 //同分人数初值为 1 //大等于本分数的人数初值为前一分数统计值加 1

inc(p); a[p]:=x; b[p]:=1; end; end; for i:=1 to k do begin read(x);

s[p]:=s[p-1]+1;

//二分查找

l:=1; r:=p; mid:=(l + r) div 2; while r>l do begin if a[mid]=x then break

//左、右和中间指针赋初值

//当右指针值不大于左指针值时退出 //查找到退出

else if a[mid]>x then l:=mid+1{若 mid 指针指向的值大于查找值, 则查找 值落在右边值赋域,改变左指针位置} else r:=mid-1; {若 mid 指针指向的值不大于查找值,则查找值落在左边 值赋域,改变右指针位置} mid:=(l+r) div 2; end; if a[mid]<>x then writeln(‘fail!’) else writeln(mid,' ',b[mid],' ',s[mid-1]); end; close(input); close(output); end. 例 6.5 对于任意给定的一组数据,将数据按从小到大或从大到小顺序进行排列称 //继续二分

为排序。排序是我们比较熟悉的概念,在现实生活中有各种各样的排序问题,有各种各 样实现排序的方法,请你例举出你遇到的排序问题和你采用的解决方法,设计实现排序 的不同算法和程序。这是一道开放型的问题,你可以对输入和输出增加限制条件。希望 先自行思考实现后再看下面的分析。 问题分析: 在第三章中,我们曾经遇到三个数的排序问题,可以获得通过对数据进行比较实现 排序的基本思想和方法。然而,当数据量很大的情况下,排序需要解决的基本问题有: 1. 如何存储数据;
12

2. 如何设计能够收敛的算法,即使问题的规模不断减小不直至解决; 3. 考虑算法时间复杂度。 下面将介绍五种排序算法的分析和实现过程。希望通过本问题的分析和实现,除了 掌握数组的灵活应用外,更重要的学会如何从不同的角度分析和解决问题。 以下算法和程序实现默认按从小到大的顺序。 先来看一个有限制条件的排序问题: 输入 N 个数,第一行是 N,之后每行一个数.输出 N 行,为这些数从小到大排序的结果. 每个数都是 1,000,000 以内的正整数。 该问题有一个很重要的条件,就是需要排序的数为 0~1,000,000 以内整数。如何用 上这个条件呢?设数组下标表示每个数,数组元素内容用于存放对应下标数据的个数, 如此,当统计好每个数的个数时,数据自然在数组中形成有序的排列了。 算法: 1、开一个 0..1,000,000 的数组 a; 2、对于每个输入的数,对应的数组下标的值增加 1; 3、按数组下标 i 从小到大的顺序,判断数组元素值,如果不为 0,输出 a[i]个下标 值 i。 这种不用比较的排序算法称为计数排序。由于只用一重循环就能实现数据的排序, 所以,算法时间复杂度为:O(n)。 程序设计: Program Counting_Sort; Var A:array[0..1000000]of longint;//开一个足够大的数组 I,j,n,m:longint; Begin Readln(n);//读入 N For i:=1 to n do Begin Readln(m);//读入数据 a[m]:=a[m]+1;//将数据对应下标的数组值+1 end; for i:=0 to 1000000 do for j:=1 to a[i] do writeln(i);//输出数据 end. 计数排序是一种高效的排序算法。但是它的应用有一定的限制,即具体数据的 范围不能超过数组大小承受能力的极限。 现在讨论一般的排序问题: 输入 N 个数,第一行是 N,之后每行一个数,输出 N 行,为这些数从小到大排
13

序的结果。 分析 1:原始想法 以站队为例,将无序的一个队列,按身高从低到高的顺列。一种比较简单的做 法:从队列中找最矮的人组成新的队列,接着从原队列中再找最矮的人接在新队列 的后面,每次从原队列中找最矮的人接在新队列的后面,直到原队列空了为止。则 新队列就是有序的队列。 算法描述为: 1.设 a 数组存放原始数据,b 数据组存放排序后的数据,t 布尔数组标志 a 数 组中对应的元素是否被取走; 2.将所有的元素设为未标志; 3.循环 N 次,重复下列操作: 遍历一次 a 数组,找出其中未被标志的元素中最小的一个,对它打上标志, 取出,放在另外的数组 b 中; 4.按顺序输出 b 数组元素。 这是一种朴素的算法,也是比较容易想到的算法。 问题与改进: 上述算法花费了三个数组来实现排序,造成了空间上的极大浪费。有没有可以 直接将结果保存在本身数组内的算法呢? (1) 引入交换思想:既然要将元素从小到大排列,那么每当找到一个逆序对(所 谓逆序对指 I,j 两个位置上元素 a[i]和 a[j],当 i<j 时,a[i]>a[j]) ,交换它们的位置, 使得这两个数有序,直到不存在逆序对为止,则序列为有序的序列。 (2)新的问题:如何寻找逆序对呢?因为不同的查找方式和顺序有可能导致算法 的效率不同,必须有规律地查找。 引出两个本质相同但寻找逆序对方法不同的排序算法:冒泡排序与选择排序。 分析 2:冒泡排序的思想 以 n 个人站队为例,从第 1 个开始,依次比较相邻的两个人是否逆序对(高在 前矮在后) ,若逆序就交换这两人,即第 1 个和第 2 个比,若逆序,交换两人,接 着第 2 个和第 3 个比,若逆序,交换两人,接着第 3 个和第 4 个比,若逆序,交换 两人,??,直到 n-1 和 n 比较,经过一轮比较后,则把最高的人排到最后,即将 最高的人像冒泡一样逐步冒到相应的位置。原 n 个人的排序问题,转换为 n-1 个人 的排序问题。第二轮从第 1 个开始,依次比较相邻的两个人是否逆序对,若逆序就 交换这两人,直到 n-2 和 n-1 比较。??,如此,进行 n-1 轮后,队列为有序的队 列。 从上述分析中可以看出,每进行一轮的比较之后,n 个数的排序规模就转化为 了 n-1 个数的排序规模,体现了算法的收敛性。 算法描述为: 1.设 a 数组存放数据; 2.对尚未排序的各元素从头到尾依次比较相邻的两个元素是否逆序(与欲排
14

顺序相反) ,若逆序就交换这两元素; 3.经过第一轮比较后便可把最大(或最小)的元素排好; 4.用同样的方法把剩下的元素逐个进行比较,如果有 n 个元素,那么一共要 进行 n-1 轮比较,就得到了所需要的排序。 程序实现方法:用两重循环完成算法,外重循环 i 控制每轮要进行多少次的比 较,第一轮比较 n-1 次,第 2 轮 n-2,??,最后一轮比较 1 次。内重循环 j 控制每 轮 i 次比较相邻两个元素是否逆序,若逆序就交换这两元素。 算法时间复杂度为 O(N^2)。 程序设计: Program Bubble_Sort; Var A:array[0..1000]of longint;//开一个和数据个数一样多的数组 I,j,n,m:longint; Begin Readln(n);//读入 N For i:=1 to n do readln(a[i]);//读入数据 For i:=n-1 downto 1 do //进行 n-1 轮冒泡 For j:=1 to i do //每轮进行 i 次的比较 If a[j]>a[j+1] then//相邻元素进行比较,如果大的在前面,则交换 Begin M:=a[j]; A[j]:=a[j+1]; A[j+1]:=m; End; For i:=1 to n do writeln(a[i]);//输出排序结果 End. 分析 3:选择排序的思想 以 n 个人站队为例,第一次,从队列中选择最矮的一个人与站在第一个位置上的人 交换位置,则第一位置上的人为最矮,n 个人的队列排序问题转换为 n-1 个人的队列排 序问题, 第二次, 2~n 中队列中选择最矮的一个人与站在第二个位置上的人交换位置, 从 n-1 个人的队列排序问题转换为 n-2 个人的队列排序问题,??,第 n-1 个和第 n 个人进 行比较、交换。经过 n-1 次选择、交换后,原队列就形成了有序的队列。 算法描述为: 1.设 a 数组存放数据; 2.在 1~n 中选择值最小的元素,与第 1 位置元素交换,则把最小元素放入第 1 个位 置; 3.在 2~n 中选择值最小的元素,与第 2 位置元素交换,??;
15

4.直到第 n-1 元素与第 n 个元素比较排序为止。 程序实现方法:用两重循环完成算法,外重循环 i 控制当前序列最小值存放的数组 位置,内循环 j 控制从 i+1 到 n 序列中选择最小的元素所在位置 k。 算法时间复杂度为 O(N^2)。 程序设计: PROCEDURE selection_Sort; VAR A:array[0..1000]of longint; I,J,K,t:LONGINT; BEGIN Readln(n);//读入 N For i:=1 to n do readln(a[i]);//读入数据 FOR I:=1 TO N-1 DO //进行 n-1 次选择 K:=I; //最小元素位置初值 FOR J:=I+1 TO N DO //从 i+1 到 n 序列中选择最小元素,记下位置 IF A[k]>A[J] THEN k:=j; t:=A[i]; //将最小元素与第 i 元素交换 A[i]:=A[k]; A[k]:=t; FOR I:=1 TO N DO WRITE(A[I],' ');//输出排序结果 WRITELN; END. 分析 4:插入排序思想: 回忆一下打牌时抓牌的情景:为了方便打牌,抓牌时一般一边抓牌一边按花色和 大小插入恰当的位置, 当抓完所有的牌时, 手中的牌是有序的。 这能不能应用到排序呢? 运用类比的思想, 当读入一个元素时, 在已经排序好的序列中, 搜寻它正确的位置, 再放入读入的元素。但不该忽略一个重要的问题:在插入这个元素前,应当先将它后面 的所有元素后移一位,以保证前面处理过的元素不致被覆盖。 算法描述为: 1. 设 a 数组存放数据; 2. 从第 2 个数开始,取出当前数作为待排序数,逐个与前面的数比较,若小 于前面数,则前面数后移,当大等于前面数时,插入当前空出的位置; 3. 直到第 n 个数插入正确位置为止。 程序实现方法:用两重循环完成算法,外重循环 i 控制待排序的数,从第 2 个数到 第 n 个数,内重循环 j 控制寻找插入的位置,j 值从 i-1 开始向前扫描,边扫描边将数据 后移,寻找到位置,插入当前值。 算法时间复杂度为 O(N^2)。
16

//开一个和数据个数一样多的数组

PROCEDURE Insertion_Sort; VAR A:array[0..1000]of longint; I,J:LONGINT; Begin Readln(n);//读入 N For i:=1 to n do readln(a[i]);//读入数据 For i:=2 to n do Begin A[0]:=a[i];j:=i-1;//用 a[0]寄存待插入的数 While a[0]<a[j] do //从后向前扫描,如果当前数比寄存的数大,则继续向前扫描 Begin a[j+1]:=a[j];//当前数后移 j:=j-1; //继续向前 end; a[j+1]:=a[0];//找到合适的位置,插入 end; For i:=1 to n do writeln(a[i]);//输出排序结果 End. 分析 5:基数排序 “基数排序法”是属于“分配式排序”,基数排序法又称“桶子法”,顾名思义,它是透 过数值中的部份信息,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数 排序法是属于稳定性的排序,其时间复杂度为 O (nlog(r)m),其中 r 为所采取的基数,而 m 为堆数,在某些时候,基数排序法的效率高于其它的比较性排序法。 基数排序的方式可以采用 LSD(Least significant digital)或 MSD(Most significant digital) ,LSD 的排序方式由数值的最右边开始,而 MSD 则相反,由数值的最左边开始。 以 LSD 为例,假设原来有一串数值如下所示: 73, 22, 93, 43, 55, 14, 28, 65, 39, 81 首先根据个位数的数值,在走访数值时将它们分配至编号 0 到 9 的桶子中: 桶子 0 1 2 3 4 5 6
17

//开一个和数据个数一样多的数组

数据

81 22 73 93 43 14 55 65

7 8 9 28 39

接下来将这些桶子中的数值重新串接起来,成为以下的数列: 81, 22, 73, 93, 43, 14, 55, 65, 28, 39 接着再进行一次分配,这次是根据十位数来分配: 桶子 0 1 2 3 4 5 6 7 8 9 14 22 28 39 43 55 65 73 81 93 数据

接下来将这些桶子中的数值重新串接起来,成为以下的数列: 14, 22, 28, 39, 43, 55, 65, 73, 81, 93 这时候整个数列已经排序完毕。如果排序的对象有三位数以上,则持续进行以上的 动作直至最高位数为止。 LSD 的基数排序适用于位数小的数列, 如果位数比较多, 使用 MSD 的效率会比较好, MSD 的方式恰与 LSD 相反, 是由高位数为基底开始进行分配, 其他的演算方式则都相同。 基数排序算法适用于整数序列,如果非整数序列的类似算法为桶子排序法。请上网 查找相关的资料。 在本例子中给出了多种排序算法,请大家进一步思考这些算法思想的异同点,它们 各自利用了问题和数据中哪些性质实现排序,设计多种数据测试各种排序算法在不同数 据情况下的时间效率,并分析原因。 可能,有同学认为掌握并能运用一种排序方法即可。但作为一种经典算法,我们需 要学习的是其算法的分析思想而不是最终结论,通过不同方法的问题解决过程逐步建立 根据问题的特点和性质有效地分析问题的意识,建立算法效率意识,通过一题多解,完 善测试数据等方面提高算法效率和程序设计能力。 多维数组 多维数组的定义 一维数组在编程中多数用于描述线性的关系:如一组数;一组成绩;一组解答等。 数组元素只有一个下标,表示该元素在数组中的位置。 二维数组在编程中多数用于描述二维的关系:如地图、棋盘、城市街道、迷宫等。
18

6..3 6.3.1

二维数组元素有两个下标:第一个下标一般表示该元素在第几行,第二个下标一般 表示在第几列。 为了描述更加复杂的关系, 比如, 平面上的若干个点或空间中的若干个点等等, Pascal 语言提供了多维数组。 多维数组类型定义如下: TYPE 数组类型标识符=array [<下标类型 1>,…, <下标类型 n>] of 元素类型; 例如,要定义一个二维数组,如下: type sample2=array[1..3,1..5] of real; var a: sample2; 相当于定义了一个二维表格,每个表格对应于一个实型变量,下标变化如下: [1,1] [2,1] [3,1] 使用二维数组要注意: 1. 数组元素的名称:数组名[i,j],表示第 i 行、第 j 列元素。如:a[3,4],表示第 3 行、第 4 列的元素。 对某一行进行处理,如:累加第 4 行的第 1~5 列元素数据,则固定行号为 4,语句 实现: for i:=1 to 5 do s:=s+a[4,i]; 对某一列进行处理,如:累加第 4 列的第 1~10 行元素数据,则固定列号为 4,语句 实现: for i:=1 to 10 do s:=s+a[i,4]; 2. 二维数组的输入输出要用双重循环来控制: 输入示例: for i:=1 to 10 do 输出示例: for i:=1 to 10 do begin for j:=1 to 5 do write(a[i,j]:4); writeln; end; 多维数组的使用与二维数组类似,下面重点学习二维数组的应用。 二维数组的应用
19

[1,2] [2,2] [3,2]

[1,3] [2,3] [3,3]

[1,4] [2,4] [3,4]

[1,5] [2,5] [3,5]

{控制行数} {读入每行的 5 个元素}

for j:=1 to 5 do read(a[i,j])

6.3.2

例 6.6

杨辉三角形(YHTriangle)

【问题描述】 杨辉三角是一个由数字排列成的三角形数表,一般形式如下: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 【输入数据】 一个正整数 n,表示三角形的行数 【输出数据】 n 行杨辉三角形 问题分析: 观察杨辉三角形不难看出,数字是有规律的,从第 3 行开始,每行第 1 个和最后一 个值为 1,其他值为上方和左上方数字和。 设二维数组 c[i,j]存储行坐标为 i、列坐标为 j 位置上元素值,则 c[i,j]= c (i-1,j-1)+ c (i-1,j) 每个元素值由其左上方和上方元素求和得到,因此,可以一行地求得元素值。 算法描述: 1. 定义二维数组 C 存放杨辉三角形的值; 2.赋初值:c[1,1]:=1; c[2,1]:=1;c[2,2]:=1; 3.用二重循环控制二维数组下标的变化,从上到下,从左到右求元素值; 4.输出杨辉三角形。 程序设计: program YHtriangle; const n = 20; var c:array[0..n,0..n]of longint; i,j,m:longint; begin c[1,1]:=1; //赋初值 c[2,1]:=1;c[2,2]:=1; for i:=3 to n do //从第 3~ n 行 begin
20

//输出行数

c[i,1]:=1; for j:=2 to i-1 do c[i,i]:=1; end; for i:=1 to n do for j:=1 to i do if j=i then writeln(c[i,j]) else write(c[i,j],' ');//输出杨辉三角形 end. 例 6.7 数字三角形(NT) //从第 2~ i-1 列

c[i,j]:=c[i-1,j-1]+c[i-1,j]; //求二维数组元素值

【问题描述】 给定一个具有 N 层的数学三角形如下图,从顶至底有多条路径,每一步可沿左斜线 向下或沿右斜线向下,路径所经过的数字之和为路径得分,请求出最小路径得分。 2 62 184 1568 【输入数据】 第 1 行,一个正整数 n,表示三角形的行数 第 2 至 n+1 行,照描述输入三角形 【输出数据】 最小路径得分,行末有换行 【样例输入】 4 2 62 184 1568 【样例输出】 10 【注意】 测试数据规模: 保证 100%的数据 n<=1000。 问题分析: 求最小路径得分,比较容易想到的是: 1.如果知道从第 1 行走到第 n 行各数字上的最小得分,那么,从中取最小值即可; 2.第 n 行是从 n-1 行走下来的,如果知道第 n-1 层各数字位置上的最小得分值,那
21

么根据规则每步只能沿左斜线向下或沿右斜线向下,要使第 n 层的各数字位上得到最小 得分值,只能从左上和右上两个得分值中取小的一个与当前位的数字相加; 3.同理,第 n-1 层各数位上的最小得分可以从第 n-2 层推出; 4.考虑第 I 层与第 I-1 层的关系,可以推出如下关系: 设 D[I,J]表示第 I 层,第 J 列位置上的最小路径得分,A[I,J]表示第 I 层,第 J 列位 置上的数字,则: D[I,J]=MIN(D[I-1,J],D[I-1,J-1])+A[I,J] 5.从上至下求得 D[I,J],那么问题的解为 D[n,J](1≤J≤n)中最小数。 进一步分析: 在上述分析中,思考问题的角度按照题意给出从第 1 层到第 n 层,如果换个角度从 第 n 层到第 1 层,每次按规则从可选的相邻两数中选择小的数向上传递,可以发现效果 是一样,且当走到第 1 层时,即为最小分值和。这样就不必再在最后一行中求最小数。 算法描述: 1. 定义二维数组 a 存放数据; 2. 读入原始数据; 3. 控制循环变量 i 从 n-1 行到第 1 行,每行重复下列操作: 求每列的元素值为当前元素值与 a[i+1,j]、a[i+1,j+1]两元素中最小值之和; 4.输出 a[1,1]。 程序设计: Program Nt; Const Filein='Nt.in'; Fileout='Nt.out'; Var N:longint; A:array[1..1000,1..1000]of longint; I,j:longint; Begin Assign(input,filein); Assign(output,fileout); Reset(input); Rewrite(output); Readln(n); //读入数据 For i:=1 to n do Begin For j:=1 to i do read(a[i,j]); Readln; End;
22

For i:=n-1 downto 1 do //控制第 n-1 行至第 1 行 For j:=1 to i do //每个元素值为下方和右下方两数中小的数加自身数 If a[i+1,j]<=a[i+1,j+1] then inc(a[i,j],a[i+1,j]) else inc(a[i,j],a[i+1,j+1]); Writeln(a[1,1]);//输出最小分值和 Close(input); Close(output); End. 例6.8 过河卒(Soldier)

【问题描述】 如图,A 点有一个过河卒,需要走到目标 B 点。卒行走规则:可以向下、或者向 右。同时在棋盘上的任一点有一个对方的马(如图的 C 点) ,该马所在的点和所有跳跃 一步可达的点称为对方马的控制点。例如图 6.1 中 C 点上的马可以控制 9 个点(图中 除 A,B 之外的黑点) 。卒不能通过对方马的控制点。

C

图 6.1

示例图

棋盘用坐标表示,A 点(0,0) 、B 点(n,m)(n,m 为不超过 100 的整数,同样马的位 置坐标是需要给出的(约定: C<>A,同时 C<>B) 。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。 【输入数据】 B 点的坐标(n,m)以及对方马的坐标(X,Y) 【输出数据】 一个整数(路径的条数) 。 【样例输入】 6632 【样例输出】 17 问题分析: 本题选自 NOIP2002 普及组试题。 设二维数组 a[I,j]表示从 A 点走到第 I 行第 j 列位置的路径条数。按题意,过河卒只 能向下、或者向右行走。
23

1.观察图中行坐标轴和列坐标轴上点的路径条数,则: A[I,0]=1,A[0,J]=1 2.对于没被马控制的坐标点,如图中[1,1]点,只能从[0,1]和[1,0]走到[1,1]点, 则: A[1,1]=A[1,0]+A[0,1]=2 同理:任意一个没被马控制的坐标点[I,j],只能从[i-1,j 和[i,j-1]走到[1,1]点,则: A[I,J]=A[I-1,J]+A[I,J-1] 3.对于被马控制的坐标点,则: A[I,J]=0 那么,对于已知马点坐标[I,j],如何标识被马控制的坐标点呢? 如图 6.2 所示,根据马的走步规则,中心位置马所能 控制的点为图中的 1~8 点,设 dx、dy 表示被马控制点相对 于马的坐标位移,则: Dx[1~8]= (2,1,-1,-2,-2,-1,1,2) Dy[1~8]= (1,2,2,1,-1,-2,-2,-1) 已知马点坐标[x,y],求得被马控制点的坐标为: X=x+dx y=y+dy 图 6.2 马的走步 综合上述分析,算法描述如下: 规则 点[X,Y]及其控制点的坐标,定义一个二维数组 a 存储从 A 点走到各点的路径条 数; 2.标识被马控制的点; 3.赋起点初值 a[0,0]:=1,求行坐标轴和列坐标轴上点的路径条数; 4.用二重循环 I,j 分别控制从第 1 行到第 n 行,从第 1 列到第 m 列,执行下列操作: (1)非马控制点,a[i,j]:=a[i-1,j]+a[i,j-1] (2)马控制点,a[i,j]:=0 5.输出 a[n,m]。 程序设计: program Soldier; const dx:array[1..8]of integer=(2,1,-1,-2,-2,-1,1,2); dy:array[1..8]of integer=(1,2,2,1,-1,-2,-2,-1); var a:array[0..100,0..100]of int64; b:array[0..100,0..100]of boolean; x,y,i,j,m,n:integer; begin read(n,m,x,y);//读入 B 点坐标和马点坐标 fillchar(a,sizeof(a),0); //A 数组初值为 0
24

1.定义一个二维布尔型 b 数组,标识马

//控制点相对马点的坐标位移

fillchar(b,sizeof(b),true);//B 数组初值为 true a[0,0]:=1; //起点路径初值为 1 b[x,y]:=false; //标识马点及其控制点 for i:=1 to 8 do if (x+dx[i]>=0) and (x+dx[i]<=m) and (y+dy[i]>=0) and (y+dy[i]<=n) then b[x+dx[i],y+dy[i]]:=false; for i:=1 to n do //求列坐标轴 上 的路径值 if b[i,0] then a[i,0]:=a[i-1,0]; for j:=1 to m do //求行坐标轴的路径值 if b[0,j] then a[0,j]:=a[0,j-1]; for i:=1 to n do //求各点的路径值 for j:=1 to m do if b[i,j] then a[i,j]:=a[i-1,j]+a[i,j-1]; writeln(a[n,m]);//输出 end. 6.4 数组应用实例 实例 1 矩形(MAXT) ——枚举法应用例举

6.4.1 【问题描述】

小明有很多个矩形,他们可能有不同的长和宽,现在, 小明需要在矩形中放入矩形, 他想在一个大的矩形中放入两个较小的矩形,就像如下图这样:

现在给出小明所拥有的矩阵, 请你选出 3 个,使得这 3 个矩阵可以像上面这张图一样, 一个套两个,输出总方案数。 注意: 1.大矩形内的两个小矩形不能重叠,比如下面的情况是不可以的。

2.内矩阵的边应与外矩形平行,即内矩形不可以斜放,如下图是不可以的。

25

3.矩形的边可以重叠。 4.允许矩形旋转 90 度后放入矩形中。 【输入文件】 文件名:MAXT.IN 文件第一行为一个整数 N(1<=N<=50),表示矩阵的个数。 之后 N 行,每行两个整数,表示矩阵的长和宽。(长宽小等于 1000) 【输出文件】 文件名:MAXT.OUT 文件中只有一个整数,表示选出合法矩形的方案数。 (矩形按输入顺序编号 1 到 N,如果两种方案使用的矩形编号组合相同,就视为相同方 案,如果有一个不相同的矩形编号,则视为不同方案) 【样例输入】 4 30 30 8 9 5 10 10 5 【样例输出】 3 【样例说明】 3 种方案: 选取 1,2,3 选取 1,2,4 选取 1,3,4 问题分析: 根据题意,已知矩形的个数和每个矩形的大小参数,很自然想到的一种方法是,先 选择最外的矩形,再选择中间的两个矩形,比较三个矩形是否符合题目中的嵌套条件。 问题是如何才能找出所有符合题目嵌套条件的方案呢?当选择最外矩形和选择中间两个 矩形时,如果把每个矩形都尝试过,那么找出所有方案的问题就迎刃而解。这种把所有 可能的情况都尝试过的方法称为枚举法。 怎样实现矩形的枚举呢? 设两个一维数组 x、y 存放矩形的长和宽,给数组下标赋予物理意义,表示第几个矩
26

形,这样,枚举数组下标值即将所有的矩形枚举过。 用三重循环,第一重循环枚举最外面一个矩形,接着用两重循环枚举中间两个矩形, 判断中间两个矩形能否放入外面矩形中。 问题的关键是如何判断中间两个矩形能否放入外面矩形中,需要考虑多种情况。如 果两个矩形可以同时放进去,则计数器加 1。 假如枚举的中间两个矩形形状如下: ① ②

那么他们的位置关系有: 1. ① ② ② 3. ① ② 4. ① 2. ①



5. ① ②

6.





7. ① ②

8. ①



27

算法描述: 1. 读入每个矩形的长和宽存入一维数组中; 2. 用一重循环枚举最外矩形; 3. 用二重循环枚举中间两个矩形; 4. 判断中间矩形的 8 种形态是否能放入最外矩形中,只要有一种形态能够放入,方 案数加 1; 5. 枚举结束,输出方案数。 程序设计: Probram MAXT; var x,y:array[1..100]of longint; ii,ans,i,j,k,n,m:longint; procedure swap(var q,p:longint);//实现两个数的交换过程 var mid:longint; begin mid:=q; q:=p; p:=mid; end; begin assign(input,'MAXT.IN');reset(input); assign(output,'MAXT.OUT');rewrite(output); readln(n); ans:=0; for i:=1 to n do readln(x[i],y[i]); //读入矩形 for ii:=1 to n do //枚举外矩形 for j:=1 to n-1 do //枚举内矩形 for k:=j+1 to n do begin m:=0; //第 1、2 种矩形状态判断 if (x[j]+x[k]<=x[ii])and(y[j]<=y[ii])and(y[k]<=y[ii]) then m:=1; if (y[j]+y[k]<=y[ii])and(x[j]<=x[ii])and(x[k]<=x[ii]) then m:=1; swap(x[j],y[j]); //第 3、4 种矩形状态判断 if (x[j]+x[k]<=x[ii])and(y[j]<=y[ii])and(y[k]<=y[ii]) then m:=1; if (y[j]+y[k]<=y[ii])and(x[j]<=x[ii])and(x[k]<=x[ii]) then m:=1; swap(x[k],y[k]); //第 5、6 种矩形状态判断 if (x[j]+x[k]<=x[ii])and(y[j]<=y[ii])and(y[k]<=y[ii]) then m:=1;
28

if (y[j]+y[k]<=y[ii])and(x[j]<=x[ii])and(x[k]<=x[ii]) then m:=1; swap(x[j],y[j]); //第 7、8 种矩形状态判断 if (x[j]+x[k]<=x[ii])and(y[j]<=y[ii])and(y[k]<=y[ii]) then m:=1; if (y[j]+y[k]<=y[ii])and(x[j]<=x[ii])and(x[k]<=x[ii]) then m:=1; swap(x[k],y[k]); //矩形恢复原来状态 ans:=ans+m; end; writeln(ans); close(input);close(output); end. 程序设计中用到了一个过程 procedure swap(var q,p:longint),实现 q、p 两数的交换, 通过主程序的 swap(x[k],y[k])调用过程, x[k]、 将 y[k]的值传给 q、 交换后 q、 传给 x[k]、 p, p y[k]返回主程序,实质上实现 x[k]、y[k]的数据交换。详细知识请看第七章。 枚举法总结: 枚举算法的基本思想是根据提出的问题,枚举所有可能状态,并用问题给定的条件 检验哪些是需要的,哪些是不需要的,能使命题成立,即为其解。 枚举算法求解的问题通常满足两个条件: 1.可预先确定每个状态的元素个数 n; 2.状态元素 a1,a2,…,an 的可能值为一个连续的值域。 枚举法的优点: 1.枚举算法一般是问题的“直译”,算法比较直观,易于理解; 2.枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上,所以算法的正确 性比较容易证明。 枚举法的缺点: 枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价,因此效率比较低。 提高枚举效率的一般方法有: 1.从问题的实际情况出发,通过预处理尽可能减少重复操作; 2.根据问题的实际的条件实施剪枝处理。 所谓剪枝,就是跳过不可能的状态,以提高枚举的效率。下面通过实例 2 进一步了 解枚举算法思想的应用。 火柴棒等式(matches) ——枚举法应用例举

6.4.2

实例 2

【问题描述】 给你 n 根火柴棍,你可以拼出多少个形如“A+B=C”的等式?等式中的 A、B、C 是 用火柴棍拼出的整数(若该数非零,则最高位不能是 0) 。用火柴棍拼数字 0-9 的拼法如 图所示:

29

注意: 1.加号与等号各自需要两根火柴棍 2.如果 A≠B,则 A+B=C 与 B+A=C 视为不同的等式(A、B、C>=0) 3.n 根火柴棍必须全部用上 【输入】 输入文件 matches.in 共一行,又一个整数 n(n<=24) 。 【输出】 输出文件 matches.out 共一行,表示能拼成的不同等式的数目。 【输入输出样例 1】 matches.in 14 【输入输出样例 1 解释】 2 个等式为 0+1=1 和 1+0=1。 【输入输出样例 2】 matches.in 18 【输入输出样例 2 解释】 9 个等式为: 0+4=4 0+11=11 1+10=11 2+2=4 2+7=9 4+0=4 7+2=9 10+1=11 11+0=11 问题分析: 本题选自 noip2008 提高组试题。 设等式三个变量为 A、B、C,如果已知 A 和 B,则 C=A+B。由于题目给出的火柴数 目范围很小,选择枚举算法,枚举 A、B 值,求得 C 值,累计满足等式 A+B=C 所用的火 柴数目为输入值即获得问题的解。 对于本题, 我们能否从细节上提高枚举算法的效率呢? 1.根据 n<=24 条件,确定枚举 A 和 B 的范围。即如果都使用最少火柴的数字(如 matches.out 9 matches.out 2

30

数字 1)构造表达式中的数,得到最大的数是多少,可以算出该数<1000,因此 A 和 B 的范围为 0~1000; 2、在枚举表达式过程中,需要反复计算每个数所用的火柴数目,即相同的数有可 能重复计算许多次的火柴数目,显然,需要想办法减少重复计算。先进行预处理,将估 算范围内的数所用的火柴数目算出; 3、枚举过程中如果当前数的火柴数目超过输入限制做剪枝处理。 算法描述: 1. 预处理:求 0~2000 数对应的火柴数目; 2. 使用循环枚举 A 值 0~1000,执行下列操作: (1) 判断 A 值的火柴数目是否超过限制值,是的,剪枝,跳过该数的处理; (2) 否,使用循环枚举 B 值 0~1000,执行下列操作: ①判断 A 和 B 值的火柴数目和是否超过限制值,是的,剪枝,跳过该数 的处理; ②否,求 C 值,若 A、B、C 值火柴数目和等于限制值,计数方案数; 3.输出方案数。 程序实现如下: program matches; const inp='matches.in'; oup='matches.out'; maxn=1000; var f:array[0..maxn*2] of longint; i,j,k,n,x,ans:longint; begin assign(input,inp); reset(input); assign(output,oup); rewrite(output); readln(n); f[0]:=6; f[1]:=2; f[2]:=5; f[3]:=5; f[4]:=4; //0~9 需要的火柴棒数 f[5]:=5; f[6]:=6; f[7]:=3; f[8]:=7; f[9]:=6; for i:= 10 to maxn*2 do begin x:=i; while x>0 do begin
31

//预处理 0~2000 每个数需要的火柴棒数

f[i]:= f[i]+f[x mod 10]; x:=x div 10; end; end; ans:=0; n:=n-4;//总火柴棒数减去'+'和'='所需的火柴棒数 for i:= 0 to maxn do //枚举 A begin if f[i]>=n then continue; //剪枝,继续 i 循环 for j:= 0 to maxn do//枚举 B begin if f[i]+f[j]>=n then continue;//剪枝,继续 j 循环 k:=i+j; if f[i]+f[j]+f[k]=n then inc(ans);//符合条件,总数加 1 end; end; writeln(ans); close(input); close(output); end. 实例 3 最大子段和(SEQ)——贪心思想应用例举

6.4.3 【问题描述】

老师给笑笑布置了一份的作业,笑笑不知如何解决,找你帮忙解决。 老师给了一串很长的数列,要求从中找出连续的一段来使得总和最大。 【输入文件】 文件名:SEQ.IN 文件中第一行包括一个整数 N,表示数列长度为 N(N <= 100000) 。 第二行包括 N 个整数来描述这个数列,每个整数的绝对值不超过 1000。 【输出文件】 文件名:SEQ.OUT 文件中只有一个整数,为最大的连续段总和。 【样例输入】 5 1 -2 3 1 -4 【样例输出】 4 问题分析:
32

求“最大连续段和”是一个比较基础的问题,可以用多种方法解决,下面讨论三种 算法,请大家通过具体的数据测试实现三种算法的程序效率,学习逐步求精的算法分析 方法。 算法 1: 枚举:用三重循环枚举子段起点位置、终点位置、求子段和,比较子段和求最大值。 算法时间效率 O(n )。 算法 2: 算法 1 中,在求子段和过程中有许多重复的操作,如:求第 3 个数到第 5 个数的和 包含在求第 2 个数到第 5 个数和之中,显然,重复进行了求和操作。如何解决呢? 解决方法是通过预处理, 求出从第 1 位置到每个位置的和 b[i], b[i]值等于 b[i-1] 而 值加当前位置值,减少了重复求和运算,对于子段[I,j]的子段和 S,则有 s=b[j]-b[i]。 这样,用两重循环枚举子段起点位置 i 与终点位置 j,求得所有子段和,比较子段 和求最大值。算法时间效率 O(n )。 算法 3: 设 B[j]为以第 j 个位置为结尾的最大子段和, B[j-1]大于 0, 若 显然, B[j]=B[J-1]+ 当前数,因为,与和大于 0 连续序列构成的序列和一定比本身数构成的序列和大,如果 B[j-1]小于 0,则 B[j]=当前数,因为,当前数大于当前数加上一个负数。 这里应用了一个贪心思想,当前数+正数>当前数,当前数+负数<当前数。通过求从 第 1 个到第 n 个数以本身数为结尾的最大子段和,即枚举了所有数最大子段和。 由于问题只求最大子段和,在求解过程能够求得以当前数为结尾的最大子段和,然 后比较记下其中的最大值即可。 设连续子段和为 t,则: t+a[i] t= a[i] 算法描述: 1. 读入序列中的 n 个数存放在 a 数组中; 2. 初值设置,第 1 个数的子段和 t=a[1],最大子段和 ans=a[1]; 3. 一重循环枚举第 2 个数到第 n 个数,执行下列操作: (1) 求以当前数为结尾的最大子段和 t; (2) 如果 t>ans,刷新 ans 值; 4. 输出 ans 值。 算法时间效率为 O(n) 。 程序设计: Program SEQ; var a:array[1..100000]of longint; n,i,t,ans:longint; begin
33
2 3

t>=0 t<0

assign(input,'SEQ.in'); reset(input); assign(output,'SEQ.out'); rewrite(output); readln(n); for i:=1 to n do read(a[i]); t:=a[1]; ans:=a[1]; for i:=2 to n do begin if t<0 then t:=a[i] //求当前数结尾的最大子段和 else t:=t+a[i]; if t>ans then ans:=t; end; writeln(ans); close(input); close(output); end. 本题分析中用到了一个贪心思想,所谓贪心思想也称之贪心算法是指,在对问题求 解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,所做 出的仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解,但对许多问题能产生整体最优解或 者整体最优解的近似解。 贪心算法的基本思路: 1.建立数学模型来描述问题; 2.把求解的问题分成若干个子问题; 3.对每一子问题求解,得到子问题的局部最优解; 4.把子问题的局部最优解合成原来问题的解。 贪心算法的基本实现过程: 从问题的某一初始解出发; while 能朝给定总目标前进一步 do 求出可行解的一个解元素; 由所有解元素组合成问题的一个可行解。 本实例,把求所有子段和的最优性问题,分成求以每个数为结尾的最大子段和子问 题,通过枚举,从子问题的最优值得到整个问题的最优解。下面通过实例 4 进一步了解 贪心算法思想的应用。 实例 4 集合删数(number) ——贪心思想应用例举
34

//t 当前数结尾的最大子段和,ans 最大子段和

//求最大子段和

6.4.4

【问题描述】 一个集合有如下元素:1 是集合元素;若 P 是集合的元素,则 2 * P +1,4*P+5 也是 集合的元素,取出此集合中最小的 n 个不同的元素,按从小到大的顺序组合成一个多位 数,现要求从中删除 m 个数位上的数字,使得剩下的数字最大,编程输出删除前和删除 后的多位数字。 注:不存在所有数被删除的情况` 【输入文件】 输入的仅一行,n,m 的值,n,m 均小于等于 30000。 【输出文件】 输出为两行,第一行为删除前的数字,第二行为删除后的数字。 【样例输入】 5 4 【样例输出】 137915 95 问题分析: 本问题实际上由两个子问题组成: 1.构造一个多位数:1 是集合元素;若 P 是集合的元素,则 2 * P +1,4*P+5 也是 集合的元素,取出此集合中最小的 K 个不同的元素,按从小到大的顺序组合成一个多位 数; 2.从多位数中删除 M 个数位上的数字,使得剩下的数字最大。 问题 1: 分析集合元素特点:若 P 是集合的元素,则 2 * P +1,4*P+5 也是集合的元素 ,而 函数 2 * P +1 和函数 4*P+5 是单调递增的函数。 将 2 * P +1 与 4*P+5 产生的元素看成两个集合, 每次从两集合中选择最小的一个元 素,作为总集合元素,继续生成两集合的元素,则所得到的总集合元素一定是有序的。 显然只需比较两集合中当前未被取走的第一个元素。 引入指针概念:设 a 指向 2 * P +1 当前未被取走的第一个元素,2 指向 4*P+5 当前 未被取走的第一个元素。 比较 a、b 指向的元素,取最小的一个,将取走元素队列的指针指向下一个元素。 例:生成 5 元素的集合数。 初值:总集合元素为{1},a=1,b=1 (1) 2*P+1 元素:{3} 4*P+5 元素:{9} 选择 3,总集合元素为{1,3},a=2,b=1 (2) 2*P+1 元素:{3,7} 4*P+5 元素:{9} 选择 7,总集合元素为{1,3,7},a=3,b=1
35

(3) 2*P+1 元素:{3,7,15} 4*P+5 元素:{9} 选择 9,总集合元素为{1,3,7,9},a=3,b=2 (4) 2*P+1 元素:{3,7,15} 4*P+5 元素:{9,17} 选择 15,总集合元素为{1,3,7,9,15},a=4,b=2 问题 2: 对于由问题 1 生成元素组成数, 如上例中的生成 5 个元素构成的数为 137915, 从中删除 m 个数,使留下的数最大。如从数 137915 中删除 4 个数字,留下的最大数为 95。 根据数的常识,我们可以得到一个贪心原则为:留下的数高位越大越好。 为此,从高位到低位扫描数中每个数字,边取数字边处理。当前数字能否作为剩余 序列的最高位?如果能,则逐个删除前面比自己小的数。 当前数是否取代前面留下的数的条件为: (1)当当前数大于前面数时; (2)还能够删除数。 算法描述: 1. 求得集合中最小的 n 个元素按从顺序存放在 p 数组中,并输出; 2. 拆分 p 数组中的每个元素; 3. 对于拆分出来的每一个数字判断是否删除前面数字保留; 4. 删除 m 个数字,输出留下的序列数。 程序设计: Program number; Type Tindex = longint; var n,m,bm,tot : TIndex; p : array[1..30000] of TIndex; S : array[0..200000] of TIndex; t : array[0..10] of Tindex; i,a,b,x,y,tail : Tindex; Begin assign(input,'number.in'); assign(output,'number.out'); reset(input); rewrite(output); readln(n,m); //读入数据 bm:=m; //保留删除数字个数 a:=1;b:=1; //两队列指针
36

p[1]:=1; //p 数组存放集合元素 For i:=2 to n do begin x:=p[a]*2+1; y:=p[b]*4+5; //求两队列指针指向的元素值 if x<=y then begin if x=y then inc(b); p[i]:=x;inc(a); end else begin p[i]:=y;inc(b); end; end; For i:=1 to n do write(p[i]);//输出集合生成的序列数 writeln; tail:=1;s[0]:=maxlongint; //tall 指针 s[1]:=1; tot:=1;;//s 数组存储留下的数字序列,tot 原序列数字个数 For i:=2 to n do //集合第 2~n 个元素 begin t[0]:=0; while p[i]>0 do //对集合中每个元素的数进行拆分成数字 begin //从低位到高位存放在 t 数组中,t[0]存放位数 inc(t[0]);t[t[0]]:=p[i] mod 10; p[i]:=p[i] div 10; end; inc(tot,t[0]);//求总数位 repeat inc(tail); while (t[t[0]]>s[tail-1])and(m>0) do {当前数字大于前面保留的数字且还 可删除} begin //删除前面保留的数字,指针前移 dec(m); dec(tail); end; s[tail]:=t[t[0]]; //保留当前数字 dec(t[0]);//继续下一个拆分数字的处理 until t[0]=0; end;
37

//选择小的数存入集合中

For i:=1 to tot-bm do //输出保留的数字 write(s[i]); writeln; close(input); close(output); End. 6.4.5 实例 5 奇因数(fsum)——递推算法应用例举

【问题描述】 我们定义 f(X)为 X 最大的奇数因数。比如 F(18)=9. 输入 n,输出 f(1)+f(2)+?+f(n) 【输入文件】 一个整数,n。 【输出文件】 输出连加的和。 【样例输入】 5 【样例输出】 11 【数据规范】 30%:n<=1000 60%:n<=1000000 100%:n<=1000000000 问题分析: 根据题意,对于所有奇数 f(x)=x,对于一个偶数 f(x)=f(x/2),那么,很容易用 O(n)时 间求得问题的解。 然而, 观察数据规模 n<=1000000000, 有否更快的解决问题的算法呢? 设 s(x) =f(1)+f(2)+?+f(x),进一步推得: 1.对于一个 s(x),如果 x 是奇数,那么由于 f(x)=x,则 s(x)=s(x-1)+x,转化为偶数和 加 X; 2.如果 x 是偶数,那么我们可以把 f(1)到 f(x)的求和分为 s(奇数)和 s(偶数); 由于奇数时 f(x)=x,s(奇数)=1+3+5+...+x-1=x*x/4 而偶数时 f(x)=f(x/2),所以 s(偶数)=f(2)+f(4)+f(6)+...+f(x)=f(1)+f(2)+f(3)+...+f(x/2)=s(x/2) 综上所述 当 x 为奇数时,s(x)=s(x-1)+x = s((x-1)/2)+(x-1)*(x-1)/4+x=s((x-1)/2)+(x+1)*(x+1)/4 当 x 为偶数时,s(x)= s(x/2)+x*x/4 根据这个递推式看出,一个 n 规模的值可以由 n/2 规模的值推出,即运算时间复杂 度为 O(logn)。
38

s(x)是一个递推式也是否个累加式,程序实现时,采用倒推思想实现更为方便,不断 让 n=n div 2,累加对应 n 的累加项值。 算法描述: 设所求最大的奇数因数和为 ans; 1. 读入 n 值; 2. 当 n>0 时,重复下列操作: (1) 当 n 为奇数时,ans=ans+(n+1)*(n+1)/4; (2) 当 n 为奇数时,ans=ans+(n)*(n)/4; (3) n=n div 2; 3.输出 ans 的值。 程序设计: Program Fsum; Const Filein='fsum.in'; Fileout='fsum.out'; Var Ans:int64; N: int64; I:longint; Begin Assign(input,filein); Assign(output,fileout); Reset(input); Rewrite(output); Readln(n); While n>0 do //采用倒推思想求最大的奇数因数和 Begin If odd(n) then Ans:=ans+ (1+n)*(n div 2+1)div 2 else Ans:=ans+(n)*(n div 2)div 2; N:=n div 2; End; Writeln(ans); Close(input); Close(output); End. 本题中用到了“递推”和“倒推”名词,其实,递推、倒推等推理思想在我们生活 中经常运用,当把推理过程用有效的数学式子和步骤表达出来,我们称之为递推算法。
39

递推是计算机数值计算中的一个重要算法,其思想是通过数学推导,将复杂的运算 化解为若干重复的简单运算,以充分发挥计算机善长于重复处理的特点。 递推算法解决问题的一般步骤: 1.建立递推关系式; 2.确定边界条件; 3.递推求解 。 递推的形式通常有:顺推法和倒推法如图 6.7 所示。

图 6.7

顺推法和倒推法表示形式

现在,请大家用上推递的思想重新阅读本章例题 6.6 杨辉三角形、例题 6.7 数字三角 形、例题 6.8 过河卒问题。从逻辑上归纳这些问题的本质特点,学会运用推递思想解决 相关问题。下面通过实例 6 进一步了解推递算法思想的应用。 6.4.6 实例 6 守望者的逃离(escape)——递推算法应用例举

【问题描述】 恶魔猎手尤迫安野心勃勃.他背叛了暗夜精灵,率深藏在海底的那加企图叛变:守望 者在与尤迪安的交锋中遭遇了围杀.被困在一个荒芜的大岛上。为了杀死守望者,尤迪安 开始对这个荒岛施咒,这座岛很快就会沉下去,到那时,刀上的所有人都会遇难:守望 者的跑步速度,为 17m/s, 以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁 法术,可在 1s 内移动 60m,不过每次使用闪烁法术都会消耗魔法值 10 点。守望者的魔 法值恢复的速度为 4 点/s,只有处在原地休息状态时才能恢复。 现在已知守望者的魔法初值 M,他所在的初始位置与岛的出口之间的距离 S,岛沉 没的时间 T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛,若 不能逃出,则输出守望者在剩下的时间内能走的最远距离。注意:守望者跑步、闪烁或休 息活动均以秒(s)为单位。且每次活动的持续时间为整数秒。距离的单位为米(m)。 【输入文件】 输入文件 escape.in 仅一行,包括空格隔开的三个非负整数 M,S,T。 【输出文件】 输出文件 escape.out 包含两行: 第 1 行为字符串"Yes"或"No" (区分大小写),即守望者是否能逃离荒岛。 第 2 行包 含一个整数,第一行为"Yes" (区分大小写)时表示守望着逃离荒岛的最短时间。第一行为
40

"No" (区分大小写) 时表示守望者能走的最远距离。 【输入输出样例 1】 escape.in 39 200 4 【输入输出样例 2】 escape.in 36 255 10 【限制】 30%的数据满足: 1 <= T<= 10, 1 <=S<= 100 50%的数据满足: 1 <= T <= 1000, 1 <= S <= 10000 100%的数据满足: 1 <= T <= 300000, 0 <= M<=1000 1 <=S <= 10^8 问题分析: 本题选自 noip2007 普及组试题。根据题意,已知守望者的魔法初值 M、所在的初 始位置与岛的出口之间的距离 S、岛沉没的时间 T。计算守望者能否在最短的时间内逃 离,若不能逃出,则输出守望者在剩下的时间内能走的最远距离。即:守望者要在最短 时间走最多的路程,而每秒有三种方法:休息(魔法恢复 4) ;跑步(移动 17m) ;闪烁 法术(花费 10 魔法,移动 60m) 可以得到如下信息: 。 1.休息和闪烁法术是有关联的(要不然还不如不休息) ; 2.有魔法的情况下,尽量用闪烁法术(因为闪烁法术移动最远) ; 3.在魔法不够的情况下,对休息(等待魔法恢复使用闪烁法术)还是跑步进行选 择。 为了理清信息,不妨将跑步和使用闪烁法术分开处理。 设想: 1.如果“守望者”不会跑步,记第 i 秒的能到达最大距离为 f[i],则: f[i-1]+60 f[i] = f[i-1] 2.把跑步的情况加入,则: f[i] = Max{f[i],f[i-1]+17}(注意:令 f[0] = 0) 如此,得到了解决问题的递推式。当 f[t](t 为限定的时间)<S 时,输出“No”及 f[t] 值,否则,输出“Yes”及 f[i]值刚好离岛时 i 值。 算法描述: 1.读入数据; 2.计算只使用闪烁法术时的每秒最大距离;
41

escape.out No 197 escape.out Yes 6

当 m(魔法)≥10 时,同时 m = m-10 当 m<10 时,同时 m = m+4

通过这样一个预处理,解决了闪烁法术的使用。

3.计算加入跑步选择时的每秒最大距离,如果在某时刻刚好离岛,则输出离岛时 间,结束; 4.如果不能离岛,输出最远距离,结束。 程序设计: Program escape; Type Tindex = longint; var m,s,t,i : Tindex; f : array[0..300000] of Tindex; Begin assign(input,'escape.in'); assign(output,'escape.out'); reset(input); rewrite(output); f[0]:=0; readln(m,s,t); //读入数据 For i:=1 to t do //计算只使用闪烁法术时的每秒最大距离 begin if m>9 then begin f[i]:=f[i-1]+60; dec(m,10); end else begin f[i]:=f[i-1]; inc(m,4); end; end; For i:=1 to t do //计算加入跑步选择时的每秒最大距离 begin if f[i]< f[i-1]+17 then f[i]:= f[i-1]+17; if f[i]>=s then begin //刚好离岛,输出 writeln('Yes'); writeln(i); close(input); close(output); halt;
42

end; end; writeln('No');//不能离岛,输出 writeln(f[t]); close(input); close(output); End. 本题有多种解决问题的方法, 然而, 在上述分析中很巧妙地运用了分而治之的思想, 把原来跑步、魔法、休息交错在一起的问题条件分离开,考虑在只有魔法情况下每秒最 远距离,此时,很容易用上问题的贪心条件,能用魔法尽量用上魔法,求只有魔法情况 下每秒最远距离的递推式写起来也很简单。接着,考虑跑步的情况,当前秒的跑步距离 由上一秒加 17 递推得到,每秒最远距离为跑步距离和魔法距离中的最大值。这是一道 很好的题,建议大家用不同方法解决之,然后,从中体会分解问题的方法和技巧。 练习题

6.5

1. 写出下列程序的运算结果(选自 NOIP 初赛试题) (1) program exp1; var i,j,k,n,,L0,L1,LK:Integer; a :array [0..20] of integer; begin readln(n,k); for i:=0 to n-1 do a[i]:=i+1; a[n]:=a[n-1];L0:=n-1; Lk:=n-1; for I:=1 to n-1 do begin L1:=L0-k; if (l1<0) then L1:=L1+n; If (l1=Lk) then begin A[L0]:=a[n]; Lk:=Lk-1; a[n]:=a[Lk]; l0:=lk End; Else Begin A[l0]:=a[l1];l0:=l1; End;

43

End; A[L0]:=a[n]; For I:=0 to n-1 do write(a[I]:40; Writeln; End. 输入:10 输出: (2) Pmgram exp2; Var I,j,p,n,q,s:integer; a :array[1..20]of integer; begin readln(p,n,q);j :=21; while (n>0)do begin j:=j-1;a[j]:=n mod 10;n:=n div 10; end; s:=0; for i:=j t0 20 do s:=s*p+a[i]; writeln(s);j :=21; while (s>O)do begin j:=j-1;a[j]:=s mod q;s:=s div q;end; for i:=j to 20 do write(a[i]);readln; end. 输入:7 3051 8 输出: (3) program program4; var a: array[0..5] of integer; sum,n,max,i,j,k:integer; cover:array[0..22000]of boolean; begin
44

4

read (a[5],a[4],a[3],a[2],a[1],a[0]); if ((a[5]=0) and (a[3]=0) and (a[1]=0)) then begin a[5]:=a[4];a[4]:=a[2]; a[3]:=a[0]; a[2]:=0 a[0]:=0; end: for i:=0 to 5 do if (a[i]>10) then a[i]:=10+(a[i] mod 2); sum:=0: for i:=0 to 5 do sum:=sum+a[i]*(6-i); if ((sum mod 2) <>0) then begin writeln(`Can``t be divided.`); Exit; End; sum:=sum div 2; max:=0; cover[0]:=True; for i:=1 to sum*2 do cover[i]:=False; for i:=0 to 5 do begin j:=0; while (j<a[i])do begin for k:=max downto 0 do begin if (cover[k]) then cover[k+6-i]:=True;end; max:=max+6-i: j:=j+1; end; end; if (cover[sum]) then writeln (`Can be divided.`) else writeln(`can``t be divided.`); end. 输入:4 7 9 20 56 48 输入:1000 7 101 20 55 1 输入:2000 5 l 1 0 0 输出: 输出: 输出:

2.补充完善下列程序(选自 NOIP 初赛试题) (1)问题描述:将 n 个整数分成 k 组(k≤n,要求每组不能为空),显然这 k 个部分均可 得到一个各自的和 s1,s2,??sk,定义整数 P 为: P=(S1-S2) +(S1 一 S3) +??+(S1-Sk) +(s2-s3) +??+(Sk-1-Sk)
2 2 2 2 2

问题求解:求出一种分法,使 P 为最小(若有多种方案仅记一种〉

45

程序说明: 数组:a[1],a[2],...A[N]存放原数 s[1],s[2],...,s[K]存放每个部分的和 b[1],b[2],...,b[N]穷举用临时空间 d[1],d[2],...,d[N]存放最佳方案 程序: program exp4; Var i,j,n,k : integer; a :array [1..100] of integer; b,d:array [0..100] of integer; s :array[1..30] of integer; begin readln(n,k); for I:=1 to n do read(a[I]); for I:=0 to n do b[I]:=1; cmin:=1000000; while (b[0]=1) do begin for I:=1 to k do for I:=1 to n do ② sum:=0; for I:=1 to k-1 do for j:= ③ sum:=sum+(s[I]-s[j])*(s[I]-s[j]); if ④ begin cmin:=sum; for I:=1 to n do d[I]:=b[I]; end; j:=n; while ⑤ do j:=j-1;
46



then

b[j]:=b[j]+1; for I:=j+1 to n do ⑥ end; writeln(cmin); for I:=1 to n do write(d[I]:40); writeln; end. (2) 问题描述:工厂在每天的生产中,需要一定数量的零件,同时也可以知道每天生 产一个零件的生产单价。在 N 天的生产中,当天生产的零件可以满足当天的需要,若当天 用不完,可以放到下一天去使用,但要收取每个零件的保管费,不同的天收取的费用也不 相同。 问题求解:求得一个 N 天的生产计划(即 N 天中每天应生产零件个数),使总的费用最少。 输入:N(天数 N<=29) 每天的需求量(N 个整数) 每天生产零件的单价(N 个整数) 每天保管零件的单价(N 个整数) 输出:每天的生产零件个数(N 个整数) 例如:当 N=3 时,其需要量与费用如下: 第一天 需要量 生产单价 保管单价 25 20 5 第二天 15 30 l0 第三天 30 32 0

生产计划的安排可以有许多方案,如下面的三种: 第一天 25 40 70 程序说明: b[n]:存放每天的需求量 c[n]:每天生产零件的单价 d[n]:每天保管零件的单价 e[n]:生产计划
47

第二天 15 0 0

第三天 30 30 0

总的费用 25*2O+15*30+30*32=1910 40*20+15*5+30*32=1835 70*20+45*5+30*10=1925

程序: Program exp5; Var i,j,n,yu,j0,j1,s:integer; b,c,d,e: array[0..30]of integer; begin readln(n); for i:=1 to n do readln(b[[i],c[I],d[i]]; fori:=1 to n do e[i]:=0; ①:=10000;c[n+2]:=0;b[n+1]:=0;jO:=1; while (jO<=n)do begin yu:=c[j0]; j1:=jO; s:=b[j0]; while begin ④ end; ④ end; for i:=1 to n do readln; end. ⑤ jO:=j1+1; j1:=j1+1;s:=s+b[j1]; ② do

3.思考题 (1)思考例 6.3 中,算法 2 程序中为什么只要筛 sqrt(n)内素数的倍数。 (2)比较思考例 6.3 中 3 种算法中的程序效率。 (3)对于“计数排序”算法,一般认为(最大数据-最小数据)的值小于多少是可 以承受的?

4.编程题 (1)以“基数排序”为关键词,上网搜索基数排序算法,尝试编程实现。 (2)方阵填数:在一个 N ? N 的方阵中,填入 1,2,??N ? N 个数,并要求构成 如下的格式:

48

例: N=5 13 14 15 16 12 23 24 17 11 22 25 18 10 21 20 19 9 8 7 1 2 3 4 6

N=6 16 17 18 19 20 15 30 31 32 21 14 29 36 33 22 13 28 35 34 23 12 27 26 25 24 11 10 9 8 7 1 2 3 4 5 6

5 (3) 、问题 d-规则问题( drule) 【问题描述】

对任意给定的 m(m∈N+)和 n(n∈N+),满足 m<n,构造一初始集合:P={x|m≤x≤n,x ∈N+}(m,n≤100)。现定义一种 d 规则如下:若存在 a∈P,且存在 K∈N+ ,K>1,使得 K?a ∈P,则修改 P 为:P=P-{y|y=s?a,s∈N+ } ,并称该 d 规则具有分值 a。现要求编制一个 程序,对输入的 m,n 值,构造相应的初始集合 P,对 P 每应用一次 d 规则就累加其相应 的分值,求能得到最大累加分值的 d 规则序列,输出每次使用 d 规则时的分值和集合 p 的变化过程。 【输入格式】 输入仅一行,M,N 的值。 【输出格式】 输出每次使用 d 规则时的分值和集合 p 的变化过程(即变化后的集合内所有的数,每 个数用空格隔开),注意 D 后面有个空格,冒号后面有个空格。如果没有一次可以变化就 输出 0。 【样例输入】 (1) 3 10 (2) 56 57 【样例输出】 (1) 5:346789 4:3679 3:7 (2) 0 (4)穿越沙漠(oil) 【问题描述】 一辆重型卡车欲穿过 S 公里的沙漠,卡车耗汽油为 1 升/公里,卡车总载油能力为 W 公升。 显然卡车装一次油是过不了沙漠的。 因此司机必须设法在沿途建立若干个贮油点, 使卡车能顺利穿过沙漠。 试问司机如怎样建立这些贮油点?每一贮油点应存储多少汽油,
49

才能使卡车以消耗最少汽油的代价通过沙漠? 【输入文件】 仅一行,读入整数 S,W(S<=1000,W<=500)。 【输出文件】 编程计算及打印建立的贮油点序号,各贮油点距沙漠边沿出发的距离以及存油量(输 出到小数点后第二位)。格式 如下: ? 0 ? 1 ? 2 ? … 【样例输入】 1000 500 【样例输出】 0 1 2 3 4 5 6 7 0.00 22.43 60.89 106.35 161.90 233.33 333.33 500.00 3881.36 3500.00 3000.00 2500.00 2000.00 1500.00 1000.00 500.00 0.00 × × × × …… (dist) (dist) ××(oil) ××(oil) ×× ……

注意:输出除了编号外距离和存油量均占 10 位。

50


更多相关文档:

第六章 数组

第六章 数组 课堂讨论或提问问题 1、 2、 在程序中,为什么要用数组这样一种数据类型? 请编写一个程序,通过定义一个整型数组,有 5 个数组元素。 (1)请将各...

第六章:数组

第六章:数组_调查/报告_表格/模板_实用文档。C语言各章节对应习题(含部分习题答案) 一维数组: 1、 定义一个 10 个元素的整数数组,赋值为 1-10,按如下格式...

第六章 数组

第六章 数组_计算机软件及应用_IT/计算机_专业资料。第六章 数组 如果在程序中涉及的数据较多,处理的是一批或多批数据,就要用到数组的的概念。在 Visual Basic ...

第六章 数组

第六章 数组_其它考试_资格考试/认证_教育专区。计算机二级等级C语言考试 二级C 语言 第六章 数组在程序设计中,为了处理方便,把具有相同类型的若干变量按有序的...

VB第六章数组

VB第六章数组_计算机软件及应用_IT/计算机_专业资料。. 单选题: (1.0 分) 以下定义数组的语句中,正确的是___。 A. Dim a( ,) as Integer B. Dim a...

第六章 数组

第六章第一节 1、一维数组的定义 数组一维数组 一维数组的一般形式为:类型说明符 数组名[常量表达式]; int a[6]; 定义了一个 int 型数组,其中数组名为 a,...

第六章数组 编程题答案

第六章数组 编程题答案 1. 将输入的 n 个整数按从小到大排序输出,并求出其中所有奇数的个数。 提示:使用冒泡法或选择法将 n 个数排序,然后在使用一个循环...

第六章 数组

第六章 数组_计算机软件及应用_IT/计算机_专业资料。第六章 数组 6.1 在 c 语言中, 引用数组元素时, 其数组下标的数据类型是 ()。 A)整型常量 B)整型表达...

第六章 数组

第六章 数组 VBVB隐藏>> 6.1 数组的概念 1.数组:一组具有相同类型的有序变量的集合。 2.数组名:数组的名称,表示有内在联系的一组变量而不是某个具体变量。...

第六章数组

第6章 6.1 问题导引与分析 数 组 到目前为止,我们所接触的变量类型(除文件...5 例如: (1)const a:array[1..3] of integer=(3,4,5); (2)const ...
更多相关标签:
第六章一维数组答案 | 空孕催乳剂梅雪第六章 | fgo第六章攻略 | fgo第六章 | 黄河大合唱第六章 | 女武神第六章青龙无暇 | fgo第六章剧情 | 传送门2第六章 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com