算法题及源程序.docx
《算法题及源程序.docx》由会员分享，可在线阅读，更多相关《算法题及源程序.docx（48页珍藏版）》请在冰点文库上搜索。
算法题及源程序
算法设计题集
第一章算法初步
第一节程序设计与算法
一、算法
算法是解决问题方法的精确描述，但是并不是所有问题都有算法，有些问题经研究可行，则相应有算法，但这并不是说问题就有结果。
上述的“可行”，是指对算法的研究。
１．待解问题的描述
待解问题表述应精确、简练、清楚，使用形式化模型刻划问题是最恰当的。
例如，使用数学模型刻划问题是最简明、严格的，一旦问题形式化了，就可依据相应严格的模型对问题求解。
２．算法设计
算法设计的任务是对各类具体问题设计良好的算法及研究设计算法的规律和方法。
常用的算法有：
穷举搜索法、递归法、回溯法、贪心法、分治法等。
３．算法分析
算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论各种复杂度，以探讨某种具体算法适用于哪类问题，或某类问题宜采用哪种算法。
算法的复杂度分时间复杂度和空间复杂度。
．时间复杂度：
在运行算法时所耗费的时间为f（n）（即 n的函数）。
．空间复杂度：
实现算法所占用的空间为g（n）（也为n的函数）。
称O（f（n））和O（g（n））为该算法的复杂度。
二、程序设计
１．程序
程序是对所要解决的问题的各个对象和处理规则的描述，或者说是数据结构和算法的描述，因此有人说，数据结构＋算法＝程序。
２．程序设计
程序设计就是设计、编制和调试程序的过程。
３．结构化程序设计
结构化程序设计是利用逐步求精的方法，按一套程式化的设计准则进行程序的设计。
由这种方法产生的程序是结构良好的。
所谓“结构良好”是指：
（１）易于保证和验证其正确性；
（２）易于阅读、易于理解和易于维护。
按照这种方法或准则设计出来的程序称为结构化的程序。
“逐步求精”是对一个复杂问题，不是一步就编成一个可执行的程序，而是分步进行。
．第一步编出的程序最为抽象；
．第二步编出的程序是把第一步所编的程序（如过程、函数等）细化，较为抽象；
．……
．第i步编出的程序比第i-1步抽象级要低；
．……
．直到最后，第n步编出的程序即为可执行的程序。
所谓“抽象程序”是指程序所描述的解决问题的处理规则，是由那些“做什么”操作组成，而不涉及这些操作“怎样做”以及解决问题的对象具有什么结构，不涉及构造的每个局部细节。
这一方法原理就是：
对一个问题（或任务），程序人员应立足于全局，考虑如何解决这一问题的总体关系，而不涉及每局部细节。
在确保全局的正确性之后，再分别对每一局部进行考虑，每个局部又将是一个问题或任务，因而这一方法是自顶而下的，同时也是逐步求精的。
采用逐步求精的优点是：
（１）便于构造程序。
由这种方法产生的程序，其结构清晰、易读、易写、易理解、易调试、易维护；
（２）适用于大任务、多人员设计，也便于软件管理。
逐步求精方法有多种具体做法，例如流程图方法、基于过程或函数的方法。
[例]求两自然数,其和是667,最小公倍数与最大公约数之比是120:
1（例如（115,552）、（232,435））。
[解]两个自然数分别为m和667-m（2≤m≤333）。
处理对象：
m（自然数）、l（两数的最小公倍数）、g（两数的最大公约数）。
处理步骤：
对m从２到333检查l与g的商为120,且余数为0时,打印m与667-m。
第一层抽象程序：
ProgramTwoNum;
Varm,l,g:
integer;
Beginform:
=2to333do
beginl:
=lcm（m,667-m）;｛求最小公倍数｝
g:
=gcd（m,667-m）；｛求最大公约数｝
if（l=g*120）and（lmodg=0）then
writeln（m:
5,667-m:
5）;
end;
End.
第二层考虑函数lcm（最小公倍数）、gcd（最大公约数）的细化。
最大公约数问题是对参数a、b，找到一个数i能整除a与b，i就是gcd的函数值。
Functiongcd（a,b:
integer）:
integer;
vari:
integer;
beginfori:
=adownto1do
ifnot（（amodi=0）or（bmodi=0））thengcd:
=i;
end;
而最小公倍数的计算是：
若干个b之和，若能被a整除，则该和便是a、b的最小公倍数。
Functionlcm（a,b:
integer）:
integer;
vari:
integer;
begini:
=b;
whileimoda=0doi:
=i+b;
lcm:
=i;
end;
第二节编程入门题例
编程入门题
（一）
1、位数对调：
输入一个三位自然数，把这个数的百位与个位数对调，输出对
调后的数。
例如：
Input3bitnatruedata:
234n=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-}{输入的数据为整数}
programThreebit;
varx,n,a,b,c:
INTEGER;
BEGINwrite（'Input3bitnaturedata:
'）;readln（n）;
IF（n>99）and（n<1000）then
begina:
=nDIV100;{求百位数}
b:
=（n-a*100）DIV10;{求十位数}
c:
=nmod10;{求个位数}
x:
=c*100+b*10+a;{得新数X}
writeln（'Number=',x:
3）;
end
ELSEwriteln（'Inputerror!
'）;
END.
2、求三角形面积：
给出三角形的三个边长为a，b，c，求三角形的面积。
提示：
根据海伦公式来计算三角形的面积：
S＝
；Area＝
[解]1．输入的三角形三边长a,b,c要满足“任意两边长的和大于第三边长”。
2．按海伦公式计算：
s=（a+b+c）/2；x=s*（s-a）*（s-b）*（s-c）这时若x>=0，则求面积：
area=
，并输出area的值。
[程序]PROGRAMhl;VARa,b,c,s,x,area:
real;BEGINwrite（'Inputa,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
Begins:
=（a+b+c）/2;x:
=s*（s-a）*（s-b）*（s-c）;
Ifx>=0ThenBeginArea:
=SQRT（x）;writeln（'Area=',area:
8:
5）;End;
End
Elsewriteln（'Inputerror!
'）
END.
3、模拟计算器：
试编写一个根据用户键入的两个操作数和一个运算符，由计算机输出运算结果的程序。
这里只考虑加（＋）、减（－）、乘（＊）、除（／）四种运算。
例１：
Inputx,y：
153
Inputoperator（+,-,*,/）:
＋
15.00+3.00=18.00
例２：
Inputx,y：
50
Inputoperator（+,-,*,/）:
／
divideiszero!
[解]该题关键是判断输入的两数是作何种运算（由输入的运算符operator决定，如'+'、'-'、'*'、'/'分别表示加、减、乘、除法的运算）。
其中要进行除（/）运算时,要先进行合法性检查，即除数不能为0。
[程序]
PROGRAMOper;
Varx,y,n:
real;
operator:
char;
Begin
write（'Inputx,y:
'）;readln（x,y）;
write（'Inputoperator:
'）;readln（operator）;
Caseoperatorof
'+':
n:
=x+y;{加法运算}
'-':
n:
=x-y;{减法运算}
'*':
n:
=x*y;{乘法运算}
'/':
Ify=0then{除法运算}
beginwriteln（'Divideiszero!
'）;halt;end
Elsen:
=x/y;
elsebeginwriteln（'Inputoperatorerror!
'）;halt;end;
End;
writeln（x:
6:
2,operator,y:
6:
2,'=',n:
6:
2）;
End.
4、念数字：
编一个“念数字”的程序，它能让计算机完成以下工作：
当你输入一个０至99之间的数后，计算机就会用汉字拼音印出这个数的念结束。
例１：
Inputdata:
35SANSHIWU
例２：
Inputdata:
0
LING
如果输入的数不在０到99之间，就印出“CUOLE”（错了），请求重新输入。
注：
为了使不熟悉汉语拼音的同学也能做这个题，把“零，一，二，三，……，九，十”的拼音法写在下面。
零LING一YI二ER三SAN四SHI五WU
六LIU七QI八BA九JIU十SHI
[解]输入数在0～99之间，若x为两位数则拆分为十位数、个位数。
然后调用念
数过程Readdigit用汉字拼音印出各位数（0～9）的念。
[程序]
{$I-}
ProgramNinShu;
Varx,a,b:
Integer;
ProcedureReadDigit（n:
Integer）;{念数过程:
n=0～9}
Begin
Casenof
0:
write（'LING'）;
1:
write（'YI'）;
2:
write（'ER'）;
3:
write（'SAN'）;
4:
write（'SHI'）;
5:
write（'WU'）;
6:
write（'LIU'）;
7:
write（'QI'）;
8:
write（'BA'）;
9:
write（'JIU'）;
End;
End;{ReadDigit}
Begin{main}
Repeatwrite（'Inputdata:
'）;readln（x）;
if（x<0）or（x>99）thenwriteln（'CuoLe'）;
Until（x>=0）and（x<=99）;
If（x>=0）and（x<=9）thenReadDigit（x）{调用念数过程}
ElseBegina:
=xDIV10;b:
=xmod10;{位数拆分}
Ifa<>1thenReadDigit（b）；
writeln（'Shi'）;
ifb<>0thenReadDigit（b）;
End;
writeln;
End.
5、数列找数：
数组A（N）的各下标变量中Ｎ个互不相等的数，键盘输入正整数Ｍ（Ｍ≤Ｎ），要求打印数组中第Ｍ大的下标变量的值。
例如：
数组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
运行结果：
INPUTANNUMBER:
３A（5）=38（即第３大的数是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的下标值）即为所求。
[程序]ProgramMax01;{冒泡排序法}vari,j,n,m,x:
integer;A,B:
ARRAY[1..100]ofinteger;
ProcedureInit;{读数初始化过程}Vari,j:
integer;fd:
boolean;Begin
write（'InputN:
'）;readln（N）;{读入N}ifN<1thenbeginwriteln（'Inputerror!
'）;halt;end;
write（'Input',N:
3,'Data:
'）;
Fori:
=1tonDo
beginread（A[i]）;B[i]:
=i;end;{读入A[i],且B[i]初值置为i}
Readln;i:
=1;fd:
=false;{数组中的数有相同的标志}whileNOTfdand（i<=N-1）doBeginj:
=i+1;WhileNOTfdand（j<=N）do
beginfd:
=A[i]=A[j];{若A[i]=A[j]，则fd=true；否则fd=false}
j:
=j+1;
end;
i:
=i+1;
End;
Iffdthen{fd为True，则表示数组中至少有两个相等的数}
beginwriteln（'Moreequalnumber!
'）;halt;end;
write（'InputM:
'）;readln（M）;
IfM>Nthen{表明所找的数M已超过输入数的总数N}
beginwriteln（'Inputerror!
'）;halt;end;
End;{Init}
Begin{MAIN}Init;{读数过程}
fori:
=1toN-1do{冒泡排序}forj:
=i+1toNdoifA[i]=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
1
2
3
4
5
6
7
8
9
10
A数组
16
57
20
19
38
41
6
13
25
32
B数组
8
1
6
7
3
2
10
9
5
4
例题中M=3,由表三知B[5]=3=M，A[5]=38即为所求。
[程序]Vari,j,k,m,n:
integer;A,B:
ARRAY[1..100]ofinteger;
ProcedureInit;
{具体程序见解法一}Begin{MAIN}
Init;{读数过程}
fori:
=1tondo
beginB[i]:
=1;{B[i]初始值为1，即假定所有A[i]都可能为最大数}
forj:
=1tondo
if（i<>j）and（A[i]=B[i]+1;
ifB[i]=Mthenk:
=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：
判断是否已找到所求数的标志}
３．当（fd=false）and（I<=n）时，做
（1）B[i]=1{表示数列中比A[i]小的数的总个数+1，初始值为1}
（2）j=1
（3）当j<=n时，做
①如果（i<>j）and（A[i]②j=j+1
（4）如果B[i]=M，则输出所求：
A[i]，且fd=true。
（5）i=i+1
4.程序结束。
[主程序]
Begin{MAIN}
Init;{读数过程}
i:
=1;fd:
=false;{找到所求解的标志值}
whilenotfdand（i<=N）do
beginB[i]:
=1;{B[i]初始值为1，即假定所有的A[i]都可能为最大的数}
j:
=1;
whilej<=ndo
begin
if（i<>j）and（A[i]=B[i]+1;
j:
=j+1;
end;{whilej}
ifB[i]=Mthen{找到所求便输出，并退出比较}
beginwriteln（'A（',i,'）=',A[i]）;fd:
=true;end;
i:
=i+1;
end;{whilei}
End.
6、数制转换：
编程输入十进制Ｎ（Ｎ：
-32767～32767），请输出它对应的二
进制、八进制、十六进制数。
例如：
INPUTN（-32767～32767）:
222
222TURNINTO2：
11011110
222TURNINTO8：
336
222TURNINTO16：
DE
[解]十进制数转化为某进制数的转换方法，如下图示：
除x逆序取余法
十进制数x进制数（x=2,8,16等）
例中n=222（十进制数），转换成x进制数的过程如下图示：
（1）十进制数→二进制数
（2）十进制数→八进制数（3）十进制数→十六进制数
x=2222被除数（最大商）x=82226x=16222E…（14）10
21110低位82731613D…（13）10
2501逆8330
2250余序0
2120数取
260余
231数
211高位
0（最大商为0时停止）
将每次所得的余数由下至上排列（逆序取余数），即有：
（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
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
字串A
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
下标i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
由上表得：
（222）10=（1100010）2=（336）8=（DE）16
[程序]
{$I-}
Programjj;
varN,k:
integer;
B:
array[1..1000]ofinteger;
Procedurechg10（N,x:
integer）;{将十进制数N转换成x进制数}
Begink:
=0;{转换后的x进制数位的长度}
whileN<>0do{N不为0时}
beginB[k]:
=Nmodx;{除以x取余数}
N:
=NDivx;{取最大商N}
k:
=k+1;{x进制数位加1}
end;
end;{chg10}
ProcedureSput（N,x:
integer）;{进制数输出}
VARi:
integer;A:
string;
BeginA:
='0123456789ABCDEF';{表示x进制数的位数串}
write（N:
6,'Turninto',x:
2,':
'）;
fori:
=k-1downto0dowrite（copy（A,B[i]+1,1））;{逆序输出x进制数}
writeln;
end;{Sput}
begin{MAIN}
write（'InputN（-32767to32767）:
'）;readln（N）;
if（N<=-32767）or（N>32767）then
beginwriteln（'Inputerror!
'）;halt;end;
chg10（N,2）;Sput（N,2）;{十进制数转换成2进制数，并输出}
chg10（N,8）;Sput（N,8）;{十进制数转换成8进制数，并输出}
chg10（N,16）;Sput（N,16）;{十进制数转换成16进制数，并输出}
end._
编程入门题
（二）
1、求素数：
求2至N（2≤N≤500）之间的素数。
例如：
输入：
N=100
输出：
23571113
171923293137
414347535961
717379838997
total=24{表示2至100之间的素数有24个}
[解法一]素数是指除1及本身以外不能被其他数整除的自然数。
下面介绍用穷举法求素数。
1．2是素数；t=0；
2．I=2～n，则：
（1）如果i是素数，则其必须是奇数且不能被2～√i中的任一个数整除。
（2）如果I是素数，则输出该素数且计数器t=t+1；
3．输出2～N之间素数的总数：
total=t;
4．程序结束
[程序]
programexa;usescrt;vari,k,n,w,t:
in
升级会员 