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

基础算法习题集


基础算法习题集(李波于 2007 年 7 月收集整理)

第一章 入门试题 ............................................................................................................................ 3 EX1_1、角谷猜想:................................................................................................................. 4 EX1_2、投票问题: ................................................................................................................ 4 EX1_3、位数对调:................................................................................................................. 5 EX1_5、模拟计算器:............................................................................................................. 6 EX1_6、求丑数: .................................................................................................................... 6 EX1_7、杨辉三角: ................................................................................................................ 7 EX1_8、奇数阶魔阵:............................................................................................................. 9 EX1_9、到天宫做客:........................................................................................................... 10 EX1_10、数列找数:............................................................................................................. 11 EX1_11、进制转换: ............................................................................................................ 14 EX1_12、求素数: ................................................................................................................ 15 EX1_13、矩阵相乘: ............................................................................................................ 16 EX1_14、找数字对:............................................................................................................. 17 EX1_15、蛇形矩阵: ............................................................................................................ 18 EX1_16、编码问题 ................................................................................................................ 20 EX1_17、约瑟夫问题(Joseph): ........................................................................................ 22 EX1_18、一元三次方程求解(NOIP2001):..................................................................... 24 EX1_19、谁拿了最多奖学金(NOIP05TG) :....................................................................... 26 第二章 递推与递归 ...................................................................................................................... 29 EX2_1、求算术平方根:....................................................................................................... 29 EX2_2、猴子分桃:............................................................................................................... 30 EX2_3、一元多项式求值(NOIP1995): ............................................................................. 31 EX2_4、贮油点: .................................................................................................................. 32 EX2_5、实数数列: .............................................................................................................. 34 EX2_6、小猴吃枣:............................................................................................................... 37 EX2_7、汉诺塔: .................................................................................................................. 38 EX2_8、求最大公约数:....................................................................................................... 39 第三章 回溯 .................................................................................................................................. 41 EX3_1、质数圈问题:........................................................................................................... 42 EX3_2、算 24 点: ................................................................................................................ 43 EX3_3、八皇后问题:........................................................................................................... 45 EX3_4、老鼠走迷宫:........................................................................................................... 47 EX3_5、跳马问题: .............................................................................................................. 49 EX3_6、数的划分: .............................................................................................................. 51 EX3_7、组合的输出:........................................................................................................... 52 EX3_8、售货员的难题:....................................................................................................... 54 第四章 贪心法 .............................................................................................................................. 56 Ex4_1、均分纸牌(NOIP2002tg) : .................................................................................... 57 EX4_2、最大整数: .............................................................................................................. 58 EX4_3、背包问题: .............................................................................................................. 59 EX4_4、排队接水: .............................................................................................................. 61 EX4_5、智力大冲浪:........................................................................................................... 62 EX4_6、取火柴游戏:........................................................................................................... 65

基础算法习题集(李波于 2007 年 7 月收集整理)

第五章 树 ...................................................................................................................................... 67 EX5_1、排序二叉树与堆排:............................................................................................... 68 EX5_2、构造二叉树:........................................................................................................... 70 EX5_3、构造哈夫曼树:....................................................................................................... 72 EX5_4、FBI 树: ................................................................................................................... 74 EX5_5、合并果子: .............................................................................................................. 75 第六章 图 ...................................................................................................................................... 77 EX6_1、一笔画问题:........................................................................................................... 78 EX6_2、最短路径问题:....................................................................................................... 80 EX6_3、六城市问题:........................................................................................................... 83 EX6_4、最小生成树问题:................................................................................................... 85 EX6_5、公路修建问题:....................................................................................................... 89 EX6_6、神经网络: .............................................................................................................. 91 第七章 搜索 .................................................................................................................................. 94 EX7_1、六城市问题:........................................................................................................... 95 EX7_2、五人分书: .............................................................................................................. 97 EX7_3、八数码难题 :....................................................................................................... 100 EX7_4、工作安排: ............................................................................................................ 107 EX7_5、机器作业问题:..................................................................................................... 110 EX7_6、最多因子数: ........................................................................................................... 112 EX7_7、魔术数字游戏:..................................................................................................... 115 EX7_8、字串变换:............................................................................................................. 118 第八章 动态规划 ........................................................................................................................ 121 EX8_1、最短路程问题:..................................................................................................... 122 EX8_2、旅行路线问题:..................................................................................................... 127 EX8_3、奶牛运送问题:..................................................................................................... 132 EX8_4、最长不下降序列:................................................................................................. 137 EX8_5、加分二叉树:......................................................................................................... 138 EX8_6、字串距离: ............................................................................................................ 140 EX8_7、乘积最大: ............................................................................................................ 142 EX8_8、拦截导弹: ............................................................................................................ 145 EX8_9、石子合并: ............................................................................................................ 147 EX8_10、砝码称重: .......................................................................................................... 154 第九章 其余试题 ........................................................................................................................ 156 全排列问题:....................................................................................................................... 156

基础算法习题集(李波于 2007 年 7 月收集整理)

第一章 入门试题
随着青少年信息技术奥赛的发展, 这一领域已经完全演变成了程序设计竞赛。 而谈到程 序设计,不得不想到这个经典表达式:程序=算法+数据结构。因此,要想在信息技术奥赛 中取得突破,算法是重中之重。

程序设计基本概念:
一、算法 算法是解决问题方法的精确描述, 但是并不是所有问题都有算法, 有些问题经研究可行, 则相应有算法,但这并不是说问题就有结果。上述的“可行” ,是指对算法的研究。 1.待解问题的描述 待解问题表述应精确、简练、清楚,使用形式化模型刻划问题是最恰当的。例如,使用 数学模型刻划问题是最简明、严格的,一旦问题形式化了,就可依据相应严格的模型对问题 求解。 2.算法设计 算法设计的任务是对各类具体问题设计良好的算法及研究设计算法的规律和方法。 常用 的算法有:穷举搜索法、递归法、回溯法、贪心法、分治法等。 3.算法分析 算法分析的任务是对设计出的每一个具体的算法,利用数学工具,讨论各种复杂度,以 探讨某种具体算法适用于哪类问题,或某类问题宜采用哪种算法。 算法的复杂度分时间复杂度和空间复杂度。 .时间复杂度:在运行算法时所耗费的时间为 f(n)(即 n 的函数)。 .空间复杂度:实现算法所占用的空间为 g(n)(也为 n 的函数) 。 称 O(f(n))和 O(g(n))为该算法的复杂度。 二、程序设计 1.程序 程序是对所要解决的问题的各个对象和处理规则的描述, 或者说是数据结构和算法的描 述,因此有人说,数据结构+算法=程序。 2.程序设计 程序设计就是设计、编制和调试程序的过程。 3.结构化程序设计 结构化程序设计是利用逐步求精的方法, 按一套程式化的设计准则进行程序的设计。 由 这种方法产生的程序是结构良好的。所谓“结构良好”是指: (1)易于保证和验证其正确性; (2)易于阅读、易于理解和易于维护。 按照这种方法或准则设计出来的程序称为结构化的程序。 “逐步求精”是对一个复杂问题,不是一步就编成一个可执行的程序,而是分步进行。 .第一步编出的程序最为抽象; .第二步编出的程序是把第一步所编的程序(如过程、函数等)细化,较为抽象; .?? .第 i 步编出的程序比第 i-1 步抽象级要低; .?? .直到最后,第 n 步编出的程序即为可执行的程序。 所谓“抽象程序”是指程序所描述的解决问题的处理规则,是由那些“做什么”操作组 成,而不涉及这些操作“怎样做”以及解决问题的对象具有什么结构,不涉及构造的每个局

基础算法习题集(李波于 2007 年 7 月收集整理)

部细节。 这一方法原理就是:对一个问题(或任务) ,程序人员应立足于全局,考虑如何解决这 一问题的总体关系,而不涉及每局部细节。在确保全局的正确性之后,再分别对每一局部进 行考虑,每个局部又将是一个问题或任务,因而这一方法是自顶而下的,同时也是逐步求精 的。采用逐步求精的优点是: (1)便于构造程序。由这种方法产生的程序,其结构清晰、易读、易写、易理解、易 调试、易维护; (2)适用于大任务、多人员设计,也便于软件管理。 逐步求精方法有多种具体做法,例如流程图方法、基于过程或函数的方法。

EX1_1、角谷猜想:
对于任意大于 1 的自然数 n,若 n 为奇数,则将 n 变为 3*n+1,否则将 n 变为 n 的一半。 经过若干次这样的变换,一定会使 n 变为 1。试验证该猜想并输出变换次数。 [分析]1.判断 n=1? 2.判断 n 是否为奇数,是则 n=n*3+1,否则 n=n div 2; 3.累计变换次数,返回 1 [程序] Program ex1_1; Var n,sum:integer; Begin Sum:=0;read(n); While n<>1 do begin If odd(n) then n:=3*n+1 else n:=n div 2; Inc(sum); End; Writeln(sum); End.

EX1_2、投票问题:
竞选时,要求选民在 A、B、C、D 四个候选人中选择(选民人数不限) ,如果选择了 A、 B、C、D 以外的人员,则视为费票。统计时输入“#”结束,请按候选人顺序输出其得票情 况。 [分析]本题最终目的是要统计 A、B、C、D 各自出现的次数,如果按照一般的方式使用 4 各统计变量分别判断并累加各自的得票数,则稍嫌麻烦。 如果换一个思路,定义数组 sum:array['A'..'D'] of integer,则可以直接使用数组变量下标 和题中候选人字母之间的联系, 当读入字符 CH 后, 如果 CH 不是废票, 则可以 inc(sum[ch]) 语句完成统计。 [程序] program ex1_2; var sum:array['A'..'D'] of integer; ch,ch1,ch2:char; s:integer; begin repeat

基础算法习题集(李波于 2007 年 7 月收集整理)

read(ch); if (ch>='A') and (ch<='D') then inc(sum[ch]); until ch='#'; for ch:='A' to 'D' do writeln(ch,':',sum[ch]); end.

EX1_3、位数对调:
输入一个三位自然数,把这个数的百位与个位数对调,输出对调后的数。例如:input: 234 output:432 [分析]1.先确定输入数 n 是否三位数,即 n>99 且 n<=999。 2.位数对调:n=abc→cba=x ①百位数 a=n 整除 100;②十位数 b=(n-a*100)整除 10;③个位数 c=n 除以 10 的余 数; 3.得对调后的数:x=c*100+b*10+a [程序] program ex1_3; var x,n,a,b,c:integer; begin write('input 3 bit nature data:'); readln(n); IF (n>99) and (n<1000) then begin a:=n DIV 100; {求百位数} b:=(n-a*100) DIV 10;{求十位数} c:=n mod 10; {求个位数} x:=c*100+b*10+a; {得新数 X} writeln('Number=',x:3); end ELSE writeln('Input error!'); END.

EX1_4、求三角形面积:
给出三角形的三个边长为 a,b,c,求三角形的面积。 提示:根据海伦公式来计算三角形的面积: S=

a?b?c ;Area= S( S ? a )( S ? b )( S ? c ) 2

[分析]1.输入的三角形三边长 a,b,c 要满足“任意两边长的和大于第三边长” 。 2.按海伦公式计算:s=(a+b+c)/2;x=s*(s-a)*(s-b)*(s-c) 这时若 x>=0,则求面积:area= x ,并输出 area 的值。 [程序] PROGRAM ex1_4; VAR a,b,c,s,x,area:real; BEGIN write('Input a,b,c:');readln(a,b,c); If (a>0) and (b>0) and (c>0) and (a+b>c)and(a+c>b)and(b+c>a) Then

基础算法习题集(李波于 2007 年 7 月收集整理)

Begin s:=(a+b+c)/2; x:=s*(s-a)*(s-b)*(s-c); If x>=0 Then Begin Area:=SQRT(x);writeln('Area=',area:8:5); End; End Else writeln('Input error!') END.

EX1_5、模拟计算器:
试编写一个根据用户键入的两个操作数和一个运算符, 由计算机输出运算结果的程序。 这里只考虑加(+) 、减(-) 、乘(*) 、除(/)四种运算。 例1:Input x,y:15 3 Input operator(+,-,*,/):+ 15.00+ 3.00= 18.00 例2:Input x,y:5 0 Input operator(+,-,*,/):/ divide is zero! [分析]该题关键是判断输入的两数是作何种运算(由输入的运算符 operator 决定, 如'+'、 '-'、'*'、'/'分别表示加、减、乘、除法的运算)。其中要进行除(/)运算时,要先进行合法 性检查,即除数不能为 0。 [程序] PROGRAM ex1_5; Var x,y,n:real; operator:char; Begin write('Input x,y:');readln(x,y); write('Input operator:');readln(operator); Case operator of '+':n:=x+y; {加法运算} '-':n:=x-y; {减法运算} '*':n:=x*y; {乘法运算} '/':If y=0 then {除法运算} begin writeln('Divide is zero!');halt;end Else n:=x/y; else begin writeln('Input operator error!');halt;end; End; writeln(x:6:2,operator,y:6:2,'=',n:6:2); End.

EX1_6、求丑数:
所谓丑数,就是那些因子只含有 2,3,5 的数。1,2,3,4,5,6,8,9,10,12,15 是最前面的 11 个丑数。请编写一个程序寻找并打印第 N(<=2000)个丑数。 [分析] 一种最容易想到的方法当然就是从 2 开始一个一个的判断一个数是否为丑数。 这种 方法的复杂度约为 O( k * h[n]),耗费时间太多。 根据丑数的定义可知,丑数除以 2,3,5 三个数各若干次必能得商为 1。换言之,丑数 其实就是以 1,2,3,5 几个数相乘而得,关键就是每个数乘多少次,可以得到第几个丑数。 于是就有这样得结论:如果前 m-1 个丑数已经求出来了(包含 1) ,那么第 m 个数肯

基础算法习题集(李波于 2007 年 7 月收集整理)

定是由前面某个丑数乘 S 里的素数得来的。 定义一个 mark 数组,mark [1] = 2,mark [2] = 3, mark [3] = 5;定义一个 ugly [1..n] 的队列,ugly [1] = 1;然后开一个 p[1..3]的指针数组,来表示 3 个质因数指向队列的位 置,初始都指向 1。 算法描述如下,直至队尾指针大于 N 时结束: 1、队尾指针 + 1,即丑数个数增加 1 个。 2、ugly [队尾指针] = Min {ugly [p[i]] * a[i] | 1 =< i <= 3 } 3、找到这个 Min 值对应的下标 j,p[j] + 1 最后 Q[N]便是题目的解。本题得求解方法实际上就是常用得构造法。这个算法复杂度 显然为 O( n * k ),已经相当不错了。 [程序] program ex1_6; const maxn=2000; mark:array [1..3] of integer=(2,3,5); {存放因子} var i,j,n:longint; min:extended; p:array[1..3] of longint; {表示 3 个质因数指向队列的位置} ugly:array[1..maxn] of extended; {存放丑数序列} begin write('Input n(n<',maxn,'):'); readln(n); ugly[1]:=1; for i:=1 to 3 do p[i]:=1; {队列位置初始都指向 1} for i:=2 to n do {循环求第 n 各丑数} begin min:=ugly[p[1]]*mark[1]; for j:=2 to 3 do if ugly[p[j]]*mark[j]<min then min:=ugly[p[j]]*mark[j]; {由已知丑数序列求下一个丑数。3 个质因数指向 队列的位置对应数值和各因子乘积的最小者,即为下一个丑数} ugly[i]:=min; for j:=1 to 3 do if ugly[p[j]]*mark[j]=min then p[j]:=p[j]+1;{变换队列指向} end; writeln('The ' ,n,'''th ugly number is ',ugly[n]:0:0) end.

EX1_7、杨辉三角:
输出杨辉三角的前 N 行(N<10)。 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 [分析] 杨辉三角是由我国古代数学家杨辉发明,主要用于求多项展开式系数。 方法一: 由杨辉三角可以推出, 除每行两端的元素外, 其余元素均是其两肩元素之和。 因此,

基础算法习题集(李波于 2007 年 7 月收集整理)

传统得做法是用二维数组来存放,以元素相加方式求解,并在最后输出。 [程序] program ex1_7_1; var yh:array[1..100,1..100]of integer; n,i,j:integer; begin readln(n); yh[1,1]:=1; for i:=2 to n do begin yh[i,1]:=1;yh[i,i]:=1; {边缘元素赋值} for j:=2 to i-1 do yh[i,j]:=yh[i-1,j-1]+yh[i-1,j]; {计算中间元素得值,即两肩元素之和} end; writeln('yang hui:'); for i:=1 to n do begin write('':40-3*i); {控制输出时得空格} for j:=1 to i do write(yh[i,j]:6); writeln; end; end. 方法二: 杨辉三角中除最左边一列数字 1 外, 其余 i 行 j 列的元素可以由公式 i! /(j!*(i-j)!) 计算而得。因此,杨辉三角可以一边计算一边输出。和第一种算法比较,该方法可以大大节 约存储空间,但由于要计算阶乘,其数据规模会比较大。并且随着数据量的增大,耗时也会 增加。 [程序] program ex1_7_2; var n,i,j:integer; function factor(m:integer):longint;{计算阶乘函数} var i:integer; s:longint; begin s:=1; for i:=1 to m do s:=s*i; factor:=s; end; function num(x,y:integer):real; {求 x 行 y 列元素的值} begin num:=factor(x)/(factor(y)*factor(x-y)); end; begin readln(n); writeln('yang hui:');

基础算法习题集(李波于 2007 年 7 月收集整理)

writeln(' ':40,1); for i:=1 to n do {计算并同时输出} begin write('':40-3*i,1); {输出空格和每行第一个元素 1} for j:=1 to i do write(num(i,j):6:0); writeln; end; end.

EX1_8、奇数阶魔阵:
魔阵是用自然数 1, 2, 3?, n2 填 n 阶方阵的各个元素位置, 使方阵的每行的元素之和、 每列元素之和及主对角线元素之和均相等。 奇数阶魔阵的一个算法是将自然数数列从方阵的 中间一行最后一个位置排起,每次总是向右下角排(即 Aij 的下一个是 Ai+1,j+1)。但若 遇以下四种情形,则应修正排数法。 (1) 列排完(即 j=n+1 时),则转排第一列; (2) 行排完(即 i=n+1 时),则转排第一行; (3) 对 A[n,n]的下一个总是 A[n,n-1]; (4) 若 Aij 已排进一个自然数,则排 Ai-1,j-2。 例如 3 阶方阵,则按上述算法可排成: 4 3 8 9 5 1 2 7 6 [分析] 此题的叙述中实际已经给出了算法描述。对于四种特殊情况进一步加以分析可知, 我们应先处理第三种普通情况,另外再对其余三种特殊情况进行判断。算法描述如下: if (i=n)and(j=n) then j:=j-1; /*下一个位置为(n,n-1)*/; else i:=i mod n +1; j:=j mod n +1; endif; [程序] program ex1_8; var a : array[1..99,1..99]of integer; i,j,k,n : integer; begin fillchar(a,sizeof(a),0); write('n=');readln(n); i:=n div 2+1;j:=n; {确定 1 填的位置} a[i,j]:=1; for k:=2 to n*n do begin if (i=n)and(j=n) then {对 A[n,n]的下一个总是 A[n,n-1]} j:=j-1 else begin i:=i mod n +1; {行排完(即 i=n+1 时),则转排第一行} j:=j mod n +1; {列排完(即 j=n+1 时),则转排第一列}

基础算法习题集(李波于 2007 年 7 月收集整理)

end; if a[i,j]<>0 then {若 Aij 已排进一个自然数,则排 Ai-1,j-2} begin i:=i-1; j:=j-2; end; a[i,j]:=k; end; for i:=1 to n do {输出} begin for j:=1 to n do write(a[i,j]:5); writeln; end; end.

EX1_9、到天宫做客:
有一天,我做了个梦,梦见我很荣幸的接到了猪八戒的邀请,到天宫陪他吃酒。我犹豫 了。天上一日,人间一年啊!当然, 我是个闲人,一年之中也没有多少时日是必须在人间的, 因此,我希望选一个最长的空闲时间段,使我在天上待的时间尽量长。记住,今年是 4000 年。天上一天也是 24 小时,每小时 60 分,每分 60 秒。 输入文件(heaven.in) 输入文件的第一行是一个非负整数 N,表示 4000 年中必须呆在人间的天数,以下共 N 行,每行两个用空格隔开的正整数,即日期(月,日),输入文件保证无错误,日期无重复。 输出文件(heaven.out) 输出文件仅有一行包含一个非负整数,即在天上的时间(四舍五入精确到秒)。 样例输入: 2 3 8 12 2 样例输出: 63266 [分析]为方便计算天数, 定义数组 day[1..11]存放前 11 个月的天数 (12 月可以直接加实际 天数,同时必须注意今年是 4000 年,即润年这一隐含条件) ; 另外定义数组 s[1..367]用于存放一年中的某天是否呆在人间,s[i]=true 表示呆在人 间,s[367]这一边界值必为 true。 最后找出 s 数组中两个 true 值之间的最大间隔,转换为秒即为所求。 [程序] program ex1_9; const day:array[1..11] of longint =(31,29,31,30,31,30,31,31,30,31,30); var i,j,n,m,d,t,max:longint; s:array[1..367] of boolean; begin assign(input,'heaven.in'); reset(input);

基础算法习题集(李波于 2007 年 7 月收集整理)

assign(output,'heaven.out'); rewrite(output); read(n); fillchar(s,sizeof(s),false); s[367]:=true; {最后边界为真} for i:=1 to n do {读入数据,同时计算那些天是必须呆在人间的} begin read(m,d); t:=0; for j:=1 to m-1 do t:=t+day[j]; t:=t+d; s[t]:=true; end; t:=0; max:=0; for i:=1 to 367 do {找可以呆在天上的最长时间} if s[i] then begin if i-t-1>max then max:=i-t-1; t:=i end; writeln((max*24*60*60+183) div 366); {转换为秒并输出} close(input); close(output); end.

EX1_10、数列找数:
数组 A(N)中存放了N个互不相等的数,键盘输入正整数M(M≤N) ,要求打印数组中 第M大的数的下标变量以及其的值。 例如:数组 A(10)的数据为:
A(1) 16 A(2) 57 A(3) 20 A(4) 19 A(5) 38 A(6) 41 A(7) 6 A(8) 13 A(9) 25 A(10) 32

运行结果:INPUT AN NUMBER:3 A(5)=38 (即第3大的数是 A(5)=38) [分析]该题要从 N 个互不相等的数中找第 M 大的值。有以下两种解法: 解法一:初始时:A 数组存放 N 个互不相等的数;B 数组用于存放数组 A 的下标。见下表一。
下标值 i 数组 A 数组 B 1 16 1 2 57 2 3 20 3 4 19 4 5 38 5 6 41 6 7 6 7 8 13 8 9 25 9 10 32 10

降序处理(冒泡排序法) : 数组 A 的元素由大到小进行排序,同时数组 B 的元素排列也随之变化。
下标值 I 数组 A 数组 B(原 数组 A 的 下标) 2 6 5 10 9 3 4 1 8 7 1 57 2 41 3 38 4 32 5 25 6 20 7 19 8 16 9 13 10 6

基础算法习题集(李波于 2007 年 7 月收集整理)

例题中 M=3,由表二知 A[3]=38,B[3]=B[M]=5(原数组 A 的下标值)即为所求。 [程序] Program ex1_10_1;{冒泡排序法} var i,j,n,m,x:integer; A,B:ARRAY[1..100] of integer; Procedure Init; {读数初始化过程} Var i,j:integer; fd:boolean; Begin write('Input N:');readln(N); {读入 N} if N<1 then begin writeln('Input error!');halt;end; write('Input ',N:3,' Data:'); For i:=1 to n Do begin read(A[i]);B[i]:=i;end;{读入 A[i],且 B[i]初值置为 i} Readln; i:=1; fd:=false; {数组中的数有相同的标志} while NOT fd and (i<=N-1) do Begin j:=i+1; While NOT fd and (j<=N) do begin fd:=A[i]=A[j]; {若 A[i]=A[j],则 fd=true;否则 fd=false} j:=j+1; end; i:=i+1; End; If fd then {fd 为 True,则表示数组中至少有两个相等的数} begin writeln('More equal number!');halt;end; write('Input M:');readln(M); If M>N then {表明所找的数 M 已超过输入数的总数 N} begin writeln('Input error!');halt;end; End; {Init} begin {MAIN} Init;{ 读数过程 } for i:=1 to N-1 do {冒泡排序} for j:=i+1 to N do if A[i]<A[j] then begin x:=A[i];A[i]:=A[j];A[j]:=x; {交换 A[i]与 A[j]的值} x:=B[i];B[i]:=B[j];B[j]:=x; {交换 B[i]与 B[j]的值} end; writeln('A(',B[M],')=',A[M]); {输出第 M 大的数、原下标值} End. 解法二(搜索法) :用 B[i]表示在 A[1]、A[2]、A[3]、……、A[N]中比 A[i]大(或相等) 的数的个数(i=1,2,3,??,N) 。搜索的结果见下表三:
下标值 i A 数组 B 数组 1 16 8 2 57 1 3 20 6 4 19 7 5 38 3 6 41 2 7 6 10 8 13 9 9 25 5 10 32 4

例题中 M=3,由表三知 B[5]=3=M,A[5]=38 即为所求。 [程序] program ex1_10_2; Var i,j,k,m,n:integer; A,B:ARRAY[1..100] of integer;

基础算法习题集(李波于 2007 年 7 月收集整理)

Procedure Init; {具体程序见解法一} Begin {MAIN} Init; {读数过程} for i:=1 to n do begin B[i]:=1; {B[i]初始值为 1,即假定所有 A[i]都可能为最大数} for j:=1 to n do if (i<>j) and (A[i]<A[j]) then B[i]:=B[i]+1; if B[i]=M then k:=i; end; writeln('A(',k,')=',A[k]); End. 在上述表三中,我们可以发现:例中 M=3,在搜索过程中当下标 i=5 时,B[5]=M=3,此 时已找到所求,即 A[5]=38。这样 i>5 时就不用再搜索下去。因此,可对解法二的算法优化 如下: 1.读数至 A 数组 2.i=1;fd=false; {fd:判断是否已找到所求数的标志} 3.当 (fd=false)and(I<=n) 时,做 (1)B[i]=1 {表示数列中比 A[i]小的数的总个数+1,初始值为 1} (2)j=1 (3)当 j<=n 时,做 ①如果(i<>j)and(A[i]<A[j]),则 B[i]的值加 1。 ②j=j+1 (4)如果 B[i]=M,则输出所求:A[i],且 fd=true。 (5)i=i+1 4.程序结束。 [程序] Program ex1_10_3; Begin {MAIN} Init;{读数过程} i:=1;fd:=false;{找到所求解的标志值} while not fd and (i<=N) do begin B[i]:=1; {B[i]初始值为 1,即假定所有的 A[i]都可能为最大的数} j:=1; while j<=n do begin if (i<>j)and(A[i]<A[j]) then B[i]:=B[i]+1; j:=j+1; end; {while j} if B[i]=M then {找到所求便输出,并退出比较} begin writeln('A(',i,')=',A[i]);fd:=true; end; i:=i+1; end;{while i} End.

基础算法习题集(李波于 2007 年 7 月收集整理)

EX1_11、进制转换:
编程输入十进制N(N:-32767~32767) ,请输出它对应的二进制、?八进制、十六进 制数。例如: INPUT N(-32767~32767):222 222 TURN INTO 2:11011110 222 TURN INTO 8:336 222 TURN INTO 16:DE [分析]十进制数转化为某进制数的转换方法,如下图示:
除 x 逆序取余法

十进制数 x 进制数(x=2,8,16 等) 例中 n=222(十进制数) ,转换成 x 进制数的过程如下图示:
(1)十进制数→二进制数 x=2 2 2 2 2 2 2 2 222 被除数(最大商) 111 0 低位 50 1 逆 25 0 余 序 12 0 数 取 6 0 余 3 1 数 1 1 高位 0 (最大商为 0 时停止) (2)十进制数→八进制数 x=8 222 8 8 27 3 0 6 3 3 (3)十进制数→十六进制数 x=16 222 16 13 0 E D ? (14)10 ? (13)10

将每次所得的余数由下至上排列(逆序取余数),即有: (222)10 转换成二进制数得到:1100010 (222)10 转换成八进制数得到:336 (222)10 转换成十六进制数得到:13、14 这时得到的逆序余数串(在数组 B[1]、B[2]、??、B[k]中)的每位数均为十进制数。 程序中利用字符串 A 来计算 x 进制数的位数(即 COPY(A,B[i]+1,1) ) ,见下表:
数组 B 字串 A 下标 i 0 0 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 A 11 11 B 12 12 C 13 13 D 14 14 E 15 15 F 16

由上表得: (222)10=(1100010)2=(336)8=(DE)16 [程序] Program ex1_11; var N,k:integer; B:array[1..1000] of integer; Procedure chg10(N,x:integer); {将十进制数 N 转换成 x 进制数} Begin k:=0; {转换后的 x 进制数位的长度} while N<>0 do {N 不为 0 时} begin B[k]:=N mod x; {除以 x 取余数} N:=N Div x; {取最大商 N} k:=k+1; {x 进制数位加 1} end; end;{chg10} Procedure Sput(N,x:integer);{进制数输出} VAR i:integer; A:string; Begin A:='0123456789ABCDEF'; {表示 x 进制数的位数串} write(N:6,' Turn into ',x:2,':');

基础算法习题集(李波于 2007 年 7 月收集整理)

for i:=k-1 downto 0 do write(copy(A,B[i]+1,1));{逆序输出 x 进制数} writeln; end; {Sput} begin {MAIN} write('Input N(-32767 to 32767):');readln(N); if (N<=-32767)or(N>32767) then begin writeln('Input error!');halt;end; chg10(N,2);Sput(N,2); {十进制数转换成 2 进制数,并输出} chg10(N,8);Sput(N,8); {十进制数转换成 8 进制数,并输出} chg10(N,16);Sput(N,16); {十进制数转换成 16 进制数,并输出} end.

EX1_12、求素数:
求 2 至 N(2≤N≤500)之间的素数。例如: 输入:N=100 输出: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 71 73 79 83 89 97 total=24 {表示 2 至 100 之间的素数有 24 个} [解法一]素数是指除 1 及本身以外不能被其他数整除的自然数。下面介绍用穷举法求素数。 1 2 是素数,t=1; ○ 2 i=3~n,则: ○ (1)如果 i 是素数,则其必须是奇数且不能被 2~√i 中的任一个数整除。 (2)如果 i 是素数,则输出该素数且计数器 t=t+1; 3 输出 2~N 之间素数的总数:total=t; ○ 4 程序结束 ○ [程序] program ex1_12_1; uses crt; var i,k,n,w,t:integer; yes:boolean; begin t:=0;clrscr;write(‘N=’);readln(n); if (n<2)and(n>500) then begin writeln(‘input error!’);halt;end; write(2:5);t:=1; for i:=3 to n do if odd(i) then begin yes:=true; w:=trunc(sqrt(I));k:=2; while (k<=w)and yes do begin if i mod k=0 then yes:=false; k:=k+1;end; if yes then begin write(i:5);t:=t+1; end; end; writeln(‘total=’,t); end. end. [解法二]筛法求素数:

基础算法习题集(李波于 2007 年 7 月收集整理)

1.建立一个包括 2,3,?,N 的数据“集合”R; 2.顺序取 R 中的数(从素数 2 开始) ,同时将其及能整除它的数从 R 中划去。 “筛法求 素数”的过程如下图示: 素 数 数据集合 R R[1] 2 { 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,??} 3 { 3, 5, 7, 9, 11, ??} 5 { 5, 7, 11, ??} ?? ??? 这样便可得到所求的素数:2,3,5,??。 [程序] program ex1_12_2; var i,j,k,n,w,t:integer; R,P:array [1..500] of integer; Begin write('N=');readln(n); if (n<2) or (n>500) thenbegin writeln('Input N error!');halt end; for i:=2 to n do R[i-1]:=i; writeln('Result:');t:=0;k:=n-1; while k>0 do begin P:=R; {数组 P 保存在 P 中} write(R[1]:5); {输出素数} t:=t+1;w:=R[1];j:=0; for i:=1 to k do if P[i] mod w<>0 then {划去 w 及 W 的倍数} begin j:=j+1; R[j]:=P[i];end; {重新构造集合 R} k:=j; {新建后 R 的元素个数} end; writeln;writeln('Total=',t); end.

EX1_13、矩阵相乘:
已知 N×M1 矩阵 A 和 M1×M 矩阵 B(1≤M、M1、N≤10) ,求矩阵 C(=A×B) 。例如: 输入:N,M1,M=4 3 4
A= 1 3 4 5 B= 1 2 –1 输出:C= 2 6 8 5 2 4 5 –1 6 3 5 27 55 69 17 3 5 6 –2 4 4 7 33 63 78 2 2 1 –3 –5 –5 –5 15 例如: C11=A11×B11+A12×B21+A13×B31 =1×1+2×2+3×(– 1) =2 C42= A41×B12+A42×B22+A43×B32 =5×6+(–1)×3+(–2)×5 =17 提示:所谓矩阵相乘(如 A×B=C) ,是指 Cij= ∑(Aik×Bkj)(i=1~N,j=1~M1,k=1~M)

[分析]该题主要考查矩阵的表示及其运算。矩阵A(N×M1)与矩阵B(M1×M)相乘得矩阵 C(N×M) ,其解法如下: For i:=1 to N do For j:=1 to M do

基础算法习题集(李波于 2007 年 7 月收集整理)

(1)cij=0; (2)k=1~M1,重复做 Cij=Cij+Aik*Bkj [程序] program ex1_13; var i,j,k,N,M1,M:integer; A,B,C:array [1..10,1..10] of integer; Begin write('N,M1,M=');readln(N,M1,M); if (N>=1)and(N<=10)and(M1>=1)and(M1<=10)and(M>=1)and(M<=10) then begin {输入 N×M1 矩阵 A}write('A='); for i:=1 to N do for j:=1 to M1 do read(A[i,j]);readln; {输入 M1×M 矩阵 B} write('B='); for i:=1 to M1 do for j:=1 to M do read(B[i,j]);readln; write('C='); for i:=1 to N do begin for j:=1 to M do{计算 Cij= ∑(Aik×Bkj)} begin C[i,j]:=0; for k:=1 to M1 do C[i,j]:=C[i,j]+A[i,k]*B[k,j]; write(C[i,j]:5); {输出矩阵 Cij} end; writeln;write(' ':2); end; writeln; end else writeln('Input N,M1,M error!'); end.

EX1_14、找数字对:
输入 N(2≤N≤100)个数字(在 0 与 9 之间) ,然后统计出这组数中相邻两数字组成的 链环数字对出现的次数。例如: 输入:N=20 {表示要输入数的数目}
0 1 5 9 8 7 2 2 2 3 2 7 8 7 8 7 9 6 5 9 输出: (7,8)=2 (8,7)=3 {指(7,8) 、 (8,7)数字对出现次数分别为 2 次、3 次) (7,2)=1 (2,7)=1 (2,2)=2 (2,3)=1 (3,2)=1

[分析]该题主要是数组的存储表示及运用。数组 A 存放所输入的 N 个数,用数组 B 表示 A[i] 与 A[i+1]相邻数字对出现的次数使用语句 B[A[i],A[i+1]]:=B[A[i],A[i+1]]+1 即可统计。计算 过程见下表:
数组 A 次数 i 求链环 数字的 过程 0 1 1 2 5 3 9 4 8 5 7 6 2 7 2 8 2 9 3 10 2 11 7 12 8 13 7 8 14 15 7 9 16 17 6 18 5 19 9

I= 1: B[0,1]=1 I= 5: B[8,7]=1 I=9: B[3,2]=1 I=13:B[8,7]=2 I=17:B[9,6]=1

I=2:B[1,5]=1 I=6:B[7,2]=1 I=10:B[2,3]=1 I=14:B[7,8]=2 I=18:B[6,5]=1

I=3: B[5,9]=1 I=7: B[2,2]=1 I=11:B[2,7]=1 I=15:B[8,7]=3 I=19:B[5,9]=1

I=4: B[9,8]=1 I=8: B[2,2]=2 I=12:B[7,8]=1 I=16:B[7,9]=1

基础算法习题集(李波于 2007 年 7 月收集整理)

[程序] Program ex1_14; var i,N:integer; fd:boolean; A:array[1..100] of integer; B:array[0..9,0..9] of integer; Begin fillchar(B,sizeof(B),0);{数组 B 初值置为 0} write('N=');readln(N); if (N>1)and(N<=100) then begin write('Enter ',N,' numbers:'); for i:=1 to N do begin read(A[i]); {输入 A[i]} if (A[i]<0)or(A[i]>9) then {A[i]的值在 0 与 9 之间} begin writeln('Input error!');halt;end; end; for i:=1 to N-1 do B[A[i],A[i+1]]:=B[A[i],A[i+1]]+1;{相邻数字对 BA[i],A[i+1]值加 1} fd:=true;writeln('Result:'); for i:=1 to N-1 do if (B[A[i],A[i+1]]>0)and(B[A[i+1],A[i]]>0) then begin write('(',A[i],',',A[i+1],')=',B[A[i],A[i+1]],' '); if A[i+1]=A[i] then writeln {相邻数字相同,如(2,2)} else writeln('(',A[i+1],',',A[i],')=',B[A[i+1],A[i]]); B[A[i+1],A[i]]:=0; fd:=false; end; if fd then writeln('Not found!'); end else writeln('Input N error!'); end.

EX1_15、蛇形矩阵:
生成一个按蛇形方式排列自然数 1,2,3,4,5,??,N 的 (1<N≤10)阶方阵。例如:
输入:N=4 输出:1 2 6 7 3 5 8 4 9 12 10 11 15 16 N=7 1 2 6 7 15 16 28 3 5 8 14 17 27 29 4 9 13 18 26 30 39 10 12 19 25 31 38 40 11 20 24 32 37 41 46 21 23 33 36 42 45 47 22 34 35 43 44 48 49
2

13 14

[分析]本题考查重点是矩阵的表示及上下标运算,旨在培养观察和分析思维能力。
例如,当 N=7 时,把 1,2,3,??,49 逐一填入数组 A 中,搜索填数的方向如右图 示。 从图中, 我们可以看出: 对每个数字 m (1, 2, ??, ~ N*N)来说,可能按以下四种搜索方向之一填数:
d=2(右上)

基础算法习题集(李波于 2007 年 7 月收集整理) m d=4 (左下) d=1(向下) d=3(向右)

按照图 10-1 的搜索方向填数时,先要把当前数字 m 填入数组 A[i,j]中,接下来就是要 确定下一次的填数的坐标及其搜索方向(即 d=?) 。现分析如下: 第一种情形(d=1,如 m=2,7,15;35,44) :
(i,j) d=1 d=2(当 j=1) (i+1,j) d=4(当 j=N)

第二种情形(d=2,如 m=2,10,21;或 34,43,48;或 7,8,9,16,17,18,19 等) :
d=2(当 i<>1 且 j<>N) (i-1,j) d=2 (i,j) d=3(当 i=1)

d=1(当 j=N)

第三种情形(d=3,如 m=29,40,47;或 4,11,22) :
d=3 (i,j) d=2(当 i=N) (i,j+1) d=4(当 j=N)

第四种情形(d=4,如 m=28,39,46;或 6,15;或 5,12,13,14 等) :
(i,j) d=4 (i+1,j) d=3(当 i=1)

d=4(当 i=N 且 j<>1)

[程序] Program ex1_15; const max=10; var d,i,j,m,N:integer; A:array [1..10,1..10] of integer; begin write('N=');readln(N); if (N>=1) and (N<=max) then begin i:=1;j:=1;m:=1;d:=1; repeat A[i,j]:=m; {填数} begin write('N=');readln(N); if (N>=1) and (N<=max) then begin i:=1;j:=1;m:=1;d:=1; repeat A[i,j]:=m; {填数}

基础算法习题集(李波于 2007 年 7 月收集整理)

case d of 1: {第一种情形}begin i:=i+1; if j=1 then d:=2 else d:=4; end; 2: {第二种情形}begin i:=i-1;j:=j+1; if j=N then d:=1 else if i=1 then d:=3;end; 3: {第三种情形}begin j:=j+1; if i=N then d:=2 else d:=4;end; 4: {第三种情形}begin i:=i+1;j:=j-1; if i=N then d:=3 else if j=1 then d:=1;end; end; m:=m+1; until m>N*N; writeln('OUTPUT:'); for i:=1 to N do begin for j:=1 to N do write(A[i,j]:4); { 输出填数 } writeln;end; end else writeln('Input N error!'); end.

EX1_16、编码问题
(95 年全国分区联赛题):设有一个数组 A:array [0..N-1] of integer; 存放的元 素为 0~N-1(1<N<=10)之间的整数,且 A[i]≠A[j](i≠j) 。例如当 N=6 时,有:A=(4, 3,0,5,1,2) 。此时,数组 A 的编码定义如下: A[0]编码为 0; A[i]编码为:在 A[0],A[1],?,A[i-1]中比 A[i]的值小的个数 (i=1,2,?,N-1) ∴上面数组 A 的编码为:B=(0,0,0,3,1,2) 要求编程解决以下问题: (1)给出数组 A 后,求出其编码; (2)给出数组 A 的编码后,求出 A 中的原数据 程序样例: 例一: 输入:Stat=1 {表示要解决的第(1)问题}
N=8 {输入8个数} A=1 0 3 2 5 6 7 4

输出:B=0 0 2 2 4 5 6 4 例二: 输入:Stat=2 {表示要解决的第(2)问题}
N=7 B=0 1 0 0 4 5 6

输出:A=2 3 1 0 4 5 6 [分析]第 1 个问题的解法:用穷举搜索法。 B[0]为 0 B[i]表示在 A[1],A[2],??,A[i-1]中比 A[i](i=1,2,??,N)小的个数。 第 2 个问题的解法:先构建数组 P,初始值为 0,1,2,3,??,N-1。然后从 B[N-1], B[N-2],??,B[1],B[0]逆向从数组 P 中取数求数组 A。以题中例二为例,求解过程如下 图:

基础算法习题集(李波于 2007 年 7 月收集整理) 下标值 i p0 p1 p2 p3 p4 p5 p6 数组 A

B0 B1 B2 0 1 0

B3 B4 0 4

B5 B6 5 6 ↑

6

0

1

2 3

4 5

6 A[6]=p[B6]=p6=6,划去 p6

5

0 1 0

0 4

5 6 ↑

0

1

2 3

4

5 A[5]=p[B5]=p5=5,划去 p5

4

0 1 0

0 4 ↑

5 6

0

1

2 3

4 A[4]=p[B4]=p4=4,划去 p4

3

0 1 0

0 4 ↑

5 6

0

1

2 3 A[3]=p[B3]=p0=0,划去 p0

2

0 1 0 ↑

0 4

5 6

1

2

3 A[2]=p[B2]=p0=1,划去 p0

1

0 1 0 ↑

0 4

5 6

2

3 A[1]=p[B1]=p1=3,划去 p2

0

0 1 0 ↑

0 4

5 6

2 A[0]=p[B0]=p0=2

从上述求解过程中,我们得到:A=(2,3,1,0,4,5,6) 。 [程序] program ex1_16; var i,j,k,m,n,stat:integer; A,B,P:array [0..10] of integer; begin write('Stat(1,or 2)=');readln(stat); case stat of 1:begin write('N='); readln(n); write('A='); for i:=0 to n-1 do read(A[i]); readln; {读入数组 A} for i:=0 to n-2 do for j:=i+1 to n-1 do if (A[i]=A[j])or(A[i]>n-1) then {数组 A 中有否相等} begin writeln('Input error!');halt; end; for i:=0 to n-1 do B[i]:=0; {编码数组 B 初始值为 0} for i:=1 to n-1 do for j:=0 to i-1 do if A[i]>A[j] then B[i]:=B[i]+1; {求数组编码} for i:=0 to n-1 do write(B[i]:5);writeln; end; 2:begin write('N='); readln(n); write('B='); for i:=0 to n-1 do read(B[i]); readln; {读编码数组 B} for i:=0 to n-1 do P[i]:=i; {建立取数数列 P} for i:=n-1 downto 0 do {由编码数组 B 逆向求原数组 A} begin A[i]:=P[B[i]]; {A[i]为数组 P 中第 B[i]号元素} for j:=B[i] to i-1 do P[j]:=P[j+1];{从 P 数组中删去 P[B[i]]} end; write('A=');

基础算法习题集(李波于 2007 年 7 月收集整理)

for i:=0 to n-1 do write(A[i]:5);writeln; {输出数组 A} end; end; end.

EX1_17、约瑟夫问题(Joseph):
将编号为 1,2,...,N 的 N 个人按顺时针方向围坐一圈,每人持有一个密码(10000 以内 的正整数)。一开始任选一个正整数作为报数上限值 M,从第一个开始按顺时针方向自 1 开 始报数,报到 M 时停止报数。报 M 的人出列,将他的密码作为新的 M 值,从他在顺时针方向 上的下一个人开始重新从 1 报数,如此下去,直至所有人全部出列为止。试设计一个程序求 出出列顺序。 Input 每组数据的第一行是两个整数 N,M(0<N,M<100), 第二行是 N 个正整数, 分别表示 1 到 N 个人持有的密码。 两组数据之间空开一行。 Output 对每组数据,按离开的顺序输出他们的编号。数字之间用一个空格分开。每组数据独占 一行输出。 [分析]本题实际是约瑟夫问题的一种改版,原问题叙述为:n 个人站成一圈,从某个人开始 数数,每次数到 m 的人就出圈,然后从下一个人重新开始数,直到最后只剩一个人,问最 后剩下的是那个位置上的人。 这是一个数学游戏。N 个人围成一圈,依次报数,可以用一个循环链表模拟这一过程。 将链表的表尾指向表头,即形成循环链表。从某个人开始报数,报到 M 的人出列,也就是 在循环链表中删除相应的结点,然后依次删除完所有的结点,此时链表为空,头指针与尾指 针相等。在具体操作中,要注意删除头结点和尾结点时指针的处理,谨防出错。 和约瑟夫原题相比,本题只是多了一个秘密设置。在处理时,只需要在某人出圈后改变 m 的值即可。 除使用链表外,使用数组也是一样的处理方式,只不过需要判断数组是否到末尾。下面 分别给出使用数组和链表解本题的程序。 [程序] program ex1_17_1; {用数组方式存储} var m,n,s,i,j:integer; a:array[1..100] of integer; begin assign(input,'yuesefu.in'); reset(input); assign(output,'yuesefu.out'); rewrite(output); readln(n,m); for i:=1 to n do read(a[i]); {读入密码列表} j:=0; for i:= 1 to n do begin s:=0; while s<m do begin

基础算法习题集(李波于 2007 年 7 月收集整理)

if j<n then inc(j) else j:=1; {到达数组末尾,转到开始位置} if a[j]<>0 then s:=s+1; end; write(j);write(' '); {当 s=m 时,第 j 个人出圈} m:=a[j]; a[j]:=0; {改变密码,同时标记第 j 人为 0,表示已经出圈} end; close(input); close(output); end. program ex1_17_2; {用链表方式存储} type link=^jd ; {定义链表} jd=record data:integer; next:link; end; var head,p,q:link; m,n:integer; procedure build; {建立链表,存放密码列表,直接以密码列表形成链环} var i:integer; begin new(head); read(head^.data); q:=head; for i:=2 to n do begin new(p); read(p^.data); q^.next:=p; q:=p; end; p^.next:=head; {链表头尾相连,形成链环} end; procedure work; {从链环中去除出圈人员} var i:integer; pre:link; begin while q^.next<>q do {直到链环中只余一个元素为止} begin for i:=1 to m do {数到 m 的人出圈} begin pre:=q; q:=q^.next; end; pre^.next:=q^.next;

基础算法习题集(李波于 2007 年 7 月收集整理)

write(q^.next); m:=q^.data; {改变 m 的值为当前出圈人密码值} dispose(q); {释放 q 结点,即该人出圈} q:=pre; end; end; begin readln(m,n); build; work; writeln(q^.data); end.

EX1_18、一元三次方程求解(NOIP2001):
有形如:ax +bx +cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a,b, c,d 均为实数),并约定该方程存在三个不同实根(根的范围在-100 至 100 之间),且根 与根之差的绝对值>=1。 要求由小到大依次在同一行输出这三个实根(根与根之间留有空格), 并精确到小数点后 2 位。 提示:记方程 f(x)=0,若存在 2 个数 x1 和 x2,且 x1<x2,f(x1)*f(x2)<0,则在(x1, x2)之间一定有一个根。 样例 输入:1 -5 -4 20 输出:-2.00 2.00 5.00 [分析] 如果是一般的求三次方程根的问题,那我们可以直接使用求根公式,但这是非常复 杂的。介于本题只要求精确到小数点后两位,因此可以通过循环逐次逼近,从而找出方程的 三个根。 方法一: 由题目给出的方程在区间内存在根的条件可知, 我们可以用一个变量 i 从-100.000 到 100.000 以步长 0.001 做循环。若 f (i) ? f (i ? 0.001) ? 0 ,则可知在区间 (i, i ? 0.001) 内存在方程的解。这样无论这个区间内的解是什么,在取两位小数的精度后都与 i 取两位小 数的结果是一样的。故我们就可以把取两位小数精度的 i 作为问题的解。另外还有可能方程 的根在区间端点 i 的情况,我们可以通过判断 f (i ) 是否为 0 来获得。 但这种方法由于用到了题目所要求的数值精度小的特殊性,故无法扩展。 [程序] Program ex1_18_1; Var t:integer; a,b,c,d,x1,x2:real; Function f(xf:real):real; Begin f:=a*xf*xf*xf+b*xf*xf+c*xf+d; End; Begin readln(a,b,c,d);
3 2

基础算法习题集(李波于 2007 年 7 月收集整理)

x1:=-100.000;t:=0; repeat x2:=x1+0.001; If f(x1)*f(x2)<0 then begin write((x1+x2)/2:0:2,' '); t:=t+1; end; x1:=x1+0.001; until (x1=100.00)or(t=3); End. 方法二: 二分法。 该方法的应用在于如果确定了方程 f ( x) ? 0 在区间 ( a, b) 内如果存在且只 存在一个根, 那么我们可以用逐次缩小根可能存在范围的方法确定出根的某精度的数值。 该 方法主要利用的就是题目所给的若在区间 ( a, b) 内存在一个方程的根,则 f (a) ? f (b) ? 0 这 个事实,并重复执行如下的过程:
1 取当前可能存在解的区间 ( a , b ) ; ○ 2 若 a ? 0.001 ? b 或 f ○ 3 若 f (a) ? f ○

b ,则可确定根为 ? a? 2 ??0

a?b 并退出过程; 2

b b ,则由题目给出的定理可知根在区间 ? a, a ? 中,故对区间 ? a? 2 ??0 2 ?

b 重复该过程; ? a, a? 2 ?
4 若 f (a) ? f ○

b b b ,则必然有 f ? a? ,也就是说根在 ? a? 中,应该 ? a? 2 ??0 2 ? ? f (b) ? 0 2 , b?

对此区间重复该过程。 最后,就可以得到精确到 0.001 的根。 再考虑什么样的区间内会有根。由于题目给出了所有的根都在-100 到 100 之间,且根

[?99, ?98) 、 [99,100) 、 与根之间差不小于 1 的限制条件, 故我们可知, 在 [?100, ?99) 、 ??、 [100,100] 这 201 个区间内, 每个区间内至多只能存在一个根。 这样对除去区间 [100,100] 外
的其他的区间 [a, a ? 1) ,要么 f (a) ? 0 ,要么 f (a) ? f (a ? 1) ? 0 时这个方程在此区间内才 有解。若 f (a) ? 0 ,显然 a 为解;若 f (a) ? f (a ? 1) ? 0 ,则可以利用上面所说的方法球出 解来。这样就可求出这个方程的所有解。 最后是输出的解要求排序。 我们既可以在求出来之后排序, 也可以从小到大的顺序求解, 就可以按照升序求出所有解。 为了简单起见,在写程序的时候,我让 x 从–100.00 到 100.00 进行枚举,得到 20000 个 f(x),比较并取跟 0 最接近的三个 f(x),对应的 x 就是答案了。 [程序]

基础算法习题集(李波于 2007 年 7 月收集整理)

program ex1_18_2; var a,b,c,d,x,tmp:real; ansx,f:array[1..3] of real; {ansx 存放方程的解,f 存放跟 0 最接近的三个 f(x)} i,j:integer; begin readln(a,b,c,d); for i:=1 to 3 do f[i]:=1; {f(x)初值均记为 1} x:=-100; while(x<=100) do begin tmp:=(d+x*(c+x*(b+x*a))); {计算 f(x)的值} j:=1; for i:=2 to 3 do if (f[i]>f[j]) then j:=i; {找出当前记录的 3 个 f(x)值中最大的} if (abs(tmp)<f[j]) then begin f[j]:=abs(tmp); ansx[j]:=x; {若新值比原 f(x)小, 改变当前 f(x)的值并记录 其对应的 x 值,确保当前记录三个 f(x)始终是最小的} end; x:=x+0.01; end; for i:=1 to 3 do {对求得的方程的解排序} for j:=i+1 to 3 do if (ansx[i]>ansx[j]) then begin tmp:=ansx[i]; ansx[i]:=ansx[j]; ansx[j]:=tmp; end; writeln(ansx[1]:0:2,' ',ansx[2]:0:2,' ',ansx[3]:0:2); end.

EX1_19、谁拿了最多奖学金(NOIP05TG) :
某校的惯例是在每学期的期末考试之后发放奖学金。 发放的奖学金共有五种, 获取的条 件各自不同: 1)院士奖学金,每人 8000 元,期末平均成绩高于 80 分(>80) ,并且在本学期内发表 1 篇或 1 篇以上论文的学生均可获得; 2)五四奖学金,每人 4000 元,期末平均成绩高于 85 分(>85) ,并且班级评议成绩高于 80 分(>80)的学生均可获得; 3)成绩优秀奖,每人 2000 元,期末平均成绩高于 90 分(>90)的学生均可获得; 4)西部奖学金,每人 1000 元,期末平均成绩高于 85 分(>85)的西部省份学生均可获 得; 5)班级贡献奖,每人 850 元,班级评议成绩高于 80 分(>80)的学生干部均可获得; 只要符合条件就可以得奖, 每项奖学金的获奖人数没有限制, 每名学生也可以同时获得

基础算法习题集(李波于 2007 年 7 月收集整理)

多项奖学金。例如姚林的期末平均成绩是 87 分,班级评议成绩 82 分,同时他还是一位学生 干部,那么他可以同时获得五四奖学金和班级贡献奖,奖金总数是 4850 元。 现在给出若干学生的相关数据, 请计算哪些同学获得的奖金总数最高 (假设总有同学能 满足获得奖学金的条件) 。 【输入文件】 输入文件 scholar.in 的第一行是一个整数 N(1 <= N <= 100) ,表示学生的总数。接 下来的 N 行每行是一位学生的数据,从左向右依次是姓名,期末平均成绩,班级评议成绩, 是否是学生干部,是否是西部省份学生,以及发表的论文数。姓名是由大小写英文字母组成 的长度不超过 20 的字符串 (不含空格) ; 期末平均成绩和班级评议成绩都是 0 到 100 之间的 整数(包括 0 和 100) ;是否是学生干部和是否是西部省份学生分别用一个字符表示,Y 表示 是,N 表示不是;发表的论文数是 0 到 10 的整数(包括 0 和 10) 。每两个相邻数据项之间用 一个空格分隔。 【输出文件】 输出文件 scholar.out 包括三行, 第一行是获得最多奖金的学生的姓名, 第二行是这名 学生获得的奖金总数。 如果有两位或两位以上的学生获得的奖金最多, 输出他们之中在输入 文件中出现最早的学生的姓名。第三行是这 N 个学生获得的奖学金的总数。 【样例输入】 4 YaoLin 87 82 Y N 0 ChenRuiyi 88 78 N Y 1 LiXin 92 88 N N 0 ZhangQin 83 87 Y N 1 【样例输出】 ChenRuiyi 9000 28700 [分析] 这个题目据问题本身而言是相当简单的, 没有牵涉到过多的算法, 属于普及型试题。 同时也是对实际问题一种分析和判断。总的来看,本题在方向上,向现实问题迈出了一步, 是信息学和生活有了更多的联系。 问题的算法是模拟。当中唯一的难点就是数据处理,考察点为数据库的建立和统计。 对于输入数据有两种方式来实现。 法一〉逐个字符累加。 首先定义 ch:char; 然后利用 c=‘ ’作为终止条件,将读入的字符连接存储到 name 中。 这样做的好处是, 后面的值可以直接用 read 语句读入。 但是最后一个值后, 要记得 readln; 法二〉一次读入,然后分离。 这样做需要逐个分离,对本题来说稍显复杂,但对 NOIP 来说此方法必须掌握,有的时 候一定要用。 具体实现,读入一个字符串 S。利用 pos(‘ ‘,s);找出空格位置。再利用 Copy 函数,和 Val 函数进行截取,和转换。 [程序] program ex1_19; var name:array[1..100] of string; a1,a2,a5:array[1..100] of longint; a3,a4:array[1..100] of char;

基础算法习题集(李波于 2007 年 7 月收集整理)

n,i,max,total,p:longint; maxname:string; ch:char; f:text; begin assign(f,'scholar.in');reset(f); readln(f,n); for i:=1 to n do begin read(f,ch); while ch<>' ' do begin name[i]:=name[i]+ch; read(f,ch); end; readln(f,a1[i],a2[i],ch,a3[i],ch,a4[i],ch,a5[i]); end; close(f); for i:=1 to n do begin p:=0; if (a1[i]>80) and (a5[i]>=1) then inc(p,8000); if (a1[i]>85) and (a2[i]>80) then inc(p,4000); if (a1[i]>90) then inc(p,2000); if (a1[i]>85) and (a4[i]='Y') then inc(p,1000); if (a2[i]>80) and (a3[i]='Y') then inc(p,850); if p>max then begin max:=p; maxname:=name[i]; end; inc(total,p); end; assign(f,'scholar.out');rewrite(f); writeln(f,maxname); writeln(f,max); writeln(f,total); close(f); end.

基础算法习题集(李波于 2007 年 7 月收集整理)

第二章 递推与递归
迭代法:
许多的实际问题都可转化为求方程 F(x)=0 的实数解问题。 求方程的根可以直接从方程 出发,逐步缩小根的存在区间,把根的近似值逐步求精到满足具体实际问题的需要为止,该 算法称为迭代。迭代的一般原则可以用一个数学模型来描述,如要求出方程 F(x)=0 的解: 先设 F(x)=G(x)-x,则方程 F(x)=0 可化为 x=G(x), 这就产生了一个迭代算法的数学模型: Xn+1=G(Xn) 从某一个数X0 出发,按此迭代模型,求出一个序列: {X0,X1,X2,X3,??,Xn-2,Xn-1,Xn} 当Xn-Xn-1 小于一个特定值 (误差许可值) 时, X≈Xn-1≈Xn, 这时可认定 x=G(x)。 也就是说,求出的Xn 已经可以作为原方程 f(x)=0 根的近似值了。迭代算法的关键在于确 定迭代函数 G(x)。确定 G(x)时需保证产生的迭代序列{Xn }是否能使两个相邻数之间的 差距越来越小(即两数的差值越靠近误差值,我们称这样的序列为收敛序列) ,因为只有这 样才能使根的存在范围越来越小,从而为根的取得创造条件。

EX2_1、求算术平方根:
求 2 的算术平方根。 [分析]使用迭代算法来解决这个问题,可先设 X=SQRT(2)-1 (即 SQRT(2)=x+1),则求 2 的 算术平方根的近似值就可以转化为求 X*(X+2)=1 的正根。列出等价方程 X=1/(X+2), 以 1/(X+2)为迭代函数,以 0 为初始近似值X0,误差值设定为 0.0000001, 则程序如下: [程序] program ex2_1; const a=0.0000001; var x0,x1,X:real; begin x0:=0;x1:=1/(x0+2); {x0、x1 的出世作} while abs(x1-x0)>a do {迭代求解,直到误差符合要求} begin x0:=x1;x1:=1/(x0+2); end; x:=x1+1; {将 X1 的值转为 2 的算术平方根} writeln('sqrt(2)=',x); end. 开始时, 迭代函数的根的近似值设定在[0,0.5]之间, 由于区间宽度大于给定误差许可 值,于是再进行迭代运算,产生下一个区间[0.4,0.5]; 其宽度仍然大于误差许可值,再产 生下一个区间;??;如此反复,直到区间的宽度小于误差给定值时,则表明在该区间中, 任意选择一个数都可以满足根的近似值要求了。 为方便起见, 取下该区间的边界置作为近似 值。这就是迭代算法的一般原则的体现了。

基础算法习题集(李波于 2007 年 7 月收集整理)

递推法:
递推法这种解题方法其实在我们编程的过程中用的很多, 只不过没有将其上升到理论的 高度罢了。所谓递推法,就是找出和时间先后相联系或和数的大小相联系的步骤,上一步和 下一步和数字的增大或减小有一定的联系。我们要么从前向后(或从小到大)推导,也可从 后向前(或从大到小)推导。如果对一个试题,我们要是能找到后一项与前一项的关系并清 楚其起始条件(最终结果),问题就好解决,让计算机一步步算就是了,让高速的计算机做这 种重复运算,可真正起到“物尽其用”的效果。由此得出两种推导方法:顺推法和倒推法, 所谓倒推法,就是在不知初始值的情况下,经某种递推关系而获知问题的解或目标,再 倒推过来,推知它的初始条件。因为这类问题的运算过程是一一映射的,故可分析得其递推 公式。然后再从这个解或目标出发,采用倒推手段,一步步地倒推到这个问题的初始陈述。 倒推法的逆过程就是顺推法,即由边界条件出发,通过递推关系式推出后项值,再由后 项值按递推关系式推出再后项值......, 依次递推, 直至从问题初始陈述向前推进到这个问 题的解为止。 两者的一般分析思路如下: if 求解条件 F1 then begin{倒推} 由题意(或递推关系)确定最终结果 Fa; 求出倒推关系式 Fi-1=g'(Fi); i=n;{从最终结果 Fn 出发进行倒推} while 当前结果 Fi 非初始值 F1 do 由 Fi-1=g(F1)倒推前项; 输出倒推结果 F1 和倒推过程; end {then} else begin{顺推} 由题意(或顺推关系)确定初始值 F1(边界条件); 求出顺推关系式 F1=g(Fi-1); i=1;{由边界条件 F1 出发进行顺推} while 当前结果 Fi 非最终结果 Fn do 由 Fi=g(Fi-1)顺推后项; 输出顺推结果 Fn 和顺推过程; end; {else}。

EX2_2、猴子分桃:
五只猴子采得一堆桃子,猴子彼此约定隔天早起后再分食。不过,就在半夜里,一只猴 子偷偷起来,把桃子均分成五堆后,发现还多一个,它吃掉这桃子,并拿走了其中一堆。第 二只猴子醒来,又把桃子均分成五堆后,还是多了一个,它也吃掉这个桃子,并拿走了其中 一堆。第三只,第四只,第五只猴子都依次如此分食桃子,第二天起来一看,桃子还剩下 4 个。那么桃子数最少应该有几个呢? [分析]怎样编程呢?先要找一下剩余桃子数目和其面前桃子数的关系。如果从开始最后找, 不好找,但如果思路一变,从最后倒推回去,可得出下面的推导式(设最后剩余数目为 x) : 5 s5=x*5/4+1 4 s4=s5*5/4+1 3 s3=s4*5/4+1 2 s2=s3*5/4+1 1 s1=s2*5/4+1 s1 即为所求。上面的规律中只要将 s1-s5 的下标去掉,表达式就变成了如下样式: s=x

基础算法习题集(李波于 2007 年 7 月收集整理)

s=x*5/4+1 s=s*5/4+1 s=s*5/4+1 s=s*5/4+1 s=s*5/4+1 因此用循环语句即可解决,程序如下: [程序] Program ex2_2; var s:real; i:integer; begin s:=4; for i:=1 to 5 do s:= s*5/4+1; writeln(s:0:0); end. 与该题类似的试题还有如卖鱼问题:卖金鱼的人将缸里的金鱼分五次全部卖出:第一次 卖出全部金鱼的二分之一加二分之一条 ,第二次卖出剩余金鱼的三分之一加三分之一条 ,第 三次卖出剩余金鱼的四分之一加四分之一条,第四次卖出剩余金鱼的五分之一加五分之一条, 现还剩下 11 条金鱼,问这渔缸里原有多少条金鱼? {分析:用倒推法,由题目原意 M:=M-(M+1)/I 推出倒退计算公式:M:=(M*I+1)/(I-1)}

EX2_3、一元多项式求值(NOIP1995):
m,n 为整数,且满足下列两个条件: ① m,n ∈{1,2,3,.....k},(1≤k≤109) 2 2 2 ② (n -mn-m ) =1 2 2 编一程序,由键盘输入 k,求一组满足上述两个条件的 m、n,并且使 m +n 的值最大。 2 2 例如:若 k=1995,则 m=987、n=1597 时,则 m、n 满足条件,且可使 m +n 的值最大。 [分析]利用二次多项式求根公式把②式变形为:

n ? m ? 5m 2 ? 4
2 2

?

?

2

因要使 m +n 的值最大,因此,根号前只取“+” 。 令 m 从 1 开始顺序取值, 代入上式逐个试验, 求出能使 n 为整数的 m 值和 n 值(见表 7-1)。 ──┳─┳─┳─┳─┳─┳─┳── m ┃1 ┃1 ┃2 ┃3 ┃5 ┃8 ┃......? ──╋─╋─╋─╋─╋─╋─╋── ?? n ┃1 ┃2 ┃3 ┃5 ┃8 ┃13┃......? ?? ──┻─┻─┻─┻─┻─┻─┻── 观察上表,可发现 m、n 的值分别组成了两组斐波那契数列,且 m、n 的所有对应值均为 斐波那契数列 1,1,2,3,5,8,13,.. ..中的前后项。由此,可得 m、n 值的变化规律 和取值方法。 利用斐波那契数列递推公式:Un=Un-1+Un-2 (U1=1,U2=1),逐项递推计算, 2 2 直到 Un 的值大于 k 为止,此时,Un-2 的值为 m,Un-1 的值为 n,且 m +n 的值最大,并且 满足②式的要求。 [程序] program ex2_3; var m,n,x,k:longint;

基础算法习题集(李波于 2007 年 7 月收集整理)

begin n:=1;x:=1; write('K=');readln(k); repeat m:=n;n:=x; x:=m+n; until x>k; wreteln('M=',m,' N=',n); end.

EX2_4、贮油点:
一辆重型卡车欲穿过 1000 公里的沙漠,卡车耗油为 1 升/公里,卡车总载油能力为 500 公升。显然卡车一次是过不了沙漠的。因此司机必须设法在沿途建立几个储油点,使卡车能 顺利穿越沙漠, 试问司机如何建立这些储油点?每一储油点应存多少油, 才能使卡车以消耗 最少油的代价通过沙漠? [分析]编程计算及打印建立的贮油点序号,各贮油点距沙漠边沿出发的距离以及存油量。 No. Distance(k.m.) oil(litre) 1 XX XX 2 XX XX 3 XX XX ... ..... ...... 设 dis[i] 为第 i 个贮油点至终点(i=0)的距离;oil[i] 为第 i 个贮油点的存贮油量; 我们可以用倒推法来解决这个问题。从终点向始点倒推,逐一求出每个贮油点的位置及 存油量。下图表示倒推时的返回点:

从贮油点 i 向贮油点 i+1 倒推的策略是,卡车在点 i 和点 i+1 间往返若干次。卡车每次 返回 i+1 处时正好耗尽 500 公升汽油,而每次从 i+1 出发时又必须装足 500 公升汽油。两点 之间的距离必须满足在耗油最少的条件下使 i 点贮足 i*500 分升汽油的要求(0<=i<=n-1)。具 体地讲, 第一个贮油点 i=1 应距终点 i=0 处 500km 且在该处贮藏 500 公升汽油, 这样才能保 证卡车能由 i=1 处到达终点 i=0 处,这就是说

dis[1]=500 oil[1]=500; 为了在 i=1 处贮藏 500 公升汽油, 卡车至少从 i=2 处开两趟满载油的车至 i=1 处。 所以 i=2 处至少贮有 2*500 公升汽油,即 oil[2]=500*2=1000。另外,再加上从 i=1 返回至 i=2 处的一 趟空载, 合计往返 3 次。 三次往返路程的耗油量按最省要求只能为 500 公升。 即 d12=500/3km dis[2]=dis[1]+d12=dis[1]+500/3

基础算法习题集(李波于 2007 年 7 月收集整理)

为了在 i=2 处贮存 1000 公升汽油,卡车至少从 i=3 处开三趟满载油的车至 i=2 处。报 以 i=3 处至少贮有 3*500 公升汽油,即 oil[3]=500*3=1500。加上 i=2 至 i=3 处的二趟返程 空车,合计 5 次。路途耗油量也应为 500 公升,即 d23=500/5,

dis[3]=dis[2]+d23=dis[2]+500/5; 依此类推,为了在 i=k 处贮藏 k*500 公升汽油,卡车至少从 i=k+1 处开 k 趟满载车至 i=k 处,即 oil[k+1]=[k+1]*500=oil[k]+500, 加上从 i=k 处返回 i=k+1 的 k-1 趟返程空间, 合 计 2k-1 次。这 2k-1 次总耗油量按最省要求为 500 公升,即 dk,k+1=500/(2k-1) dis[k+1]=dis[k]+dk,k+1 =dis[k]+500/(2k-1);

最后,i=n 至始点的距离为 1000-dis[n],oil[n]=500*n。为了在 i=n 处取得 n*500 公 升汽油,卡车至少从始点开 n+1 次满载车至 i=n,加上从 i=n 返回始点的 n 趟返程空车,合 计 2n+1 次 , 2n+1 趟 的 总 耗 油 量 应 正 好 为 (1000-dis[n])*(2n+1) , 即 始 点 藏 油 为 oil[n]+(1000-dis[n])*(2n+1)。 [程序] program ex2_4; var k:integer; {贮油点位置序号} d, {累计终点至当前贮油点的距离} d1:real; {i=n 至始点的距离} oil,dis:array[1..10] of real; i:integer; {辅助变量} begin writeln('NO.','distance(k.m)':30,'oil(1.)':80);

基础算法习题集(李波于 2007 年 7 月收集整理)

k:=1; d:=500; { 从 i=1 处开始向始点倒推} dis[1]:=500; oil[1]:=500; repeat k:=k+1; d:=d+500/(2*k-1); dis[k]:=d oil[k]:=oil[k-1]+500; until d>=1000; dis[k]:=1000; {置始点至终点的距离值} d1:=1000-dis[k-1]; {求 i=n 处至始点的距离} oil[k]:=d1*(2*k+1)+oil[k-1]; {求始点藏油量} for i:=0 to k do {由始点开始,逐一打印始点至当前贮油点的距离和藏油量} writeln(i,1000-dis[k-i]:30,oil[k-i]:80); end. {main}

EX2_5、实数数列:
一个实数数列共有 N 项, 已知 ai=(ai-1-ai+1)/2+d, (1<i<N)(N<60)。 键盘输入 N, d, a1,an,m,输出 am。输入数据均不需判错。 [分析]分析该题,对公式: Ai=(Ai-1-Ai+1)/2+d (1<i<N) (n<60) 作一翻推敲,探讨其数字变换规律。不然的话会无从下手。 令 X=A2 s2[i]=(pi,Qi,Ri)表示 Ai=PiX+QiD+RiA1 我们可以根据 Ai=Ai-2-2Ai-1+2D =PiX+QiD+RiA1 推出公式 PiX+QiD+RiA1=(Pi-2-2Pi-1)X+(Qi-2-2Qi-1+2)D+(Ri-2-2Ri-1)A1 比较等号两端 X,D 和 A1 的系数项,可得 Pi=Pi-2-2Pi-1 Qi=Qi-2-2Qi-1+2 Ri=Ri-2-2Ri-1 加上两个边界条件 P1=0 Q1=0 R1=1 (A1=A1) P2=1 Q2=0 R2=0 (A2=A2) 根据 Pi、Qi、Ri 的递推式,可以计算出 S2[1]=(0,0,1); S2[3]=(-2,2,1); S2[4]=(5,-2,-2); S2[5]=(-12,8,5); ................... S2[i]=(Pi,Qi,Ri); ................... S2[N]=(PN,QN,RN);

基础算法习题集(李波于 2007 年 7 月收集整理)

有了上述基础,AM 便不难求得。有两种方法: 1、由于 AN、A1 和 PN、QN、RN 已知,因此可以先根据公式: A2=AN-QND-RNA1/PN 求出 A2。然后将 A2 代入公式 A3=A1-2A2+2D 求出 A3。然后将 A3 代入公式 A4=A2-2A3+2D 求出 A4。然后将 A4 代入公式 ............................ 求出 Ai-1。然后将 Ai-1 代入公式 Ai=Ai-2-2Ai-1+2D 求出 Ai。依此类推,直至递推至 AM 为止。 上述算法的缺陷是由于 A2 是两数相除的结果,而除数 PN 递增,因此精度误差在所 难免,以后的递推过程又不断地将误差扩大,以至当 M 超过 40 时,求出的 AM 明显徧离正确 值。显然这种方法简单但不可靠。 2、我们令 A2=A2,A3=X,由 S3[i]=(Pi,Qi,Ri)表示 Ai=PiX+QiD+RiA2 (i>=2) 可计算出: S3[2]=(0,0,1)=S2[1]; S3[3]=(1,0,0)=S2[2]; S3[4]=(-2,2,1)=S2[3]; S3[5]=(5,-2-2)=S2[4]; ...................... S3[i]=(..........)=S2[i-1]; ..................... S3[N]=(..........)=S2[N-1]; 再令 A3=A3,A4=X,由 S4[i]=(pi,Qi,Ri)表示 Ai=PiX+QiD+RiA3 (i>=3) 可计算得出: S4[3]=(0,0,1)=S3[2]=S2[1]; S4[4]=(1,0,0)=S3[3]=S2[2]; S4[5]=(-22,1)=S3[4]=S2[3]; .......................... S4[i]=(...........)=S3[i-1]=S2[i-2]; ....................... S4[N]=(...........)=S3[N-1]=S2[N-2]; 依此类推,我们可以发现一个有趣的式子: AN=PN-i+2*Ai+QN-i+2*D+RN-i+2*Ai-1, 即 Ai=(AN-QN-i+2*D-RN-i+2*Ai-1)/PN-i+2 我们从已知量 A1 和 AN 出发,依据上述公式顺序递推 A2、A3、...、AM.由于 PN-i+2 递减, 因此最后得出的 AM 要比第一种算法趋于精确。 程序代码如下: program ex2_5; const maxn=60; var n,m,i :integer; d :real; list :array[1..maxn] of real; {list[i]-------对应

基础算法习题集(李波于 2007 年 7 月收集整理)

ai} s Pi} {s[i,2]--------对应 Qi} {s[i,3]--------对应 Ri} procedure init; begin write('n m d ='); readln(n,m,d); {输入项数,输出项序号和常 数} write('a1 a',n,'='); readln(list[1],list[n]); {输入 a1 和 an} end; {init} procedure solve; begin s[1,1]:=0;s[1,2]:=0;s[1,3]:=1; { 求 递 推 边 界 (P1,Q1,R1) 和 (P2,Q2,R2)} s[2,1]:=1;s[2,2]:=0;s[2,3]:=0; { 根 据 公 式 Pi<---Pi-2 2*Pi-1} {Qi<---Qi-2 - 2*Qi-1} {Ri<---Ri-2 - 2*Ri-1} {递推(P3,Q3,R3)......Pn,Qn,Rn}} for i:=3 to n do begin s[i,1]:=s[i-2,1]-2*s[i-1,1]; s[i,2]:=s[i-2,2]-2*s[i-1,2]+2; s[i,3]:=s[i-2,3]-2*s[i-1,3]; end; {for} end;{solve} procedure main; begin solve; {求(P1,Q1,R1)..(Pn,Qn,Rn)} {根据公式 Ai=(An-Qn-i+2 * d-Rn-i+2 * Ai-1)/Pn-i+2} {递推 A2..Am} for i:=2 to m do list[i]:=(list[n]-s[n-i+2,2]*d-s[n-i+2,3]*list[i-1])/s[ n-i+2,1]; writeln('a',m,'=',list[m]:20:10); {输出 Am} :array[1..maxn,1..3] of real; {s[i,1]-------- 对 应

基础算法习题集(李波于 2007 年 7 月收集整理)

end; begin init; main; readln; end.

{main} {输入数据} {递推和输出 Am}

递归:说白了递归就象我们讲的那个故事:山上有座庙,庙里有个老和尚,老和尚在讲故
事,它讲的故事是:山上有座庙,庙里有个老和尚,老和尚在讲故事,它讲的故事是:?? 也就是直接或间接地调用了其自身。 就象上面的故事那样,故事中包含了故事本身。因为对自身进行调用,所以需对程序段 进行包装,也就出现了函数。 函数的利用是对数学上函数定义的推广, 函数的正确运用有利于简化程序, 也能使某些 问题得到迅速实现。对于代码中功能性较强的、重复执行的或经常要用到的部分,将其功能 加以集成,通过一个名称和相应的参数来完成,这就是函数或过程,使用时只需对其名字进 行简单调用就能来完成特定功能。 函数又可分为自定义的和系统附带的, 但不管是自定义的还是系统的, 他们都对相应的 功能进行了封装,以利于我们经常性地使用。例如我们的对一个小数取整数 INT()函数,不 论什么样的小数,往()中一放,将来得到的值就自动将小数去除了。函数执行完将返回一 个值,当然这个值可以是各种类型的,子程序仅仅执行一个过程,不返回数值。 函数和过 程是执行递归的干将。 递归调用技术的运用, 是在牺牲计算机内存空间和程序执行速度的基础上得到的。因 为在递归调用的执行过程中, 系统必须花费时间与空间以栈的方式记下每次调用的返回位置 地址及每一次过程执行的中间结果,以便当递归调用终止条件成立时,能沿着 "逐步深入" 的路线"逐步返回",取得这些数据,最终准确地回到初始调用处。

EX2_6、小猴吃枣:
小猴第一天摘下若干枣子,当即吃掉了一半,不过瘾又多吃了一个;第二天吃了剩下的 一半又多吃了一个;以后每一天都吃了前一天剩下的一半多一个。到第十天小猴再想吃时, 见到只剩下一只枣子了。问第一天这堆枣子有多少? [分析]从上题中我们可看到一个令人欣喜的规律,第十天为 1,第九到第一天中后一天与 1 的和的两倍与前一天相等。下面就对这一规律做了描述: Function monkey(x:Integer):Integer; begin If x >= 10 Then monkey=1 Else monkey:=2*(monkey(x+1)+1); End; 我们定义 monkey()函数的时候通过 monkey()自身来进行了定义,这就是递归。递归是 个特殊的循环,是一个有着非常美妙的循环规则的循环。上题中我们只要在主程序中调用 monkey(1),即将第一天打印出来,一切 OK。而这中间究竟是怎么工作的,我们可以不管。 [程序] Program ex2_6; Function monkey(x:Integer):Integer; begin If x >= 10 Then monkey=1 Else monkey:=2*(monkey(x+1)+1);

基础算法习题集(李波于 2007 年 7 月收集整理)

End; Writeln(monkey(1)); End. 正是有了 monkey()函数,在对其自身调用的过程中实现了我们的所求,关于函数、过 程和他们之间发生的故事还有很多, 仅仅列举了其中奇妙的几点, 还有许多东东等着您的发 现和利用。

EX2_7、汉诺塔:
相传在古印度的布拉玛婆罗门圣庙的僧侣在进行一种被称为汉诺塔的游戏, 其装置是一 块铜板,上面有三根杆(编号 A、B、C),A 杆上自下而上、由大到小按顺序串上 64 个金盘。 A 杆上的金盘全部移到 C 杆上,并仍原有顺序叠好。条件是每次只能移动一个盘,并且在每 次移动都不允许大盘移到小盘之上。 现要求利用递归调用技术给出 N 个盘从 A 杆移到 C 杆的

A

B

C

移动过程。 [分析]这个移动过程很复杂与烦琐, 但规律性却很强。 使用递归调用技术来解决这个移动过 程,先得找到一个递归调用模型。想要得到汉诺塔问题的简单解法,着眼点应该是移动 A 杆最底部的大盘,而不是其顶部的小盘。不考虑 64 个盘而考虑 N 个盘的一般情况。要想将 A 杆上的 N 个盘移至 C 杆,我们可以这样设想: 1.以 C 盘为临时杆,从 A 杆将 1 至 N-1 号盘移至 B 杆。 2.将 A 杆中剩下的第 N 号盘移至 C 杆。 3.以 A 杆为临时杆,从 B 杆将 1 至 N-1 号盘移至 C 杆。 我们看到,步骤 2 只需移动一次就可以完成;步骤 1 与 3 的操作则完全相同, 唯一区 别仅在于各杆的作用有所不同。这样,原问题被转换为与原问题相同性质的、规模小一些的 新问题。即: HANOI(N,A,B,C) 可转化为 HANOI(N-1,A,C,B)与 HANOI(N-1,B,A,B) 其中 HANOI 中的参数分别表示需移动的盘数、起始盘、临时盘与终止盘, 这种转换直 至转入的盘数为 0 为止,因为这时已无盘可移了。 这就是需要找的递归调用模型。 将 N 个盘从 A 柱移动到 C 柱需要移动盘的次数是 2n - 1 ,那么 64 个盘移动次数就 是 18446744073709511615,近 19 亿亿次。这是一个天文数字,即使用一台功能很强的计算 机解汉诺塔问题,也需要很长的时间。因此,在运行程序时,输入的 N 不能太大。据说婆罗 门圣庙的僧侣声称, 汉诺塔游戏结束时,就标志着世界末日的到来,现在看来确实如此。 因为如果每秒移动一次, 移完 64 个盘大约需要 5800 亿年, 而太阳系的寿命也只不过 150 亿 年。 [程序] program ex2_7; var a,b,c:char; n:byte; procedure hanoi(n:byte;a,b,c:char);

基础算法习题集(李波于 2007 年 7 月收集整理)

begin if n>0 then begin hanoi(n-1,a,c,b); {以 C 为临时杆,从 A 杆将 1 至 N-1 号盘移至 B 杆} writeln('Move ',a,' to ',c); {将 A 杆中剩下的第 N 号盘移至 C 杆} hanoi(n-1,b,a,c); {以 A 杆为临时杆,从 B 杆将 1 至 N-1 号盘移至 C 杆} end; end; begin a:='A';b:='B';c:='C'; write('N=');readln(n); hanoi(n,a,b,c); end.

EX2_8、求最大公约数:
用递归算求自然数 A,B 的最大公约数。 [分析]求最大公约数的方法有许多种,若用欧几里德发明的辗转相除方法如下: ①定义求 X 除以 Y 的余数的过程; ②如果余数不为 0,则让 X=Y,Y=余数,重复步骤①,即调用过程; ③如果余数为 0,则终止调用过程; ④输出此时的 Y 值。 以下程序是辗转相除法与递归结合实现的程序。 [程序] Program ex2_8; Var a,b,d: integer; Procedure Gdd(x, y: nteger);{递归过程} begin if x mod y =0 then d :=y else Gdd(y, x mod y) {递归调用过程} end; begin write(’input a, b=’); readln(a, b); Gdd(a, b); writeln(’(’, a, ’,’, b, ’)=’, d ); readln end.

EX2_9、过河卒:
如图,A 点有一个过河卒,需要走到目标 B 点。卒行走规则:可以向下、或者向右。 同时在棋盘上的任一点有一个对方的马(如上图的 C 点),该马所在的点和所有跳跃一步可 达的点称为对方马的控制点。 例如上图 C 点上的马可以控制 9 个点 (图中的 P1, P2 ? P8 和 C)。卒不能通过对方马的控制点。

基础算法习题集(李波于 2007 年 7 月收集整理)

棋盘用坐标表示,A 点(0,0)、B 点(n,m)(n,m 为不超过 20 的整数,并由键盘输入), 同样马的位置坐标是需要给出的(约定: C<>A,同时 C<>B)。现在要求你计算出卒从 A 点 能够到达 B 点的路径的条数。 [输入]: 键盘输入 B 点的坐标(n,m)以及对方马的坐标(X,Y){不用盘错} [输出]: 屏幕输出 一个整数(路径的条数)。 [输入输出样例]: 输入: 6 6 3 2 输出: 17 [分析]这是一道老得不能再老的题目了,很多书上都有类似的题目,NOIp97 普及组的最后 一题就和本题几乎一模一样。有些同学由于没见过与之类似的题目,在比赛时用了搜索,当 n 到 14,15 左右就会超时,其实,本题稍加分析,就能发现:要到达棋盘上的一个点,只 能从左边过来或是从上面下来,所以根据加法原理,到达某一点的路径数目,等于到达其相 邻上,左两点的路径数目之和,因此我们可以使用逐列(或逐行)递推的方法来求出从起始 顶点到重点的路径数目,即使有障碍(我们将马的控制点称为障碍) ,这一方法也完全适用, 只要将到达该点的路径数目置为 0 即可,用 F[i,j]表示到达点(i,j)的路径数目,g[i,j]表 示点(i, j)有无障碍,递推方程如下:

F[0,0] F[i,j] F[i,0] F[0,j] F[i,j]

= = = = =

1 0 F[i-1,0] F[0,j-1] F[i-1,j] + F[i,j-1]

{ g[x,y] = 1 } {i > 0, g[x,y] = 0} {j > 0, g[x,y] = 0} {i > 0, j > 0, g[x, y] = 0}

基础算法习题集(李波于 2007 年 7 月收集整理)

本题与第三题一样,也要考虑精度问题,当 n,m 都很大时,可能会超过 MaxLongInt,所以要 使用 Comp 类型计数(Comp 类型已经足够了, 即使 n=20,m=20, 没有任何障碍的情况下的结果 也只有 14,5 位的样子)。 [程序] program ex2_9; const dx: array[1..8] of Shortint=(-2,-1,1,2,2,1,-1,-2); dy: array[1..8] of Shortint=(1,2,2,1,-1,-2,-2,-1); var n,m,x,y,i,j:Byte; g:array[0..20,0..20] of Byte; f:array[0..20,0..20] of Comp; begin Readln(n,m,x,y); Fillchar(g,Sizeof(g),0); g[x,y]:=1; for i:=1 to 8 do if (x+dx[i]>=0) and (x+dx[i]<= n) and (y+dy[i]>=0) and (y+dy[i]<=m) then g[x+dx[i],y+dy[i]]:=1; f[0,0]:=1; for i:=1 to n do if g[i,0]=0 then f[i,0]:=f[i-1,0]; for i:=1 to m do if g[0,i]=0 then f[0,i]:= f[0,i-1]; for i:=1 to n do for j:=1 to m do if g[i,j]=0 then f[i,j]:=f[i-1,j]+f[i,j-1]; Writeln(f[n,m]:0:0) end.

第三章 回溯
回溯法也称为试探法, 该方法首先暂时放弃关于问题规模大小的限制, 并将问题的候选 解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时,就选择下一个候选解;倘 若当前候选解除了还不满足问题规模要求外, 满足所有其他要求时, 继续扩大当前候选解的 规模,并继续试探。如果当前候选解满足包括问题规模在内的所有要求时,该候选解就是问 题的一个解。在回溯法中,放弃当前候选解,寻找下一个候选解的过程称为回溯。扩大当前 候选解的规模,以继续试探的过程称为向前试探。 回溯是最常用的搜索方法之一, 它采用深度优先的策略来枚举所有可能的解, 结合题设 条件的限定,从而得到问题的解。 其递归形式的框架如下: procedure tryall; var i:integer; Begin

基础算法习题集(李波于 2007 年 7 月收集整理)

If target() then output; {达到目标则输出} For i:=1 to p do If defined(i) then begin down(i); tryall; up(i); end; {递归深入尝试} End; 其中: 变量 p 表示每一阶段决策的可选方案数; target()函数返回布尔值,用来判断是否完成一次搜索找到一组问题的解; output 过程用于记录或输出所得的解; defined(i)函数返回布尔值,用来判断该阶段是否可以采用方案 I; down(i)过程用来记录目前阶段的决策,进入下一阶段; up(i)过程是回溯,返回上一阶段,寻求新的方案。 非递归形式的框架如下: k:=1; fillchar(a,sizeof(a),0); while k>0 do begin inc(a[k]); flag:=false; while not flag and (a[k]<=p) do if not defined(a[k]) then inc(a[k]) else flag:=true; if flag then begin down; if target() then output; end else up; 其中数组 a 用于记录各个阶段所采用的方案。

EX3_1、质数圈问题:
有 1 到 10 这 10 个数,现在要想把它们排成一个圈,满足相邻两个数之和为质数。输出 所有可能的方案。 [分析]10 个数字放成一圈,要满足题意,实际就是安排每个数字的位置。我们可以假设将 数字 1 的位置固定,接下来要做的就是尝试其余 9 个数放置的方式了。 为方便判断,在此将 10 个数两两相加范围内可能形成的质数用数组 simp 描述出来了, 使用对应位置判断即可。 用回溯法解决的程序描述如下: [程序] program ex3_1; const simp:array[3..19] of Boolean =(true,false,true,false,true,false,false,false,true,false,true,false,fals e,false,true,false,true); {1 到 10 这 10 个数中,相邻两个数之和最大为 19,19 以内的质数是有限的。本数组记录了 3 到 19 内所有质数} var used:array[1..10] of boolean; {数字 i 是否被使用} order:array[1..10]of byte; {正确排放序列} total:longint; procedure seach(step:byte); var i:byte;

基础算法习题集(李波于 2007 年 7 月收集整理)

begin if step=11 then {step=11 表示已经正确地形成了一个圈} begin if simp[order[10]+order[1]] then {判断第一个数和最后一个是之和是否为质数} begin for i:=1 to 10 do write(order[i],' '); writeln; inc(total); end; end else for i:=2 to 10 do if not used[i] and simp[i+order[step-1]] then {数字 i 未被使用且与前面一个数之和是质数,则作如下记录} begin order[step]:=i; used[i]:=true; seach(step+1); {递归寻找并填充下一个数} used[i]:=false; {回溯} end; end; begin fillchar(used,sizeof(used),0); used[1]:=true; order[1]:=1; {第一个数放 1,固定} seach(2); writeln('total=',total); end.

EX3_2、算 24 点:
几十年前全世界就流行一种数字游戏,至今人仍有人乐此不疲。在中国,我们把这种游 戏称为“算 24 点” 。你作为游戏者将得到 4 个 1~9 之间的自然数作为操作数,而你的任务是 对这四个数进行适当的算术运算,要求运算结果等于 24。 你可以使用的运算符只有:+、-、*、/,你还可以使用()来改变运算顺序。注意:所 有的中间结果必须是整数, 所以一些除法运算是不允许的 (例如: 2*2/4 是合法的, 而 2* (2/4) 是不合法的) 。 输入:只有一行,四个 1 到 9 之间的自然数。 输出:如果有解,只要输出一个解。输出的是三行数据,分别表示运算的步骤。 第一行是输入的两个数和一个运算符运算后的结果; 第二行是第一行的结果和一个输入的数据以及一个运算符运算后的结果; 第三行是第二行的结果和一个输入的数据、一个运算符以及“=24” 。 如果两个操作数有大小的话则先输出大的。 如果没有解则输出“No answer! ” 样例: point24.in 1237

基础算法习题集(李波于 2007 年 7 月收集整理)

point24.out 2+1=3 7*3=21 21+3=24 [分析]算 24 点的主要应用是四种运算。开始状态有四个操作数,一个运算符对应两个操作 数, 所以一开始选择两个操作数分别与四个运算符进行循环判断, 每一次运算后都会产生一 个新的运算数,使运算数的个数减少一个。最初四个运算数需要进行三次运算,最终变成一 个数,该数为 24 则满足题意。 由于操作的层数比较少(仅三层) ,因此可以使用回溯法来完成此题。只需找到一个符 合题意的解即可结束,若所有情况都找过后仍然没有符合要求的,则可输出“No answer! ” 。 [程序] program ex3_2; type arr=array [1..4] of integer; var i,result,n,len:integer; d:arr; {d 数组存放最初的 4 个操作数} r:array [1..3,1..4] of integer; {存放结果的 3 个表达式;每个表达式除”=” 外包含 4 个项目,其中第二个项目表示运算符} procedure print; {} var i,j:integer; begin assign(output,'point24.out'); rewrite(output); for i:=1 to 3 do begin for j:=1 to 3 do if j<>2 then write(r[i,j]) {j=2 则输出运算符} else case r[i,j] of 1:write('+'); 2:write('-'); 3:write('*'); 4:write('/') end; writeln('=',r[i,4]) {输出表达式计算结果} end; close(output); end; procedure try(k:integer;d:arr); {递归求解过程; 以 d 数组中的 k 个数构成表达式} var a,b,i,j,l,t:integer; e:arr; {临时存放剩余操作数,用于递归到下一层} begin if k=1 then if d[1]=24 then {若仅余一个运算数且值为 24 则输出,程序结束} begin print;halt; end else else

基础算法习题集(李波于 2007 年 7 月收集整理)

begin for i:=1 to k-1 do for j:=i+1 to k do begin a:=d[i]; b:=d[j]; if a<b then begin t:=a;a:=b;b:=t end; {为满足题意的操作数输出大小而排序} t:=0; for l:=1 to k do if (l<>i) and (l<>j) then begin t:=t+1;e[t]:=d[l] end; {将数组 d 向数组 e 中转移,为递归求下一步作准备} r[5-k,1]:=a; r[5-k,3]:=b; r[5-k,4]:=-1; for l:=1 to 4 do {以本层所取两数做求值尝试} begin case l of 1:r[5-k,4]:=a+b; 2:r[5-k,4]:=a-b; 3:r[5-k,4]:=a*b; 4:if b<>0 then if a mod b=0 then r[5-k,4]:=a div b end; {作除法操作时,需判断除数是否为 0} r[5-k,2]:=l; if r[5-k,4]<>-1 then begin e[t+1]:=r[5-k,4];{将求值结果存入数组 e,作为下一层的操作数} try(k-1,e) end end end end; end; begin assign(input,'point24.in'); reset(input); for i:=1 to 4 do read(d[i]); close(input); try(4,d); {初试时,d 数组有 4 个操作数开始进行尝试} assign(output,'point24.out'); rewrite(output); writeln('No answer!'); close(output); end.

EX3_3、八皇后问题:

基础算法习题集(李波于 2007 年 7 月收集整理)

在一个8×8的棋盘里放置8个皇后, 要求每个皇后两两之间不相"冲" (在每一横列竖 列斜列只有一个皇后) 。 [分析]这道题可以用递归循环来做,分别一一测试每一种摆法,直到得出正确的答案。主要 解决以下几个问题: 1、冲突。包括行、列、两条对角线: (1)列:规定每一列放一个皇后,不会造成列上的冲突; (2)行:当第 I 行被某个皇后占领后,则同一行上的所有空格都不能再放皇后,要把以 I 为下标的标记置为被占领状态; (3)对角线:对角线有两个方向。在同一对角线上的所有点(设下标为(i,j)) ,要么(i+j) 是常数,要么(i-j)是常数。因此, 当第 I 个皇后占领了第 J 列后,要同时把以(i+j)、(i-j) 为下标的标记置为被占领状态。 2、数据结构。 (1)解数组 A。A[I]表示第 I 个皇后放置的列;范围:1..8 (2)行冲突标记数组 B。B[I]=0 表示第 I 行空闲;B[I]=1 表示第 I 行被占领;范围:1..8 (3)对角线冲突标记数组 C、D。 C[I-J]=0 表示第(I-J)条对角线空闲;C[I-J]=1 表示第(I-J)条对角线被占领;范围: -7..7 D[I+J]=0 表示第(I+J)条对角线空闲;D[I+J]=1 表示第(I+J)条对角线被占领;范围: 2..16 算法流程: 1、数据初始化。 2、从 n 列开始摆放第 n 个皇后(因为这样便可以符合每一竖列一个皇后的要求) ,先测试 当前位置(n,m)是否等于0(未被占领): 如果是,摆放第 n 个皇后,并宣布占领(记得要横列竖列斜列一起来哦),接着进行递归; 如果不是, 测试下一个位置(n,m+1), 但是如果当 n<=8,m=8 时, 却发现此时已经无法摆放时, 便要进行回溯。 3、当 n>8 时,便一一打印出结果。 [程序] program ex3_3; var a:array [1..8] of integer; b,c,d:array [-7..16] of integer; t,i,j,k:integer; procedure print; begin t:=t+1; write(t,' '); for k:=1 to 8 do write(a[k],' '); writeln; end; procedure try(i:integer); var j:integer; begin for j:=1 to 8 do {每个皇后都有 8 种可能位置} if (b[j]=0) and (c[i+j]=0) and (d[i-j]=0) then {判断位

基础算法习题集(李波于 2007 年 7 月收集整理)

置是否冲突} begin a[i]:=j; {摆放皇后} b[j]:=1; {宣布占领第 J 行} c[i+j]:=1; {占领两个对角线} d[i-j]:=1; if i<8 then try(i+1) {8 个皇后没有摆完,递归摆 放下一皇后} else print; 果} b[j]:=0; c[i+j]:=0; d[i-j]:=0; end; end; begin for k:=-7 to 16 do {数据初始化} begin b[k]:=0; c[k]:=0; d[k]:=0; end; try(1);{从第 1 个皇后开始放置} end. {回溯} {完成任务,打印结

EX3_4、老鼠走迷宫:
在以下地图中,一只老鼠从点[1,1]出发,要到达点[6,7],请你为它找一条可以通行的 路。地图如下: (1,0,1,1,1,1,1) (1,0,1,0,0,0,1) (1,0,1,0,0,0,1) (1,0,1,0,0,0,1) (1,0,1,0,0,0,1) (1,1,1,0,0,0,1) (0,0,0,0,0,0,0) [分析]一个简单的求解方法是:从入口出发,沿某一方向进行探索,若能走通,则继续向前 走;否则沿原路返回,换一方向再进行搜索,直到所有可能的通路都探索到为止。即所谓的 回溯法。 求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时, 通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前探索,若能走通,则继续 往前走;否则沿原路退回,换一个方向再继续探索,直至所有可能的通路都探索到为止。为 了保证在任何位置上都能沿原路退回, 显然需要用一个后进先出的结构来保存从入口到当前 位置的路径。因此,在求迷宫通路的算法中应用“栈”也就是自然而然的事了。 假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”, 则求迷宫 中一条路径的算法的基本思想是:若当前位置"可通",则纳入"当前路径",并继续朝“下一

基础算法习题集(李波于 2007 年 7 月收集整理)

位置”探索, 即切换“下一位置”为“当前位置”, 如此重复直至到达出口; 若当前位置“不 可通”, 则应顺着“来向”退回到“前一通道块”, 然后朝着除“来向”之外的其他方向继 续探索;若该通道块的四周四个方块均“不可通”,则应从“当前路径”上删除该通道块。 所谓“下一位置”指的是“当前位置”四周四个方向(东、南、西、北)上相邻的方块。 [程序] Program ex3_4; const dx:array[1..4] of integer=(1,0,-1,0); dy:array[1..4] of integer=(0,1,0,-1); {dx,dy 分别标志前进增加的横、纵坐标} map:array[0..8,0..8] of integer=((0,0,0,0,0,0,0,0,0), (0,1,0,1,1,1,1,1,0), (0,1,0,1,0,0,0,1,0), (0,1,0,1,0,0,0,1,0), (0,1,0,1,0,0,0,1,0), (0,1,0,1,0,0,0,1,0), (0,1,1,1,0,0,0,1,0), (0,0,0,0,0,0,0,0,0), (0,0,0,0,0,0,0,0,0)); {地图, 人为将迷宫 的最外圈置为 0,表明不能走,避免每次的比较} var x,y,d:array[1..64] of integer; {x,y 分别用于记录走过的横、纵坐标;d 用于记录 某一步是否确定,作已走的标记} step:integer; {走过的步数} a:array[0..8,0..8] of boolean; {存放各点是否已经走过} tx,ty,td,nx,ny:integer; {tx,ty 为当前位置;nx,xy 为下一个位置,td 为方向增量} i,j:integer; procedure writeout; {输出过程} var i:integer; begin for i:=1 to step do begin write (x[i]:3,y[i]:3); writeln; end; end; begin for i:=0 to 8 do for j:=0 to 8 do a[i,j]:=true; {起始时,各点均未走过} step:=1;x[step]:=1;y[step]:=1;d[step]:=0; {初始化} repeat tx:=x[step]; ty:=y[step];td:=d[step]+1; {出发位置[1,1]} while td<=4 do {四个方向进行尝试} begin nx:=tx+dx[td]; ny:=ty+dy[td]; {改变方向,即坐标位置,确定下一点}

基础算法习题集(李波于 2007 年 7 月收集整理)

if (nx=7) and (ny=7) then begin writeout;halt;end; {到终点则结束} if (map[nx,ny]=1) and (a[nx,ny]) then{nx,ny 点未走且可以通行} begin step:=step+1;x[step]:=nx;y[step]:=ny;d[step]:=0; a[nx,ny]:=false;break; {记录该步骤,并标记为已经走过} end else td:=td+1; {td 增加,即为尝试另外一个方向} end; if td>4 then step:=step-1; {4 个方向均尝试过后,退回到上一步} until step=0; if step=0 then writeln(' NO answer!'); end.

EX3_5、跳马问题:
在 5*5 格的棋盘上,从(1,1)点出发,按日字跳马,要求不重复地跳经所有方格。求 出符合要求的所有跳马方案。输出前 5 个方案及总方案数。 输出格式示例: 1 16 21 10 25 20 11 24 15 22 17 2 19 6 9 12 7 4 23 14 3 18 13 8 5 [分析]本题是典型的回溯算法问题,设骑士在某一位置,设(x,y),按规则走,下一步可以 是如图所示的 8 个位置之一。 3 4 骑士 5 6 7 8 2 1

我们将重点考虑前进的方向: 如果某步可继续走下去, 就试探着走下去且考虑下一步的 走法,若走不通则返回,考虑另一个位置,其算法是: procedure 试探下一步 begin 选择准备 循环体开始 8 个位置中选择一个; if 选择可接受 then begin 记录移动情况; if 棋盘未遍历完 then begin 试探下一步; if 试探不成功 then 删去以前的记录(回溯)

基础算法习题集(李波于 2007 年 7 月收集整理)

end end 循环体结束 end; 马走的路径可以用二维数组表示:横向和纵向,其走的方向有 8 种可能,用数组表示某 点对应的 8 个方向坐标。 我们约定 =0 当棋格(I,j)未被占据 B[I,j] =k 当棋格(I,j)在第 k 次移动中被占据 用数组 b 记录移动的情况,当可以走通时则 b[i1,j1]:=I,若走不通需删除以前记录时 则 b[I,j]:=0。用 k 表示当前进行的方向,选下一个位置就是改变下标值:设当前下标为 (x,y)->(u1,v1)其关系是 u1=x-1,v1=y+2;(x,y)->(u2,v2)有关系是 u2=x-2,v2=y+1 等,用 坐标增量来表示移动情况。 [程序] program ex3_5; var a:array[1..5,1..5] of integer; {记每一步走在棋盘的哪一格} b:array[1..5,1..5] of boolean; {棋盘的每一格有没有被走过} u,v:array[1..8] of integer; {8 个方向上的 x,y 增量} i,j,num:integer; procedure print; {打印方案} var k,kk:integer; begin num:=num+1; {统计总方案} if num<=5 then {打印出前 5 种方案} begin for k:=1 to 5 do {打印本次方案} begin for kk:=1 to 5 do write(a[k,kk]:5); writeln; end; end; end; procedure try(i,j,n:integer); {以每一格为阶段,在每一阶段中试遍 8 个方向} var k,x,y:integer; {这三个变量一定要定义局部变量} begin if n>25 then begin print; exit;end ; {达到最大规模打印、统计方案} for k:=1 to 8 do {试遍 8 个方向} begin x:=i+u[k]; y:=j+v[k] ; {走此方向,得到的新坐标}

基础算法习题集(李波于 2007 年 7 月收集整理)

if (x<=5) and (x>=1) and (y<=5) and (y>=1)and b[x,y] then {如果新坐标在棋盘上,并且这一格可以走} begin b[x,y]:=false; a[x,y]:=n; try(x,y,n+1); {从(x,y)去搜下一步该如何走} b[x,y]:=true; a[x,y]:=0; end; end; end; begin u[1]:=1; v[1]:=-2;{8 个方向的 x,y 增量,可以定义数组常量存放} u[2]:=2; v[2]:=-1; u[3]:=2; v[3]:=1; u[4]:=1; v[4]:=2; u[5]:=-1; v[5]:=2; u[6]:=-2; v[6]:=1; u[7]:=-2; v[7]:=-1; u[8]:=-1; v[8]:=-2; for i:=1 to 5 do {初始化} for j:=1 to 5 do begin a[i,j]:=0; b[i,j]:=true; end; a[1,1]:=1; b[1,1]:=false; {从(1,1)第一步开始走} try(1,1,2); {从(1,1)开始搜第 2 步该怎样走} writeln(num); {输出总方案(304)} end.

EX3_6、数的划分:
整数 n 分成 k 份,且每份不能为空,任意两份不能相同(不考虑顺序)。 例如:n=7,k=3,下面三种分法被认为是相同的。 1,1,5; 1,5,1; 5,1,1; 问有多少种不同的分法。 输入:n,k (6<n<=200,2<=k<=6) 输出:一个整数,即不同的分法。 样例 输入: 7 3 输出:4 {四种分法为:1,1,5; 1,2,4; 1,3,3; 2,2,3;} [分析]此题可以用回溯法求解,设自然数 n 拆分为 a1,a2,…,ak,必须满足以下两个条件: (1)n=a1+a2+…+ak ; (2)a1<=a2<=…<=ak (避免重复计算); 现假设己求得的拆分数为 a1,a2,…ai,且都满足以上两个条件,设 sum=n-a1-a2-…-ai,我们

基础算法习题集(李波于 2007 年 7 月收集整理)

根据不同的情形进行处理: (1)如果 i=k,则得到一个解,则计数器 t 加 1,并回溯到上一步,改变 ai-1 的值; (2)如果 i<k 且 sum>=ai,则添加下一个元素 ai+1; (3)如果 i<k 且 sum<ai,则说明达不到目标,回溯到上一步,改变 ai-1 的值; 算法实现步骤如下: 第一步:输入自然数 n,k 并初始化;t:=0; i:=1;a[i]:=1; sum:=n-1; nk:=n div k; 第二步:如果 a[1]<=nk 重复: 若 i=k,搜索到一个解,计数器 t=t+1;并回溯; 否则:① 若 sum>=a[i]则继续搜索; ② 若 sum<a[i]则回溯; 搜索时,inc(i);a[i]:=a[i-1];sum:=sum-a[i]; 回溯时,dec(i); inc(a[i]); sum:=sum+a[i+1]-1; 第三步:输出。 [程序] Program ex3_6; var n,nk,sum,i,k:integer; t:longint; a:array[1..6]of integer; begin readln(n,k); nk:=n div k; t:=0; i:=1;a[i]:=1; sum:=n-1;{初始化} repeat if i=k then{判断是否搜索到底} begin inc(t); dec(i);inc(a[i]); sum:=sum+a[i+1]-1; end {回溯} else begin if sum>=a[i] then {判断是否回溯} begin inc(i);a[i]:=a[i-1];sum:=sum-a[i];end{继续搜} else begin dec(i); inc(a[i]); sum:=sum+a[i+1]-1; end;{回溯} end; until a[1]>nk; writeln(t); end.

EX3_7、组合的输出:
排列与组合是常用的数学方法,其中组合就是从 n 个元素中抽出 r 个元素(不分顺序且 r<=n) ,我们可以简单地将 n 个元素理解为自然数 1,2,??,n,中任取 m 个数。 现要求你不用递归的方法输出所有组合。例如 n=5,m=3,所有组合为: 123 124 125 134 135 145 234 235 245 345 输入:一行两个自然数 n,r(1<n<21,1<=r<=n) 输出:所有的组合,每一个组合占一行且其中的元素按由小到大的顺序排序,每个元素 占三个字符的位置,所有的组合也按字典顺序。 样例: comppages.in 53

基础算法习题集(李波于 2007 年 7 月收集整理)

compages.out 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 方法一:因为组合数跟顺序的选择无关。因此对同一个组合的不同排列,只需取其最小的一 个(即按从小到大排序) 。从上面的组合序列可以看出,从最小的组合 123 开始首先改变地 三位,直到第三位等于 5;此时让第二位加 1,第二位以后的各位在第二位的基础上依次加 1,重新形成一个组合。依次类推,直到所有的位都满足条件 C[k]=n-k+1(其中 C[k]是第 k 位的数值,k 为当前位置,n 为总位数)时便完成了任务。 因此,可以设计如下算法: 1.最后一位数最大可达 N,倒数第二位数最大可达 N-1,?,依此类推,倒数第 K 位数最大 可达 N-K+1。 若 m 个元素组合用 C1C2 ?Cm 表示,且假定 C1<C2< ?<Cm, Ci<=N-m+i, i=1,2,?,m。 2.当存在 Cj<N-R+J 时,其中下标的最大者设为 I,即 I=max{J | Cj<N-R+J},则作 Ci := Ci +1,与之对应的操作有 Ci+1 := Ci +1 ,Ci+2 := Ci +1+1 ,?. ,Cm := Cm-1 +1 [程序] program ex3_7_1; const maxn=10; var i,j,n,m,count :integer; c :array[1..maxn]of integer; {c 数组记录当前组合} Begin Write('n & m:'); readln(n,m); for i:=1 to m do begin {初始化,建立第一个组合} c[i]:=i; write(c[i]); end; count:=1; writeln; while true do begin j:=m; while (c[j]=n-m+j) and ( j>0) do dec(j); {求 I=max(J | Cj<N-R+J)} if j=0 then break; c[j]:=c[j]+1; for i:=j+1 to m do c[i]:=c[i-1]+1; {建立下一个组合} for i:=1 to m do write(c[i]);writeln; {输出} inc(count);

基础算法习题集(李波于 2007 年 7 月收集整理)

end; writeln('count:',count); End. 方法二:使用回溯法求解时,如果不用递归,则关键是如何确定回溯条件。如果选取第 i 个元素时选择了 a[i],根据输出条件应该有 a[i]-i<=n-r,如果不满足这个条件则说明当前第 i 个元素已经再无数可取,需要回溯,将其值减 1,退回到上一步并将上一步原来的值再增 加 1,重复上述过程。当全部取完时,i 回到 0,a[0]的值增加 1 后变成 1,此时整个过程结 束。 [程序] program ex3_7_2; {compages} const maxn=20; var i,j,n,r:integer; a:array [0..maxn] of integer; begin readln(n,r); for i:=0 to r do a[i]:=i; {初始化状态} i:=0; while a[0]=0 do begin if a[i]-i<=n-r then {如果还可以选取数字} if i=r then {如果已经选够了 r 个数字} begin for j:=1 to r do write(a[j]:3); {输出一个组合} writeln; a[i]:=a[i]+1 {最后一个数字值增加 1} end else begin {没有选够 r 个数字,下一个数字从当前数字的下一个开始} i:=i+1; a[i]:=a[i-1]+1 end else if i>0 then {如果后面无数字可选但还可以回溯} begin i:=i-1; {后退一步} a[i]:=a[i]+1 end end; end.

EX3_8、售货员的难题:
某乡有 n 个村庄(1<n<40),有一个售货员,他要到各个村庄去售货,各村庄之间的路程 s(0<s<1000)是已知的,且 A 村到 B 村与 B 村到 A 村的路大多不同。为了提高效率,他从商 店出发到每个村庄一次,然后返回商店所在的村,假设商店所在的村庄为 1,他不知道选择 什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。 输入:村庄数 n 和各村之间的路程(均是整数) 输出:最短的路程。

基础算法习题集(李波于 2007 年 7 月收集整理)

样例: salesman.in 3 {村庄数} 021 {村庄 1 到各村的路程} 102 {村庄 2 到各村的路程} 210 {村庄 2 到各村的路程} salesman.out 3 [分析]题目给定的村庄数目不多(最多 40 个) ,因此可以使用回溯法解决。从第一个村庄出 发找出所有经过其他所有村庄的回路,计算最短的路程。 用一个过程 procedure road(step,line:byte)来描述走的情况,其中 step 表示当前已 到村庄数、line 表示当前所在的村庄、如果 step=n,则只能回到起点,直接看第 line 个村 庄到第一个村庄的路程加上已经走过的总路程, 如果比原先求得的最小值还小则替换 (如果 需要,同时也可以保存路径) 。如果 step<n,那么就将还没有到过的村庄一个一个地试,也 就是调用下一步 road(step+1,新到的村庄号)。 [程序] program ex3_8; var a:array[1..40,1..40] of byte; {存放村庄间的路程} n,i,j:byte; min ,m :longint; {min 存放最小路程,m 存放当前所走路程} bj:array[1..40] of boolean; {标志某个村庄是否到过} input,output:text; procedure init; begin assign(input,'salesman.in'); reset(input); readln(input,n); for i:=1 to n do for j:=1 to n do read(input,a[i,j]); close(input); fillchar(bj,sizeof(bj),true); min:=99999999; {定义初始最小值} m:=0; end; procedure road(step,line:byte); var i,j,k:byte; begin if step=n then {已经走过所有村庄} if m+a[line,1]<min then min:=m+a[line,1] else {判断当前路程是否为最小值} else for i:=2 to n do {将除第一个村庄外的所有村庄都试探一遍} if (i<>line) and bj[i] then {如果第 i 个村庄不是当前所处村庄并且没有到过} begin m:=m+a[line,i]; {到第 i 个村庄,所走路程增加} bj[line]:=false; {置第 line 个村庄到过的消息} if m <min then road(step+1,i); {递归调用下一步}

基础算法习题集(李波于 2007 年 7 月收集整理)

m:=m-a[line,i]; end;

bj[line]:=true; {回溯,准备试探下一步}

end; procedure print; begin assign(output,'salesman.out'); rewrite(output); writeln(output,min); close(output); end; begin init; road(1,1); print end.

第四章 贪心法
贪心法(greedy method)就是只顾眼前利益,每次都选最好的。贪心法的基本思路:
从问题的某一个初始解出发逐步逼近给定的目标, 以尽可能快地求得更好的解。 当达到 算法中的某一步不能再继续前进时,算法停止。 在求最优解问题的过程中,依据某种贪心标准,从问题的初始状态出发,直接去求每一 步的最优解,通过若干次的贪心选择,最终得出整个问题的最优解,这种求解方法就是贪心 算法。 从贪心算法的定义可以看出, 贪心法并不是从整体上考虑问题, 它所做出的选择只是在 某种意义上的局部最优解,而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 该算法存在问题: 1. 不能保证求得的最后解是最佳的;

基础算法习题集(李波于 2007 年 7 月收集整理)

2. 不能用来求最大或最小解问题; 3. 只能求满足某些约束条件的可行解的范围。 实现该算法的过程: 从问题的某一初始解出发; while 能朝给定总目标前进一步 do 求出可行解的一个解元素; 由所有解元素组合成问题的一个可行解;

Ex4_1、均分纸牌(NOIP2002tg) :
有 N 堆纸牌,编号分别为 1,2,?, N。每堆上有若干张,但纸牌总数必为 N 的倍数。 可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编号为 1 堆上取的纸牌,只能 移到编号为 2 的堆上;在编号为 N 的堆上取的纸牌,只能移到编号为 N-1 的堆上;其他 堆上取的纸牌,可以移到相邻左边或右边的堆上。现在要求找出一种移动方法,用最少的移 动次数使每堆上纸牌数都一样多。例如 N=4,4 堆纸牌数分别为: 9 8 9 14 移动 3 次可达到目的: 从 4 取 4 张牌放到 3 (9 8 13 10) -> 从 3 取 3 张牌放到 2(9 11 10 10)-> 从 2 取 1 张牌放到 1(10 10 10 10) 。 [输 入]:键盘输入文件名。 文件格式:N(N 堆纸牌,1 <= N <= 100) A1 A2 ? An (N 堆纸牌,每堆纸牌初始数,l<= Ai <=10000) [输 出]:输出至屏幕。格式为:所有堆均达到相等时的最少移动次数。 [输入输出样例] a.in: 4 9 8 17 6 屏慕显示:3 [分析]设 a[i]为第 i 堆纸牌的张数(0<=i<=n) ,v 为均分后每堆纸牌的张数,s 为最小移到 次数。我们用贪心法,按照从左到右的顺序移动纸牌。如第 i 堆(0<i<n)的纸牌数 a[i]不等 于平均值,则移动一次(即 s 加 1),分两种情况移动: (1)若 a[i]>v,则将 a[i]-v 张纸牌从第 I 堆移动到第 I+1 堆; (2)若 a[i]<v,则将 v -a[i]张纸牌从第 I+1 堆移动到第 I 堆; 为了设计的方便,我们把这两种情况统一看作是将 a[I]-v 张牌从第 I 堆移动到第 I+1 堆;移动后有:a[I]:=v;a[I+1]:=a[I+1]+a[I]-v; 在从第 i+1 堆中取出纸牌补充第 i 堆的过程中,可能会出现第 i+1 堆的纸牌数小于零 (a[i+1]+a[i]-v<0 )的情况。 如 n=3,三堆纸牌数为(1,2,27)这时 v=10,为了使第一堆数为 10,要从第二堆移 9 张纸牌到第一堆, 而第二堆只有 2 张纸牌可移, 这是不是意味着刚才使用的贪心法是错误的 呢? 我们继续按规则分析移牌过程,从第二堆移出 9 张到第一堆后,第一堆有 10 张纸牌, 第二堆剩下-7 张纸牌,再从第三堆移动 17 张到第二堆,刚好三堆纸牌数都是 10,最后结果 是对的,从第二堆移出的牌都可以从第三堆得到。我们在移动过程中,只是改变了移动的顺 序,而移动的次数不变,因此此题使用贪心法是可行的。 [程序] Program ex4_1;

基础算法习题集(李波于 2007 年 7 月收集整理)

var i,n,s:integer;v:longint; a:array[1..100]of longint; f:text;fil:string; begin readln(fil); assign(f,fil);reset(f); readln(f,n);v:=0; for i:=1 to n do begin read(f,a[i]); inc(v,a[i]); end; v:=v div n; {每堆牌的平均数} for i:=1 to n-1 do if a[i]<>v then {贪心选择} begin inc(s);{移牌步数计数} a[i+1]:=a[i+1]+a[i]-v;{使第 i 堆牌数为 v} end;{then} writeln(s); end. 利用贪心算法解题,需要解决两个问题: 一是问题是否适合用贪心法求解。 比如整钞找零的问题,如果一个货币系统有 3 种币值, 面值分别为一角、五分和一分,求最小找币数时,可以用贪心法求解;如果将这三种币值改 为一角一分、五分和一分,就不能使用贪心法求解。用贪心法解题很方便,但它的适用范围 很小, 判断一个问题是否适合用贪心法求解, 目前还没有一个通用的方法, 在信息学竞赛中, 需要凭个人的经验来判断何时该使用贪心算法。 二是确定了可以用贪心算法之后, 如何选择一个贪心标准, 才能保证得到问题的最优解。 在选择贪心标准时, 我们要对所选的贪心标准进行验证才能使用, 不要被表面上看似正确的 贪心标准所迷惑。

EX4_2、最大整数:
设有 n 个正整数,将他们连接成一排,组成一个最大的多位整数。例如:n=3 时,3 个整 数 13,312,343,连成的最大整数为:34331213 又如:n=4 时,4 个整数 7,13,4,246 连接成的最大整数为 7424613 输入:N N 个数 输出:连接成的多位数 [分析]此题很容易想到使用贪心法, 有很多同学把整数按从大到小的顺序连接起来, 测试题 目的例子也都符合,但最后测试的结果却不全对。按这种贪心标准,我们很容易找到反例: 12, 121 应该组成 12121 而非 12112,那么是不是相互包含的时候就从小到大呢?也不一定, 如: 12, 123 就是 12312 而非 12112,这样情况就有很多种了。 是不是此题不能用贪心法呢? 其实此题是可以用贪心法来求解,只是刚才的贪心标准不对,正确的贪心标准是:先把 整数化成字符串,然后再比较 a+b 和 b+a,如果 a+b>b+a,就把 a 排在 b 的前面,反之则把 a 排在 b 的后面。 [程序]

基础算法习题集(李波于 2007 年 7 月收集整理)

Program ex4_2; var s:array[1..20] of string; t:string;i,j,k,n:longint; begin readln(n); for i:=1 to n do begin read(k); str(k,s[i]); end; for i:=1 to n-1 do for j:=i+1 to n do {用两重循环比较大小并作排序} if s[i]+s[j]<s[j]+s[i] then begin{交换} t:=s[i]; s[i]:=s[j]; s[j]:=t; end; for i:=1 to n do write(s[i]); end. 贪心算法所作的选择可以依赖于以往所作过的选择, 但决不依赖于将来的选择, 也不依 赖于子问题的解, 因此贪心算法与其它算法相比具有一定的速度优势。 如果一个问题可以同 时用几种方法解决,贪心算法应该是最好的选择之一。

EX4_3、背包问题:
有一个背包,背包容量是 M=150。有 7 个物品,物品可以分割成任意大小。要求尽可能 让装入背包中的物品总价值最大,但不能超过总容量。 物品 重量 价值 A 35 10 B 30 40 C 60 30 D 50 50 E 40 35 F 10 40 G 25 30

[分析] 目标函数: ∑pi 最大 约束条件是装入的物品总重量不超过背包容量:∑wi<=M( M=150) 接下来我们需要解决的问题就是根据贪心的原则选择贪心策略, 有以下几种策略可供我 们选择: (1)每次挑选价值最大的物品装入背包,得到的结果是否最优? (2)每次挑选所占空间最小的物品装入是否能得到最优解? (3)每次选取单位容量价值最大的物品,成为解本题的策略。 ? 通过简单的比较衡量,我们会毫不犹豫地选择第三种贪心策略。 Program ex4_3; const m=150; n=7;

基础算法习题集(李波于 2007 年 7 月收集整理)

var xu:integer; i,j:integer; goods:array[1..n,0..2] of integer; {存放物品的重量和价值} ok:array[1..n,1..2] of real; {标志某物品是否被装入} procedure init; {初始化,读入数据} var i:integer; begin xu:=m; for i:=1 to n do begin write('Enter the price and weight of the ',i,'th goods:'); goods[i,0]:=i; read(goods[i,1],goods[i,2]); readln; ok[i,1]:=0; ok[i,2]:=0; end; end; procedure make; {物品初始处理} var bi:array[1..n] of real; i,j:integer; temp1,temp2,temp0:integer; begin for i:=1 to n do bi[i]:=goods[i,1]/goods[i,2]; {计算物品的单位容量价值} for i:=1 to n-1 do for j:=i+1 to n do {对物品按照单位容量价值进行排序}

begin if bi[i]<bi[j] then begin temp0:=goods[i,0]; temp1:=goods[i,1]; temp2:=goods[i,2]; goods[i,0]:=goods[j,0]; goods[i,1]:=goods[j,1]; goods[i,2]:=goods[j,2]; goods[j,0]:=temp0; goods[j,1]:=temp1; goods[j,2]:=temp2; end; end; end; begin init; make; for i:=1 to 7 do

基础算法习题集(李波于 2007 年 7 月收集整理)

begin if goods[i,2]>xu then break; ok[i,1]:=goods[i,0]; ok[i,2]:=1; {物品 i 被装入标记} xu:=xu-goods[i,2]; {计算剩余空间} end; j:=i; if i<=n then {还有物品未被装入} begin ok[i,1]:=goods[i,0]; ok[i,2]:=xu/goods[i,2]; {装入剩余物品中价值最大的物品的一部分} end; for i:=1 to j do writeln(ok[i,1]:1:0,':',ok[i,2]*goods[i,2]:2:1); {输出} end.

EX4_4、排队接水:
有 n 个人在一个水龙头前排队接水,假如每个人接水的时间为 Ti,请编程找出这 n 个 人排队的一种顺序,使得这 n 个人的平均等待时间最小。 输入:输入文件共两行,第一行为 n,第二行分别表示第 1 个人到第 n 个人每人的接水 时间 T1,T2,?? Tn 每个数据之间有 1 个空格。 输出:输出文件有两行,第一行为一种排队顺序,即 1 到 n 的一种排列;第二行为这种 排列方案下的平均等待时间(输出结果精确到小数后两位). 样例: water.in 10 56 12 1 99 1000 234 33 55 99 812 water.out 1 2 7 8 1 4 9 6 10 5 291.90 [分析]首先需要理解平均等待时间的概念。 平均等待时间就是每个人的等待时间之和再除以 n,因为 n 是个常数,所有等待时间之和最小也就等同于平均等待时间最小。假设取水的人 是按照 1??n 的顺序排列的,那么问题就转化为求以下公式的最小值: Total=T1+(T1+T2)+(T1+T2+T3)+?+(T1+T2+?+Tn) ,对公式换个写法如下: Total=nT1+(n-1)T2+(n-3)T3+??+2Tn-1+Tn,现在你是否发现了一点什么呢?如果让 T1 最小、T2 次之??Tn 最大,也就是把接水时间少的人尽可能排在前面,总的等待时间就最 少了。 问题的本质就转变为把 n 个等待时间按照非递减顺序进行排序, 输出这种排序并求出 这种排列下的平均等待时间了。 [程序] program ex4_4; var i,j,k,p,s:longint; a:array[1..200,1..2] of longint; begin assign(input,'water.in'); assign(output,'water.out'); reset(input); rewrite(output);

基础算法习题集(李波于 2007 年 7 月收集整理)

readln(k); for i:=1 to k do begin read(a[i,1]);a[i,2]:=i;end; for i:=1 to k-1 do for j:=i+1 to k do if a[i,1]>a[j,1] then begin a[i,1]:=a[i,1]+a[j,1];a[j,1]:=a[i,1]-a[j,1];a[i,1]:=a[i,1]-a[j,1]; {排序} p:=a[i,2];a[i,2]:=a[j,2];a[j,2]:=p;end; for i:=1 to k do if i<k then write(a[i,2],' ') else writeln(a[i,2]); p:=0; s:=a[1,1]; for i:=2 to k do begin p:=p+s;s:=s+a[i,1];end; {求等待总时间} writeln(p/k:0:2); close(input); close(output) end.

EX4_5、智力大冲浪:
小伟报名参加中央电视台的智力大冲浪节目。 本次挑战赛吸引了众多参赛者, 主持人为 了表彰大家的勇气,先奖励每个参赛者 m 元。先不要太高兴!因为这些钱还不一定都是你 的?接下来主持人宣布了比赛规则: 首先,比赛时间分为 n 个时间段(n<=500) ,它又给出了很多小游戏,每个小游戏都必 须在规定期限 ti 前完成(1<=ti<=n) 。如果一个游戏没能在规定前完成,则要从奖励 m 元中 扣去一部分钱 wi, wi 为自然数,不同的游戏扣去的钱是不一样的。当然,每个游戏本身 都很简单, 保证每个参赛者都能在一些个时间段内完成而且都必须从整时段开始。 主持人只 是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者,小伟很想赢得冠军,当 然更想赢取最多的钱!注意:比赛绝对不会让参赛者赔钱。 输入:输入文件 riddle.in,共 4 行 第一行为 m,表示一开始奖励给每位参赛者的钱; 第二行为 n,表示有 n 个小游戏 第三行有 n 个数,分别表示游戏 1 到 n 的规定完成期限; 第四行有 n 个数,分别表示游戏 1 到 n 不能在规定期限前完成的扣款数。 输出:输出文件 riddle.out,仅 1 行。表示小伟能赢取更多的钱。 样例:riddle.in 10000 7 1 2 4 3 1 4 6 70 60 50 40 30 20 10 riddle.out 9950 [分析]同背包问题。 因为不同的小游戏不能准时完成时具有不同的扣款权数, 而且本题又是 一个最优解问题, 因此很容易就想到了贪心法。 利用不同的贪心策略, 也有不同的处理方式。 方法一: 贪心的主要思想是要让扣款数大的尽量准时完成。 因此我们就想到了先把这些任务

基础算法习题集(李波于 2007 年 7 月收集整理)

按照扣款的数目进行排序,把大的排在前面,先进行放置。假如扣款最多的一个任务的完成 期限是 k,那我们应该把它安排在哪个时段完成呢?最好放在第 k 时段,因为放在 1 到 k 时 段的任何位置效果都是一样的。 一旦出现一个不可能在规定时段前完成的任务, 则把其放到 最后一个时段(即放弃,因为反正已经不能完成,放前面会耽误其余任务的完成) 。 [程序] Program ex4_5_1; var i,j,k,n,s,m:longint; boo:boolean; a,b:array[1..100] of longint; {存放期限和扣款数} hash:array[1..100] of boolean; {某位置是否被占} procedure sort; var p,q:longint; begin for i:=1 to n-1 do for j:=i+1 to n do if b[i]<b[j] then {按照扣款数目排序,大的在前} begin p:=b[i];b[i]:=b[j];b[j]:=p; p:=a[i];a[i]:=a[j];a[j]:=p;end; end; begin fillchar(hash,sizeof(hash),true); assign(input,'riddle.in'); reset(input); assign(output,'riddle.out'); rewrite(output); readln(m); readln(n); for i:=1 to n do read(a[i]); {输入} for i:=1 to n do read(b[i]); sort; for i:=1 to n do begin boo:=true; for j:=a[i] downto 1 do if hash[j] then begin boo:=false;hash[j]:=false;break;end; if boo then begin for k:=n downto 1 do if hash[k] then begin hash[k]:=false;break;end; inc(s,b[i]); end; end; writeln(m-s); close(input); close(output);

基础算法习题集(李波于 2007 年 7 月收集整理)

end. 方法二:本题可以采用另外一种贪心策略,即先把所有数据按照结束时间的先后排序,然后 从前向后寻找。当找到第 n 个时段,发现里面分配的任务的结束时间等于 n-1,则说明此任 务之前的任务中必须放弃一个,于是回头寻找 1?n 的这 n 个时段,挑出一个扣款数目最小 的去掉,然后调整(移动)排列顺序,即后面数据填补前面去掉的空格。 [程序] program ex4_5_2; var m,n,p,min,minx,total:longint; w,t:array[1..100] of longint; i,j:longint; begin assign(input,'riddle.in'); assign(output,'riddle.out'); reset(input); rewrite(output); readln(m); readln(n); for i:=1 to n do read(t[i]); for i:=1 to n do read(w[i]); for i:=1 to n-1 do for j:=i+1 to n do {按结束时间排序} if (t[i]>t[j]) or (t[i]=t[j]) and (w[i]>w[j]) then begin p:=t[i]; t[i]:=t[j]; t[j]:=p; p:=w[i]; w[i]:=w[j]; w[j]:=p; end; for i:=1 to n do if (t[i]<i) and (i<=n) then {排在 i 位置的任务需要在 i 时段前完成} begin min:=maxlongint; for j:=1 to i do {在 i 时段前寻找一个扣款数最少的任务} if w[j]<min then begin min:=w[j]; minx:=j; end; total:=total+min; {扣掉不能完成的那项任务} for j:=minx to n-1 do {移动后面的项,填补去掉任务的空格} begin w[j]:=w[j+1]; t[j]:=t[j+1]; end; dec(n); dec(i);

基础算法习题集(李波于 2007 年 7 月收集整理)

end; writeln(m-total); close(input); close(output); end.

EX4_6、取火柴游戏:
输入 k 及 k 个整数 n1,n2,n3….nk ,表示有 k 堆火柴棒,第 I 堆火柴棒的根数为 ni, 接着便是你和计算机取火柴棒的对弈游戏。 取的规则如下: 每次可以从一堆中取走若干根火 柴, 也可以一堆全部取走, 但不允许跨堆取, 也不允许不取。 谁取走最后一根火柴为胜利者。 例如:k=2,n1=n2=2,A 代表你,P 代表计算机,若 决定 A 先取; A: (2,2) (1,2) {从一堆中取一根} P: (1,2) (1,1) {从另一堆中取一根} A: (1,1) (1,0) {P 胜利} P: (1,0) (0,0) 如果决定 A 后取: P: (2,2) (2,0) {A 胜利} A: (2,0) (0,0) 又如 k=3,n1=1,n2=2,n3=3,A 决定后取; P: (1,2,3) (0,2,3) A: (0,2,3) (0,2,2) A 已将游戏归结为(2,2)的情况,不管 P 如何取 A 都必胜。 编一个程序,在给出初始状态之后,判断是先取必胜还是先取必败,如果是先取必胜, 请输出第一次该如何取。如果是先取必败,则输出必“lose” 样例:match.in 3 3 6 9 match.out 4 3 3 6 5 [分析]从问题的描述分析, 可以将问题中的 k 堆火柴抽象为 k 个非负数, 而每取一次火柴棒 可以看成是让其中某个自然数变小,当所有的数都变成 0 时,游戏结束,最后一次取火柴棒 的人胜利。 如果数据量小或者不考虑时间因素, 可以使用递推的方式来处理。 即从终了状态 (全 0) 倒推出初始状态的值是先取必胜还是必败, 因为某一状态的值可以从他所有的取一次后的下 一状态得到,如果某一状态的下一状态都是先取必败,则这一状态为先取必胜,反之亦然。 当数据量较大时,上述方法很难实现。为解决本问题,首先引入关于 n 个非负整数的奇 偶状态的定义:如果把 n 个非负整数转化为二进制数,然后对 n 个二进制数按位相加(对应 位相加,不进位) ,若每一位相加的和都是偶数,则称这 n 个非负整数的状态为偶状态,否 则为奇状态。 任何 n 个数在偶状态时,可以让其中某个数变小,从而使这 n 个数变为奇状态,反之亦 然。比如:n=3 时,有 3 堆火柴数量分别是 3,6,9,则分别转化为二进制后对应为:0011, 0110,1001,最高位和为 1,其中 9 对应的二进制数的最高位为 1,将其变更为 0;次高位 之和也是 1,9 对应的二进制数次高位是 0,将其变为 1;后两位数字之和都是偶数,无需改 变。这样数字 9(1001)就被变成了 5(0101) ,改变之后的 3(0011) ,6(0110) ,5(0101)

基础算法习题集(李波于 2007 年 7 月收集整理)

就是一个偶状态。 通过这样一个奇偶状态的认识,我们可以得出一种贪心策略:程序中用 n 个包含 16 个 元素的数组来存放每个非负整数对应的二进制数, 如 b[I,0]存放第 i 个数的最低位, n 个数 的状态取决于他们对应的二进制数的各位数字之和的奇偶性,而各个数字的奇偶性只需用 0 或 1 来表示,0 表示奇,1 表示偶。最后的状态(全 0)为偶状态,所有开始时状态为偶状 态则先取必败(先取后局面变成了奇状态,后取一方一定可以将其取为偶状态,直到取光为 止) ,反之则先取必胜。 [程序] program ex4_6; const maxn=100; var i,j,k,n,s:integer; heap:array[1..maxn] of integer;{存放每堆火柴数} b:array[1..maxn,0..15] of integer; {存放每堆火柴数对应的二进制数} sum,temp:array[0..15] of integer; {sum 存放按位加之和;temp 存放被改变数} begin assign(input,'match.in'); assign(output,'match.out'); reset(input); rewrite(output); readln(n); for i:=1 to n do read(heap[i]);{输入火柴堆数及每堆火柴数} for i:=0 to 15 do sum[i]:=0; for i:=1 to n do for j:=0 to 15 do b[i,j]:=0; for i:=1 to n do {将每堆火柴数对应的数字转化为二进制数} begin k:=heap[i];j:=0; while k<>0 do begin b[i,j]:=k mod 2; k:=k div 2; j:=j+1 end; end; for i:=1 to n do for j:=0 to 15 do sum[j]:=sum[j]+b[i,j]; {按位求和} for j:=0 to 15 do sum[j]:=sum[j] mod 2; {各位之后除 2,为判断奇偶状态准备} s:=0; for j:=0 to 15 do s:=s+sum[j]; {求各位和之和,因各位和已经除 2,所有此处和若 为 0,则表示为偶状态,否则为奇状态} if s=0 then writeln('lose') {偶状态,先取必败} else begin {奇状态,取第一步} j:=15; while sum[j]=0 do j:=j-1; {从高位开始找第一个奇状态位,记为 j} i:=1; while b[i,j]=0 do inc(i);{从第一个数起找二进制数第 j 位为 1 的数,记为 i} for j:=0 to 15 do temp[j]:=(b[i,j]+sum[j]) mod 2; {改变第 i 个数的值} k:=0;

基础算法习题集(李波于 2007 年 7 月收集整理)

for j:=15 downto 0 do k:=k*2+temp[j]; {计算第 i 个数改变后的值} k:=heap[i]-k;heap[i]:=heap[i]-k; write(k,' '); writeln(i); for i:=1 to n do write(heap[i],' '); writeln end; close(input); close(output) end.

第五章 树
树是一种非线性的数据结构, 用它能很好地描述有分支和层次特性的数据集合。 树型结 构在现实世界中广泛存在, 如社会组织机构的组织关系图就可以用树型结构来表示。 树在计 算机领域中也有广泛应用, 如在编译系统中, 用树表示源程序的语法结构。 在数据库系统中, 树型结构是数据库层次模型的基础,也是各种索引和目录的主要组织形式。在许多算法中, 常用树型结构描述问题的求解过程、所有解的状态和求解的对策等。在这些年的国内、国际 信息学奥赛、大学生程序设计比赛等竞赛中,树型结构成为参赛者必备的知识之一,尤其是 建立在树型结构基础之上的搜索算法。 在树型结构中,二叉树是最常用的结构,它的分支个数确定、又可以为空、并有良好的

基础算法习题集(李波于 2007 年 7 月收集整理)

递归特性,特别适宜于程序设计,因此也常常将一般树转换成二叉树进行处理。

EX5_1、排序二叉树与堆排:
输入一组不同的整数(约定大于等于 0,输入负数表示结束),排序后按从小到大输出。 [分析]实际上就是要对 n 个数进行排序。 既然要用到二叉树, 问题也就变成了典型的排序二 叉树了。 方法一:直接使用二叉树建立的方式,即利用二叉树插入 排序。先生成一个结点,再根据大小决定这个结点是插在 左子树上还是右子树上,如此重复直到输入一个负数。 [程序] Program ex5_1_1; type tree=^node; node=record data:integer; lchild,rchild:tree; end; var bt:tree; n:integer; procedure creat_order_tree(var btx:tree;nx:integer);{插入一个数到一棵排序二叉 树中去} var p,s,f:tree; flag:boolean; {用来标识要插入的数是否在树中出现过,防止同一个数重复出现在树中} begin new(s); s^.data:=nx; s^.lchild:=nil; s^.rchild:=nil; {以上 4 个语句为新建一个结点 s} flag:=true; {假设没出现过} p:=btx; {P 指向根结点} while (p<>nil)and flag do {为结点 S 找插入位置、同时判断是否出现过} begin f:=p; if s^.data=p^.data then flag:=false; {出现过做标记} if s^.data<p^.data then p:=p^.lchild; {沿左子树方向找} if s^.data>p^.data then p:=p^.rchild; {沿由子树方向找} end; if flag then begin {没出现过、且 p=nil 说明已找到叶结点了,那么插入到叶结点 的左右孩子中} if btx=nil then btx:=s; {作为根结点} if s^.data<f^.data then f^.lchild:=s; {插入左孩子} if s^.data>f^.data then f^.rchild:=s; {右孩子} end; end; procedure inorder_print(btx:tree); {递归中序输出} begin

基础算法习题集(李波于 2007 年 7 月收集整理)

if btx<>nil then begin inorder_print(btx^.lchild); {从小到大输出,如果要求从大到小, write(btx^.data,' '); 只要先右再左就可以了 } inorder_print(btx^.rchild); end; end; begin {主程序} bt:=nil; { 根结点初始化,不指向任何结点} writeln('input data(if <0 then over!):'); repeat {不断输入正数,不断插入} read(n); if n>=0 then creat_order_tree(bt,n); until n<0; write('output sorted data:'); inorder_print(bt); writeln; readln; end. 注:procedure creat_order_tree 也可改成递归过程,如下: procedure insert(var btx:tree;nx:integer); begin new(s); s^.data:=nx; s^.lchild:=nil; s^.rchild:=nil; if btx=nil then btx:=s; {作为根结点} else if s^.data<btx^.data then insert(btx^.lchild,nx); {插到左子树} else if s^.data>btx^.data then insert(btx^.rchild,nx); {插到右子树} end; 方法二:堆排序。堆:设有数据元素的集合(R1,R2,R3,...Rn)它们是一棵顺序二叉树的结 点且有 Ri<=R2i 和 Ri<=R2i+1(或>=) 堆的性质: 堆的根结点上的元素是堆中的最小元素, 且堆的每一条路径上的元素都是有 序的。 堆排序的思想是: 1)建初始堆(将结点[n/2],[ n/2]-1,...3,2,1 分别调成堆) 2)当未排序完时 输出堆顶元素,删除堆顶元素,将剩余的元素重新建堆。 [程序] Program ex5_1_2; var buf:array[1..10000]of integer; num,i,j:byte; {num 为待排序总数} procedure arrange(l,r:byte);{将左右子树都为堆的数整理成新堆}

基础算法习题集(李波于 2007 年 7 月收集整理)

var i,j,w:byte; begin i:=buf[l]; while l*2<=r do {L 是否还有子树} begin j:=buf[l*2]; w:=l*2; if (l*2<r) and (buf[l*2+1]>buf[l*2]) then {L 是否还有右子树,其值是否大于左 子树} begin j:=buf[l*2+1]; inc(w); end; if i<j then begin buf[l]:=j; l:=w; end {交换 L 与其子树 W} else break; end; buf[l]:=i; {根结点定位} end; procedure readnum; begin i:=1;num:=0; read(buf[i]); while buf[i]>0 do begin inc(num); inc(i); read(buf[i]); end; begin readnum; for i:=num div 2 downto 2 do arrange(i,num); {先将根结点的左右子树整理为堆} for i:=1 to num do {整理 1 到 num-i+1 号记录为堆} begin arrange(1,num-i+1); j:=buf[1];buf[1]:=buf[num-i+1];buf[num-i+1]:=j; {交换根结点与最后的叶结点} end; for i:=1 to num do write(buf[i]:5); end.

EX5_2、构造二叉树:
给定二叉树的前序遍历和中序遍历,打印后序遍历。 [分析]根据二叉树的遍历规则,如果已知先序、中序,可以推出后序;已知后序、中序也可 以推出先序;已知先序、后序也可以推出中序,但不是唯一的。 分析可知,先序序列第一个元素为树的根,在中序序列中找到这个根元素,即可将中序 序列分成左子树和右子树两个序列。 依照此法, 利用递归方式可以非常容易地求出后序序列。 [程序]

基础算法习题集(李波于 2007 年 7 月收集整理)

program ex5_2; type node=^rec; rec=record data:char; lchild,rchild:node; end; var rootfirst,rootmiddle:string;{存放输入的先序和中序序列} tree:node; procedure wrong; {错误信息输出} begin writeln('rootfirst array and rootmiddle array are not from the same tree!'); halt; end; procedure maketree(rf,rm:string;var tree:node); {构造二叉树} begin if rf<>'' then begin if pos(rf[1],rm) =0 then wrong; {判错} new(tree); tree^.data:=rf[1]; {根结点} maketree(copy(rf,2,pos(rf[1],rm)-1),copy(rm,1,pos(rf[1],rm)-1),tree^.lchild); maketree(copy(rf,pos(rf[1],rm)+1,length(rf)-pos(rf[1],rm)),copy(rm,pos(rf[1],r m)+1,length(rm)-pos(rf[1],rm)),tree^.rchild); {递归构造,分别生成左右子树} end else tree:=nil; end; procedure printtree(tree:node); {后序输出} begin if tree<>nil then begin printtree(tree^.lchild); printtree(tree^.rchild); write(tree^.data); end; end; begin write('input rootfirst array:'); readln(rootfirst); write('input rootmiddle array:'); readln(rootmiddle); maketree(rootfirst,rootmiddle,tree); write('rootlast array='); printtree(tree);

基础算法习题集(李波于 2007 年 7 月收集整理)

end.

EX5_3、构造哈夫曼树:
哈夫曼树 (最优二叉树) 是指带权路径长度最小的二叉树。 构建哈夫曼树的基本思想是: 权越大离跟越近。 如何构造最优叶子二叉树?D?A?Huffman 给出了一个简单而又漂亮的算法, 这个算法称 为哈夫曼算法。它的基本思想是要让权大的叶子离根最近。具体作法是: (1) 根据给定的 n 个权值 {w1,w2,?,wn} , 构造 n 棵二叉树的集合 F= {T1,T2,?,Tn} , 其中每棵二叉树中均只含一个带权值为 wi 的根结点,其左、右子树为空树; (2)在 F 中选取其根结点的权值为最小的两棵二叉树,分别作为左、右子树构造一棵 新的二叉树,并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和; (3)从 F 中删去这两棵树,同时加入刚生成的新树; (4)重复(2)和(3)两步,直到 F 中只含一棵树为止。 从上述算法中可以看出,F 实际上是森林,该算法的思想是不断地进行森林 F 中的二叉 树的“合并”,最终得到哈夫曼树。 实际上,哈夫曼算法的实现与实际问题所采用的存储结构有关。 方法一:现假设用数组 F 来存储哈夫曼树,其中第 i 个数组元素 F[i]是哈夫曼树中的一个 结点,其地址为 i,有 3 个域,Data 域存放该结点的权值,lChild 域和 rChild 域分别存放 该结点左、右子树的根结点的地址(下标)。在初始状态下: F[i].Data=Wi, F[i].lChild=F[i].rChild=0,i=1,2,?,n。 即先构造了 n 个方形叶子。 在以后每步构造一棵新二叉树时, 都需要对森林中所有二叉 树的根结点进行排序,因此可用数组 a 作为排序暂存空间,其中第 i 个数组元素 a[i]是森 林 F 中第 i 棵二叉树的根结点,有 2 个域,Data 是根结点所对应的权值,Addr 是根结点在 F 中的地址(下标)。在初始状态下:a[i].Data=Wi,a[i].Addr=i,i=1,2,?n。 [程序] Program ex5_3_1; Const m=10; Type arr=array[1..m] of real; Var Hf,nnode:arr; PROCEDURE CreateHuffmanTree(F,t,a,n) {已知 n 个权值 a[i],构造哈夫曼树 F,且根结点地址(下标)为 t} VAR i:Integer; BEGIN FOR i:=1 TO n DO BEGIN {初始化} F[i].Data:=a[i].Data; F[i].lChild:=0; F[i].rChild:=0; a[i].Addr:=I END; t:=n+1; {t 指向下一个可利用单元} i:=n; {当前森林中的二叉树是 i} WHILE i>=2 DO BEGIN Insert(a,i); {对 a 的前 i 个元素按 Data 域进行排序} F[t].Data:=a[1].Data+a[2].Data; {生成新的二叉树}

基础算法习题集(李波于 2007 年 7 月收集整理)

F[t].lChild:=a[1].Addr; F[t].rChild:=a[2].Addr; a[1].Data:=F[t].Data; {修改森林} a[1].Addr:=t; a[2].Data:=a[i].Data; {修改森林} a[2].Addr:=a[i].Addr; i:=i-1; {二叉树数目减一} t:=t+1; END; END; Createhuffmantree(hf,1,nnode,m); End. 方法二:使用指针链表来建立二叉链表形式的哈夫曼树。 [程序] program ex5_3_2; const n=4;m=7; type node=record w:real; parent,lchild,rchild:0..m end; htree=array[1..m] of node; {定义哈夫曼树的链式存储结构} var htree1:htree; procedure gjtree(var ht:htree); {构造树} var i,j:integer; small1,small2:real; p1,p2:0..m; begin for i:=1 to m do with ht[i] do {初始化} begin w:=0;lchild:=0;rchild:=0;parent:=0; end; for i:=1 to n do read(ht[i].w); {读入各结点权值} for i:=n+1 to m do begin p1:=0;p2:=0; small1:=1000;small2:=1000; for j:=1 to i-1 do if ht[j].parent=0 then if ht[j].w<small1 then begin small2:=small1;small1:=ht[j].w;p2:=p1;p1:=j end else if ht[j].w<small2 then begin small2:=ht[j].w;p2:=j end;

基础算法习题集(李波于 2007 年 7 月收集整理)

{找到两个权值最小的结点,以此两个结点构建一棵新树} ht[p1].parent:=i; ht[p2].parent:=i; ht[i].lchild:=p1; ht[i].rchild:=p2; ht[i].w:=ht[p1].w+ht[p2].w;{以找到的两个权值最小结点构建新树} end; end; begin gjtree(htree1); {调用构造过程} end.

EX5_4、FBI 树:
我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为 B 串,全“1”串 称为 I 串,既含“0”又含“1”的串则称为 F 串。 FBI 树是一种二叉树[1],它的结点类型也包括 F 结点,B 结点和 I 结点三种。由一个长 度为 2N 的“01”串 S 可以构造出一棵 FBI 树 T,递归的构造方法如下: 1) T 的根结点为 R,其类型与串 S 的类型相同; 2)若串 S 的长度大于 1,将串 S 从中间分开,分为等长的左右子串 S1 和 S2;由左子串 S1 构造 R 的左子树 T1,由右子串 S2 构造 R 的右子树 T2。 现在给定一个长度为 2N 的“01”串,请用上述构造方法构造出一棵 FBI 树,并输出它 的后序遍历[2]序列。 【输入文件】 输入文件 fbi.in 的第一行是一个整数 N (0 <= N <= 10) , 第二行是一个长度为 2N 的 “01” 串。 【输出文件】 输出文件 fbi.out 包括一行,这一行只包含一个字符串,即 FBI 树的后序遍历序列。 【样例输入】 3 10001011 【样例输出】 IBFBBBFIBFIIIFF 【数据规模】对于全部的数据,N <= 10。 [分析]此题的后序遍历适合用递归算法完成。 由题目可知, 输入数据给出的字符为所要遍历 的 fbi 树的叶结点代码,又因为字符串的长度为 2 的整数次幂,故此 fbi 树为完全二叉树。 由于题中明确规定:子符串中的字符都是‘0’,为 B 串;都是‘1’,为 I 串;既有‘0’又有‘1’, 为 F 串。即:二叉树的子结点都是 B,父结点为 B;子结点都是 I,父结点为 I;既有 I 又有 B,父结点为 F。因此,根据树的子结点可以求出父结点。我们要做的是根据子结点后序遍 历二叉树。基本算法为: procedure bianli(x,y:integer) ;//遍历过程;x,y:为子结点在数组 a 中的位置。 begin if x=y then 输出叶结点 //结束递归条件,结点为一个字符。 else begin 求出父结点; 遍历左子树;

基础算法习题集(李波于 2007 年 7 月收集整理)

遍历右子树; 输出父结点; end; end; [程序] program ex5_4; var a:array[1..10000]of '0'..'1'; n,i,l:integer; f1,f2:text; treeb,treei:boolean; tree:char; procedure bianli(x,y:integer);{x,y 为所要遍历的树的叶结点在数组 a 中位置} begin if x=y then case a[x] of '0':write(f2,'B'); '1':write(f2,'I'); end {输出叶结点} else begin bianli(x,x+(y-x+1) div 2-1); {遍历左子树} bianli(x+(y-x+1)div 2,y); {遍历右子树} treei:=false;treeb:=false; for i:=x to y do if a[i]='0' then treeb:=true else treei:=true; {求出树的父结点} if treei and treeb then tree:='F' else begin if treei then tree:='I'; if treeb then tree:='B' {输出父结点} end; write(f2,tree); end end; begin assign(f1,'fbi.in'); reset(f1); {输入文件名"fbi,in"} assign(f2,'fbi.out');rewrite(f2); {输出文件名"fbi.out"} readln(f1,n);l:=1; for i:=1 to n do l:=l*2; for i:=1 to l do read(f1,a[i]); {读入数据,l 为字符串长度} bianli(1,l);writeln(f2); close(f1); close(f2) end.

EX5_5、合并果子:
在一个果园里, 多多已经将所有的果子打了下来, 而且按果子的不同种类分成了不同的 堆。多多决定把所有的果子合成一堆。

基础算法习题集(李波于 2007 年 7 月收集整理)

每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。 可以看出,所有的果子经过 n-1 次合并之后,就只剩下一堆了。多多在合并果子时总共消 耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。 假定每个果子重量都为 1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合 并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。 例如有 3 种果子,数目依次为 1,2,9。可以先将 1、2 堆合并,新堆数目为 3,耗 费体力为 3。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为 12,耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明 15 为最小的体力耗费值。 输入文件: 输入文件 fruit.in 包括两行,第一行是一个整数 n(1<=n<=10000),表示果子的 种类数。第二行包含 n 个整数,用空格分隔,第 i 个整数 ai(1<=ai<=20000)是第 i 种 果子的数目。 输出文件: 输出文件 fruit.out 包括一行,这一行只包含一个整数,也就是最小的体力耗费值。 输入数据保证这个值小于 231。 样例输入 3 1 2 9 样例输出 15

[分析]显然,每次从现有的数中选取两个最小数的进行合并(将这两个数删除),将合并后的 数记录下来,重复 n-1 次,就能保证值最小。
先将果子数排序,取其中最小的两堆合并,得到一个新堆;再排序,再取其中最小的 两堆合并??直到只剩一堆。为尽快出解,排序的速度显得格外重要,程序建堆采取快速排 序,时间复杂度 O(nlogn),也可以直接采取堆排序,时间复杂度同样 O(nlogn).这样总的时间 复杂度 O(nlogn)。

[程序]
program ex5_5; var n,i,j,k,min,mid,max:word; a:array[1..10000]of longint;{存放各堆果子数} p,temp:longint; procedure QuickSort(l, r:Integer);{对数组 a 快速排序(升序)} var i,j,x,y:integer; begin i:=l; j:=r; x:=a[(l+r) DIV 2]; repeat while a[i]<x do inc(i); while x<a[j] do dec(j); if i<=j then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; inc(i);dec(j); end; until i>j;

基础算法习题集(李波于 2007 年 7 月收集整理)

if l<j then QuickSort(l,j); if i<r then QuickSort(i,r); end; begin assign(input,'fruit.in'); reset(input); assign(output, 'fruit.out'); rewrite(output); readln(input,n); for i:=1 to n do read(input,a[i]); close(input); QuickSort(1,n);{用快速排序法对果子堆按升序排列} p:=0; for i:=1 to n-2 do begin inc(a[i+1],a[i]);{把第 i 堆合并到第 i+1 堆} inc(p,a[i+1]);{累加合并所耗体力值} {用二分法将刚合并得到的新堆插入到相应位置,使整个序列再次成为升序序列} min:=i+2;max:=n; while min<=max do begin mid:=(min+max) div 2; if a[mid]=a[i+1] then begin j:=mid;break; end; if a[mid]<a[i+1] then min:=mid+1 else max:=mid-1; end; if min>max then j:=min; temp:=a[i+1]; for k:=i+1 to j-2 do a[k]:=a[k+1]; a[j-1]:=temp; end; p:=p+a[n]+a[n-1];{合并最后两堆} write(output,p); close(output); end.

第六章 图
基本概念:
图:数据之间的关系是任意,每个元素的前趋和后续个数是不定的,M:N; 定义:简单讲,一个图是由一些点和这些点之间的连线组成的。严格意义讲,图是一种 数据结构,定义为:graph=(V,E)。V 是一个非空有限集合,代表顶点(结点),E 代表 边的集合,一般用(Vx,Vy)表示,其中,Vx,Vy 属于 V。

基础算法习题集(李波于 2007 年 7 月收集整理)

图的方向: 如果边是没有方向的, 称为“无向图”。 表示时用一队圆括号表示, 如: (Vx, Vy),(Vy,Vx),当然这两者是等价的。并且说边(Vx,Vy)依附于(相关联)顶点 Vx 和 Vy。 如果边是带箭头的,则称为“有向图”,表示时用一队尖括号表示,此时<Vx,Vy> 与<VY,VX>是不同的,如<VX,VY>的起点为 VX,终点为 VY。有向图中的边又称为弧。起点 称为弧头、终点称为弧尾。< P><Vy,Vx>是不同的,如<Vx,Vy>的起点为 Vx,终点为 Vy。 弧:有向图中的边又称为弧。起点称为弧头、终点称为弧尾。 相邻:若两个结点 U、V 之间有一条边连接,则称这两个结点 U、V 是关联的。 带权图:两点间不仅有连接关系,还标明了数量关系(距离、费用、时间等)。 图的阶:图中结点的个数。 结点的度:图中与结点 A 关联的边的数目,称为结点 A 的度。 入度:在有向图中,把以结点 V 为终点的边的数目称为 V 的入度; 出度:在有向图中,把以结点 U 为起点的边的数目称为 U 的出度; 奇点:度数为奇数的结点; 偶点:度数为偶数的结点; 终端结点:在有向图中,出度为 0 的结点; 定理 1:图中所有结点的度数之和等于边数的 2 倍; 定理 2:任意一个图一定有偶数个奇点; 连通:如果图中结点 U,V 之间存在一条从 U 通过若干条边、点到达 V 的通路,则称 U、 V 是连通的。 路(径):从一个结点出发,沿着某些边连续地移动而到达另一个指定的结点,这种依 次由结点和边组成的序列,叫“路”或者“路径”。 路径长度:路径上边的数目。 简单路径:在一个路径上,各个结点都不相同,则称为简单路径。 回路:起点和终点相同的路径,称为回路,或“环”。 连通图:对于图 G 中的任一对不同顶点 U、V,都有一条(U,V)通路,则称图 G 是连 通的。 强连通图:在有向图 G 中,每一对结点之间都有路径的图。 网络:带权的连通图。

EX6_1、一笔画问题:
请你设计一个程序,对给定的一个图,由计算机判断能否一笔画出,若能请打印出一笔 画的先后顺序;若不能则打印“NO SOLUTION!”。 [分析]

由数学知识可知: 当一个图的顶点全是偶点或仅有两个奇点时才能一笔画出, 而且此图 必须是连通图。 给出几个数学概念: 1.欧拉路:在无孤立结点的图 G 中,若存在一条路,经过图中每条边一次且仅一次, 则称此路为欧拉路。如下图(左)可以构成一个欧拉路

基础算法习题集(李波于 2007 年 7 月收集整理)

2.欧拉回路:若存在一条路,经过图中每条边一次且仅一次,且回到原来位置,则 称此路为欧拉回路。因此,七桥问题转换成了欧拉回路问题。如下图(右)可以构成一个欧 拉路

3. 欧拉图:存在欧拉回路的图,称为欧拉图。 4. 定理 1:存在欧拉路的条件:图是连通的,且存在 0 个或 2 个奇点。 5. 定理 2:存在欧拉回路的条件:图是连通的,且存在 0 个奇点。 6. 哈密尔顿图:无孤立结点的连通图,若存在一条路,经过图中每一个结点一次且 仅一次,则称为哈密尔顿图。 7. 哈密尔顿环: 是一条沿着图的 n 边环行的路径, 它访问每一个结点一次且仅一次, 并且返回到它的开始位置。 [算法设计] 1、 建立邻接矩阵,link[i,j]:=1 或 0; 2、 求每个顶点的度数,存入 degree[i]; 3、 统计奇点的个数,存入 odt; 4、 若无奇点,则可从任意一结点出发开始一笔画,一般 start:=1; 5、 若有 2 个奇点,则从其中一个奇点 i 出发开始一笔画,start:=i; 6、 若奇点个数超过 2 个,则不能一笔画出。 如何画呢?即如何打印序列呢? 细化第 4、5 步: 4.1 设 sum 为图的总度数; 4.2 从一个奇点(偶点)出发,打印出来,且 degree[i]-1; 4.3 从邻接矩阵中找到结点 i 的下一个邻接点 j,且 degree[j]-1; 4.4sum:=sum-2; 4.5 判断“sum=0”,成立就结束,否则转 4.2。 [程序] program ex6_1; const n=6; link:array[1..n,1..n] of 0..1 {邻接矩阵,也可定义成数组变量 =((0,1,0,0,1,1), 从键盘读入,容易错) (1,0,1,1,0,1), (0,1,0,1,0,0), (0,1,1,0,1,1), (1,0,0,1,0,1), (1,1,0,1,1,0)); var degree:array[1..n] of integer; i,j,r,sum,odt,start,now:integer; begin sum:=0; {总度数} odt:=0; {奇点个数} start:=1; {起点,默认为第 1 个结点}

基础算法习题集(李波于 2007 年 7 月收集整理)

for i:= 1 to n do {求每个结点的度,统计奇点个数,确定起点 start} begin degree[i]:=0; for j:=1 to n do degree[i]:=degree[i]+link[i,j]; sum:=sum+degree[i]; if odd(degree[i]) then begin odt:=odt+1;start:=i; end; end; if odt>2 then writeln('no solution!') else begin now:=start; {now 为当前结点} write(start); repeat r:=0; repeat {找满足条件的下一个结点} r:=r+1 until ((link[now,r]>0) and ((degree[r]>1) or ((degree[r]=1) and (sum=2)))); link[now,r]:=0; link[r,now]:=0; sum:=sum-2; {两个点均置访问标记,且总度数-2} dec(degree[now]); dec(degree[r]); {各点度数-1} now:=r; {下个起点} write('--->',r); {输出} until sum=0; end; writeln; readln; end.

EX6_2、最短路径问题:
根据不同情况采用不同思路, 求图的最短路径有两种经典算法: 一是求图中每一对顶点 间最短路径的弗洛伊德算法;二是求从某个顶点(源结点)到其它顶点(目的结点)最短路 径的迪杰斯特拉算法。分别介绍如下: 弗洛伊德(floyed)算法:弗洛伊德算法仍从图的带权邻接矩阵 cost 出发,其基本思想是: 假设求从顶点 vi 到 vj 的最短路径,如果从 vi 到 vj 有弧,则从 vi 到 vj 存在一条长度为 cost[I,j]的路径, 该路径下一定是最短路径, 尚需进行 n 次试探。 首先考虑路径 (vi ,v1,,vj) 是否存在 (即判别弧 (vi ,v1,) 和 (v1,vj) 是否存在) 。 如果存在, 则比较 (vi,vj) 和 (vi,v1,vj) 的路径长`度取长度较短者为从 vi 到 vj 的中间顶点的序号不大于 1 的最短路径。假如在路 径上再增加一个顶点 v2,也就是说,如果(v1 ,...,v2,)和(v2 ,...,v1)分别是当前找到 的中间顶点的序号不大于 1 的最短路径,那么(v1 ,... v2, ,...vj )就有可能是从 vi 到 vj 的中间顶点的序号不大于 2 的最短路径。将它和已经得到的从 vi 到 vj 中间顶点诒不大于 1 的最短路径相比较,从中选出间顶点的序号不大于 2 的最短路径之后,再增加一个顶点 v3, 继续进行试探。依次类推,在一般情况下,若(vi ,...,vk)和(vk,...,vj)分别是从 vi 到 vk 和从 vk 到 vj 的中间顶点的序号不大于 k-1 的最短路径,则将(vi ,... vk,...vj )和已经

基础算法习题集(李波于 2007 年 7 月收集整理)

得到的从 vi 到 vj 且中间顶点序号不大于 k-1 的最短路径相比较,其长度较短者便是从 vi 到 vj 的中间顶点的序号不大于 k 的最短路径。这样,在经过 n 次比较后,最后求得的必是从 vi 到 vj 的最短路径。按此方法,可以同时求得各对顶点间的最短路径。 问题:求任意两点间的最短路径。 4 ④ ② 4 7 1 ① 8 ③ 3 2 2 ⑤ 1 9 ⑥

程序思路如下: p:任意两点路径 如何输出任意两点间路径: 0 0 2 5 2 5 ①由 P[1,6]=5 知 5 为中间点 0 0 0 5 0 5 ②由 P[1,5]=2 知 2 为(1,5)中间点 2 0 0 0 0 4 ③由 P[1,2]=0,P[2,5]=0 知 1 至 2,2 至 5 为直达 5 5 0 0 0 0 ④由 P[5,6]=4 知 4 为(5,6)中间点, (5,4) , (4,6)无中间点 2 0 0 0 0 4 得路径为 1→2→5→4→6 5 5 4 0 4 0 [程序] program ex6_2_1;(Floyd) const max=6; v:array[1..max,1..max] of integer=(( 0, 4, 8,99,99,99), ( 4, 0, 3, 4, 1,99), ( 8, 3, 0, 2, 2,99), (99, 4, 2, 0, 1, 7), (99, 1, 2, 1, 0, 9), (99,99,99, 7, 9, 0)); var p:array[1..max,1..max] of integer; {P:路径数组} start,ending,i,j,k:integer; {START:始点, ENDING:终点} procedure print(i,j:integer); {递归输出 I 到 J 的最短路径} var k:integer; begin k:=p[i,j]; if k<>0 then begin print(i,k);write(k,'=>');print(k,j);end; end; begin write('start,ending:'); readln(start,ending); for i:=1 to max do for j:=1 to max do p[i,j]:=0; {路径变量清零} for k:=1 to max do {对 V 进行 max 次替换} for i:=1 to max do for j:=1 to max do if v[i,k]+v[k,j]<v[i,j] then

基础算法习题集(李波于 2007 年 7 月收集整理)

{若 I 经过 K 到 J 比 I 直接到 J 费用低则替换} begin v[i,j]:=v[i,k]+v[k,j];p[i,j]:=k;end; {P[I,J]表示 I 经过 P[I,J]到 J, P[I,J]=0 表示 I 直接到 J } write(start,'=>');print(start,ending);writeln(ending); end. 迪杰斯特拉(Dijkstra)算法: 讨论带权有向图,并称路径上的第一个顶点为源点(soruse), 最后一个顶点为终点 (destination) 。 下面讲一种最常见的最短路径问题----从某个源点到其余各顶点的最短路 径。 例: ②

3 2




3


1 2


2


4 3

[程序] program ex6_2_2;(dijkstra) const max=6; s:array[1..max,1..max] of integer=((0, 3, 2, 100,100,100), (3, 100,100,2, 3, 100), (2, 100,100,4, 100,3), (100,2, 4, 100,100,2), (100,3, 100,100,100,1), (100,100,3, 2, 1, 100)); var ss:array[1..max] of integer; {存点 1 到各点的最短路径长度} p:array[1..max] of set of 1..max; {存点 1 到各点的最短路径集合} i,j,k,l,m,n:integer; q:set of 1..max; {已扩展的点的集合} begin l:=100; l:{存当前最短的边,初值为 100} for i:=1 to max do{初始化,存与点 1 相连的各点到点 1 的当前最短路径长度和路径 集合} begin ss[i]:=s[1,i];if ss[i]<l then p[i]:=[1]+[i] else p[i]:=[] end; q:=[1]; {已扩展点的集合初值} for k:=1 to max -1 do {循环 max-1 次,分别求点 1 到其余各点的最短路径} begin l:=100;j:=1; {j:当前要扩展的点(初值为 1)} for i:=1 to max do {找当前要扩展的点 j(边长最短的)} if not(i in q) and (ss[i]<l) then begin j:=i;l:=ss[i] end; q:=q+[j]; {扩展当前第 j 点}

基础算法习题集(李波于 2007 年 7 月收集整理)

for i:=1 to max do {修正点 1 到各点的最短距离} if not(i in q) and (ss[j]+s[j,i]<ss[i]) then begin ss[i]:=ss[j]+s[j,i];p[i]:=p[j]+[i] end end; for i:=2 to max do {输出最短路径和距离} begin for j:=1 to max do if j in p[i] then write(j:2); writeln('s=':5,ss[i]) end; end. 在实际应用中,根据实际情况,也可以采用其他方法,如搜索(深度优先搜索或广度优 先搜索) 。例如:

EX6_3、六城市问题:
下图是六个城市之间道路联系的示意图, 连线表示两城市间有道路相通, 连线旁的数字 表示路程。请编写一程序,由计算机找出从 C1 城到 C6 城之间路程最短的一条路径,输出路

径序列及总长度。 [分析]link[i,j]:=0 表示城市 i 与城市 j 之间没有通路,否则为权值。基本思想为:假设 K 为当前城市编号,R 为下一城市编号(2<=R<=6),按下列规则进行遍历: if link(k,r)>0 且 Cr 没有被访问过 then 记录该城市编号,k:=r。 可以用深度优先遍历,也可用广度优先遍历。 下面的程序采用后者,前者留给大家完成。注意,广度优先遍历时,最先找到的路径未 必是最短路径,而只是走过城市最少的路径而已。所以,找到一条路径后应采用“打擂台” 的思想保存最小值。另外,按照广度优先遍历的要求,设一个 pnt 数组和 open、closed 用 于队列存放之间结点。 [程序] program ex6_3; const max=maxint; link:array[1..5,1..6] of integer=((0,4,8,0,0,0), (4,0,3,4,6,0), (8,3,0,2,2,0), (0,4,2,0,4,9),

基础算法习题集(李波于 2007 年 7 月收集整理)

(0,6,2,4,0,4)); type fg=set of 1..6; var mincost,step,open,closed,i,k,n,r:integer; path:array[1..7] of 1..6; {存放最终结果} flag:array[1..100] of fg; {标志数组,队列,头尾指针分别为 open,closed} city,pnt:array[1..100] of byte; {数值数组,pnt 用于队列} procedure exam; {判断最短路径和求和} var n,i,y,cost:integer; s:array[1..7] of 1..6; begin y:=open; n:=0; cost:=0; while y> 0 do begin inc(n);s[n]:=y;y:=pnt[y]; end; {计算步长(深度 )} for i:=n-1 downto 1 do {计算路径} cost:=cost+link[city[s[i+1]],city[s[i]]]; if cost<mincost then begin step:=n-1; {记忆最短路径} mincost:=cost; for i:=1 to step do path[i]:=city[s[i]]; end; end; procedure print; {输出 path 数组和 mincost} begin writeln('the shortest path:'); write('1'); for i:=step downto 1 do write('->',path[i]); writeln; writeln('mincost=',mincost); end; BEGIN mincost:=max; {打擂台,赋初值} flag[1]:=[1]; city[1]:=1; {初始化,从第一个结点 C1 开始遍历} n:=0; pnt[1]:=0; {队列初始化} closed:=0; open:=1; repeat {直到队列空,结束程序} inc(closed); k:=city[closed];

基础算法习题集(李波于 2007 年 7 月收集整理)

if k<>6 then begin {判断有没有到达目的结点 C6} for r:=2 to 6 do {广度遍历} if (not(r in flag[closed])) and (link[k,r]>0) then begin {没访问过,则进队} inc(open); city[open]:=r; flag[open]:=flag[closed]+[r]; pnt[open]:=closed; if r=6 then exam; end; end; until closed>=open; print; readln; END.

EX6_4、最小生成树问题:
如果图 G=(V,E)是一个连通的无向图,则从 G 的任一个顶点出发进行一次深度优先 遍历或广度优先遍历便可遍历全部图。 设遍历过程中走过的边的集合为 TE(G),显然 T=(V,TE)是 G 的一个连通子图,且 T 本身也是一棵树(无根树),则称 T 是 G 的生成树。 下图(B)和(C)是对(A)分别进行深度和广度优先遍历得到的一种生成树。注意, 图的生成树是不唯一的。 对于一棵带权树, 生成树中各边的权值之和称为这棵生成树的代价, 代价最小的生成树称为“最小代价生成树”。

如何求最小代价生成树呢?普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法是两个 利用 MST 性质构造最小生成树的算法。 普里姆(Prim)算法:R.C.Prim 提出的求最小代价生成算法是常用的一种,设图的顶 点集合 V 共有 n 个顶点,则算法如下: 1、设置一个顶点的集合 S1 和一个边的集合 TE,S1 和 TE 的初始状态均为空集; 2、选定图中的一个顶点 K,从 K 开始生成最小代价生成树,将 K 加入到集合 S1; 3、 重复下列操作, 直到选取了 n-1 条边: 选取一条权值最小的边 (X, Y) , 其中 X∈S1, not(Y∈S1)。将顶点 Y 加入集合 S1,边(X,Y)加入集合 TE。 下图给出了上图(A)的最小代价生成树的生成过程:

基础算法习题集(李波于 2007 年 7 月收集整理)

[程序] program ex6_4_1;(prim) const max=6; s:array[1..max,1..max] of byte=((0,6,1,5,0,0), (6,0,5,0,3,0), (1,5,0,5,6,4), (5,0,5,0,0,2), (0,3,6,0,0,6), (0,0,4,2,6,0)); ss:array[2..max] of byte=(100,100,100,100,100); {扩展用数组,ss[I]=0 表示 I 点已扩展,ss[I]<>0 表示 ss[I]是当前所有已扩展点到点 I 的路径中的最短路径。} var q:array[1..max,1..max] of byte; {最小生成树矩阵,q[I,j]<>0 表示 I 点与 j 点 连} p:array[1..max] of byte; {存 ss[I]的另一端点,即 s[I,p[I]]=ss[I]} i,j,l,m,n:integer; begin for i:=1 to max do for j:=1 to max do q[i,j]:=0; {清零} for i:=2 to max do if s[1,i]<>0 then begin ss[i]:=s[1,i];p[i]:=1 end; {ss 数组赋初值,并找出与 1 点相通的所有点。} for i:=2 to max do begin l:=100; for j:=2 to max do {找出与当前树中所有点相连的最短边中的最小边} if (ss[j]<>0) and (ss[j]<l) then begin l:=ss[j];m:=j;n:=p[m] end ss[m]:=0;q[n,m]:=l;n:=m; {ss[m]置零,表示 m 点已扩展,q[n,m]建树} for j:=2 to max do {找出与 m 点相连的边(另一端点为 j) ,若小于 ss[j]则替换} if (s[n,j]<>0) and (ss[j]<>0) and (s[n,j]<ss[j]) then begin ss[j]:=s[n,j];p[j]:=n end; end; for i:=1 to max do {输出最小生成树矩阵} begin for j:=1 to max do write(q[i,j]);writeln end; writeln end. 克鲁斯卡尔(Kruskal)算法:克鲁斯卡尔算法的时间复杂度为 O(eloge)(e 为网中边的数 目),因此它相对于普里姆算法而言,适合于求边稀疏的网的最小生成树。 假设连通网 N=(V,{E}) ,则令最小生成树的初始状态为只有 n 个顶点而无边的非连通 图 T=(V,{∮}) ,图中每个顶点自成一个连通分量。在 E 中选择代价最小的边,若该边依 附的顶点落在 T 中不同的连通分量上, 则将此边加入到 T 中, 否则舍去此边而选择下一条代 价最小的边。依次类推,直至 T 中所有顶点都在同一连通分量上为止。 例如图为依照克鲁斯卡尔算法构造一棵最小生成树的过程。代价分别为 1,2,3,4 的 四条边由于满足上述条件,则先后被加入到 T 中,代价为 5 的两条边(1,4)和(3,4)被 舍去。因为它们依附的两顶点在同一连通分量上,它们若加入 T 中,则会使 T 中产生回路, 而下一条代价(=5)最小的边(2,3)联结两个连通分量,则可加入 T。因此,构造成一棵 最小生成树。

基础算法习题集(李波于 2007 年 7 月收集整理)

上述算法至多对 e 条边各扫描一次,假若以“堆”来存放网中的边,则每次选择最小 代价的边仅需 O(loge)的时间(第一次需 O(e) ) 。又生成树 T 的每个连通分量可看成是一 个等价类,则构造 T 加入新的过程类似于求等价类的过程,由此可以以“树与等价类”中介 绍的 mfsettp 类型来描述 T,使构造 T 的过程仅需用 O(eloge)的时间,由此,克鲁斯卡 尔算法的时间复杂度为 O(eloge) 。 ① 6 5 1 ④ ② 5 5 ③ 3 6 4 2 6 ⑥ ⑤ ① ① ⑤ ① 1 1 ④ ② ④ ② 1 ④ ② ③ ③ 3 ③ 2 2 ⑤ ⑥ ⑤ ① ② 3 ⑤ 1 ③ 4 ⑥ ⑤ 2 ⑤ ⑤ ⑥ ⑤ ② 3 5 ⑤ ① 1 ③ 4 ⑥ ⑤ 2 ④ ⑥ ⑤



[程序] program ex6_4_2;(kruskal) label 10; const max=6; s:array[1..max,1..max] of byte=((0,6,1,5,0,0), (0,0,5,0,3,0), (0,0,0,5,6,4), (0,0,0,0,0,2), (0,0,0,0,0,6), (0,0,0,0,0,0)); var p:array[1..(max*(max-1) div 2),0..2] of byte;{存所有边数(存权、两端点)} f:array[1..max,1..max] of integer; {生成树邻接表} q:array[1..max,1..2] of integer; {生成树链表} i,j,l,m,n,zs:integer; begin for i:=1 to max do q[i,2]:=0; {链表指针清零} l:=0; for i:=1 to max do {找出所有边} for j:=1 to max do if s[i,j]<>0 then begin l:=l+1;p[l,0]:=s[i,j];p[l,1]:=i;p[l,2]:=j

基础算法习题集(李波于 2007 年 7 月收集整理)

end; for i:=1 to l-1 do {边按权升序排序} for j:=i+1 to l do if p[i,0]>p[j,0] then begin zs:=p[i,0];p[i,0]:=p[j,0];p[j,0]:=zs; zs:=p[i,1];p[i,1]:=p[j,1];p[j,1]:=zs; zs:=p[i,2];p[i,2]:=p[j,2];p[j,2]:=zs; end; f[p[1,1],p[1,2]]:=p[1,0]; {第一条边加入生成树邻接表} q[p[1,1],1]:=p[1,1];q[p[1,1],2]:=-p[1,1];{端点加入链表,根节点链指针为负} q[p[1,2],1]:=p[1,2];q[p[1,2],2]:=p[1,1]; i:=1;j:=0; {I:所选边的序号,j:当前要选的边数} repeat i:=i+1;m:=p[i,1];n:=p[i,2]; {取当前选中边的两端点序号} repeat {分别查找两端点的根} if m>0 then m:=q[m,2] until m<=0; repeat if n>0 then n:=q[n,2] until n<=0; if (m<0) and (m=n) then goto 10; {若为同一根,则重选} f[p[i,1],p[i,2]]:=p[i,0]; {当前边加入生成树邻接表} if m=n then {当前边两端点均不在树中,则新建一棵树} begin q[p[i,1],1]:=p[i,1];q[p[i,1],2]:=-p[i,1]; q[p[i,2],1]:=p[i,2];q[p[i,2],2]:=p[i,1] end; if (m<0) and (n=0) then {若一端点在某棵树中,则加入} begin q[p[i,2],1]:=p[i,2];q[p[i,2],2]:=p[i,1] end; if (n<0) and (m=0) then {若另一端点在某棵树中,则加入} begin q[p[i,1],1]:=p[i,1];q[p[i,1],2]:=p[i,2]; end; if (m<0) and (n<0) then q[-n,2]:=-m; {边接两棵树} j:=j+1; 10:until j>max-1; for i:=1 to max do {输出生成树邻接表} begin for j:=1 to max do write(f[i,j]); writeln; end;

基础算法习题集(李波于 2007 年 7 月收集整理)

end.

EX6_5、公路修建问题:
下图所示的网络代表 6 个城市间的交通网,边上权是公路的造价,现在要用公路把 6 个城市联系起来,这要修筑 5 条公路,如何设计使得这 5 条公路总的造价最小。

[分析]这是一个最小生成树问题, 所谓最小生成树就是从某个顶点出发遍历图中的各点, 且 使各边权的总和为最小, 一个网络的最小生成树不一定是唯一的。 下图是上图的两个最小生 成树,它们权的总和均为 5+16+11+6+18=56。

算法步骤: 构成最小生成树的典型算法有 Prime 算法与 Kruskal 算法等。 本题解答用 Kruskal 算法: ⒈先把平面上各顶点之间的边统统擦掉,只剩下一些孤立的点; ⒉把各边的长度按从小到大的次序排列好; ⒊按从小到大的次序把每边加到图中去, 每加进去一条边, 就判断一下是否产生回路? 没有回路就加进去下一条边;若产生回路就放弃这条边,而考虑下一条边,碰到两条等长的 边,可任取一条; ⒋重复步骤3,直至加满(n-1)条边,就把n个顶点连接起来了,且边长总和为最 小。 [程序] program ex6_5; const max=10; type way=set of 1..max; gradat=array[1..max,1..max] of real; var data:gradat; k,n:byte; cost:real; already:way; path:array[1..2,1..max] of byte; procedure getdata;{输入数据} var

基础算法习题集(李波于 2007 年 7 月收集整理)

i,j:byte; begin read(n); for i:=1 to n do for j:=1 to n do read(data[i,j]); for i:=1 to n do begin for j:=1 to n do write(data[i,j]:5); writeln; end; writeln; end; procedure print;{输出} var i:byte; begin for i:=1 to n-1 do writeln('Road side:',path[1,i]:3,path[2,i]:3); writeln('Total=',cost); end; procedure lookfor(var n1,n2:byte);{查找这一轮中的最小边} var i,j:byte; m:real; begin m:=1e+36; for i:=1 to n do if i in already then for j:=1 to n do if (not(j in already)) and (data[i,j]<>0) and (data[i,j]<m) then begin m:=data[i,j]; n1:=i; n2:=j; end; end; procedure add;{记录最小生成树及总造价} var i,j:byte; begin repeat lookfor(i,j); already:=already+[j];

基础算法习题集(李波于 2007 年 7 月收集整理)

cost:=cost+data[i,j]; inc(k); path[1,k]:=i; path[2,k]:=j; until already=[1..n]; end; begin getdata; already:=[1]; k:=0; cost:=0; add; print; readln; end.

EX6_6、神经网络:
人工神经网络(Artificial Neural Network)是一种新兴的具有自我学习能力的计算 系统,在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究 一直是当今的热门方向, 兰兰同学在自学了一本神经网络的入门书籍后, 提出了一个简化模 型,他希望你能帮助他用程序检验这个神经网络模型的实用性。 【问题描述】 在兰兰的模型中,神经网络就是一张有向图,图中的节点称为神经元,而且两个神经 元之间至多有一条边相连,下图是一个神经元的例子:

神经元〔编号为 1) 图中,X1—X3 是信息输入渠道,Y1-Y2 是信息输出渠道,C1 表示神经元目前的状态, Ui 是阈值,可视为神经元的一个内在参数。 神经元按一定的顺序排列,构成整个神经网络。在兰兰的模型之中,神经网络中的神 经无分为几层;称为输入层、输出层,和若干个中间层。每层神经元只向下一层的神经元 输出信息,只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。

基础算法习题集(李波于 2007 年 7 月收集整理)

兰兰规定,Ci 服从公式:(其中 n 是网络中所有神经元的数目) 公式中的 Wji(可能为负值)表示连接 j 号神经元和 i 号神经元的边的权值。当 Ci 大 于 0 时,该神经元处于兴奋状态,否则就处于平静状态。当神经元处于兴奋状态时,下一秒 它会向其他神经元传送信号,信号的强度为 Ci。 如此.在输入层神经元被激发之后,整个网络系统就在信息传输的推动下进行运作。现 在,给定一个神经网络,及当前输入层神经元的状态(Ci),要求你的程序运算出最后网络 输出层的状态。 【输入格式】 输入文件第一行是两个整数 n(1≤n≤200)和 p。接下来 n 行,每行两个整数,第 i+ 1 行是神经元 i 最初状态和 其阈值(Ui),非输入层的神经元开 始时状态必然为 0。 再下面 P 行,每行由两个整数 i,j 及一个整数 Wij,表示连接神经元 i、j 的边权值为 Wij。 【输出格式】 输出文件包含若干行, 每行有两个整数, 分别对应一个神经元的编号, 及其最后的状态, 两个整数间以空格分隔。 仅输出最后状态非零的输出层神经元状态, 并且按照编号由小到大 顺序输出! 若输出层的神经元最后状态均为 0,则输出 NULL。 【输入样例】 5 6 1 0 1 0 0 1 0 1 0 1 1 3 1 1 4 1 1 5 1 2 3 1 2 4 1 2 5 1 【输出样例】 3 1 4 1 5 1 [分析] 这是 NOIP2003 复赛试题。题目阅读起来有些费神,题中边的权值 W,神经元的状态 值 C,阀值 U,均未明确指出其取值范围,反映出命题不严谨。 对题目仔细阅读后发现, 本题是比较简单的, 但要注意神经元的层数, 只输出最大层 (输 出层)的状态非零的神经元的状态,在中间层中只有神经元处于兴奋状态时(Ci>0)才会向 下一层传送信号。 [程序] program ex6_6; const

基础算法习题集(李波于 2007 年 7 月收集整理)

maxn=200;maxp=200; var i,j,n,p,maxlayer:integer; w:array[0..maxp]of longint;{存放边的权值} start,terminal:array[0..maxp]of byte;{存放边的起点与终点} u,c:array[0..maxn]of longint;{存放神经元的阀值与状态值} layer:array[0..maxn]of byte;{存放神经元的层数} f1,f2:text;fn1,fn2,fileNo:string; flag:boolean; begin write('Input fileNo:'); readln(fileNo); fn1:='network.in'+fileNo; fn2:='network.ou'+fileNo; assign(f1,fn1);reset(f1); assign(f2,fn2);rewrite(f2); readln(f1,n,p); for i:=1 to n do readln(f1,c[i],u[i]); fillchar(layer,sizeof(layer),0); for i:=1 to p do begin readln(f1,start[i],terminal[i],w[i]);{读入边的起点,终点,权} layer[terminal[i]]:=layer[start[i]]+1;{计算终点的层数(比起点大 1)} end; close(f1); maxlayer:=layer[terminal[p]];{求最大层数,即输出层的层数} for i:=1 to n do{计算非输入层的节点 i 的状态值} if layer[i]>0 then begin for j:=1 to p do if (terminal[j]=i) and (c[start[j]]>0){与目标节点 i 有边相连的节点 j 且 其状态处于兴奋时(Cj>0)才向节点 I 传送信号} then c[i]:=c[i]+w[j]*c[start[j]]; c[i]:=c[i]-u[i]; end; {输出结果} flag:=true; for i:=1 to n do if (layer[i]=maxlayer) and (c[i]>0) then begin writeln(f2,i,' ',c[i]); flag:=false; end; if flag then writeln(f2,'NULL'); close(f2); end.

基础算法习题集(李波于 2007 年 7 月收集整理)

第七章 搜索
搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况, 从 而求出问题的解的一种方法。 搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并 寻找符合目标状态的节点的过程。 所有的搜索算法从其最终的算法实现上来看, 都可以划分成两个部分──控制结构和产 生系统,而所有的算法的优化和改进主要都是通过修改其控制结构来完成的。 从类别划分,搜索可以分为穷举搜索、回溯搜索、深度优先搜索和广度优先搜索。 深度搜索与广度搜索的控制结构和产生系统很相似,唯一的区别在于对扩展节点选取 上。由于其保留了所有的前继节点,所以在产生后继节点时可以去掉一部分重复的节点,从 而提高了搜索效率。这两种算法每次都扩展一个节点的所有子节点,而不同的是,深度搜索 下一次扩展的是本次扩展出来的子节点中的一个, 而广度搜索扩展的则是本次扩展的节点的

基础算法习题集(李波于 2007 年 7 月收集整理)

兄弟节点。在具体实现上为了提高效率,所以常采用不同的数据结构。

EX7_1、六城市问题:
下图是六个城市之间的道路联系示意图, 连线表示两城市有路径相通, 连线旁的数字表 示路径长度。请找出 C1 到 C6 的没有重复城市的所有路径,打印这些路径以及长度。 C2 C5

6 2
C1

5 3 8 7
C3 C4

6
C6

4

4

[分析] 本题可以采用深度搜索来解决。 用深度优先搜索解题时,在每一步搜索中,优先扩展深度最深、即最新生成的子结点, 这样的搜索方法称为深度优先搜索。 搜索过程中需要记录下所有的开、闭节点,我们采用两个数组 OPEN 和 CLOSE 记录。 由于深度优先搜索优先扩展新产生的子结点,OPEN 表需要采用堆栈的方式,即后进先出原 则。算法如下: 1)初始化数组,CLOSE 表为空,OPEN 表为初始节点; 2)从 OPEN 表表顶部弹出一个节点作为当前节点; 3)扩展当前节点,将新产生的节点放入 OPEN 表顶部,将当前节点移入 CLOSE 表; 4)比较新产生的节点与目标节点,若相同则输出; 5)若 OPEN 表不为空则转 2; 6)结束。 在此,我们采用一个 6×6 的邻接矩阵来表示城市之间连同情况,矩阵中零表示没有连 同,否则表示路径长度。 接下来考虑产生规则,每一个节点的后继节点必须满足以下条件:1)该节点与当前节 点有路径相连;2)该节点未在前面路径中出现过。在扩展每一个节点时,只需要用一个循 环判断每一个节点是否满足上述条件。 产生出的节点,我们把他们存储在 OPEN 表顶部,作为下一次扩展的对象。 [程序] program ex7_1; type prec=^rec; rec=record city:string[6]; len:integer; last,next,father:prec; end; const link:array[1..6,1..6] of integer=((0,2,4,0,0,0), (2,0,3,8,6,0), (4,3,0,7,5,0),

基础算法习题集(李波于 2007 年 7 月收集整理)

(0,8,7,0,3,4), (0,6,5,3,0,6), (0,0,0,4,6,0)); var op,cl:prec; total:integer; procedure init; begin new(op); with op^ do begin city:='1'; len:=0; next:=nil; father:=nil; last:=nil; end; cl:=nil; total:=0; end; procedure getpath; begin if cl=nil then cl:=op else begin cl^.next:=op; cl:=cl^.next; end; op:=op^.last; end; procedure expand; var i,j:integer; c:char; procedure output; var i:integer; begin with cl^ do begin write('1'); for i:=2 to length(city) do write('-',city[i]); writeln(':',len); end; inc(total); end; begin with cl^ do begin j:=ord(city[length(city)])-48;

基础算法习题集(李波于 2007 年 7 月收集整理)

if j=6 then output else for i:=1 to 6 do if link[j,i]>0 then begin c:=char(i+48); if pos(c,city)=0 then begin if op=nil then begin new(op); op^.last:=nil end else begin new(op^.next); op^.last:=op; op:=op^.next; end; op^.father:=cl; op^.city:=city+c; op^.len:=len+link[j,i]; end; end; end; end; begin init; repeat getpath; expand; until op=nil; writeln('total:',total); end.

EX7_2、五人分书:
有 A、B、C、D、E 5 本书,要分给张、王、刘、赵、钱 5 位同学,每人只能选 1 本。 每个人都将自己喜爱的书填写在下表中。请你设计一个程序,打印出让每个人都满意的所 有分书方案。 ┌──┬───┬───┬───┬───┬───┐? ? ? ? ? │??│?A │ B │ C │ D │ E │? ? ? ? ? ├──┼───┼───┼───┼───┼───┤? ? ? ? ? │?张│?√?│???│?√?│?√?│???│? 1 ? 0 ? 1 ? 1 ? 0 ├──┼───┼───┼───┼───┼───┤? ? ? ? ? │?王│?√?│?√?│???│???│?√?│? 1 ? 1 ? 0 ? 0 ? 1 ├──┼───┼───┼───┼───┼───┤? ? ? ? ? │?刘│???│?√?│?√?│???│???│? 0 ? 1 ? 1 ? 0 ? 0 ├──┼───┼───┼───┼───┼───┤? ? ? ? ?

基础算法习题集(李波于 2007 年 7 月收集整理)

│?赵│???│???│???│?√?│???│? 0 ? 0 ? 0 ? 1 ? 0 ├──┼───┼───┼───┼───┼───┤? ? ? ? ? │?钱│???│?√?│???│???│?√?│? 0 ? 1 ? 0 ? 0 ? 1 └──┴───┴───┴───┴───┴───┘? ? ? ? ? [方法一] 题目中每人喜爱哪本书是随意的,无规律可循,所以用穷举方法解较为合适。按 穷举法的一般算法,可以暂不考虑一些条件,先求出满足部分条件的解,即可行解。然 后,再加上尚未考虑的条件,从可行解中删除不符合这些条件的解,留下的就是问题的 解。具体到本题中,我们可以先不考虑“让每人都满意”这个条件,这样,就只剩“每 人选一本且只能选一本”这一个条件了。在这个条件下,可行解是 5 本书的所有全排列, 一共有 5!=120 种情况。从这 120 种可行解中删去不符合“每人都满意”这一条件的解, 剩下的就是本题的解。 为编程方便,我们用 1、2、3、4、5 分别表示这 5 本书。这 5 个数字的—种全排 列就是 5 本书的一种分法。例如 54321 就表示第五本书(即 E)分给张,第四本书(即 D) 分给王??,第—本书(即 A)分给钱。 每个人“喜爱书表”,在程序中我们用二维数组 Like[i,j]来表示,1 表示喜爱, 0 表示不喜爱。排列的产生可以用穷举法,也可以用专门算法。 算法设计: 第一步:产生 5 个数字的一个全排列; 第二步:检查所产生的全排列是否符合“喜爱书表”,如果符合就输出; 第三步:检查是否所有排列都产生了,如果没有产生完,则返回第一步; 第四步:结束。 根据题目给出的条件,还可以对上面算法进行一些改进。例如产生一个全排列 12345 时,第一个数 1 表示将第一本书给小张。但从表中可以看出,这是不可能的,因 为小张只喜欢第三、第四本书。也就是说,1X X X X 这一类分法是不符合条件的。由 此使我们想到,如果选定第一本书后,就立即检查一下是否符合条件,当发现第一个数 的选择不符合条件时,就不必再产生后面的 4 个数了,这样做可以减少很多的运算量。 换句话说,第一个数只在 3 和 4 中选择,这样就可以减少 3/5 的运算量。同理,在选定 了第一个数后,其他 4 个数字的选择也可以用类似的方法处理,即选择第二个数后,立 即检查是否符合条件。例如,第一个数选 3,第二个数选 4 后,立即进行检查,发现不 符合条件,就另选第二个数。这样就又把 34XXX 一类的分法删去了,从而又减少了一部 分运算量。 综上所述,改进后本题算法应该是:在产生各种排列时,每增加一个数字,就检 查一下该数的加入是否符合条件,如不符合,就立刻换一个;若符合条件,则再产生下 一个数。因为从第 i 本书到第 i+1 本书的寻找过程是相同的,所以可以用递归方法编程。 我们用二维数组 like 存放“喜爱书表”,用集合 flag 存放已分出书的编号,数组 book 存储各人所分得书的编号,如 book[1]=3,则表示第一个同学(小张)分得编号为 3 的书。 [程序] Program ex7_2_1; type five=1..5; const like: array[five,five] of 0..1 =((1, 0, 1,1 ,0), (1,1,0,0,1),(0,1,1,0,0),(0,0,0,1,0),(0,1,0,0,1)); {个人对各种书的喜好情况}

基础算法习题集(李波于 2007 年 7 月收集整理)

name:array[five] of string[5] = ('zhang', 'wang','liu', 'zhao', 'qian' ); {数组 name 存放学生姓名} var book: array[1..5] of 0..5;{存放各人分配到的书的编号} flag: set of five; c: integer; procedure print; {打印分配方案} var i: integer; begin inc(c); {计数,统计得到分配方案数} writeln( 'answer', c,':'); for i:=1 to 5 do writeln(name[i]: 10,':', chr(64 + book[i] ) ); end; procedure try(i: integer); {判断第 I 个学生分得书的编号} var j: integer; begin for j:=1 to 5 do if not(j in flag) and (like[i,j]>0) then begin {第 j 本书未选过,且第 I 个学生喜爱第 j 本书} flag:= flag + [j]; {修改已选书编号集合,加入第 j 本书} book[i]:=j; {记录第 I 个学生分得书的编号} if i= 5 then print {I = 5,5 个学生都分到自己喜爱的书} else try(i + 1); {i<5,继续搜索下一个学生可能分到书的情况} flag:= flag - [j]; {后退一步,以便查找下一种分配方案} book[i]:=0; end end; begin flag:= []; c:=0; try(1); readln end. [方法二] 从表中看出,赵同学只喜爱 D 这一本书,无其它选择余地。因此,赵同学得到 书的编号在搜索前就确定下来了。为了编程方便,可以把赵钱 2 人位置交换,这样程序 只需对张王刘钱 4 人情况进行搜索测试。 另外,发现表示“喜爱书表”的数组有多个 0,为减少不必要的试探,我们改用 链表来表示。例如第三位同学的链表是:Like[3,0]=2.Like[3,2]=3.Like[3,3]=0, 其中,Like[3,0]=2 表示他喜爱的第一本书编号是 2,Like[3,2]=3 即表示喜爱的编号 为 2 的书后面是编号为 3 的书,Like[3,3]=0,表示编号为 3 的书是其最后 1 本喜爱的 书。 这样基本算法不变,但程序改进如下:

基础算法习题集(李波于 2007 年 7 月收集整理)

Program ex7_2_2; {linking List} type five=1..5;{将小张的喜欢的书改成了 ACD} const Link: Array[ 1..5,0..5 ] of 0..5 = ((1,3,0,4,0,0),(1,2,5,0,0,0),(2,0,3,0,0,0),(4,0,0,0,0,0),(2,0,5,0,0,0)); {个人对各种书的喜好情况} name:array[five] of string[5] = ('zhang', 'wang','liu', 'zhao', 'qian' ); {数组 name 存放学生姓名} var book: array[1..5] of 0..5;{存放各人分配到的书的编号} flag: set of five; c: integer; procedure print; {打印分配方案} var i: integer; begin inc(c); {计数,统计得到分配方案数} writeln( 'answer', c,':'); for i:=1 to 5 do writeln(name[i]: 10,':', chr(64 + book[i] ) ); end; procedure try(i: integer); {判断第 I 个学生分得书的编号} var j: integer; begin j:=0; repeat j:=link[i,j]; { 取链表中喜爱书编号 j } If not(j in flag) and (j>0) then Begin flag:= flag+ [j]; book[i]:=j; if i=5 then print else try(i + 1); flag:= flag - [j]; {后退一步,以便查找下一种分配方案} book[i]:=0; End; until j = 0; end; begin flag:= []; c:=0; try(1); readln end.

EX7_3、八数码难题 :
要求用最少的步数将左边方阵变为右边方阵。

基础算法习题集(李波于 2007 年 7 月收集整理)

2 8 3 1 6 4 -> 8 7 5

1 2 3 4 7 6 5

[方法一] 本题可以采用“广度双向搜索”方法实现。广度双向搜索指的是搜索沿两个力向同时进 行,即: 正向搜索:从初始结点向目标结点方向搜索; 逆向搜索:从目标结点向初始结点方向搜索; 当两个方向的搜索生成同一子结点时终止此搜索过程。 广度双向搜索算法如下: 广度双向搜索通常有两中方法: 1. 两个方向交替扩展 2. 选择结点个数较少的那个力向先扩展. 方法 2 克服了两方向结点的生成速度不平衡的状态,明显提高了效率。 算法说明: 设置两个队列 c:array[0..1,1..maxn] of jid,分别表示正向和逆向的扩展队列。 设置两个头指针 head:array[0..1] of integer 分别表示正向和逆向当前将扩展结点 的头指针。 设置两个尾指针 tail:array[0..1] of integer 分别表示正向和逆向的尾指针。 maxn 表示队列最大长度。 算法语言描述如下: 1.主程序代码 repeat {选择节点数较少且队列未空、未满的方向先扩展} if (tail[0]<=tail[1]) and not((head[0]>=tail[0])or(tail[0]>=maxn)) then expand(0); if (tail[1]<=tail[0]) and not((head[1]>=tail[1])or(tail[1]>=maxn)) then expand(1); {如果一方搜索终止,继续另一方的搜索,直到两个方向都终止} if not((head[0]>=tail[0])or(tail[0]>=maxn)) then expand(0); if not((head[1]>=tail[1])or(tail[1]>=maxn)) then expand(1); Until ((head[0]>=tail[0])or(tail[0]>=maxn)) And ((head[1]>=tail[1])or(tail[1]>=maxn)) 2.expand(st:0..1)程序代码如下: inc(head[st]; 取出队列当前待扩展的结点 c[st,head[st]] for i:=1 to maxk do begin if tail[st]>=maxn then exit; inc(tail[st]); 产生新结点; check(st);{检查新节点是否重复} end; 3.check(st:0..1)程序代码:

基础算法习题集(李波于 2007 年 7 月收集整理)

for i:=1 to tail[st]-1 do if c[st,tail[st]]^.*=c[st,i]^.* then begin dec(tail[st]);exit end; bool(st);{如果节点不重复,再判断是否到达目标状态} 4.bool(st:0..1)程序代码: for i:=1 to tail[1-st] do if c[st,tail[st]]^.*=c[1-st,i]^.* then print(st,tail[st],i); {如果双向搜索相遇(即得到同一节点),则输出结果} 5.print(st,tail,k)程序代码: if st=0 then begin print0(tail);print1(k) end; else begin print0(k);print1(tail) end; 6.print0(m)程序代码: if m<>0 then begin print(c[0,m]^.f);输出 c[0,m]^.* end; {输出正方向上产生的结点} 7.print1(m)程序代码; n:=c[1,m]^.f while m<>0 begin 输出 c[1,n]^.*; n:=c[1,n]^.f; end {输出反方向上产生的结点} [本题程序] program ex7_3_1; const maxn=4000; type jid=record str:string[9]; f:0..maxn; dep:byte; end; bin=0..1; var c:array[0..1,1..maxn] of ^jid; head,tail:array[0..1] of integer; start,goal:string[9]; procedure init; var i,j:integer; begin start:='283164705'; goal:='123804765'; for i:=0 to 1 do for j:=1 to maxn do new(c[i,j]); c[0,1]^.str:=start; c[0,1]^.f:=0; c[0,1]^.dep:=0; c[1,1]^.str:=goal; c[1,1]^.f:=0; c[1,1]^.dep:=0; for i:=0 to 1 do

基础算法习题集(李波于 2007 年 7 月收集整理)

begin head[i]:=0;tail[i]:=1;end; end; procedure print(st:bin;tail,k:integer); procedure print0(m:integer); begin if m<>0 then begin print0(c[0,m]^.f);writeln(c[0,m]^.str) end; end; procedure print1(m:integer); var n:integer; begin n:=c[1,m]^.f; while n<>0 do begin writeln(c[1,n]^.str); n:=c[1,n]^.f end; end; begin if st=0 then begin writeln('step=',c[0,tail]^.dep+c[1,k]^.dep); print0(tail); print1(k);end else begin writeln('step=',c[0,k]^.dep+c[1,tail]^.dep); print0(k); print1(tail); end ; halt; end; procedure check(st:bin); procedure bool(st:bin); var i:integer; begin for i:=1 to tail[1-st] do if c[st,tail[st]]^.str=c[1-st,i]^.str then print(st,tail[st],i); end; var i:integer; begin for i:=1 to tail[st]-1 do if c[st,tail[st]]^.str=c[st,i]^.str then begin dec(tail[st]);exit end; bool(st); end; procedure expand(st:bin); var i,p0,p1,d:integer; str0,str1:string[9]; begin inc(head[st]); str0:=c[st,head[st]]^.str; d:=c[st,head[st]]^.dep;

基础算法习题集(李波于 2007 年 7 月收集整理)

p0:=pos('0',str0); for i:=1 to 4 do begin if tail[st]>=maxn then exit; p1:=p0+2*i-5; if (p1 in [1..9]) and not ((p0=3) and (p1=4))and not((p0=4)and (p1=3)) and not((p0=6)and(p1=7))and not((p0=7)and(p1=6)) then begin inc(tail[st]); str1:=str0; str1[p0]:=str1[p1]; str1[p1]:='0'; c[st,tail[st]]^.str:=str1; c[st,tail[st]]^.f:=head[st]; c[st,tail[st]]^.dep:=d+1; check(st); end; end; end; begin init; check(0); repeat if (tail[0]<=tail[1]) and not((head[0]>=tail[0])or(tail[0]>=maxn)) then expand(0);

相关文章:
对数运算基础练习题
对数运算基础练习题_高一数学_数学_高中教育_教育专区。适合对数运算最初接触者,...对数运算习题 2页 1下载券 对数计算练习题 2页 5下载券 对数与对数运算练习...
第8章怎样研究算法排序算法示例练习题答案解析
基本的算法, 很多复杂算法都是以排序为基础进行...即子集合数 不应该超过(Bmemory-2) ;所以待排序...排序算法习题 6页 免费 全排列算法解析(完整版) 16...
算法分析与设计习题集
算法分析与设计习题集_IT/计算机_专业资料。算法分析与设计习题集基础篇 1、 算法有哪些特点?它有哪些特征?它和程序的主要区别是什么? 2、 算法的时间复杂度指的...
高二导数计算练习题(基础题)
高二导数计算练习题(基础题)_高二数学_数学_高中教育_教育专区。一、基本初等函数的导数公式: (1)f(x)=C(C 为常数) ,则 f ’(x)=___ (3)f(x)=sinx...
F算法与程序框图练习(基础题有答案)
F算法与程序框图练习(基础题有答案)_数学_高中教育_教育专区。算法与程序框图练习 A、处理框内 A、流程线 B、判断框内 B、注释框 ( ) 班级 姓名 ) D、...
matlab基础练习题(带答案)
matlab基础练习题(带答案)_从业资格考试_资格考试/认证_教育专区。Matlab 基础...[my,idx]=min(y) x(idx) 数值计算 1、 在 MATLAB 中,A 是一个 10×...
算法与程序设计习题集与考点整理
第一学期算法与程序设计习题集一、常见的运算 类别 算术运算符 关系运算符 逻辑...算法的三种基本结构:顺序结构、分支结构、循环结构 (1)顺序结构 顺序结构按照自...
基础工程习题集附答案2012
基础工程习题集附答案2012_其它考试_资格考试/认证_教育专区。基础工程 复习 试卷...A.做在天然地基上、埋置深度小于 5m 的一般基础; B.在计算基础的侧面摩...
MATLAB矩阵运算基础练习题
MATLAB矩阵运算基础练习题_理学_高等教育_教育专区。第2章 MATLAB 矩阵运算基础 ...? ? ? 2.5 计算矩阵 ? ? 3 7 4 ? 与 ? 6 7 9 ? 之和,差,积,...
算法分析与设计复习题及参考答案
4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归调用,将递归算法转化...①画出子集和问题的解空间树; ②该树运用回溯算法,写出依回溯算法遍历节点的...
更多相关标签: