算 法 设 计 题 集
第一章 算法初步
第一节 程序设计与算法
一、算法
算法是解决问题方法的精确描述,但是并
不是所有问题都有算法,有些问题经研究可行,
则相应有算法,但这并不是说问题就有结果。
上述的“可行”,是指对算法的研究。
1.待解问题的描述
待解问题表述应精确、简练、清楚,使用
形式化模型刻划问题是最恰当的。例如,使用
数学模型刻划问题是最简明、严格的,一旦问
题形式化了,就可依据相应严格的模型对问题
求解。
2.算法设计
算法设计的任务是对各类具体问题设计良
好的算法及研究设计算法的规律和方法。常用
的算法有:穷举搜索法、递归法、回溯法、贪
心法、分治法等。
3.算法分析
算法分析的任务是对设计出的每一个具体
的算法,利用数学工具,讨论各种复杂度,以
探讨某种具体算法适用于哪类问题,或某类问
题宜采用哪种算法。
算法的复杂度分时间复杂度和空间复杂
度。
.时间复杂度:在运行算法时所耗费的时
间为 f(n)(即 n 的函数)。
.空间复杂度:实现算法所占用的空间为
g(n)(也为 n 的函数)。
称 O(f(n))和 O(g(n))为该算法的复杂度。
二、程序设计
1.程序
程序是对所要解决的问题的各个对象和处
理规则的描述,或者说是数据结构和算法的描
述,因此有人说,数据结构+算法=程序。
2.程序设计
程序设计就是设计、编制和调试程序的过
程。
3.结构化程序设计
结构化程序设计是利用逐步求精的方法,
按一套程式化的设计准则进行程序的设计。由
这种方法产生的程序是结构良好的。所谓“结
构良好”是指:
(1)易于保证和验证其正确性;
(2)易于阅读、易于理解和易于维护。
按照这种方法或准则设计出来的程序称为
结构化的程序。
“逐步求精”是对一个复杂问题,不是一步
就编成一个可执行的程序,而是分步进行。
.第一步编出的程序最为抽象;
.第二步编出的程序是把第一步所编的程
序(如过程、函数等)细化,较为抽象;
.……
.第 i 步编出的程序比第 i-1 步抽象级要
低;
.……
.直到最后,第 n 步编出的程序即为可执
行的程序。
所谓“抽象程序”是指程序所描述的解决
问题的处理规则,是由那些“做什么”操作组
成,而不涉及这些操作“怎样做”以及解决问
题的对象具有什么结构,不涉及构造的每个局
部细节。
这一方法原理就是:对一个问题(或任务),
程序人员应立足于全局,考虑如何解决这一问
题的总体关系,而不涉及每局部细节。在确保
全局的正确性之后,再分别对每一局部进行考
虑,每个局部又将是一个问题或任务,因而这
一方法是自顶而下的,同时也是逐步求精的。
采用逐步求精的优点是:
(1)便于构造程序。由这种方法产生的
程序,其结构清晰、易读、易写、易理解、易
调试、易维护;
(2)适用于大任务、多人员设计,也便
于软件管理。
逐步求精方法有多种具体做法,例如流程
图方法、基于过程或函数的方法。
[例]求两自然数,其和是 667,最小公倍数
与最大公约数之比是 120:1(例如(115,552) 、
(232,435))。
[解]两个自然数分别为 m和 667-m(2≤m≤
333)。
处理对象:m(自然数)、l(两数的最小公倍
数)、g(两数的最大公约数)。
处理步骤:对 m 从 2 到 333 检查 l 与 g 的商
为 120,且余数为 0 时,打印 m 与 667-m 。
第一层抽象程序:
Program TwoNum;
Var m,l,g:integer;
Begin for m:=2 to 333 do
begin l:=lcm(m,667-m); {求最小
公倍数}
g:=gcd(m,667-m); {求最大公约数}
if (l=g*120)and(l mod g=0) then
writeln(m:5,667-m:5);
end;
End.
第二层考虑函数
lcm(最小公倍数)、gcd
(最大公约数)的细化。
最大公约数问题是对参数 a、b,找到一个
数 i 能整除 a 与 b,i 就是 gcd 的函数值。
Function
gcd(a,b:integer):integer;
var i:integer;
begin for i:=a downto 1 do
if not((a mod i=0)or(b mod
i=0)) then gcd:=i;
end;
而最小公倍数的计算是:若干个 b 之和,
若能被 a 整除,则 该 和 便 是 a 、b 的最小公倍数。
Function
lcm(a,b:integer):integer;
var i:integer;
begin i:=b;
while i mod a=0 do i:=i+b;
lcm:=i;
end;
第二节 编程入门题例
编
编
程
程
入
入
门
门
题
题
(
(
一
一
)
)
1
、位数对调
:输入一个三位自然数,把这个数的百位与个位数对调,输出对
调后的数。例如:Input 3 bit natrue data:234
n=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
[程序]
{$I-} {输入的数据为整数}
program Threebit;
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.
2
、求三角形面积:
给出三角形的三个边长为 a,b,c,求三角形的面积。
提示:根据海伦公式来计算三角形的面积:
S=
2
cba
+
+
;Area= ))()(( cSbSaSS −−−
[解]1.输入的三角形三边长 a,b,c 要满足“任意两边长的和大于第三边长”。
2.按海伦公式计算:s=(a+b+c)/2;x=s*(s-a)*(s-b)*(s-c)
这时若 x>=0,则求面积:area= x ,并输出 area 的值。
[程序]
PROGRAM hl;
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
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.
3
、模拟计算器:
试编写一个根据用户键入的两个操作数和一个运算符,由计算机输出运算结果
的程序。这里只考虑加(+)、减(-)、乘(*)、除(/)四种运算。
例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 Oper;
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.
4
、念数字:
编一个“念数字”的程序,它能让计算机完成以下工作:当你输入一个0至 99 之
间的数后,计算机就会用汉字拼音印出这个数的念结束。
例1:Input data:35
SAN SHI WU
例2:Input data:0
LING
如果输入的数不在0到 99 之间,就印出“CUO LE”(错了),请求重新输入。
注:为了使不熟悉汉语拼音的同学也能做这个题,把“零,一,二,三,……,九,十”的
拼音法写在下面。
零 LING 一 YI 二 ER 三 SAN 四 SHI 五 WU
六 LIU 七 QI 八 BA 九 JIU 十 SHI
[解]输入数在 0~99 之间,若 x 为两位数则拆分为十位数、个位数。然后调用念
数过程 Readdigit 用汉字拼音印出各位数(0~9)的念。
[程序]
{$I-}
Program NinShu;
Var x,a,b:Integer;
Procedure ReadDigit(n:Integer);{念数过程:n=0~9}
Begin
Case n of
0:write('LING ');
1:write('YI ');
2:write('ER ');
3:write('SAN ');
4:write('SHI ');
http://chzg99.blogdriver.com
5:write('WU ');
6:write('LIU ');
7:write('QI ');
8:write('BA ');
9:write('JIU ');
End;
End; {ReadDigit}
Begin {main}
Repeat write('Input data:');readln(x);
if (x<0) or (x>99) then writeln('Cuo Le');
Until (x>=0)and(x<=99);
If (x>=0)and(x<=9) then ReadDigit(x) {调用念数过程}
Else Begin a:=x DIV 10; b:=x mod 10; {位数拆分}
If a<>1 then ReadDigit(b);
writeln(' Shi');
if b<>0 then ReadDigit(b);
End;
writeln;
End.
5
、数列找数
:数组 A(N)的各下标变量中N个互不相等的数,键盘输入正整数M(M≤N),要
求打印数组中第M大的下标变量的值。
例如:数组 A(10)的数据为:
A(1)
A(2)
A(3)
A(4)
A(5) A(6) A(7) A(8)
A(9) A(10)
16 57 20 19 38 41 6 13
25 32
运行结果:INPUT AN NUMBER:3
A(5)=38 (即第3大的数是 A(5)=38)
[解]该题要从 N 个互不相等的数中找第 M 大的值。有以下两种解法:
解法一:初始时:A 数组存放 N 个互不相等的数;B 数组用于存放数组 A 的下标。见下表一。
下标值 i 1 2 3 4 5 6 7 8
9 10
数组 A 16
57 20 19 38 41 6 13
25 32
数组 B 1 2 3 4 5 6 7 8
9 10
降序处理(冒泡排序法):
数组 A 的元素由大到小进行排序,同时数组 B 的元素排列也随之变化。
下标值 I 1 2 3 4 5 6 7 8
9 10
数组 A 57
41 38 32 25 20 19 16
13 6
数组 B(原
数组 A 的
下标)
2
6
5
10
9
3
4
1
8
7
例题中 M=3,由表二知 A[3]=38,B[3]=B[M]=5(原数组 A 的下标值)即为所求。
[程序]
Program Max01;{冒泡排序法}
var i,j,n,m,x:integer;
A,B:ARRAY[1..100] of integer;
Procedure Init; {读数初始化过程}
Var i,j:integer; fd:boolean;
Begin