haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

各类算法精选

发布时间:2014-02-03 11:04:40  

枚举法

有4个学生,上地理课时提出我国四大谈水湖的排列次序如下: 甲:洞庭湖最大,洪泽湖最小,鄱阳湖第三;

乙:洪泽湖最大,洞庭湖最小,鄱阳湖第二,太湖第三;

丙:洪泽湖最小,洞庭湖第三;

丁:鄱阳湖最大,太湖最小,洪泽湖第二,洞庭湖第三;

对于各湖泊应处的位置,每个人只说对了一个。根据以上描述和条件,编写程序,让计算机判断一下各湖泊应该处于第几位。

解题思路:设置洞庭湖、洪泽湖、鄱阳湖、太湖分别用字母A、B、C、D代表,最大到最小依次用数字4——1表示。应用枚举法可以解决此问题,不过稍微复杂罗嗦点。 源程序如下:

program hupo;

var

a,b,c,d:integer;

begin

for b:=1 to 4 do

for a:=1 to 4 do

if ((b=1) and (a<>2)) or ((a=2) and (b<>1)) then

if a<>b then

for c:=1 to 4 do

if (a<>c) and (b<>c) then

if (a+b+c<>7) and (a+b<>5) and (a+c<>6) and (b+c<>3) then for d:=1 to 4 do

if c<>d then

if (b+a<>5) and (b+c<>7) and (b+d<>6) then

if (a+c<>4) and (a+d<>3) and (c+d<>5) then

if (c+d<>5) and (c+b<>7) and (c+a<>6) then

if (d+b<>4) and (d+a<>3) and (b+a<>5) then

writeln('a=',a,' b=',b,' c=',c,' d=',d)

end.

改进程序:

program ygzj;

var

a,b,c,d:integer;

begin

for a:=1 to 4 do

for b:=1 to 4 do

for c:=1 to 4 do

begin

d:=10-a-b-c;

if ord(a=1)+ord(b=4)+ord(c=3)=1 then

if ord(b=1)+ord(a=4)+ord(c=2)+ord(d=3)=1 then

if ord(b=4)+ord(a=3)=1 then

if ord(c=1)+ord(d=4)+ord(b=2)+ord(a=3)=1 then

if a*b*c*d=24 then

writeln('洞庭湖第':3,a:3,'洪泽湖第':3,b:3,'波阳湖第':3,c:3,'太湖第':3,d:3);

end;

writeln

end.

选择排序算法

在介绍选择排序法之前先介绍一种把最小的数放在第一个位置上的算法,当然也可以用前面所讲的冒泡排序法,现在我们改用一种新的算法:其指导思想是先并不急于调换位置,先从A[1]开始逐个检查,看哪个数最小就记下该数所在的位置P,等一躺扫描完毕,再把A[P]和A[1]对调,这时A[1]到A[10]中最小的数据就换到了最前面的位置。算法的步骤如下:

1)、先假设A[1]中的数最小,记下此时的位置P=1;

2)、依次把A[P]和A[I](I从2变化到10)进行比较,每次比较时,若A[I]的数比A[P]中的数小,则把I的值赋给P,使P总是指向当前所扫描过的最小数的位置,也就是说A[P]总是等于所有扫描过的数最小的那个数。在依次一一比较后,P就指向10个数中最小的数所在位置,即A[P]就是10个数中最小的那个数;

3)把A[P]和A[1]的数对调,那么最小的数就在A[1]中去了,也就是在最前面了。

如果现在重复此算法,但每重复一次,进行比较的数列范围就向后移动一个位置。即第二遍比较时范围就从第2个数一直到第N个数,在此范围内找最小的数的位置P,然后把A[P]与A[2]对调,这样从第2个数开始到第N个数中最小数就在A[2]中了,第三遍就从第3个数到第N个数中去找最小的数,再把A[P]与A[3]对调……此过程重复N-1次后,就把A数组中N个数按从小到大的顺序排好了。这种排序的方法就是选择排序法。以上算法可以用图4表示:

程序代码:

program xuanze(input,output);

const n=10;

type

colarr=array[1..n] of integer;

var

a:colarr;I,j,p,t:integer;

begin

writeln(‘input 10 integer num:’);

for I:=1 to n do read(a[I]);

for j:=1 to n-1 do

begin

p:=j

for I:=j+1 to n do if a[I]<a[p] then p:=I; t:=a[p];a[p]:=a[j];a[j]:=t;

end;

writeln(‘output num:’);

for I:=1 to n do

write(a[I]:5)

end.

冒泡排序算法

在解释冒泡排序算法之前,先来介绍把10个数(放在数组A中)中最大的那个数放

在最后位置上的一种算法。算法描述如下:

(1)从数组A[1]到A[10],把相临的两个数两两进行比较。即A[1]和A[2]比较,比较完后A[2]再与A[3]比较,……最后是A[9]和A[10]比较。

(2)在每次进行比较的过程中,如果前一个数比后一个数大,则对调两个数,也就是说把较大的数调到后面,较小的调到前面。比如在第一次的比较中,如果A[1]比A[2]大则A[1]和A[2]的值就互换。下图用6个数据来说明以上的算法。

假设6个数据是:A[]=5 7 4 3 8 6

A[1] A[2] A[3] A[4] A[5] A[6]

5 7 4 3 8 6 第一次,A[1]=5和A[2]=7比较,7>5,不进行对调。 5 7 4 3 8 6 第二次,A[2]=7和A[3]=4比较,4<7,进行对调,

那么第二次比较完后的数据是5 4 7 3 8 6

5 4 7 3 8 6 第三次,A[3]=7和A[4]=3比较,3<7,进行对调,

那么第三次比较完后的数据是5 4 3 7 8 6

5 4 3 7 8 6 第四次,A[4]=7和A[5]=8比较,8>7,不进行对调。

5 4 3 7 8 6 第五次,A[6]=6和A[5]=8比较,6<8,进行对调,

那么第五次也就是最后一次的结果是

5 4 3 7 6 8

由上例可以看出,对于6个数,排好一个数(最大的数)需要进行5次比较,可以推断出,对于N个数,一躺需要 N-1次比较操作,

上述算法已经把N个数中最大的数放到了A[N]中,再重复上述算法,把A[1]到A[N-1]中最大的数放到A[N-1]中,这样A[N-1]中存放的就是第二大的数,接着把A[1]到A[N-2]中最大的数放到A[N-2]中,……最后把A[1]到A[2]中大的那个数放到A[2]中,每重复一次两两比较后,比较的范围就朝前移动一个位置,此算法经过N-1次就完成了A[1]到A[N]中的的数由小到大的排列。

注意:如果要由大到小排列则在比较时前一个数比后一个数小就进行对调,方法相反。 由此可以看出,冒泡法的基本思想就是:在待排序的数据中,先找到最小(大)的数据将它放到最前面,再从第二个数据开始,找到第二小(大)的数据将它放到第二个位置,以此类推,直到只剩下最后一个数为止。这种排序方法在排序的过程中,是小的数就如气泡一样逐层上浮,而使大的数逐个下沉,于是就形象地取名为冒泡排序,又名起泡排序。

程序要求: 从键盘输入十个数,然后按从小到大的顺序输出。

程序代码:

program bubble(input,output);

const n=10;

type

colarr=array[1..n] of integer;

var

a:colarr; t,i,j:integer;

begin

writeln(‘INPUT 10 integer num:’);

for I:=1 to n do read(a[I]);

readln;

for j:=1 to n-1 do

for I:=1 to n-j do

if a[I]>a[I+1] then

begin

t:=a[I];a[I]:=a[I+1];a[I+1]:=t

end;

writeln(‘OUTPUT new num:’);

for I:=1 to n do

begin

write(a[I]:4);

if I mod 5=0 then writeln

end;

end.

程序运行结果如下:

input 10 integer num: {提示输入10个数}

7 6 23 21 19 18 10 16 5 13 {假如输入的数据} output new num: {冒泡排序后输出结果} 5 6 7 10 13

16 18 19 21 23

问题:假如要从从大到小输出程序应该怎么改?

两重循环总共执行了多少次?

插入排序算法

通过学习上述两种方法可以了解排序的基本思想,也可以对任何一个无序数组作出从大到小(降序)或从小到大(升序)的排列。现在假设有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据。

题目:A数组中有N个数据,按从小到大的顺序排列,输入一个数X,把X的值插入到数组A中,使得插入后的A数组仍然按从小到大排列。

那么这个问题的解决算法就是:

1)、通过比较大小找到X应插入的位置,假如应该放在第I个位置;

2)、把从I开始的(包括I)的所有数组元素依次向后移动一个位置,即A[I+1]:=A[I];

3)、A[I]:=X

代码如下:

program charu(input,output);

var

a:array[1..11] of integer;

x,I,j,n:integer;

f:Boolean;

Begin

{给数组赋一个已经排序好的初值,设A[1]到A[10]分别等于1到10}

For I:=1 to 10 do A[I]:=I;

Writeln(‘数组原来的排列值是:’);

For I:=1 to 10 do write(a[I]:4);

Writeln;

Writeln(‘输入一个整数:’);

Readln(x);

F:=false;

I:=0;N:=10;

Repeat

I:=I+1;

If a[I]>x then f:=ture;

Until I>n or f=ture;

J:=n+1;

While j<>I do

begin

A[j]:=a[j-1];

J:=j-1

End;

A[I]:=x;

Writeln(‘ 插入一个数后的数组排列值是:’);

For I:=1 to n+1 do

Write(a[I]:4)

End.

注意:此排序方法要求数组一定要有足够的预留空间来容纳插入后的数据。

快速排序算法

快速排序是对冒泡排序的一种改进。它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

假设要排序的数组是A[1]……A[N],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一躺快速排序。一躺快速排序的算法是:

1)、设置两个变量I、J,排序开始的时候I:=1,J:=N;

2)以第一个数组元素作为关键数据,赋值给X,即X:=A[1];

3)、从J开始向前搜索,即由后开始向前搜索(J:=J-1),找到第一个小于X的值,两者交换;

4)、从I开始向后搜索,即由前开始向后搜索(I:=I+1),找到第一个大于X的值,两者交换;

5)、重复第3、4步,直到I=J;

例如:待排序的数组A的值分别是:(初始关键数据X:=49) : 进行第一次交换后: 27 38 65 97 76 13 49

( 按照算法的第三步从后面开始找<X的值,27

进行第二次交换后: 27 38 49 97 76 13 65

( 按照算法的第四步从前面开始找>X的值,65>49,两者交换,此时I:=3 ) 进行第三次交换后: 27 38 13 97 76 49 65

( 按照算法的第五步将又一次执行算法的第三步从后开始找<X的值,13

进行第四次交换后: 27 38 13 49 76 97 65

( 按照算法的第四步从前面开始找大于X的值,97>49,两者交换,此

时J:=4 )

此时再执行第三不的时候就发现I=J,从而结束一躺快速排序,那么经过一躺快速排序之后的结果是:27 38 13 49 76 97 65,即所以大于49的数全部在49的后面,所以小于49的数全部在49的前面。

快速排序就是递归调用此过程——在以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列,根据这种思想对于上述数组A的快速排序的全过程如图6所示:

初始状态 {49 38 65 97 76 13 27}

进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}

分别对前后两部分进行快速排序27结束结束 {49 65} 76 49

图6 快速排序全过程

1)、设有N(假设N=10)个数,存放在S数组中;

2)、在S[1。。N]中任取一个元素作为比较基准,例如取T=S[1],起目的就是在定出T应在排序结果中的位置K,这个K的位置在:S[1。。K-1]<=S[K]<=S[K+1..N],即在S[K]以前的数都小于S[K],在S[K]以后的数都大于S[K];

3)、利用分治思想(即大化小的策略)可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组对象只有一个数据为止。

如具体数据如下,那么第一躺快速排序的过程是:

数组下标: 1 2 3 4 5 6 7 8 9 10

45 36 18 53 72 30 48 93 15 36

I (1) 36 36 18 53 72 30 48 93 15 45

(2) 36 36 18 45 72 30 48 93 15 53

(3) 36 36 18 15 72 30 48 93 45 53

(4) 36 36 18 15 45 30 48 93 72 53

(5) 36 36 18 15 30 45 48 93 72 53

通过一躺排序将45放到应该放的位置K,这里K=6,那么再对S[1。。5]和S[6。。10]分别进行快速排序。程序代码如下:

program kuaisu(input,output);

const n=10;

var

s:array[1..10] of integer;

k,l,m:integer;

procedure qsort(lx,rx:integer); var

I,j,t:integer;

Begin

I:lx;j:rx;t:s[I];

Repeat

While (s[j]>t) and (j>I) do Begin

k:=k+1;

j:=j-1

end;

if I<j then

begin

s[I]:=s[j];I:=I+1;l:=l+1; while (s[I]<t) and (I<j) do begin

k:=k+1;

I:=I+1

End;

If I<j then

begin

S[j]:=s[I];j:=j-1;l:=l+1; End;

End;

Until I=j;

S[I]:=t;I:=I+1;j:=j-1;l:=l+1; If lx<j then qsort(lx,j); If I<rx then qsort(I,rx)

End;{过程qsort结束}

Begin

Writeln('input 10 integer num:'); For m:=1 to n do read(s[m]); K:=0;l:=0;

Qsort(l,n);

Writeln('排序后结果是:'); For m:=1 to n do write(s[m]:4) End.

</X的值,13

一般快速排序法

{快速排序法的一躺排序程序}

program kuaisu(input,output);

type

arr=array[1..7] of integer;

var

a:arr;

i,j,k:integer;

procedure sort(var a:arr;var m,n:integer); var

x,p,q:integer;

begin

x:=a[m];

repeat

while ((mx)) do n:=n-1;

p:=a[m];a[m]:=a[n];a[n]:=p;

while ((m

p:=a[m];a[m]:=a[n];a[n]:=p

until m=n

end;

begin

writeln('input 10 integer num:');

i:=1;j:=1;k:=7;

repeat

read(a[i]);

i:=i+1;

until i>7;

sort(a,j,k);

for i:=1 to 7 do write(a[i]:4);

writeln('j=',j:4,'k:',k:4) end.

标准快速排序算法

program kuaisu(input,output); const n=10;

var

s:array[1..10] of integer; k,l,m,o:integer;

procedure qsort(lx,rx:integer); var

I,j,t:integer;

Begin

I:=lx;j:=rx;t:=s[I];

Repeat

While (s[j]>t) and (j>I) do Begin

k:=k+1;

j:=j-1

end;

if I<j then

begin

s[I]:=s[j];I:=I+1;l:=l+1; while (s[I]<t) and (I<j) do begin

I:=I+1

End;

If I<j then

begin

S[j]:=s[I];j:=j-1

End;

End;

Until I=j;

S[I]:=t;I:=I+1;j:=j-1; o:=o+1; writeln('第',o:3,'次排序的结果:'); for m:=1 to 10 do write(s[m]:5); writeln;

If lx<j then qsort(lx,j);

If I<rx then qsort(I,rx)

End;{过程qsort结束}

Begin

Writeln('input 10 integer num:'); For m:=1 to n do read(s[m]); K:=0;l:=1; o:=0;

Qsort(l,n);

Writeln('shu chu jie guo:');

For m:=1 to n do write(s[m]:4) ; End.

二分查找法完整版

program jjzx(input,output);

var

a:array[1..10] of integer;

i,j,n,x:integer;

begin

writeln('输入10个从小到大的数:');

for i:=1 to 10 do read(a[i]);

writeln('输入要查找的数:');

readln(x);

i:=1; n:=10; j:=trunc((i+n)/2);

if a[n]

writeln('查找失败,数组中无此元素!')

else

a[j]>x then j:=trunc((i+n)/2)

end

else

j:=trunc((i+n)/2)

end

(a[j]=x) or (i=j) ;

if a[j]=x then writeln('查找成功!位置是:',j:3) else

writeln('查找失败,数组中无此元素!')

end

end.

想想还有其他的方法解决X大于数组中的任何一个数的方法这种情况的方法吗?

统计算法

作用:在给定的范围内求出符合设定条件的记录个数。

算法基本思想:用一个条件语句判断当前记录是否符合给定条件,符合则统计个数加一。用循环实现对所有记录的操作。

举例说明:

例一、 从键盘敲进任意个(少于255个)字符,然后求出其中某一个字母的个数(如大写字母A)。

分析:用一个字符串变量来接受从键盘输入的字符,然后从第一个字符开始对每一个字符进行处理,如果是A则个数加一,最后把总的统计个数输出。

程序代码:

program jjzx(input,output);

type

str=string[255];

var

st:str;

n,i,j:integer;

begin

writeln(‘请输入一行字符: ‘);

readln(st);

j:=lenth(st); {把字符串的实际长度赋给j}

n:=0;

for i:=1 to j do

if ord(st[i])=65 then n:=n+1;

writeln(‘你输入的字符是: ‘,st);

writeln((‘其中字符A的个数和: ‘,n)

end.

动态规划-航线设置

问题描述:美丽的莱茵河畔,每边都分布着N个城市,两边的城市都是唯一对应的友好城市,现需要在友好城市开通航线以加强往来.但因为莱茵河常年大雾,如果开设的航线发生交叉现象就有可能出现碰船的现象.现在要求近可能多地开通航线并且使航线不能相交!

假如你是一个才华横溢的设计师,该如何设置友好城市间的航线使的航线数又最大又不相交呢? 分析:此问题可以演化成求最大不下降序列来完成.源程序如下:

program dongtai; {动态规划之友好城市航线设置问题}

var

d:array[1..1000,1..4] of integer;

i,j,k,n,L,p:integer;

procedure print(L:integer); {打印结果}

begin

writeLn('最多可设置的航线数是 : ',k);

repeat

writeLn(d[L,1]:4,d[L,2]:4); {输出可以设置航线的友好城市代码}

L:=d[L,4]

untiL L=0

end;

begin

writeLn('输入友好城市对数: ');

readLn(n);

writeLn('输入友好城市对(友好城市放在同一行:'); {输入}

for i:=1 to n do

readLn(d[i,1],d[i,2]); {D[I,1]表示起点,D[I,2]表示终点}

for i:=1 to n do

begin

d[i,3]:=1; {D[I,3]表示可以设置的航线条数}

d[i,4]:=0 {D[I,4]表示后继,即下一条航线从哪里开始设置,为0表示不能设置下一条航线} end;

for i:=n-1 downto 1 do {从倒数第二个城市开始规划}

begin

L:=0; p:=0; {L表示本城市后面可以设置的航线数,P表示下条航线从哪个城市开始}

for j:=i+1 to n do {找出本城市后面可以设置的最大航线数和小条航线到底从哪个城市开始设置} if (d[i,2]L) then

{如果本城市I的终点小于后面城市的终点(即不相

交)} {并且此城市后面可以设置的航线数大于L}

begin

L:=d[j,3]; {那么L等于城市J的可以设置航线数}

p:=j {P等于可以设置下条航线的城市代码}

end;

if L>0 then {如果本城市后面总共可以设置的航线数>0则}

begin

d[i,3]:=L+1; {本城市可以设置的航线数在下个城市可以设置航线数的基础上加1} d[i,4]:=p {D[I,4]等于本城市后续城市的代码}

end

end;

k:=d[1,3]; {K为可以设置最大航线数,假设初值为第一个城市可以设置的航线数}

L:=1; {L为城市代码,初值为第一个城市}

for i:=2 to n do {找出可以设置航线的最大值,赋值给K,同时L记下哪个可以设置最大航线数的城市代码}

if d[i,3]>k then

begin

k:=d[i,3];

L:=i

end;

for i:=1 to n do {打印结果,因为有可能有多种方案,所以只要哪个城市可以设置的航线数等于最大值K就打印结果}

if d[i,3]=k then print(i)

end.

归并排序算法

合并排序(MERGE SORT)是又一类不同的排序方法,合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列,因此它又叫归并算法。它的基本思想就是假设数组A有N个元素,那么可以看成数组A是又N个有序的子序列组成,每个子序列的长度为1,然后再两两合并,得到了一个 N/2 个长度为2或1的有序子序列,再两两合并,如此重复,值得得到一个长度为N的有序数据序列为止,这种排序方法称为2—路合并排序。

例如数组A有7个数据,分别是: 49 38 65 97 76 13 27,那么采用归并排序算法的操作过程如图7所示:

初始值[27]

看成由长度为1的7个子序列组成 第一次合并之后 [

[

[[27

] 看成由长度为1或2的

4个子序列组成 第二次合并之后 [

] [看成由长度为4或3的2个子序列组成 第三次合并之后 []

图6 归并排序算法过程图

合并算法的核心操作就是将一维数组中前后相邻的两个两个有序序列合并成一个有序序列。合并算法也可以采用递归算法来实现,形式上较为简单,但实用性很差。

合并算法的合并次数是一个非常重要的量,根据计算当数组中有3到4个元素时,合并次数

是2次,当有5到8个元素时,合并次数是3次,当有9到16个元素时,合并次数是4次,按照这一

X

规律,当有N个子序列时可以推断出合并的次数是X(2 >=N,符合此条件的最小那个X)。 源程序:

program hebing;

const

n=10;

var

a:array[1..n] of integer;

i:integer;

procedure init;

var

i:integer;

begin

for i:=1 to n do read(a[i]); readln;

end;

procedure merge(low,mid,high:integer); var

h,i,j,k:integer;

b:array[1..n] of integer; begin

h:=low; i:=low; j:=mid+1;

while (h<=mid) and (j<=high) do begin

if (a[h]<=a[j]) then

begin

b[i]:=a[h]; h:=h+1; end

else

begin

b[i]:=a[j]; j:=j+1; end;

i:=i+1;

end;

if h>mid then

for k:=j to high do

begin

b[i]:=a[k]; i:=i+1; end

else

for k:=h to mid do

begin

b[i]:=a[k]; i:=i+1; end;

for k:=low to high do

a[k]:=b[k];

end;

procedure mergesort(low,high:integer); var

mid:integer;

begin

if low<high then

begin

mid:=(low+high) div 2; mergesort(low,mid);

mergesort(mid+1,high); merge(low,mid,high); end;

end;

数字全排列问题

数字全排列问题:

任意给出从1到N的N个连续的自然数,求出这N个自然数的各种全排列。如N=3时,共有以下6种排列方式:

123,132,213,231,312,321。

注意:数字不能重复,N由键盘输入(N<=9)。

解题思路:

应用回溯法,每个数的取法都有N个方向(1——N),当取够N个数时,输出一个排列,然后退后一步,取前一个数的下一个方向(即前一个数+1),并且要保证所有数字不能重复。当前数字的所有方向都取完时,继续退一步,一直重复到第一个数为止。

程序代码:

program quanpailie; {数字全排列问题}

var

a:array[1..9] of integer;

k,x,n:integer;

function panduan(j,h:integer):boolean; {判断当前数字是否能赋值给当前数组元素} var

m:integer;

begin

panduan:=true;

for m:=1 to h-1 do

if a[m]=j then panduan:=false {如果当前数字与前面的数组元素相同则不能赋值} end;

procedure try(h:integer);

var

i,j,m:integer;

begin

for j:=1 to n do

if panduan(j,h) then

begin

a[h]:=j; {能够赋值,且长度k加一}

k:=k+1;

if k=n then {如果长度达到N则表示一种组合已经完成,输出结果} begin

for m:=1 to n do

write(a[m]);

write('':4);

x:=x+1; {每输出一种排列方式加一}

if x mod 5=0 then writeln; {每行输出5种排列方案} end

else

try(h+1); {对下一个数组元素进行赋值}

k:=k-1 {回溯的时候一定要把长度减一}

end

end;

begin

writeln('输入 N:');

readln(n);

k:=0; {k表示长度,长度初始值为0}

x:=0; {x表示总的排列方式}

try(1); {对第一个数组元素赋值}

writeln('共有 ', x ,' 种排列方案')

end.

优化高精度减法说明:用字符串来存放减数和被减数,最大限制255位减255位} {优化在于用一个数组元素存放4位数,节省存储空间}

program jjzx; {本程序没有考虑两负数相间减}

var s,s1,s2:string;

a,b,c:array[1..260] of integer;

i,l,m,k1,k2:integer;

d:char; {D用来表示正负号}

begin

writeln('input s1:');readln(s1);

writeln('input s2:');readln(s2);

l:=length(s1);

m:=length(s2);

if l

begin

s:=s1;s1:=s2;s2:=s;d:='-'

end;

if l=m then {如果长度一样则直接比较,S1小就要与S2调换}

if s1

begin

s:=s1;s1:=s2;s2:=s;d:='-'

end;

l:=length(s1); m:=length(s2);

k1:=261;

repeat {转换S1,一个数组元素用来存放4位数字}

k1:=k1-1;

s:=copy(s1,l-3,4);

val(s,a[k1],i);

s1:=copy(s1,1,l-4);

l:=l-4

until l<=0;

k2:=261; {转换S2}

repeat

k2:=k2-1;

s:=copy(s2,m-3,4);

val(s,b[k2],i);

s2:=copy(s2,1,m-4);

m:=m-4

until m<=0;

for i:=260 downto k1 do

if a[i]

begin

c[i]:=a[i]+10000-b[i]; {注意是加上10000} a[i-1]:=a[i-1]-1;

end

else

c[i]:=a[i]-b[i];

writeln('jie guo shi :');

write(d:2); {首先输出符号位}

write(c[k1]); {在输出最高位,因为最高位不用补0} for i:=k1+1 to 260 do {注意补0的方法}

begin

if c[i]<1000 then write('0');

if c[i]<100 then write('0');

if c[i]<10 then write('0');

write(c[i]);

end;

writeln

end.

高精度阶乘

program jjzx; {本程序最大限制为求N(N<999)的阶乘}

var

a,b,c:array[1..1000] of integer;

i,j,l,m,k1,k2,x,y,z,w,n,t:integer;

procedure chengfa; {高精度乘法}

begin

for l:=1 to k1 do

for m:=1 to k2 do

begin

x:=a[l]*b[m];

y:=x div 10;

z:=x mod 10;

w:=l+m-1;

c[w]:=c[w]+z;

c[w+1]:=c[w+1]+y+c[w] div 10;

c[w]:=c[w]mod 10

end;

k1:=k1+k2; {位数为K1、K2的两数相乘最大只有K1+K2位}

if c[k1]=0 then k1:=k1-1; {如果最高位为0则位数减少一位}

for t:=1 to k1 do a[t]:=c[t]; {把一次高精度相乘的结果放到A数组中,以便下次相乘}

for t:=1 to k1 do c[t]:=0; {同时把数组C清空,以便下次相乘,因为每调用此过程一次都是一次 全新的高精度乘法,所以数组C必须清空}

end;

procedure zhuanhuan; {把I每一位分解开分别赋值给数组B的每一个元素} begin

if i>=100 then

begin

k2:=3;

b[3]:=i div 100;

b[2]:=(i-b[3]*100) div 10;

b[1]:=i-b[3]*100-b[2]*10

end

else

if i>=10

then

begin

k2:=2;

b[2]:=i div 10;

b[1]:=i-b[2]*10

end

else

begin

k2:=1;

b[1]:=i

end;

end;

begin

writeln('input:');

readln(n);

a[1]:=1; {最后结果放在数组A中}

k1:=1;

for i:=2 to n do

begin

zhuanhuan;

chengfa;

end;

writeln(n:2,'!= ');

for i:=k1 downto 1 do write(a[i]) end.

最小数字子串

键盘输入一个高精度正整数t(不超过240位),去掉其中S个数字后,剩下的数字按原顺序组成一个新数,试对给定的 t 与 S, 寻找一种方案,使剩下的数字组成的新数最小.

program lxw001;

var t1,t2:string[250];

a,b:array[1..250] of integer;

i,j,r,s,s1:integer;

begin

writeln("输入数字串:"); readln(t1);

writeln("输入删除数字个数:");readln(s);

s1:=s; r:=0; t2:="";

for i:=1 to length(t1) do a[i]:=i;

repeat

i:=1;

for j:=1 to s1+1 do if t1[j] if i>1 then

for j:=1 to i-1 do begin inc(r); b[r]:=a[j] end;

t2:=t2+copy(t1,i,1);

delete(t1,1,i);

for j:=1 to length(t1) do a[j]:=a[j+i];

s1:=s1-(i-1);

if length(t1)=s1 then {处理尾部应删的数}

begin

for j:=1 to s1 do begin inc(r);b[r]:=a[j] end;

s1:=0; t1:="";

end;

until s1=0;

t2:=t2+t1;

writeln("最小数:",t2);

write("删除数字的位置: ");

for i:=1 to s do write(b[i]," ");

writeln;

end.

邮票面值

发行一套四种不同面值的邮票,限定使用时不超过3枚,为了能连续贴出1,2,...,r的面值, 如何确定四种面值,使 r 最大?

program lxw002;

var

s1,s2,s3,s4: integer;

r,r0,r1,r2,r3,r4: integer;

stamp: set of 1..100;

function workr(s1,s2,s3,s4:integer):integer;

var n1,n2,n3,n4,f:integer;

begin

stamp:=[];

for n1:=0 to 3 do

for n2:=0 to 3-n1 do

for n3 :=0 to 3-n1-n2 do

for n4:=0 to 3-n1-n2-n3 do

begin

f:=n1*s1+n2*s2+n3*s3+n4*s4;

stamp:=stamp+[f]

end;

f:=1;

while f in stamp do f:=f+1;

workr:=f-1

end;

begin{main};

s1:=1; r0:=0;

for s2:=s1+1 to 3*s1+1 do

for s3:=s2+1 to 3*s2+1 do

for s4:=s3+1 to 3*s3+1 do

begin

r:=workr(s1,s2,s3,s4);

if r>r0 then

begin

r0:=r;

r1:=s1; r2:=s2; r3:=s3; r4:=s4

end;

end;

writeln("s1=",r1,", s2=",r2,", s3=",r3,", s4=",r4);

writeln("The max value is: ",r0)

end.

字符移动

n个A与n个B(n≥4)排成一排, 开始时, 字符B全排在A的后面,然后将它移成A,B 相间的情形: AAAABBBB → ABABABAB. 要求如下:

(1) 每次同时移动两相邻字符, 不得调换顺序.

(2) 总步数应尽量少.

program lxw003;

var i,n,step:integer;

s:array [1..100] of char;

procedure display;

var i:integer;

begin

write("No.",step:2," ");

for i:=1 to 2*n+2 do write(s[i]);

writeln

end;

procedure move(i,k:integer);

var j:integer;

begin

step:=step+1;

for j:=0 to 1 do

begin s[k+j]:=s[i+j]; s[i+j]:=" " end;

display

end;

begin{main}

repeat writeln("input n:"); readln(n) until n>3;

step:=0;

for i:=1 to n do s[i]:="A";

for i:=n+1 to 2*n do s[i]:="B";

s[2*n+1]:=" "; s[2*n+2]:=" ";

display;

if n>4 then

for i:=n downto 5 do

begin move(i,2*i+1); move(2*i-1,i) end;

move(4,9); move(8,4); move(2,8);

move(7,2); move(1,7)

end.

子集定和问题

由键盘输入N, B={1,2,...,N}为连续N个整数的集合, 取B中若干不同的整数, 使这些整数之和为给定的M, 共有多少种不同的取法?

program lxw004;

var m,n,i:integer;

s:longint;

function aa(k,m:integer):longint;

var i,t1,kz:integer;

temp:longint;

begin

if (k>m) or (k=1)and(m>1) or (k=0)and(m>0) then

begin aa:=0; exit end;

if k=m then begin aa:=1; exit end;

temp:=0; {处理 k<m的情形}

t1:=m-k; kz:=k-1;

if kz>m-k then kz:=m-k;

for i:=1 to kz do temp:=temp+aa(i,t1);

aa:=temp;

end;

begin

writeln("输入最大整数:"); readln(n);

writeln("输入定和数:"); readln(m);

s:=0;

for i:=1 to n do s:=s+aa(i,m);

writeln("计算结果:",s);

end.

素数方阵

设 D 为5行5列的方阵, 其元素表示为D(I,J), 每个D(I,J)皆是0--9中的某个数字,D(1,1)=r为已知. 试求满足以下条件的全部方阵 D:

(1) D 的每行,每列,每条对角线均为一个五位素数.

(2) 由键盘输入S, 上述各素数的各位数字之和均等于S.

program lxw005; {素数矩阵}

const s:array [1..4] of integer= (1,3,7,9);

type arr2=array [0..50000] of boolean;

e5=array [1..5] of shortint;

var x: array [1..2] of ^arr2;

limit,k,k1,t,ss,tt,r,sum1:longint;

a1:array[1..1000] of e5;

d1:array[1..5] of e5;

g1,temp:e5;

procedure p2;forward;

procedure p3;forward;

procedure p4;forward;

procedure p5;forward;

procedure p6;forward;

procedure look(p, w:integer;st:e5;var tr:boolean);

{p=1:处理行,w:行号. p=2:处理列w:列号. 不处理对角线 }

label 10;

var i:integer;

j,k:shortint;

begin

tr:=false;

for i:=1 to tt do

begin

for j:=1 to 5 do if a1[i,j]<>st[j] then goto 10;

case p of

1: for k:=1 to 5 do d1[w,k]:=st[k];

2: for k:=1 to 5 do d1[k,w]:=st[k];

end;

tr:=true; exit;

10:

end;

end;

function plac(ad:longint;i:integer):integer;

var

pl2,sta:integer;

ad2:string[5];

ad3:string[1];

begin

str(ad:5,ad2); ad3:=copy(ad2,i,1);

val(ad3,pl2,sta); plac:=pl2;

end;

procedure assign_g(a1,a2,a3,a4,a5:shortint);

begin

g1[1]:=a1; g1[2]:=a2; g1[3]:=a3; g1[4]:=a4; g1[5]:=a5; end;

procedure prim1;

{ 求 100000 以内的素数及取定和的五位素数 } var i,j,t,t1,t2,t3,pr,ii:longint;

pl:e5;

begin{1}

limit:=50000;

for j:=1 to 2 do getmem(x[j],sizeof(x[j]^));

for i:=1 to limit do x[1]^[i]:=true;

x[2]^:=x[1]^; x[1]^[1]:=false;

for i:=1 to round(sqrt(limit)) do

if x[1]^[i] then

begin{2}

t:=i;

t2:=limit div t;

for j:=2 to t2 do x[1]^[t*j]:=false;

t3:=2*limit div t;

for j:=t2+1 to t3 do x[2]^[j*t-limit]:=false; end;{2}

tt:=0;

for j:=1 to 2 do

begin {3}

t:=10000;

if j=2 then t:=1;

for i:=t to limit do

if x[j]^[i] then

begin

ii:=i+(j-1)*limit;

for k:=1 to 5 do pl[k]:=plac(ii,k);

if pl[1]+pl[2]+pl[3]+pl[4]+pl[5]=sum1 then begin inc(tt); a1[tt]:=pl; end;

end;

end; {3}

writeln("tt=",tt);

for j:=1 to 2 do freemem(x[j],sizeof(x[j]^));

end;{1}

procedure p1; { 第 1 行 }

var i,j:integer;

begin{3}

d1[1,1]:=r;

for j:=1 to tt do

if (a1[j,1]=r) then

begin{5}

temp:=a1[j];

d1[1,2]:=temp[2]; d1[1,3]:=temp[3];

d1[1,4]:=temp[4]; d1[1,5]:=temp[5];

p2;

end;{5}

end;{3}

procedure p2; {第 5 列}

var i1,i2,i3,i4:integer;

tr2:boolean;

begin

for i1:=1 to 4 do

for i2:=1 to 4 do

for i3:=1 to 4 do

for i4:=1 to 4 do

if (d1[1,5]+s[i1]+s[i2]+s[i3]+s[i4])=sum1 then begin

assign_g(d1[1,5],s[i1],s[i2],s[i3],s[i4]);

look(2,5,g1,tr2);

if tr2 then p3;

end;

end;

procedure p3; {主对角线}

var temp1,temp2:shortint;

j:integer;

begin{3}

temp1:=d1[1,1]; temp2:=d1[5,5];

for j:=1 to tt do

begin{5}

temp:=a1[j];

if (temp[1]=temp1)and(temp[5]=temp2) then

begin

d1[2,2]:=temp[2]; d1[3,3]:=temp[3]; d1[4,4]:=temp[4]; p4;

end;

end;{5}

end;{3}

procedure p4; {第 5 行 }

var i1,i2,i3,i4:integer;

tr4:boolean;

begin

for i1:=1 to 4 do

for i2:=1 to 4 do

for i3:=1 to 4 do

for i4:=1 to 4 do

if (s[i1]+s[i2]+s[i3]+s[i4]+d1[5,5])=sum1 then begin

assign_g(s[i1],s[i2],s[i3],s[i4],d1[5,5]); look(1,5,g1,tr4);

if tr4 then p5;

end;

end;

procedure p5; {次对角线及第 4 列,第 2 列,第 3 行} label 50;

var temp1,temp2,temp3,t31,t32,t34,t5:shortint; tr5,tr52,tr53:boolean;

j:integer;

begin

temp1:=d1[5,1]; temp2:=d1[3,3]; temp3:=d1[1,5]; for j:=1 to tt do

begin

temp:=a1[j];

if (temp[1]=temp1) and (temp[3]=temp2) and (temp[5]=temp3) then

begin {p5.3}

d1[4,2]:=temp[2];

d1[2,4]:=temp[4];

t34:=sum1-(d1[1,4]+d1[2,4]+d1[4,4]+d1[5,4]); if (t34<0)or(t34>9) then goto 50;

assign_g(d1[1,4],d1[2,4],t34,d1[4,4],d1[5,4]); look(2,4,g1,tr5);

if tr5=false then goto 50;

t32:=sum1-(d1[1,2]+d1[2,2]+d1[4,2]+d1[5,2]); if (t32<0)or(t32>9) then goto 50;

assign_g(d1[1,2],d1[2,2],t32,d1[4,2],d1[5,2]); look(2,2,g1,tr52);

if tr52=false then goto 50;

t31:=sum1-(d1[3,2]+d1[3,3]+d1[3,4]+d1[3,5]); if (t31<=0)or(t31>9) then goto 50;

assign_g(t31,d1[3,2],d1[3,3],d1[3,4],d1[3,5]); look(1,3,g1,tr53);

if tr53 then p6;

end;{p5.3}

50:

end;

end;

procedure p6; { 第 1 列, 第 2,4 行, 第 3 列 } label 60;

var i1,i2,i3,i4:integer;

t23,t43:shortint;

tr6:boolean;

begin

for i1:=1 to 9 do

for i2:=1 to 9 do

begin

assign_g(d1[1,1],i1,d1[3,1],i2,d1[5,1]);

look(2,1,g1,tr6);

if tr6=false then goto 60;

t23:=sum1-(d1[2,1]+d1[2,2]+d1[2,4]+d1[2,5]); if (t23<0)or(t23>=9) then goto 60;

assign_g(d1[2,1],d1[2,2],t23,d1[2,4],d1[2,5]); look(1,2,g1,tr6);

if tr6=false then goto 60;

t43:=sum1-(d1[4,1]+d1[4,2]+d1[4,4]+d1[4,5]); if (t43<0)or(t43>9) then goto 60;

assign_g(d1[4,1],d1[4,2],t43,d1[4,4],d1[4,5]); look(1,4,g1,tr6);

if tr6=false then goto 60;

if (d1[1,3]+d1[2,3]+d1[3,3]+d1[4,3]+d1[5,3])<>sum1 then goto 60;

for i3:=1 to 5 do g1[i3]:=d1[i3,3];

look(2,3,g1,tr6);

if tr6=false then goto 60;

inc(ss); writeln("No.",ss);

for i3:=1 to 5 do

begin for i4:=1 to 5 do write(d1[i3,i4]:2); writeln; end; 60:;

end;

end;

begin

write("d[1,1]="); readln(r);

write("sum of row="); readln(sum1);

ss:=0; prim1; p1;

if ss=0 then writeln("No Solution!");

end.

全排列问题

求 1,2,...,n 这n个数字的全部可能的排列.

program lxw006;

const nn=20;

type row=array [1..20] of shortint;

var p: row;

n,i: integer;

num:longint;

procedure wrtperm(n:integer; var s:row); var i:integer;

begin

for i:=1 to n do write(s[i]:3);

writeln;

end;

procedure perm(n:integer; var p:row; var i:integer); var j,j1,j2,t,m:integer;

begin

i:=n;

repeat dec(i) until (p[i]<p[i+1]) or (i<1); if i>0 then

begin

j:=i+1;

for t:=i+1 to n do

if p[i]<p[t] then j:=t;

m:=p[i]; p[i]:=p[j]; p[j]:=m;

t:=(n-i) div 2;

for j:=1 to t do

begin

j1:=i+j; j2:=n-j+1;

m:=p[j1]; p[j1]:=p[j2]; p[j2]:=m; end;

end;

end;

begin {main}

writeln("输入N:(<=20)"); readln(n); num:=1;

for i:=1 to n do p[i]:=i;

i:=1;

while i>0 do

begin

wrtperm(n,p); perm(n,p,i);

if i>0 then inc(num); end;

writeln("num=",num); end.

上一篇:不该过洋节
下一篇:弹球比赛规则
网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com