第八届全国青少年信息学
奥林匹克联赛复赛普及组
解题报告
学生姓名 薛 原
（.天津实验中学，九年级（8B）班，300074）
目 录
一、级数求和（20分 NOIPC1）... 1
问题描述... 1
算法分析... 1
结论... 2
程序清单... 2
四、过河卒（30分NOIPC4）... 3
问题描述... 3
算法分析... 4
程序清单... 4
一、级数求和（20分 NOIPC1）
问题描述
已知：Sn=1+1/2+1/3+...+1/n.显然对于任意一个整数k,当n足够大的时候，Sn大于k。
现给出一个整数K，（1<=k<=15）要求计算出一个最小的n，使得Sn>K。
求出所有解。
【输入】
键盘输入：k
【输出】
屏幕输出：n
【输入输出样例】
输入：1
输出：2
算法分析
本题采高精度除法和高精度加法。
因为Sn=1+1/2+1/3+...+1/n ，当n每增大1时，1/n的结果减小的速度将会很快，所以当n足够大时1/n的结将会很小，用real型存放显然不可行，所以采用高精度计算中的一位除以多位数的除法来计算1/n的结果。因为1<=k<=15，所以2<=n<=1835421,n只要用longint型存放即可。
程序开始先读入k值，n从1做起，每次n:=n+1,计算1/n，用数组a:array[0..max] of integer存放1/n的结果，其中a[0]用来存整数部a[1..max]用来存放小数部分。 用数组 b:array[-1..max] of integer存前n项的sn的值，其b[-1],b[0]共同存整数部分，每计一次1/n的值，都把a数组和b数组的值相加，存放在b数组中。
当且仅当b[-1],b[0]共同存整数部分值等于k时程序即可结束，并输出 n值。这是因为sn还有小数部分，实际上sn的值已经大于k值。可是当k=1时，n应该等于2，所以读k=1时，只要输出n=2 并终止程序即可。
结论
K
1
2
3
4
5
6
7
8
N
2
4
11
31
83
227
616
1674
K
9
10
11
12
13
14
15
N
4591
12367
33617
91380
248397
675214
1835421
k=15时用时间125-130秒。
程序清单
{///////////////////////
NOIPC1题一 级数求和
日期：2002年11月30日
作者：薛原
修改日期：
////////////////////////}
program a02_1;
const max=100;{数组最大下标值}
var a,b:array[-1..max] of integer;{a:n的倒数，b:Sn}
k:integer;
n:longint;
procedure make;
var i:integer;
s,g:longint;
begin
repeat
n:=n+1;
{求1/n}
a[0]:=1 div n;
g:=1 mod n;
for i:=1 to max do
begin
s:=g*10;
g:=s mod n;
a:=s div n;
end;
{计算Sn}
s:=0;g:=0;
for i:=max downto 0 do
begin
s:=a+b+g;
g:=s div 10;
b:=s mod 10;
end;
b[-1]:=b[-1]+g;
until (b[0]=k) or ((b[-1]*10+b[0]=k) and (b[-1]<>0));
end;
begin
write('k=');readln(k);
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
if k=1 then begin write('2');halt;end
else begin n:=0;make;end;
writeln('n=',n);readln;readln;
end.四、过河卒（30分NOIPC4）
问题描述
如图,A点有一过河卒，需要走到目标B点。卒行走的规则：可以向下，或者向右。
1
1
2
2
3
3
4
4
5
6
7
8
卒 A
C
马
P5
P4
P3
P2
P1
P8
P6
P7
B（4，8）
X
Y
同时在棋盘上的任一点有一个对方的马（如图中C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。
例如上图C点的马可控制9个点（P1...P8，C）。卒不能通过对方马的控制点。棋盘用坐标表示，A点（0，0），B点（n，m）（n，m为不超过20的整数，并有键盘输入），同样，马的位置坐标是需要给出的（约定：C≠A同时C≠B）。
现在要你计算出 卒从A点出发能够到达B点的路径的条数。
【输入】
键盘输入：
B点坐标（n,m）以及对马的坐标（X,Y）{不用判错}
【输出】
屏幕输出：一个整数(路径的条数)
【输入输出样例】
输入：
6 6 3 2
输出：17
算法分析
本题与1997年初中组第3题相似，采用动态规求解，即用逐行递推和迭代法依次计算从起点到各顶点路径总数，从而最终算出到达终点路径总数。具体方法如下：
用数组a:array[-3..23,-3..23] of real存放棋盘状态。
首先从键盘读入：棋盘的长度和宽度即B点坐标（n,m），以及对马的坐标（X,Y）。因为马的坐标（X,Y）以及该马所在的点和所有跳跃一步可达的点即马的控制点，不能经过，所以将这9个点在数组中的值赋为-1。
因为卒只能向前走或向右走，所以对于某一点有如下递推关系式：
a[x-1,y]+a[x,y-1] 当 a[x-1,y]≠-1，a[x,y-1] ≠-1 时
a[x,y-1] 当 a[x-1,y]=-1，a[x,y-1] ≠-1 时
a[x,y]= a[x-1,y] 当 a[x-1,y] ≠-1，a[x,y-1]=-1 时
0 当 a[x-1,y]=-1，a[x,y-1]=-1 时
其中a[0,x]，a[x,0]这些点都只有1种方法或无法通过。
最后，只要输出a[n,m]的值即为所求。
程序清单
{///////////////////////
NOIPC4题四 过河卒
日期：2002年11月30日
作者：薛原
修改日期：2002年12月1日（滕伟）
////////////////////////}
program a02_4;
var a:array[-3..23,-3..23] of real;
n,m,x,y:integer;
procedure init;
begin
a[x,y]:=-1;
a[x-1,y-2]:=-1;a[x-1,y+2]:=-1;
a[x-2,y-1]:=-1;a[x-2,y+1]:=-1;
a[x+1,y-2]:=-1;a[x+1,y+2]:=-1;
a[x+2,y-1]:=-1;a[x+2,y+1]:=-1;
end;
procedure make;
var i,j:integer;
begin
for i:=0 to n do if a[i,0]<>-1 then a[i,0]:=1 else break;
for i:=0 to m do if a[0,i]<>-1 then a[0,i]:=1 else break;
for i:=1 to n do
for j:=1 to m do
if a[i,j]<>-1 then
begin
if (a[i-1,j]<>-1) and (a[i,j-1]<>-1) then a[i,j]:=a[i-1,j]+a[i,j-1];
if (a[i-1,j]=-1) and (a[i,j-1]<>-1) then a[i,j]:=a[i,j-1];
if (a[i-1,j]<>-1) and (a[i,j-1]=-1) then a[i,j]:=a[i-1,j];
if (a[i-1,j]=-1) and (a[i,j-1]=-1) then a[i,j]:=0;
end;
{ for i:=0 to n do
begin
for j:=0 to m do
write(a[i,j]:10:0);
writeln;
end;}
write(a[n,m]:0:0);readln;readln;
end;
begin
fillchar(a,sizeof(a),0);
write('n,m,x,y=');readln(n,m,x,y);
init;
make;
end.
