数学与程序设计 章维铣
begin
assign(input,'game.in'); reset(input);
assign(output,'game.out'); rewrite(output); readln(g);
for i:=1 to g do begin
readln(m,n); if m while (m div n=1) and (m<>n) do begin t:=m mod n; m:=n; n:=t; f:=-f; end; if f=1 then writeln('Stan wins') else writeln('Ollie wins'); end; close(input); close(output); end. 题2 不相关元素（Irrelevant Elements） 【问题描述】 年轻的密码分析学家Georgie正在研究产生从0到m – 1的随机数的不同的方案。他认为标准的随机数发生器不够好。所以，他发明了一个更为随机性的随机数产生方案。 首先，Georgie选择n并且产生n个从0到m – 1的随机数。产生的随机数为a1,a2,??,an。然后，Georgie计算出每对相邻的两个数的和。把初始的数组替换成为和的数组，这样得到n-1个整数：a1 + a2，a2 + a3，??，an–1 + an。然后对新的数组执行同样的操作，得到n-2个数。重复这个过程，直到只有一个数剩下。这个数取它摸m的值。这样给出这个过程产生的结果。 Georgie自豪地向他的计算机老师描述这个方案，却被老师指出这个方案有很多缺点。其中一个重要的缺点是这个过程的结果有时候甚至不依赖于最初产生的某些数。比如，当n=3并且m=2，这个时候，结果不依赖于a2。 第 21 页 共 29 页 数学与程序设计 章维铣 现在，Georgie想要研究这个现象。如果产生的结果不依赖于初始数组的第i个元素，那么，他称这个元素为不相关的。他考虑不同的n和m，想要知道对于这些参数，哪些元素是不相关的。你帮他找出来。 输入 9 输入文件包含n和m（1 <= n <= 100,000，2 <= m <= 10）。 输出 对于给定的n和m，输出文件的第一行输出初始数组中不相关元素的数量。第二行输出所有的i，其中第i个元素是不相关的。第二行输出的数必须升序排列并且相邻两数间严格用一个空格隔开。 样例 IRRELE.IN 3 2 IRRELE.OUT 1 2 【算法提示】 1.a1,a2,…an经n-1次求和操作后，其和表示为 1i?1n?1a1?Cna?...?Ca?....?C?12n?1in?1an 对其取模与 ai无关的条件是 i?1Cn?1 mod m=0 即 1i?1(n?1)(n?2)...(n?i?1)为整数 Cn?1= (i?1)!mm2.为了简化运算，上式为整数的等价条件是分子部分的质因子集包含分母部分的质因子集。 【参考程序】 program irrele; var e,sun,i,nn,j,k,n,m:longint; a:array[1..1000,1..2]of longint; b:array[1..1000]of longint; r:array[1..200000] of longint; f:boolean; function check(i:longint):boolean; var j:longint; fl:boolean; begin 第 22 页 共 29 页 数学与程序设计 章维铣 fl:=true; for j:=2 to round(sqrt(i)) do if i mod j=0 then begin fl:=false; break; end; check:=fl; end; begin assign(input,'irrele.in'); reset(input); assign(output,'irrele.out'); rewrite(output); readln(n,m); close(input); if n=1 then begin writeln(0); close(output); halt; end; sun:=0; e:=0; fillchar(a,sizeof(a),0); for i:=2 to m do begin if (check(i)) and (m mod i=0) then begin e:=e+1; a[e,1]:=i; while m mod i=0 do begin a[e,2]:=a[e,2]+1; m:=m div i; end; end; if m=1 then break; end; f:=true; fillchar(b,sizeof(b),0); nn:=n; n:=n-1; for i:=1 to e do begin while n mod a[i,1]=0 do begin n:=n div a[i,1]; b[i]:=b[i]+1; end; if b[i] if f then begin sun:=sun+1; r[sun]:=2; end; n:=nn; for i:=3 to (n+1) div 2 do 第 23 页 共 29 页 数学与程序设计 章维铣 begin k:=i-1; for j:=1 to e do begin while k mod a[j,1]=0 do begin k:=k div a[j,1]; b[j]:=b[j]-1; end; if k=1 then break; end; k:=n-i+1; for j:=1 to e do begin while k mod a[j,1]=0 do begin k:=k div a[j,1]; b[j]:=b[j]+1; end; if k=1 then break; end; f:=true; for j:=1 to e do if b[j] sun:=sun+1; r[sun]:=i; end; end; for i:=sun downto 1 do begin if n+1-r[i]<>r[i] then begin sun:=sun+1; r[sun]:=n+1-r[i]; end; end; writeln(sun); for i:=1 to sun do begin if i<>1 then write(' '); write(r[i]); end; if sun<>0 then writeln; close(output); end. 题3 游戏节目(Gladiators) 第 24 页 共 29 页 数学与程序设计 章维铣 【问题描述】 电视游戏节目Gladiators的最后一关是障碍赛。为了使比赛多样化，每星期的障碍赛路线都是不一样的。路线是由m个障碍物一个接一个地排下来的。障碍物的高度各不相同。每个障碍物有两个高度相等的平台组成。在路线上，一个障碍物的两个平台之间只可以摆放高度比它们高的平台。 左图是从侧面看障碍物的形状。右图是一条合法的路线，有5个障碍物组成，游戏者将从左到右越过这些障碍。 游戏的创作者希望即使是不同的路线，游戏的结果也是可比的。因此，他希望每种路线的难度都差不多。 一条路线的难度等于所有高度比左面一个平台高的平台的数目，最左边的平台总是计算在内，因为它左面没有平台，可以假设高度为0。例如，右图的路线难度为4。 你的任务是：对于已知的障碍物个数和难度，计算有多少种不同的路线。 输入 输入数据包含两个非负整数m和k，m是障碍物的个数，k是要求的难度。 输出 100 由m个障碍物组成的难度为k的路线有多少种？我们保证答案不超过10。 样例 GLADIATORS.IN 3 2 GLADIATORS.OUT 8 【算法提示】 m个障碍物组成的难度为k的路线数设为s(m,k),s(m,k)可看成前m-1个平台摆放后，再将第m个平台插入进去，第m个平台插入的位置分为两种，一种是难度不变；另一种难度增加1。根据加法原理，s(m,k)=a*s(m-1,k)+b*(m-1,k-1);a是使难度不变的可插入位置数，b是使难度加1的可插入位置数。对于(m-1,k)，插入位置从左到右共有k个；对于（m-1,k-1）, 插入位置从右到左共有2*m-k个（第m个平台有2m个位置可插入）。 得到递推公式 s(m,k)=(2*m-k)*s(m-1,k-1)+k*s(m-1,k) 【参考程序】 Program gladiators; Const infile='gladiators.in'; oufile='gladiators.out'; 第 25 页 共 29 页 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数学与程序设计(5)在线全文阅读。
相关推荐：