信息学奥赛基础知识讲解

辅导信息学奥赛的几点体会,精心备课，突破疑点难点，追求直观高效。,分析：将十进数转换成二进制数,一般采用除二取余法。如果用一个数组b来存放二进制数,可以依次把所得的余数存入b0、b1、bn,最后按bn、bn-1、b1、b0的顺序输出这些余数,就得到了所求的二进制数。,1、读入一个十进制自然数，将其转换成二进制数后输出。,例如：,余数：,0,输出结果为：11001,0,1,0,1,1,0,1,2,3,4,5,6,var i,j,n:longint; b:array 031 of 01; begin readln(n); write(n,'=('); i:=0; while（ ）do begin （ ）; i:=i+1; 指定下一个余数的存放位置 n:=n div 2 产生的商将作为新的被除数 end; for j:=（ ）do write(bj); writeln(')2') end.,n0,bi:=n mod 2,i-1 downto 0,后进先出,Str1=3210 Str2=98765,a,0 1 2 3,b,5 6 7 8 9,5,7,9,1,1,0,1,对位 相加 进位,2、高精度加法,var str1,str2:string; a,b:array1100 of 09; l1,l2,i,j,k:integer; begin readln(str1); readln(str2); l1:=length(str1); l2:=length(str2); if l1l2 then j:=l1 else j:=l2; k:=0; for i:=l1 downto 1 do begin k:=k+1; ak:=ord(str1i)-ord('0'); end;,k:=0; for i:=l2 downto 1 do begin k:=k+1; bk:=ord(str2i)-ord('0'); end; for i:=1 to j do begin ai:=ai+bi; if ai=10 then begin ai:=（ ）; ai+1:=（ ）; end; end; if ai+1=0 then j:=j-1; for i:=j+1 downto 1 do write(ai); writeln; end.,处理进位,从低位到高位依次将各位数相加,用字符串形式输入加数和被加数,ai-10,ai+1+1,分析：类似加法，可以用竖式求乘法。在做乘法运算时，同样也有进位，同时对每一位进行乘法运算时，必须进行错位相加。,8 4 8 2 3,×,2 5 4 4 1 6 9 6,1 9 5 0 4,3*8+0+0=24 c1=4,3*4+2+0=14 c2=4,3*8+1+0=25 c3=5,c4=2,2*8+0+4=20 c2=0,2*4+2+5=15 c3=5,2*8+1+2=19 c4=9,c5=1,3、高精度乘法,var s1,s2:string; a,b:array1100of 09; c:array1200of 09; la,lb,lc, i,j,x,y,z,w:integer; begin readln(s1); readln(s2); la:=length(s1); lb:=length(s2); lc:=la+lb; 积的位数为la+lb-1或者la+lb； for i:=la downto 1 do ala-i+1:=ord(s1i)-ord('0'); for i:=lb downto 1 do blb-i+1:=ord(s2i)-ord('0'); for i:=lc downto 1 do ci:=0; for i:=1 to la do begin x:=0; 上次乘积进位初始化 for j:=1 to lb do 对乘数的每一位进行处理 begin x:=ai*bj+x div 10+ci+j-1; ci+j-1:= x mod 10; end; ci+j:= x div 10; end; while (clc=0) and (lc1) do lc:=lc-1; for i:=lc downto 1 do write(ci); writeln; end.,var yh:array15,15of integer; i,j:integer; begin yh1,1:=1; for i:=2 to 5 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 5 do begin for j:=1 to i do write(yhi,j:3); writeln; end; end.,1,1,1,1,1,2,1,1,3,3,1,1,4,6,4,4、阅读程序，写出运行结果。,5、2001年普及组、提高组初赛试题（穷举法） 在A、B两个城市之间设有N个路站(如下图中的S1，且N100)，城市与路站之间、路站和路站之间各有若干条路段(各路段数=20，且每条路段上的距离均为一个整数)。 A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段，最后到达B。通路上路段距离之和称为通路距离(最大距离=1000)。当所有的路段距离给出之后，求出所有不同距离的通路个数(相同距离仅记一次)。 例如：下图所示是当N=1时的情况：,从A到B的通路条数为6，但因其中通路5+5=4+6，所以满足条件的不同距离的通路条数为5。 数据结构： N记录A，B间路站的个数； 数组Di，0记录第i-1个到第i个路站间路段的个数; Di，1，Di，2，记录每个路段的距离; 数组G记录可取到的距离。,0 1 1 1 8+4+3=15 g15=1,0 1 1 2 8+4+4=16 g16=1,0 1 2 1 8+5+3=16 g16=1,0 1 2 2 8+5+4=17 g17=1,0 1 3 1 8+7+3=18 g18=1,0 1 3 2 8+7+4=19 g19=1,0 2 1 1 6+4+3=13 g13=1,0 2 1 2 6+4+4=14 g14=1,0 2 2 1 6+5+3=14 g14=1,0 2 2 2 6+5+4=15 g15=1,0 2 3 1 6+7+3=16 g16=1,0 2 3 2 6+7+4=17 g17=1,b0 b1 b2 b3,1 1 1 1 穷举结束,D1，0=2, D1，1=8, D1，2=6 D2，0=3, D2，1=4, D2，2=5， D2，3=7 D3，0=2, D3，1=3, D3，2=4,var i,j,n,s:integer; b:array0100 of integer; d:array0100,020 of integer; g:array01000 of 01; begin readln(n); for i:=1 to n+1 do begin readln(di,0); for j:=1 to di,0 do read(di,j); end; d0,0:=1; for i:=1 to n+1 do bi:=1; b0:=0; for i:=1 to 1000 do gi:=0;,while( )do begin s:=0; for i:=1 to n+1 do s:=( ); gs:=1; j:=n+1; while( )do j:=j-1; bj:=bj+1; for i:=j+1 to n+1 do bi:=1; end; s:=0; for i:=1 to 1000 do( ); writeln(s); readln; end.,b01,s+d i , bi ,bj=dj,0,s:=s+gi,穷举用,循环开关,求当前通路的距离,统计不同的通路条数,作记录,产生一种新的方案,要求在国际象棋棋盘上放置八个皇后，使她们不能互相攻击，即任何两个皇后不能处在同一行、同一列、同一条线上。请找出所有的摆法。,分析： 如果我们把8*8的棋盘看成是一个平面直角坐标系，那么任意两个皇后在平面上的坐标应同时满足以下三个条件： 两个皇后的横坐标不相等。 两个皇后的纵坐标不相等。 两个皇后的横坐标之差的绝对值不等于纵坐标之差的绝对值。 我们用数组xi来描述八个皇后在棋盘上的状态， xi =j表示在第i行的第j列放置了一个皇后。,IK,当IK时，XI XK,当IK时，|I-K|XI-XK|,6、八皇后问题（回溯法）,const n=8; var i,j,k:integer; x:array1n of integer; function place(k:integer):boolean; var i:integer; begin place:=true; for i:=1 to k-1 do if ( ) or (abs(xi-xk)=abs(i-k) then( ) ; end; procedure print; var i:integer; begin for i:=1 to n do write(xi:4); writeln; end;,procedure try(k:integer); var i:integer; begin if( )then begin print; exit end; for i:= 1 to n do begin ( ); if( )then try(k+1); end; end ; begin try(1); end.,xi=xk,k=n+1,place:=false,xk:=i,place(k),如下图所示为一个数字三角形，请编程计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。（只要求输出总和） 规定： 一步可沿左斜线向下或右斜线向下走； 图形行数小于等于100； 三角形中的数字为0，1，99; 测试数据通过键盘逐行输入，如下图数据应以如下所示格式输入： 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输出：30,