信息奥赛题库(含答案)

信息奥赛题库（2011-4-3）---【信息奥赛题库】编制组打印杨辉三角前10行标程programyhsj10;varyh:array[1..10,0..10]ofinteger;i,j:integer;beginyh[1,1]:=1;fori:=2to10doforj:=1toidoyh[i,j]:=yh[i-1,j]+yh[i-1,j-1];fori:=1to10dobeginforj:=1toidowrite(yh[i,j],'');writeln;end;End.2.读入10个数，输出偶数项及它们和，输出奇数项及它们的平均数。（读入10个数输出偶数项及它们和输出奇数项及它们的平均数）标程programexe6_1;vari,s,t,n:integer;a:array[1..10]ofinteger;beginfori:=1to10doread(a[i]);fori:=1to10doifimod2=0thenbeginwrite(a[i],'');s:=s+a[i];end;writeln(s);fori:=1to10doifimod2<>0thenbeginwrite(a[i],'');t:=t+a[i];n:=n+1;end;writeln(t/n);end.3.读入n个数，打印其中的最大数及其位置号（读入n个数打印其中的最大数及其位置号）标程programexe6_2;vari,max,min,t,n:integer;a:array[1..10]ofinteger;beginfori:=1to10doread(a[i]);max:=a[1];min:=a[1];t:=1;n:=1;fori:=2to9dobeginifmax<a[i]thenbeginmax:=a[i];t:=I;end;ifmin>a[i]thenbeginmin:=a[i];n:=I;end;end;writeln(max,'',t);writeln(min,'',n);end.4.交换a和b的值标程programp1_1;vara,b,x:integer;beginread(a,b);x:=a;a:=b;b:=x;writeln(a,'',b);End.Problem1:leader2谁是组长2问题描述八中信息组需要选一个组长。信息组一共有n个人，分别用1到n编号，其中m个人参与了投票。得票数过半（票数大于mdiv2）的人将被选为组长。输入数据将告知这m个人分别将票投给了谁，请统计出谁将担任八中信息组的组长。输入数据第一行两个数n和m。第二行有m个数，这些数都是不超过n的正整数，表明这m个人的选择。输出数据输出将被选为组长的人。如果没有人的票数过半，请输出-1。输入样例747727输出样例7时间限制各测试点1秒内存限制你的程序将被分配32MB的运行空间数据规模1<=n<=maxlongint1<=m<=1000000考察内容查找第k大元素programleader2;vara:array[1..1000000]oflongint;n,m:longint;procedurereadp;vari:longint;beginreadln(n,m);fori:=1tomdoread(a[i]);end;procedureswap(vart1,t2:longint);vart3:longint;begint3:=t1;t1:=t2;t2:=t3;end;functionfind(l,r,k:longint):longint;vari,j,mid:longint;beginifl=rthenexit(a[l]);i:=l;j:=r;mid:=a[(i+j)div2];repeatwhilea[i]<middoinc(i);whilea[j]>middodec(j);ifi<=jthenbeginswap(a[i],a[j]);inc(i);dec(j);end;untili>j;if(l<=j)and(k<=j)thenexit(find(l,j,k));if(i<=r)and(k>=i)thenexit(find(i,r,k));exit(mid);end;functionleader(x:longint):boolean;vari,count:longint;begincount:=0;fori:=1tomdoifa[i]=xtheninc(count);exit(count>mdiv2);end;{====main====}varx:longint;beginassign(input,'leader2.in');reset(input);assign(output,'leader2.out');rewrite(output);readp;x:=find(1,m,mdiv2);ifleader(x)thenwriteln(x)elsewriteln(-1);close(input);close(output);End.Problem2:typewrt有故障的打字机问题描述一台打字机准备将1到10^n的数依次打出。在打印过程中，这台打字机出现了一个故障：数字“3”打不出来。因此，所有含有数字“3”的数都没有被正确地打出。试问没有被正确打出的数一共有多少个。输入数据输入一个正整数n。输出数据输出从1到10^n这些数中不能被正确打印的数的个数。输入样例2输出样例19时间限制各测试点1秒内存限制你的程序将被分配32MB的运行空间数据规模n<=1000考察内容高精度运算（乘法，高精度乘以单精度）programtypewrt;typearr=array[0..1000]ofinteger;functionmul(a:arr;b:integer):arr;vari:integer;ans:arr;beginfillchar(ans,sizeof(ans),0);fori:=1toa[0]dobeginans[i]:=ans[i]+a[i]*b;ans[i+1]:=ans[i+1]+ans[i]div10;ans[i]:=ans[i]mod10;end;ifans[a[0]+1]>0thenans[0]:=a[0]+1elseans[0]:=a[0];exit(ans);end;{===main===}vari,n:integer;ans:arr;beginassign(input,'typewrt.in');reset(input);assign(output,'typewrt.out');rewrite(output);readln(n);ans[0]:=1;ans[1]:=1;fori:=1tondoans:=mul(ans,9);fori:=ndownto2dowrite(9-ans[i]);writeln(10-ans[1]);close(input);close(output);End.Problem3:maxsum最大约数和问题描述选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。输入数据输入一个正整数S。输出数据输出最大的约数之和。样例输入11样例输出9样例说明取数字4和6，可以得到最大值(1+2)+(1+2+3)=9。时间限制各测试点1秒内存限制你的程序将被分配32MB的运行空间数据规模S<=1000考察内容0/1背包programmaxsum;vara:array[1..1000]oflongint;f:array[0..1000,0..1000]oflongint;s:longint;functionsum(x:longint):longint;vari,ans:longint;beginans:=0;fori:=1tox-1doifxmodi=0thenans:=ans+i;exit(ans);end;proceduresolve;vari,j:longint;beginfori:=1tosdoforj:=1tosdobeginf[i,j]:=f[i-1,j];if(j-i>=0)and(f[i-1,j-i]+a[i]>f[i,j])thenf[i,j]:=f[i-1,j-i]+a[i];end;end;{===main===}vari:longint;beginassign(input,'maxsum.in');reset(input);assign(output,'maxsum.out');rewrite(output);readln(s);fori:=1tosdoa[i]:=sum(i);solve;writeln(f[s,s]);close(input);close(output);end.Problem4:flu流感会结束吗问题描述八中一共有n个学生。这n个学生里一共有m对朋友关系。在流感发作期，每个健康学生都要看望当天他生病的朋友（如果有的话），并在第二天被传染上疾病（除非他在免疫期内）；每个生病的学生在第二天都会痊愈，并在这一天具有免疫性。从第三天起，看望生病的朋友将再次使他染上流感。初始时（第一天），只有一个学生患有流感。试问多少天后流感会自动结束。输入数据第一行输入两个正整数n和m。接下来m行每行两个正整数x,y，表示编号为x的学生和编号为y的学生是一对朋友。输入数据保证每一对朋友关系只描述一次。最后一行输入一个正整数，代表初始时患有流感的学生的编号。输出数据如果流感永远不会结束，请输出-1，否则输出多少天后流感会结束。答案保证不超过2000000000。样例输入44122334241样例输出3样例说明第一天1号学生生病，2号学生访问他；第二天2号学生生病，其它三个学生访问他，由于1号处于免疫期，未患流感；第三天3、4号学生生病，2号学生访问他们。第四天3、4号学生痊愈，流感结束。时间限制各测试点1秒内存限制你的程序将被分配32MB的运行空间数据范围n,m<=100000。考察内容图的宽度优先遍历programflu;typepointer=^rec1;rec1=recordvalue:longint;next:pointer;end;rec2=recordnode,step:longint;end;varconnect:array[1..100000]ofpointer;queue:array[1..100000]ofrec2;hash:array[1..100000]ofboolean;n,m,t:longint;procedureinsert(x,y:longint);vartmp:pointer;beginnew(tmp);tmp^.value:=x;tmp^.next:=connect[y];connect[y]:=tmp;end;procedurereadp;vari,x,y:longint;beginreadln(n,m);fori:=1tomdobeginreadln(x,y);insert(x,y);insert(y,x);end;readln(t);end;proceduresolve;varclosed,open:longint;tmp:pointer;beginclosed:=0;open:=1;queue[1].node:=t;queue[1].step:=1;hash[t]:=true;repeatclosed:=closed+1;tmp:=connect[queue[closed].node];whiletmp<>nildobeginifnothash[tmp^.value]thenbeginhash[tmp^.value]:=true;open:=open+1;queue[open].node:=tmp^.value;queue[open].step:=queue[closed].step+1;end;tmp:=tmp^.next;end;untilclosed>=open;writeln(queue[open].step);end;beginassign(input,'flu.in');reset(input);assign(output,'flu.out');rewrite(output);readp;solve;close(input);close(output);End.从键盘输入10个数，将这10个数逆序输入，并求这10个数的和，输出这个和。programp1;vara:array[1..10]ofinteger;i,s:integer;beginfori:=1to10doread(a[i]);fori:=10downto1dowrite(a[i],'');writeln;s:=0;fori:=1to10dos:=s+a[i];writeln('s=',s);end.用筛法求100以内的素数（质数）。分析：素数是除了1和它本身以外没有其它约数的数。用筛法求素数的方法是：用质数筛去合数：从第一个素数2开始，把它的倍数去掉；这样2以后的第一个非0数就一定也是素数，把它的倍数也删了……重复这个删数过程，直到在所找到的素数后再也找不到一个非0数。把所有非0数输出。programp2;vara:array[1..100]ofinteger;i,j,k:integer;beginfori:=1to100doa[i]:=i;a[1]:=0;i:=2;whilei<=100dobegink:=i;whilek<=100dobegink:=k+i;a[k]:=0;end;i:=i+1;whilea[i]=0doi:=i+1;end;fori:=1to100doifa[i]<>0thenwrite(a[i],'');end.竞赛小组共有20位同学，这学期每位同学共参与了三项比赛，请统计每位同学的平均分。分析：定义一个20行3列的二维数组来存放这些成绩。定义一个20个元素的一维数组来存放平均分。programp1;vara:array[1..20,1..3]ofinteger;b:array[1..20]ofreal;i,j:integer;beginfori:=1to20dobeginforj:=1to3doread(a[i,j]);readln;end;fori:=1to20dob[i]:=0;fori:=1to20dobeginforj:=1to3dob[i]:=b[i]+a[i,j];b[i]:=b[i]/3;end;fori:=1to20dowrite(b[i]:5:1);writeln;end.求n个自然数的最大公约数;programgcd1;constmaxn=100;varn,i,gcd:integer;a:array[1..maxn]ofinteger;procedureenter;beginwrite('n=(<100)');readln(n);fori:=1tondorepeatwrite('a[',i,']=');readln(a[i]);untila[i]>0;end;procedurefind_gcd(x,y:integer);varr:integer;beginr:=xmody;whiler<>0dobeginx:=y;y:=r;r:=xmody;endgcd:=y;end;procedureprint;beginwriteln('GCD=',gcd);end;beginenter;gcd:=a[1];fori:=2tondofind_gcd(gcd,a[i]);print;end.编一程序，求从10名同学中选出3名代表，有几种不同的选法。（公式：C(m,n)=m!/n!*(m-n)!从m中选n)programzohe1;varm,n:integer;c:longint;functionfactor(x:integer):longint;vari:integer;p:longint;beginp:=1;fori:=1toxdop:=p*i;factor:=p;end;beginwrite('m,n=');readln(m,n);c:=factor(m)div(factor(n)*factor(m-n));writeln('c(',m,',',n,')=',c);end.例4：全局变量和局部变量。programlocal_global;vari,k:integer;proceduresub1;vari,j:integer;begini:=17;writeln('iinsub=',i);writeln('kinsub=',k);end;begini:=2;k:=9;writeln('iinmain=',i);writeln('kinsub=',k);sub1;writeln('iinmain=',i);writeln('jinmain=',j);readln;end.1、验证卡布列克运算。（cab.pas）任意一个四位数，只要它们各个位上的数字是不全相同的，就有这样的规律：1)将组成该四位数的四个数字由大到小排列，形成由这四个数字构成的最大的四位数；2)将组成该四位数的四个数字由小到大排列，形成由这四个数字构成的最小的四位数(如果四个数中含有0，则得到的数不足四位)；3)求两个数的差，得到一个新的四位数(高位零保留)。重复以上过程，最后得到的结果是6174，这个数被称为卡布列克数请你写一个程序，计算一个四位数经过上述运算最后得到卡布列克数所需的步数。输入文件：cab.in文件包含一行数据，即一个四位正整数。输出文件：cab.out文件包含一个整数，即步数。Programcab;varc,t:array[1..4]ofinteger;i,j,temp,step:integer;s:array[1..4]ofchar;beginfori:=1to4doread(s[i]);readln;fori:=4downto1doc[i]:=ord(s[5-i])-ord('0');step:=0;while(c[1]<>4)or(c[2]<>7)or(c[3]<>1)or(c[4]<>6)dobeginfori:=1to3doforj:=i+1to4doifc[i]>c[j]thenbegintemp:=c[i];c[i]:=c[j];c[j]:=tempend;fori:=1to4dot[i]:=c[5-i];fori:=1to4dobeginc[i]:=c[i]-t[i];j:=i;whilec[j]<0dobeginc[j]:=c[j]+10;j:=j+1;c[j]:=c[j]-1endend;step:=step+1end;writeln(step);end.2、最大整数。（string.pas）设有n个正整数（n≤30000），将它们联接成一排，组成一个最大的多位整数。例如：n=3时，3个整数13，312，343联接成的最大整数为：34331213又如：n=4时，4个整数7，13，4，246联接成的最大整数为：7424613输入文件：s.in文件第一行包含一个正整数，即正整数的个数n，文件第二行为n个正整数，各数之间用空格分隔。输出文件：s.out文件包含一行数据，即联接成的多位数。vara:array[1..30000]ofstring;n,i,j,k,code,m:integer;s:string;beginreadln(n);fori:=1tondobeginread(k);str(k,a[i]);end;fori:=ndownto2dobeginforj:=1toi-1doif(a[j]+a[j+1])<(a[j+1]+a[j])thenbegins:=a[j];a[j]:=a[j+1];a[j+1]:=s;end;end;.fori:=1tondowrite(a[i]);end.3、蛇形方阵。（snake.pas）任给n，试按如下方式对A[I,j]赋值，例如：Entern:6126715163581417264913182527101219242833112023293234212230313536输入文件：snake.in文件包含一个正整数，即阶数n。输出文件：snake.out文件包含n行，每行n个数的蛇形方阵。varn,i,j,r,c,k:integer;beginreadln(n);fori:=1tondobeginforj:=1tondobeginifi+j<=n+1thenk:=(i+j-2)*(i+j-1)div2+(i+j)mod2*i+(i+j-1)mod2*jelsebeginr:=n+1-i;c:=n+1-j;k:=n*n+1-(r+c-2)*(r+c-1)div2-(r+c)mod2*r-(r+c-1)mod2*c;end;write(k:4);end;writeln;end;end.4、谁拿了最多奖学金(scholar.pas)某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同：1)院士奖学金，每人8000元，期末平均成绩高于80分（>80），并且在本学期内发表1篇或1篇以上论文的学生均可获得；2)五四奖学金，每人4000元，期末平均成绩高于85分（>85），并且班级评议成绩高于80分（>80）的学生均可获得；3)成绩优秀奖，每人2000元，期末平均成绩高于90分（>90）的学生均可获得；4)西部奖学金，每人1000元，期末平均成绩高于85分（>85）的西部省份学生均可获得；5)班级贡献奖，每人850元，班级评议成绩高于80分（>80）的学生干部均可获得；只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。例如姚林的期末平均成绩是87分，班级评议成绩82分，同时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是4850元。现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件）。【输入文件】输入文件scholar.in的第一行是一个整数N（1<=N<=100），表示学生的总数。接下来的N行每行是一位学生的数据，从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。姓名是由大小写英文字母组成的长度不超过20的字符串（不含空格）；期末平均成绩和班级评议成绩都是0到100之间的整数（包括0和100）；是否是学生干部和是否是西部省份学生分别用一个字符表示，Y表示是，N表示不是；发表的论文数是0到10的整数（包括0和10）。每两个相邻数据项之间用一个空格分隔。【输出文件】输出文件scholar.out包括三行，第一行是获得最多奖金的学生的姓名，第二行是这名学生获得的奖金总数。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。第三行是这N个学生获得的奖学金的总数。【样例输入】4YaoLin8782YN0ChenRuiyi8878NY1LiXin9288NN0ZhangQin8387YN1【样例输出】ChenRuiyi900028700programscholar;varname:array[1..100]ofstring;a1,a2,a5:array[1..100]oflongint;a3,a4:array[1..100]ofchar;n,i,max,total,p:longint;maxname:string;ch:char;beginreadln(n);fori:=1tondobeginread(ch);whilech<>''dobeginname[i]:=name[i]+ch;read(ch);end;readln(a1[i],a2[i],ch,a3[i],ch,a4[i],ch,a5[i]);end;fori:=1tondobeginp:=0;if(a1[i]>80)and(a5[i]>=1)theninc(p,8000);if(a1[i]>85)and(a2[i]>80)theninc(p,4000);if(a1[i]>90)theninc(p,2000);if(a1[i]>85)and(a4[i]='Y')theninc(p,1000);if(a2[i]>80)and(a3[i]='Y')theninc(p,850);ifp>maxthenbeginmax:=p;maxname:=name[i];end;inc(total,p);end;writeln(maxname);writeln(max);writeln(total);end.奇数魔方阵把整数1到n（n为奇数）排成一个n*n方阵，使方阵中的每一行·每一列以及对角线上的数之和都相同programjsmfz;varmagic:array[1..100,1..100]ofinteger;i,j,k,h,l,n:integer;beginread(n);fori:=1tondoforj:=1tondomagic[i,j]:=0;k:=1;i:=1;j:=ndiv2+1;magic[i,j]:=k;whilek<n*ndobegink:=k+1;h:=i-1;l:=j-1;ifl=0thenl:=n;ifmagic[h,l]=0thenbeginmagic[h,l]:=k;i:=h;j:=l;endelsebeginmagic[i+1,j]:=k;i:=i+1;end;end;fori:=1tondobeginforj:=1tondowrite(magic[i,j]:3);writeln;end;end.输入50名学生4门功课的成绩，输出各人各科成绩及总分programcj;vara:array[1..50,1..6]ofinteger;i,j:integer;beginfori:=1to50doforj:=1to5doread(a[i,j]);fori:=1to50doforj:=2to5doa[i,6]:=a[i,6]+a[i,j];fori:=1to50dobeginforj:=1to6dowrite(a[i,j],'');writeln;end;End.稀疏矩阵化简programxsjz;constn=5;vara:array[1..n,1..n]ofinteger;b:array[1..100,1..3]ofinteger;i,j,k:integer;beginfori:=1tondoforj:=1tondoread(a[i,j]);k:=0;fori:=1tondoforj:=1tondoifa[i,j]<>0thenbegink:=k+1;b[k,1]:=i;b[k,2]:=j;b[k,3]:=a[i,j];end;fori:=1tokdobeginforj:=1to3dowrite(b[i,j]:3);end;End.将a和b中大的值给max的程序programp1_2;vara,b,max:integer;beginread(a,b);max:=a;ifb>maxthenmax:=b;writeln(max);End.给定一个正整数n，判定它是否为素数的程序programp1_3;vari,n,r,w:integer;beginread(n);w:=0i:=2;repeatr:=nmodi;ifr=0thenw:=1;i:=i+1;until(i>n-1)or(w=1);ifw=0thenwriteln('yes')elsewriteln('no')End.输入两个数a，b，输出较大的数。programtt;vara,b:integer;beginreadln(a,b);ifa>bthenwriteln(a)elsewriteln(b);end.某全自动加油站a,b,c三种汽油的单价(元/kg)分别是1.50、1.35和1.18，也提供了“自己加”或“协助加”两个服务等级，这样用户可以得到5%或10%的优惠。编一个程序，用户输入加油量、汽油品种和服务类型(f-自动，m-自己，e-协助)，然后计算应付款。programpcase1;varoil,help:char;kg,total:real;beginwrite('Entertheamountinkilograms(kg):');readln(kg);write('Whichtypeofthegasoline(a,b,c):');readln(oil);wirte('Whichtypeforservice(f,m,e):');readln(help);caseoilof'a':total:=1.50*kg;'b':total:=1.35*kg;'c':total:=1.18*kg;elsewriteln('InputError!')end;casehelpof'f':;'m':total:=total*(1-0.05);'e':total:=total*(1-0.10);elsewriteln('InputError!')end;writeln;writeln('Totalis',total:10:2);end.从键盘上读入年和月，输出该月有多少天。programpcase2;varyear,month,day:integer;runnian:boolean;beginwrite('Enteryearandmonth:');readln(year,month);casemonthof1,3,5,7,8,10,12:day:=31;4,6,9,11:day:=30;2:beginrunnian:=(yearmod400=0)or((yearmod4=0)and(yearmod100<>0));caserunnianoftrue:day:=28;false:day:=29;end;end;end;end.从键盘输入10个数，将这10个数逆序输入，并求这10个数的和，输出这个和。programp1;vara:array[1..10]ofinteger;i,s:integer;beginfori:=1to10doread(a[i]);fori:=10downto1dowrite(a[i],'');writeln;s:=0;fori:=1to10dos:=s+a[i];writeln('s=',s);end.用筛法求100以内的素数（质数）。分析：素数是除了1和它本身以外没有其它约数的数。用筛法求素数的方法是：用质数筛去合数：从第一个素数2开始，把它的倍数去掉；这样2以后的第一个非0数就一定也是素数，把它的倍数也删了……重复这个删数过程，直到在所找到的素数后再也找不到一个非0数。把所有非0数输出。programp2;vara:array[1..100]ofinteger;i,j,k:integer;beginfori:=1to100doa[i]:=i;a[1]:=0;i:=2;whilei<=100dobegink:=i;whilek<=100dobegink:=k+i;a[k]:=0;end;i:=i+1;whilea[i]=0doi:=i+1;end;fori:=1to100doifa[i]<>0thenwrite(a[i],'');end.下面是一个建立和使用文件的程序：programwenjian;constn=3;m=2;typestudent=recordname:string;score:array[1..m]of0..100;end;varst:array[1..n]ofstudent;stfile:fileofstudent;sumst:array[1..n]ofinteger;sumsub:array[1..m]ofinteger;sum:integer;procedurenewfile;vari,j:integer;beginassign(stfile,'score.fil');rewrite(stfile);fori:=1tondobeginwriteln('Inputstudent',i,'nameand',m,'score');readln(st[i].name);forj:=1tomdoread(st[i].score[j]);readln;write(stfile,st[i]);end;close(stfile);writeln;writeln;end;procedurejisuan;vari,j:integer;beginassign(stfile,'score.fil');reset(stfile);fori:=1tomdosumsub[i]:=0;fori:=1tondobeginread(stfile,st[i]);withst[i]dobeginsumst[i]:=0;forj:=1tomdobeginsumst[i]:=sumst[i]+score[j];sumsub[j]:=sumsub[j]+score[j];end;end;end;close(stfile);sum:=0;fori:=1tondosum:=sum+sumst[i];fori:=1tondobeginwithst[i]dobeginwrite(name);forj:=1tomdowrite(score[j]:6);end;writeln(sumst[i]:6);end;write('sum=');fori:=1tomdowrite(sumsub[i]:6);writeln(sum:8);end;beginnewfile;jisuan;End.连续输入一序列整数,组成链表（并以动态的形式把它们记录下来）,当输入的数为-1时,停止输入,然后把输入的整数按相反的顺序输出.programlianbiao;typelink=^data;data=recordnum:integer;next:link;end;varp,q:link;i:integer;beginq:=nil;readln(i);whilei<>-1dobeginnew(p);withp^dobeginnum:=i;next:=q;end;q:=p;readln(i);end;whilep<>nildobeginwrite(p^.num:6);p:=p^.next;end;readln;end.输入若干整数（输入32767停止输入）排序（小到大）输出之。programlianbiao;typelink=^data;data=recordnum:integer;next:link;end;varhead,p,q,r:link;i:integer;beginhead:=nil;readln(i);whilei<>32767dobeginnew(p);p^.num:=i;p^.next:=nil;ifhead=nilthenbeginhead:=p;endelsebeginq:=head;ifp^.num<q^.numthenbeginhead:=p;p^.next:=qendelsebeginwhile(p^.num>=q^.num)and(q<>nil)dobeginr:=q;q:=q^.next;end;ifq=nilthenr^.next:=pelsebeginr^.next:=p;p^.next:=qendend;end;readln(i);end;p:=head;whilep<>nildobeginwrite(p^.num:6);p:=p^.next;end;readln;end.计算n!可用递归公式如下:1当n=0时fac(n)={n*fac(n-1)当n>0时可编写程序如下:programfac2;varn:integer;functionfac(n:integer):real;beginifn=0thenfac:=1elsefac:=n*fac(n-1)end;beginwrite('n=');readln(n);writeln('fac(',n,')=',fac(n):6:0);End.楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法.设n阶台阶的走法数为f(n)显然有1n=1f(n)={2n=2f(n-1)+f(n-2)n>2可编程序如下：programlouti;varn:integer;functionf(x:integer):integer;beginifx=1thenf:=1elseifx=2thenf:=2elsef:=f(x-1)+f(x-2);end;beginwrite('n=');read(n);writeln('f(',n,')=',f(n))End.例3梵塔问题如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上不能出现大盘压小盘.找出移动次数最小的方案.程序如下:programfanta;varn:integer;proceduremove(n,a,b,c:integer);beginifn=1thenwriteln(a,'--->',c)elsebeginmove(n-1,a,c,b);writeln(a,'--->',c);move(n-1,b,a,c);end;end;beginwrite('Entern=');read(n);move(n,1,2,3);end.例4快速排序快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1,处理结束.程序如下:programkspv;constn=7;typearr=array[1..n]ofinteger;vara:arr;i:integer;procedurequicksort(varb:arr;s,t:integer);vari,j,x,t1:integer;begini:=s;j:=t;x:=b[i];repeatwhile(b[j]>=x)and(j>i)doj:=j-1;ifj>ithenbegint1:=b[i];b[i]:=b[j];b[j]:=t1;end;while(b[i]<=x)and(i<j)doi:=i+1;ifi<jthenbegint1:=b[j];b[j]:=b[i];b[i]:=t1;enduntili=j;b[i]:=x;i:=i+1;j:=j-1;ifs<jthenquicksort(b,s,j);ifi<tthenquicksort(b,i,t);end;beginwrite('inputdata:');fori:=1tondoread(a[i]);writeln;quicksort(a,1,n);write('outputdata:');fori:=1tondowrite(a[i]:6);writeln;end.例1由键盘上输入任意n个符号;输出它的全排列.programhh;constn=4;vari,k:integer;x:array[1..n]ofinteger;st:string[n];t:string[n];procedureinput;vari:integer;beginwrite('Enterstring=');readln(st);t:=st;end;functionplace(k:integer):boolean;vari:integer;beginplace:=true;fori:=1tok-1doifx[i]=x[k]thenbeginplace:=false;breakend;end;procedureprint;vari:integer;beginfori:=1tondowrite(t[x[i]]);writeln;end;begininput;k:=1;x[k]:=0;whilek>0dobeginx[k]:=x[k]+1;while(x[k]<=n)and(notplace(k))dox[k]:=x[k]+1;ifx[k]>nthenk:=k-1elseifk=nthenprintelsebegink:=k+1;x[k]:=0endend;end.例2.n个皇后问题:programhh;constn=8;vari,j,k:integer;x:array[1..n]ofinteger;functionplace(k:integer):boolean;vari:integer;beginplace:=true;fori:=1tok-1doif(x[i]=x[k])or(abs(x[i]-x[k])=abs(i-k))thenplace:=false;end;procedureprint;vari:integer;beginfori:=1tondowrite(x[i]:4);writeln;end;begink:=1;x[k]:=0;whilek>0dobeginx[k]:=x[k]+1;while(x[k]<=n)and(notplace(k))dox[k]:=x[k]+1;ifx[k]>nthenk:=k-1elseifk=nthenprintelsebegink:=k+1;x[k]:=0endend;End.插入排序varn,i,j:longint;a:array[0..10000]oflongint;beginreadln(n);fori:=1tondoread(a[i]);fori:=2tondobegina[0]:=a[i];j:=i-1;while(a[0]<a[j])and(j>0)dobegina[j+1]:=a[j];j:=j-1;end;a[j+1]:=a[0];end;fori:=1tondowrite(a[i]:4);end.归并排序（求逆序对）vara,x,y,z,b:array[1..100000]oflongint;n,i:longint;ans:int64;proceduremerge(l,mid,r:longint);vari,j,k:longint;beginfori:=ltomiddox[i]:=a[i];fori:=mid+1tordoy[i]:=a[i];i:=l;j:=mid+1;k:=l-1;whilek<rdobeginif((x[i]>=y[j])or(j>r))and(i<=mid)thenbegininc(k);z[k]:=x[i];inc(i);endelsebegininc(k);z[k]:=y[j];inc(j);ans:=ans+mid-i+1;end;end;fori:=ltordoa[i]:=z[i];end;proceduresort(l,r:longint);varmid:longint;beginmid:=(l+r)shr1;ifl<midthensort(l,mid);ifmid+1<rthensort(mid+1,r);merge(l,mid,r);end;procedureqsort(l,r:longint);vari,j,x,t:longint;begini:=l;j:=r;x:=b[(l+r)shr1];repeatwhileb[i]>xdoinc(i);whileb[j]<xdodec(j);ifi<=jthenbegint:=a[i];a[i]:=a[j];a[j]:=t;t:=b[i];b[i]:=b[j];b[j]:=t;inc(i);dec(j);end;untili>j;ifi<rthenqsort(i,r);ifj>lthenqsort(l,j);end;beginreadln(n);fori:=1tondoread(b[i]);fori:=1tondoread(a[i]);qsort(1,n);sort(1,n);writeln(ans);end.快速排序vara:array[1..10000]oflongint;n,i:longint;procedureasd(l,r:longint);vart,m,i,j:longint;begini:=l;j:=r;m:=a[(l+r)div2];repeatwhilem<a[i]doinc(i);whilem>a[j]dodec(j);ifi<=jthenbegint:=a[i];a[i]:=a[j];a[j]:=t;inc(i);dec(j);end;untili>j;ifj>lthenasd(l,j);ifi<rthenasd(i,r);end