|
大家好！《请你编程》又与你们见面了。虽然上期题目比较难，但来稿却并没有因此而减少，这体现了大家对《请你编程》的支持和对编程的浓厚兴趣！从这次投稿来看，基本上都找到了该算法的规律以及解题的方法，并且能按要求得出正确答案，但有些读者的思路不太清晰，程式冗长，直接影响到可读性。有读者认为以前一些题目过于简单，其实我们的宗旨是尽量让更多的读者参与，重点放在编程的思路、结构以及可读性上。
9902请你编程解题思路:
显而易见，存在一些数据对，使得第一个船夫“必败”，如以下数列：
No.1 1 2 mother 1
No.2 3 5
No.3 4 7 mother 2
No.4 6 10 mother 3
No.5 8 13
No.6 9 15 mother 4
No.7 11 18
对于该数列，存在如下特点：
1、对第n项数据对i,j,其中i为在前n－1项中未曾出现过的数中最小的一个，j=i＋n,这可以用反证法证明。
2、对第n项数据对i,j，有n=j－i。易证。
3、任一正整数k，必定在该数列中出现且只出现一次，这也可用反证法证明。
4、如果数据对i,j属于该数列，则数据对i＋j,i＋2＊j也属于该数列。
5、如果数据对i,j属于该数列，则数据对j－1,i＋j－1也属于该数列。
6、对于数据对i,j，用特点4推出的数据对i＋j,i＋2＊j称为其右儿子；用特点5推出的数据对j－1,i＋j－1称为其左儿子。则有：数据对i,j的右儿子为数列的第j项，左儿子为数列的第i项。结合特点4、5、6易证。
7、对于属于该数列但不能用特点4推出的数据对i,j称为母数据对，可以用特点4推出的数据对称为子数据对。则有：母数据对数列中第n项可由数列中第n项用特点5推出，子数据对数列中第m项可由数列中第m项用特点4推出。
根据以上特点，给出解题的递归算法：
若i<=j，则i,j不属于该数列；
若j－i,i＋1属于该数列，则i,j属于该数列；
若2＊i－j,j－i属于该数列，则i,j属于该数列。
解题完毕。
该题的难度在于看出该数列的两个递推公式，并且算法是判断i,j是否是在数列中，而不是判断数列中是否有i,j（若如此，数组必定会越界，且运行超时）。
源程序：
function right(x,y:longint):boolean;
begin
if (x<=0) or (y<=0) then begin right:=false;exit;
end;
if (x=1)and(y=2) then begin right:=true;exit;end;
if x>=y then begin right:=false;exit;end;
if right(2＊x－y,y－x) then begin right:=true;exit;
end;
if right(y－x,x＋1) then begin right:=true;exit;end;
right:=false;
end;
const
s:array[false..true]of string=(′first′,′second′);
var
f:text;
i,j,t:longint;
begin
assign(f,′river.txt′);reset(f);writeln;
while not eof(f) do
begin
readln(f,i,j);
if (i=0)and(j=0) then break;
if i>j then begin t:=i;i:=j;j:=t;end;
writeln(s[right(i,j)]);
end;
close(f);
end.
9904请你编程题目
建一个n×n的矩阵，分别将数字1、2、3…… n2填入矩阵（每个数字只能使用一次），使矩阵的每一行、每一列以及对角线数字的和都相等，但有些矩阵不会满足这些条件（例如：2×2
矩阵）。请读者编写一个程序：任意输入一个正整数n值，如果该矩阵满足以上条件，就输出这个矩阵，否则，输出一段信息。
来稿请寄磁盘稿或用E－mail投稿，请写明编程思路和源程序，将来稿寄到电脑报编辑部的收信地址或E－mail邮箱，同时欢迎提供请你编程的题目。来稿截止日期：1999年4月15日。
本期获奖名单：
娄江鸿（湖北省） 王 利（湖北省）
薄新维（辽宁省） 葛 勇（上海市）
刘少迪（湖南省） 顾伟庆（上海市）
张赞波（江苏省） 黄本宇（安徽省）
陆欣蔚（浙江省） 罗海泓（江苏省）
每位获奖者将获得苦丁香公司提供的光盘一张。
本文出自：《电脑报》1999年03月08日第09期
|