下载文档原格式
2009年东莞市小学生程序设计竞赛镇区选拨赛上机试题分析
一、最大的数
本题目利用穷举法求和,关键在于变量类型的设置。数据范围说明:60%的M的值小于等于30000，100%的M的值小于等于1000000000. 求和的变量S用整型能过6个点，用长整型能过10个点。
主要程序如下：
s:=0; n:=1;
s:=s+n;
while s<=m do
begin
n:=n+1;
s:=s+n;
end;
n:=n-1;
二、有趣的等式
本题的解法有很多，最简单的用穷举法同样能把题目的10测试点全部通过。由于100%的数据N小于等于1000，所以N的3次方的值不会超过1000000000，用长整型设置数据就可以了。
那么在这里说明一下参考程序的算法。从题目中1^3=1=1, 2^3=3+5=8, 3^3=7+9+11=27, 4^3=13+15+17+19=64我们不难发现对于不同的N（N=1，2，3……），其首个奇数加数有如下规律：
1^3：1
2^3：3
3^3：7
4^3：13
5^3：21
1+（2）=3——3+（4）=7——7+（6）=13——13+（8）=21
我们发现在每两两奇数加数的差值是一个首项为2，公差为2的等差数列，因此我们可以通过等差数列求和公式把对于N（N=2，3，4……）的首个奇数加数求出来，进而把其他奇数列出。
主要程序如下：
k:=n*n-n+1;{K为N的首个奇数加数}
for i:=1 to n do
begin
writeln(fout,k);
k:=k+2;
end;
如果学生不会运用等差数列公式，如下程序段同样可以达到目的：
read(n);i:=1;
for a:=1to n-1o
i:=i+2*a; {I为N的首个奇数加数}
for a:=1 to n do
begin m[a]:=i;
i:=i+2;
end;
三、猴子选大王
这是一道典型的约瑟夫问题，在08小学生程序设计比赛镇初赛中第二题中出现过，算法是一样的。
用数组元素表示n个猴子,猴子有两种状态:留在圈上或者退出圆圈。我们可以用设标记的方法区分这两种状态，以确定留在圆圈上参加报数的猴子。
建立数组b[n]，其下标代表开始报数时猴子所处的位置，当数组元素b[i]的值为true时，表示猴子在圈上，当a[i]的值为flase时，表示猴子已经退出圆圈。
设立两个计数器，分别统计报数的情况k和圆圈中剩下的猴子数s。从第i个猴子开始报数，当某个猴子所报数为m时，将代表猴子的数组元素置flase，打印该猴子的编号，并将圆圈中的猴子数s减1，当圆圈中剩下的猴子数为1时，程序结束。
i:=1; k:=1; s:=n;
fillchar(b,sizeof(b),true);
while s>1 do begin
inc(i);
if i>n then i:=1; {当全部猴子报数完，又从第一只猴子开始重新报数}
if b[i] then begin
inc(k);
if k>m then k:=1; {当猴子报数超过M，又从1开始重新报数}
if k=m then begin {当报数到M，则对应的猴子出队}
b[i]:=false;
dec(s);
end;
end;
end;
四、聪明的小李
这是一道典型的贪心算法的题目，由于正整数N的有效数位为240位，所以很自然地采取了字符串类型存储N。那么如何决定哪S位被删除呢？是不是最大的S个数字呢？为了尽可能逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的字符串最小的字符删去,即按高位到低位的顺序搜索,若各位数字递增,则删除最后一个数字;否则删除第一个递减区间的首字符,这样删一便形成了一个新数字串.然后回到串首,按上述规则再删除下一个数字.重复以上过程S次为止,剩下的数字串便是问题的解了.对于可能会出现在串首的0情况或整个数字串都是0的情况要把无用的零删去。在这里我觉得还要注意的一个地方就是题目中并无提及删去S位后的数字的长度为length(n)-s,因此在考虑题目的时候不需要考虑每删除一个数字后新的数字是否首位为0，只要满足删除一个数字后新的字符串为最小即可。
参考程序如下：
for a:=1 to s do
begin
bj:=0;
c:=length(n);
for b:=1 to c-1 do
if n[b]>n[b+1] then
begin
delete(n,b,1); {搜索第一个递增区间的末字符，然后删除}
bj:=1;
break;
end;
if bj=0 then delete(n,c,1); {
end;
while (n[1]='0') and (length(n)>1) do delete(n,1,1);{删除串首可能产生的无用0}
