pascal入门算法.doc

算 法 设 计 初步与典型试题枚举搜索31、枚举数字33、百钱买百鸡44、分书问题5逻辑判断65、谁是小偷66、质量评比67、谁获冠军78、四大淡水湖8递推法89、【菲波纳葜数列】810、递推关系的应用“杨辉三角”911、蜜蜂爬行1013、铺骨牌（2000年 全国联赛初赛）11倒退1114、贮油点11枚举素数1315、素数1316、歌德巴赫猜想1417、计算真因子14筛法1518、求素数（95年，全国联赛初赛）1519、用筛法统计楼梯级数16最大公约数与最小公倍数1720.求两个正整数的最大公约数1721、求两个正整数的最小公倍数18进制转换1822、十进制转换为n进制1923. N进制数转化为十制数20循环问题2024、猴子选大王2025、狐狸捉兔子2126、约瑟环22数组2327、求递增和递减子序列2428、马鞍数2529、数学黑洞617426方阵填数2730、方阵填数2731、蛇形矩阵：28字符数组与字符串30一、定义30二、字符串的常用内部函数和过程30三、字符数组与字符串应用3136、寻找单词3337、【题目】从键盘输入一个长度不超过40的字符串,按要求进行删除.34数组与字符串应用3638、高精度加法程序3639、回文算术37递归算法3840、 利用递归调用手段编程计算N!。3941、 利用递归调用技术求菲波纳葜数列的第N项。4042、输入一串以.结束的字符，按逆序输出。4143、用递归函数求最大公约数4244、汉诺塔42嵌套4445、三齿轮问题44搜索算法（回溯、深度优先）4546、八皇后问题4547、求N个数的全排列4748、跳马问题（骑士遍历）4749、深度优先搜索解分书问题5050、四色问题。（图论中的搜索问题）53 枚举搜索枚举指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判断哪些是无用的，哪些是有用的，能使命题成立即为其解。一般思路：a、对命题建立正确的数学模型，b、根据命题确定数学模型中各变量的范围（即可能解的范围），c、利用循环语句、条件语句逐步求解或证明。1、枚举数字【题目】编程找出四位数abcd中满足下述关系的数： (ab+cd)(ab+cd)=abcd【算法】搜索问题：10009999关键是边枚举边分离高位、低位，后判断var: I,m,n,k:integer;begin for I:=1000 to 9999 do beginm:=I div 100;n:=I-m*100;k:=(m+n)*(m+n);if k:=I then writeln(I); end;end.2、钞票换硬币【题目】把一元钞票换成一分、二分、五分硬币（每种至少一枚），有哪些种换法？【答案】461种【参考程序】 var i,j,k,total:integer; begin total:=0; 总数设为 for i:=1 to 99 do i:二分硬币最多99枚 for j:=1 to 49 do j:二分硬币最多49枚 for k:=1 to 19 do k:五分硬币最多19枚 if i*1+j*2+k*5=100 then begin writeln(i:3,j:3,k:3); inc(total); 总数加 end; writeln(total); readln; end.3、百钱买百鸡【题目】一只公鸡值元，一只母鸡值元，只小鸡值元，现用一百元要买一百只鸡， 问有什么方案？【答案】四种方案： 公鸡 母鸡 小鸡 var I,j,k,s:integer; BeginS:=0; For I:=0 to 20 do For j:=0 to 33 do For k:=0 to 300 do Begin if (5*I+3*j+1/3*k)=100and(I+j+k=100) Then write(I,j,k); S:=s+1; End; Write(s:5);End.4、分书问题【题目】有、五本书，要分给张、王、刘、 赵、钱五位同学，每人只能选一本, 事先让每人把自 己喜爱的书法填于右表，编程找出让每人都满意的方 案。 张 【答案】四种方案 王 张 王 刘 赵 钱 刘 赵 钱 【参考程序】 var z,w,l,zh,q,total:byte; procedure output; begin writeln(zhang:,chr(z+64); writeln(wang:,chr(w+64); writeln(liu :,chr(l+64); writeln(zhao:,chr(zh+64); writeln(qian:,chr(q+64); writeln; inc(total); end; begin total:=0; for z:=3 to 4 do for w:=1 to 5 do if (w3) and (w4) then for l:=2 to 3 do for zh:=1 to 4 do if zh3 then for q:=2 to 5 do if (q3) and (q4) then begin if z+w+l+zh+q=15 then if z*w*l*zh*q=120 then output; end; write(total); end.逻辑判断【逻辑判断】根据条件利用取值函数ord对条件进行取值，然后利用循环语句穷举。5、谁是小偷【题目】有、四名偷窃嫌疑犯，其中一人是小偷，审问中，说：“我 不是小偷”，说：“是小偷”，说：“小偷肯定是”，说：“ 在冤枉人”，有三人说真话，一人说假话，问到底谁是小偷？【参考程序】 var thief:char; begin for thief:=A to D do if ord(thiefA)+ord(thief=C)+ord(thief=D)+ ord(thiefD)=3 then writeln(The Thief is : ,thief); end.6、质量评比【题目】家工厂的产品在一次评比中分获，在公布结果前，已知 厂产品肯定不是第二、三名，五厂代表猜测评比结果， 厂的代表说：厂一定能获得第一名。 厂的代表说：我厂的产品可能获第二名。 厂的代表说：厂的产品质量最次。 厂的代表说：厂的产品不是最好的。 厂的代表说：厂的产品会获得第一名。 公布结果后，证明只有产品获第一名和第二名的两个厂的代表猜对了。 求个厂产品各获第几名。【答案】 【参考程序】 var a,b,c,d,e:byte; begin for a:=1 to 5 do for b:=1 to 5 do for c:=1 to 5 do for d:=1 to 5 do begin e:=15-a-b-c-d; if (e2) and (e3) and (a*b*c*d*e=120) then if(ord(e=1)+ord(b=2)+ord(a=5)+ ord(c1)+ ord(d=1)=2) and (ord(e=1) and (a=1) or (a=2)+ ord(b=2) and (b=1) or (b=2)+ ord(a=5) and (c=1) or (c=2)+ ord(c1) and (d=1) or (d=2)+ ord(d=1) and (e=1) or (e=2) =2) then writeln(a:,a, b:,b, c:,c, d:,d, e:,e); end; end.7、谁获冠军【题目】甲乙丙丁戊五个人在运动会上分获百米、二百米、跳高、跳远和铅球冠军，有 四个人猜测比赛结果： 说：乙获铅球冠军，丁获跳高冠军。 说：甲获百米冠军，戊获跳远冠军。 说：丙获跳远冠军，丁获二百米冠军。 说：乙获跳高冠军，戊获铅球冠军。 其中每个人都只说对一句，说错一句。求五人各获哪项冠军。【算法】用1,2,3,4,5分别代表百米、二百米、跳高、跳远和铅球个项目，用a,b,c,d,e 分别代表五人。如b=3 表示乙获跳高冠军。用多重循环穷举出来。【答案】甲 乙 丙 丁 戊 【参考程序】 var a,b,c,d,e:byte; begin for a:=1 to 5 do for b:=1 to 5 do for c:=1 to 5 do for d:=1 to 5 do begin e:=15-a-b-c-d; if (ord(b=5)+ord(d=3)=1) and (ord(a=1)+ord(e=4)=1) and (ord(c=4)+ord(d=2)=1) and (ord(b=3)+ord(e=5)=1) and (a*b*c*d*e=120) then writeln(a:,a,b:,b,c:,c,d:,d,e:,e); end; end.8、四大淡水湖【题目】四个学生上地理课时，回答四大淡水湖，这样说。甲说：“最大洞庭湖，最小洪泽湖，鄱阳湖第三” ；乙说：“最大洪泽湖，最小洞庭湖，鄱阳湖第二，太湖第三” ；丙说：“最小洪泽湖，洞庭湖第三” ；丁说：“最大鄱阳湖，最小太湖，洪泽湖第二，洞庭湖第三” 。其中每个学生仅答对一个。请判断各个湖的大小。【参考程序】Var dong,hong,bo,tai:integer;Begin For dong:=1 to 4 do For hong:=1 to 4 do If hongdong then For bo:=1 to 4 do If (hongbo) and (bodong) then Begin Tai:=10-dong-hong-bo; If(ord(dong=1)+ord(hong=4)+ord(bo=3)=1) and(ord(hong=4)+ord(dong=4+ord(bo=2)+ord(tai=3)=1) and (ord(hong=4)+ord(dong=3)=1)and (ord(bo=1)+ord(tai=4)+ord(hong=2)+ord(dong=3)=1)Then writeln(dong,hong,bo,tai);End;Readln;End.递推法递推法：是一种重要的数学方法，特点已知条件和所求问题总存在一定的关系，在计算时，找到前后过程的关系，即（递推式）；顺推：从已知条件出发，逐步推出要解决的问题。逆推：从问题出发推到已知条件。顺推 9、【菲波纳葜数列】寻找第n项与前面几项的关系式，以及初始项的值。【题目】Fibonacci数列的代表问题由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”（又称“Fibonacci问题”）：有雌雄一对兔子，假设过两个月便可繁殖雌雄各一的一对小兔子。问n个月后共有多少对兔子。第个月第个月f(x)=f(x-1)+f(x-2)第个月第个月第个月第个月第个月第个月【参考程序】var a,b,n,c:integer;begin read(n); a:=0; b:=1; for i:=2 to n dobegin c:=a+b; b:=c; a:=b;end; write(c);end.10、递推关系的应用“杨辉三角”【题目】递推关系应用十分广泛，其中有一个非常重要的应用就是著名的杨辉三角（又称“pascal三角”）杨辉三角形：打印杨辉三角形的前行，杨辉三角形如图：10101010本图大家不容易找到规律，但是如果将它转化为右图，不难发现杨辉三角形其实就是一个二维表的下三角部分，假设二维数组yh存储，每行首尾元素为，是其中任意一个非首尾元素yhi,j的值其实就是yhi-1,y-1和yhi-1,j的和；另外每一行后元素个数刚好等于行数。有了数组元素的值，要打印杨辉三角形，只需控制一下输出起始位置就行。【参考程序】var yh:array1.10,1.10 of integer; i,j:integer;begin yh1,1:=1; 设首行元素 for i:=2 to 10 do begin yhi,1:=1; yhi,i:=1;设每行首尾元素值 for j:=2 to i-1 do yhi,j:=yhi-1,j-1+yhi-1,j;设定非首尾元素end; for i:=1 to 10 do begin write( :(40-3*i);每行起始元素字位 for j:=1 to i do write(yhi,j:6); writeln; end;end.在今天的信息学竞赛中，递推关系的应用也日趋广泛，下面就让我们从近年的两道题中体会递推关系。11、蜜蜂爬行【题目】有一只经过训练的蜜蜂只能爬向右侧相临的蜂房，不能方向爬行。11973 4 6810ab 试求出蜜蜂从蜂房a爬到蜂房b的解路线数。【分析】这是一道很典型的Fibonacci数列题目，其中的递推关系很明，由于蜜蜂只能爬向右侧相临的蜂房，不能方向爬行的限制决定了蜜蜂到b点后路径的解是从b-1点或b-2点到达的（两路径不重复），故fn=fn-1+fn-2（a+2nb）；也是条件fa=1，f（a1）=1。12、平向分割问题 8 7【题目】设有n条封闭曲线把平向分割成的区域个数。 4 2 1 12 9 3 1 3 2 1 11 13 10 7 6 2 4 3 5n=1 n=2 a1=1 a2=3a2-a1=2 n=3 n=4 a4=13 a3-a2=4 a3=7 a4-a3=6 an-an-1=2(n-1)【分析】这个公式是我们观察幅图得出个局部的结论不能保证正确性，不是有广泛性。下面我们证明当平面上已有n-1条曲线将平面分割成an-1个区域后，第n-1条曲线与其它曲线相交一次，就增加一个区域。因为平面上已经有了n-1条封闭曲线，且第n条曲线与已有的每一条封闭曲线恰好相交与两点，不会与任意两条曲线相交于同一点，故平面上一点增加2(n-1)个区域，加上已有的an-1个区域，一共有an-1+2(n-1)区域，所以本题的递推关系an=an-1+2(n-1)，边界条件是a1=1。13、铺骨牌（2000年 全国联赛初赛）有2n的一个长方形方格，用一个的骨牌铺满方格，例如n=3时，为方格，此时用一个的骨牌铺满方格，共有种铺法。编写一个程序，试对给出的任意一个n（n），输出铺法点数。n=1n=2n=2种排法n=2种排法n=1种排法n=3先定第一个格先定前个格f(3)=f(2)+f(1)n-1排法 f(n)=f(n-1)+f(n-2) 边界条件n=1 f(1)=1 n=2 f(2)=2nn-2种排从第一块骨牌排列方法考虑，只有这两种可能。Fibonacci数列倒退14、贮油点【题目】一辆重型卡车欲穿过1000公里的沙漠，卡车耗油为1升/公里，卡车总载油能力为500公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立若干个贮油点，使卡车能顺利穿过沙漠。试问司机怎样建立这些贮油点？每一个贮油点应存储多少汽油，才能使卡车以消耗最少汽油的代价通过沙漠。编程计算及打印建立的贮油点序号。贮油点距沙漠边沿出发的距离以及存储油量，格式如下：No distance(k.m) oil(litve)1 xx xx2 xx xx【分析】设wayI第I贮油点到终点 (I=0) 的距离 oilI第I个贮油点的贮油量。终点起点 I=0 I=1 I=2 I=n 500公里【参考程序】way1=500;oil1=500; dk,k+1=500/(2k-1); wayk+1=wayk+dk,k+1=wayk+500/(2k-1) wayk+1-wayn=500/(2k-1)第n个点 wayn-1000-wayn,oiln=n*500n+1次满载车 （2n+1）次*（1000-wayn）始点存油为oiln+(1000-wayn)*(2n+1) var k:integer;贮油点位置号d,累计终点至当前贮油点的距离d1:real;I=n至终点的距离oil,way:away1.10 of real; I:integer; Begin writeln(No,distance:30,oil:80);K:=1;D:=500从I=1处开始向终点倒推Way1:=500;Oil1:=500;Repeat K:=k+1;D:=d+500/(2*k-1)lWayk:=d;Oilk:=0ilk-1+500Until d=1000;Wayk:=1000;置始点到终点的距离值D1:=1000-wayk-1;求I=n处至终点的距离Oilk:=d1*(2*k+1)+oilk-1;求始点贮油量由始点开始，逐一打印至当前贮油点的距离和贮油量for I:=0 to 12 do writeln(I,1000-wayk-I:30,oi(k-I:80); end.枚举素数15、素数【题目】求1100之间的素数算法：素数是大于1，且除了1和它车身外，不能被其它任何整数所整除的整数。讨论：根据素数的反义可知2，3，5，7，11，13，17等是素数1，4，6，8，9，10，12，14，15等不是素数为了判断某数I 是否为素数，一个最简单的方法是用2，3，4，5，I 这些数每一个去除I ，看能否被除尽，若被其中一个除尽则I 不是素数，否则 I 是素数。当I 较大时，用这种方法。除的次数太多，程序的复杂程度会加大，为了减少除的次数。提示运行效率，下面介绍的是其中一种方法。用2、3、4sqrt(I) 去除，如果小于等于sqrt( I)的数都除不尽，则大于sqrt(I)的数也不能除尽。用反证法证明：假设有大于sqrt(I)的数能被除尽I，则它的商k必小于sqrt(I)，是k能除尽I（其商为j），这是与原命题（小于等于sqrt(I)的数都除不尽I）相矛盾的，假设不成立，原命题得到证明。输出1100中的素数【参考程序】 var I,j,count:integer; flag:Boolean; begin count:=0; for I:=2 to 100 do begin flag:=true; for j:=2 to round(sqrt(i) do if I mod j=0 then flag:=false;不是素数找点 if flag then begin write(i);count:=count+1; if count mod 5=0 then writeln(i) 答对打印end; end.16、歌德巴赫猜想【题目】验证歌德巴赫猜想：任一充分大的偶数，可用两个素数之和表示，例如：4=2+26=3+38=3+598=19+79 算法：读入偶数n，将它分成p和q，使n=p+q。p从2开始（每次加1），q=n-p，如p，q均为素数，则输出结果，否则将p加1再试。【参考程序】 var n,p,q,j:integer;flagp,flagq:Boolean;begin read(n); p:=1;repeat p:=p+1; q:=n-p; flagp:=true; for j:=2 to round(sqrt(p) do if p mod j=0 then flagp:=false; flagq:=true;for j:=2 to round(sqrt(q) do if q mod j=0 then flagq:=false; until flagp and flagq; writeln(n,=,p,+,q)end.17、计算真因子【题目】求正整数n和m之间具有最多真因子的数，真因子定义：如果rdo then dod; p0:=p end; End;输出真因子个数的最大值do和只有do个真因子数p0。筛法【筛法】 符合条件的留下来，不符合条件的筛下去或者不符合的留下来符合的筛去。18、求素数（95年，全国联赛初赛）【题目】素数是大于1，且除了1和它本身外，不能被其它任意整数整除的整数。 算法：将整数2、3、4、5、6、7、8、9、10放于集合中（筛）然后从该集合中选出当前最小元素（2）将它作为素数输出，再从集合（筛）中去该数的所有倍数（2、4、6、8、10），再从当前集合中最元素（3）将它作为素数输出，从集合去掉该数的所有倍数（3、6、9）如此继续，直到集合为空。“筛法求素数”的过程如下图示：素数R1 数据集合R 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，。 【参考程序】 const n=1000; var sieve:set of 1.n; 筛 next,mul:integer; begin sieve:=2.n; next:=2; repeat while not(next in sieve) do next:=next+1; mul:=next; weriteln(next);while mul=n do begin sieve:=sieve-mul; 筛去 mul:=mul+next; 倍数 end; until sieve= ; end. 19、用筛法统计楼梯级数 【题目】一步跨2级多1级、一步跨3级多2级；如果分别用4、5、6、7去除级数分别余3、3、5、5。要求用筛选法求这个楼梯最少有多少级？ 【枚举法】 for I:=2 to 1000 do if (I mod 2=1) and (I mod 3=2) and (I mod 4=3) and (I mod 5=3) and (I mod 6=5) and (I mod 7=5) then begin write(i); halt；end.【筛法】 将跨2阶不余1的筛去，跨3阶不余2的筛去，跨4阶不余3的筛去，跨5阶不余3的筛去，跨6阶不余5的筛去，跨7阶不余5的筛去。余下的就是符合条件的。var a:array1.1000 of Boolean; b:array1.10 of integer; k,I,n,t:integer;begin for I:=2 to 1000 do aI:=true; n:=2; t:=1;b1:=1;b2:=2;b3:=3;b4:=3;b5:=5;b6:=5; 表示各种跨法的余数repeat for k:=2 to 1000 do if ak=true then if (k-bt) mod n0 then ak:=flase; 把不可能的情况筛去 余数n:=n+1;步数t:=t+1;下一种可能 until n7;一共筛7次 for I:2 to 1000 do if aI:=true then begin write(I:5); readln; halt;end; end.最大公约数与最小公倍数20.求两个正整数的最大公约数解：若自然数a既是M和约数，又是N的约数，则称a为M和N的公约数，其中最大的称为最大公约数。为了求得最大公约数，可以从最大可能的数（如M或N）向下寻找，找到的第一个公约数即是最大公约数。var m,n,a,b:integer; Beginread(m,n);if mn then begin b:=n;n:=m;m:=b;end; a :=n+1;Repeat a := a-1;Until (M mod a=0) and (N mod a=0);writeln(a);Readln;End.21、求两个正整数的最小公倍数【利用最大公约数】先求两个数的最大公约数，然后去除两个数的乘积，得到的就是最小公倍数。【数学方法】若干个b之和，若能被a整除，则该和便是a、b的最小公倍数。Function lcm(a,b):integer; Var I:integer;Begin I:=b; While I mod a =0 do I:=I+1; Lcm:=I;End;例3.9 输入任一的自然数A, B, 求A , B的最小公倍数。解:这里采用适合计算机查找的方法: 设D是它们的最小公倍数。先找出A, B当中的较大者并存放在A中, 将较小者存放在B中, 让D=A, 当D能够整除B时, 则D是所求的最小公倍数;当D不能整除B，就逐次地让D增加A。例如：A=18,B=12, 步骤如下： 让D=A(D=18) 当(D mod B)0 为真时 ( D不能整除B ) 就做 D=D+A, 重复; 当(D mod B)0 为假时结束循环，并输出D。 var a,b,d,t : word;begin readln(a , b); if ab then begin t:=a; a:=b; b:=tend; d:=a; whiled mod b 0do 当条件为真时就做do后面的语句 inc(d,a); writeln(d) ; End.进制转换十进制数转化为某进制数的转换方法，如下图示： 除x逆序取余法 十进制数 x进制数（x=2,8,16等） 例中n=222（十进制数），转换成x进制数的过程如下图示：（1）十进制数二进制数 （2）十进制数八进制数 （3）十进制数十六进制数 x=2 222 被除数（最大商） x=8 222 6 x=16 222 E （14）10 2 111 0 低位 8 27 3 16 13 D （13）10 2 50 1 逆 8 3 3 0 2 25 0 余 序 0 2 12 0 数 取 2 6 0 余 2 3 1 数 2 1 1 高位 0 （最大商为0时停止） 将每次所得的余数由下至上排列(逆序取余数)，即有： （222）10 转换成二进制数得到：1100010 （222）10 转换成八进制数得到：336（222）10 转换成十六进制数得到：13、1422、十进制转换为n进制【题目】键盘输入一个十进制的整数，及确定进制n，把这个数转换成相应的n进制输出。 （其中n） 例如：输入，n 则输出 (10)10=(101)3【参考程序】 var i,j,m,n:longint; a:array 1.100 of byte; 用数组存放求出的余数 begin writeln(input m,n); fillchar(a,sizeof(a),0); readln(m,n); write(m); i:=0; repeat i:=i+1; ai:= m mod n; m:=m div n; until m=0; write(=(); for j:=i downto 1 do if aj9 then write(chr(aj+55) 如果大于，用字母输出 else write(aj); writeln(),n);readln; en