筛法的应用

大榕树 \ Pascal语言 \ Pascal练习

筛法的应用

原文链接：http://www.mydrs.org/program/list.asp?id=235
例：
传说中有一个残暴的国王，喜欢杀戮百姓。有一次，他抓到30个百姓并要一一杀掉。在这30个百姓中间有一个聪明人，他站出来对国王说：“请国王大发慈悲，赦免二人不死。”国王问：“赦免哪二人不死？”那个聪明人回答说：“我们30个人围成一圈，从1开始报数，凡数到5的人就拉出去杀掉。剩下的人继续从1开始报数，循环反复，直到剩下两个人为止，这两个人被赦免。”
国王一听很有意思，采纳了聪明人的建议，赦免了两个人，而那个聪明人就是其中之一。请你设计一个程序，由计算机判断聪明人要站在什么位置，才能躲过这一场屠杀。
　
问题分析：
首先，设百姓的人数为M人，设数到N的人被杀掉。
用数组A（M）存放M个人是否还在圈中的信息。其中，
A（I）＝1 表示第I个人还在圈中。
A（I）＝0 表示第I个人已被杀掉。
开始时，数组A中所有的元素都是1，表示每个人都站在圈中。
用K＝K＋A（I）来实现报数功能，因为只有还在圈中的人才能使K的值增加。
用变量D来记录出圈的人数，当D＝M时，表示所有的人都出圈了。最后出圈的两个人就是被赦免的人。
　
程序清单：
CLS
INPUT "m="; m: INPUT "n="; n
DIM a(m)
FOR i = 1 TO m: a(i) = 1: NEXT i
d = 0: k = 0
DO
FOR i = 1 TO m
k = k + a(i): IF k <> n THEN GOTO 1
PRINT USING "####"; i; : p = p + 1: IF p > 5 THEN p = 0: PRINT
a(i) = 0: k = 0: d = d + 1
IF d = m THEN END
1 NEXT i
LOOP
　
例二：
请你设计一个程序，让计算机找出40个自然数来，使得其中任意两个数之差均不相等。
问题分析：
首先，开辟一个数组S(I)，准备存放这40个数，再开辟一个数组CHA(I)，用来存放两个数的差。
寻找某一个满足条件的自然数的过程如下：
把1和2放进数组S中；
把1放进数组CHA中；
当寻找下一个自然数时，要把这个自然数与数组S中的每一个数相减，再判断所得的差是否在数组CHA中；
如果所得的差不在数组CHA中，说明又找到一个满足条件的自然数。把这个自然数放进数组S中，同时把这个自然数与数组S中原有的每一个自然数的差记录在数组S中去。
如果所得的差与数组CHA中的某一个数重复，说明这个自然数不符合条件，继续寻找下一个自然数。
重复步骤（3），直到找到40个自然数为止。
程序清单：
CLS
INPUT "n="; n
DIM s(n), cha(3000)
s(1) = 1: s(2) = 2
cha(1) = 1: s = 2: y = 2: PRINT 1, 2,
1 : y = y + 1
FOR k = 1 TO s
PRINT k, y, s(k), cha(y - s(k))
IF cha(y - s(k)) = 1 THEN GOTO 1
NEXT k
s = s + 1: s(s) = y
FOR k = 1 TO s - 1
cha(y - s(k)) = 1
PRINT y - s(k), cha(y - s(k))
NEXT k
PRINT y, : IF s < n THEN GOTO 1
END

作者：
来源：网络之家
时间：2001-10-06

上一篇：埃及分数之和
下一篇：国际信息学奥赛简介