2006NOIP初赛

《2006NOIP初赛》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.Programex403;ConstNN=7;TypeArr1=array[0..30]ofchar;vars:arr1;k,p:integer;functionfun1(s:arr1;a:char;n:integer):integer;varj:integer;beginj:=n;while(a0)dodec(j);dec(j)j:=j-1fun1:=j;end;Functionfun2(s:arr1;a:char;n:integer):integer;varj:integer;beginj:=1;while(a>s[j])and(j

2、inc(j);inc(j)j:=j+1fun2:=j;end;beginfork:=1toNNdos[k]:=chr(ord('A')+2*k+1);k:=fun1(s,'M',NN)+fun2(s,'M',NN);writeln(k);end.输出：_____________4.programex404;varx,x2:longint;proceduredigit(n,m:longint);varn2:integer;beginif(m>0)thenbeginn2:=nmod10;write(n2:2);if(m>1)thendigit(ndiv10,mdiv10);n2

3、:=nmod10;write(n2:2);end;end;beginwriteln('Inputanumber:');readln(x);x2:=1;while(x2

4、该输出（每行输出5个排列）：121321233231程序：Programex501;Vari,n,k:integer;a:array[1..10]ofinteger;count:longint;Procedureperm2(j:integer);vari,p,t:integer;beginif①thenbeginfori:=ktondobegininc(count);t:=a[k];a[k]:=a[i];a[i]:=t;for②dowrite(a[p]:1);write('');t:=a[k];a[k]:=a[i];a[i]:=t;if(countmod5=0)thenwri

5、teln;end;exit;end;fori:=jtondobegint:=a[j];a[j]:=a[i];a[i]:=t;③;t:=a[j];④;endend;beginwriteln('Entryn,k(k<=n):');read(n,k);count:=0;fori:=1tondoa[i]:=i;⑤;end.2．（TSP问题的交叉算子）TSP问题(TravelingSalesmanProblem)描述如下：给定n个城市，构成一个完全图，任何两城市之间都有一个代价（例如路程、旅费等），现要构造遍历所有城市的环路，每个城市恰好经过一次，求使总代价达到最小的一条环路。遗传算法

6、是求解该问题的一个很有效的近似算法。在该算法中，一个个体为一条环路，其编码方法之一是1到n这n个数字的一个排列，每个数字为一个城市的编号。例如当n=5时，“34215”表示该方案实施的路线为3->4->2->1->5->3。遗传算法的核心是通过两个个体的交叉操作，产生两个新的个体。下面的程序给出了最简单的一种交叉算法。具体过程如下：(1)选定中间一段作为互换段，该段的起止下标为t1，t2，随机生成t1，t2后，互换两段。(2)互换后，在每个新的排列中可能有重复数字，因而不能作为新个体的编码，一般再做两步处理：(2.1)将两个互换段中，共同的数字标记为0，表示已处理完。(2.2

7、)将两个互换段中其余数字标记为1，按顺序将互换段外重复的数字进行替换。例如：n=12，两个个体分别是：a1:1354*2679*1012811a2:32112*671011*8549t1=5，t2=8。上述每一行中，两个星号间的部分为互换段。假定数组的下标从1开始，互换后有：a1:1354*671011*1012811a2:32112*2679*8549然后，将数字6,7对应的项标记为0，星号内数字2,9,10,11对应的项标记为1，并且按顺序对应关系为:10<->2，11<->9。于是，将a1[9]=