【学习任务6】找出一个自然数
2011-10-22 20:44阅读：
【学习任务6】找出一个自然数N( 1 ≤
N ≤ 15，且N为奇数)，要求找出这样的
N个连续的正整数，使得前(N+1)／2个正整数的平方和等于后(N-1)／2个正整数的平方和。
pan > v
规定：连续的正整数中最小的数不大于100。
v 例如：当 N=5时，满足条件的5个正整数为：10，11，12，13，14
v 且102+112+122=132+142
v 输入：N
v
输出：满足条件的N个正整数。
v
【问题分析】
v
要找连续的N个正整数(N为奇数，且1≤N≤15)，使得前(N+1)／2个数的平方和等于后(N-1)／2的平方和。据题意知，N的取值只可能是1，3，5，7，9，11，13，15这8个奇数，下面我们分别来讨论：
v
当N =
1时，因为(1+1)/2=1，(1-1)／2=0，一个正整数的平方和不可能为0，所以 N=1不符合；
v
当N =
3时因为(3+1)／2 =
2，(3-1)／2=1，即讨论前面2个连续正整数，和后面一个正整数的平方和的问题。
v
连续的3个正整数可能是：1 2
3，2 3
4，3 4
5，4 5
6，…
v
1，2，3 12+22=5 32=
9 前面平方和<后面平方和
v
2，3，4 22+32=13
42=16 前面平方和<后面平方和
v
3，4，5 32+42=25
52=25
满足条件，前面平方和=后面平方和
v
4，5，6 42+52=41
62=36 前面平方和>后面平方和
v
显然，当N=3时，满足条件的3个正整数为3，4，5；当N=5时，连续的5个正整数可能是：1 2 3 4
5，2 3 4 5
6，……，10 11 12 13
14，……用类似的方法可知答案只有一个，即满足条件的5个正整数为10，11，12，13，14。
v
由以上分析，只要根据问题中的条件，将可能的解的情况列举出来，进行一一验证是否符合整个问题的求解要求。当N为某一个值时，可能有一个答案，也有可能不存在符合条件的值。
v
变量说明：
v
N：输入的自然数；
v
A：数组，用于存放符合条件的N个整数；如果N=1，则输出“无解”，结束；
v
X：累加器，用于存放前(N+1)／2个数的平方和；
v
Y：累加器，用于存放后(N—1)／2个数的平方和；
v
C：累加器，用于从1开始递增枚举；
v
I：循环变量。
v
【算法设计】
v
（0）先判断是否满足条件N为奇数，且1≤N≤15；
v
（1）符合条件后，建立一个有N个元素的数组A(N)，A(N)之中的初值皆为0；
v
（2）给C清0；
v
（3）将连续N个整数按序放到A数组中；
v
（4）求前(N+1)／2个数组变量值平方和，放入X中；
v
（5）求后(N+1)／2个数组变量值平方和,放入Y中；
v
（6）如果X=Y则找到解，输出结果结束；
v
（7）若没有找到解，X、Y清0，穷举变量C增1；
v
（8）将A数组皆增加1，即A(I)=C；
v
（9）如果C=100，则结束循环。
v
（10）结束。
v
【程序清单】
v DO
v INPUT
'请输入奇数N(1—15)'；N
v LOOP
UNTIL N / 2 <> N \ 2
AND N >= 1 AND N <= 15
v IF N = 1 THEN PRINT
＂没有!＂:
END
v DIM A(N): C = 0
v DO
v FOR I = 1 TO N: A(I) = A(I) + I: NEXT
I
v FOR I = 1 TO (N + 1) / 2: X = A(I) *
A(I) + X: NEXT I
v FOR I = (N + 1) / 2 + 1 TO N: Y = A(I) *
A(I) + Y: NEXT I
v IF X = Y THEN
v FOR I = 1 TO N
v
PRINT
A(I)；
v NEXT I: PRINT
v
EXIT DO
’找到符合条件的数后，结束穷举
v END
IF
v X = 0: Y = 0: C = C +
1
v FOR I = 1 TO N: A(I) = C: NEXT
I
v
LOOP
UNTIL C = 100
’当N个整数中最小数为100时还没找到，则结束穷举
v END
v
【运行结果】
v
请输入奇数N(1—15)：1
v
没有!
v
再运行一次：
v
请输入奇数N(1—15)：3
v
3 4
5
v
在数学中，我们常提到排列组合，什么叫排列，什么叫组合呢?以一个例子来说明，如举出所有用1，2，3这三个数字组成的，且每位数字互不相同的三位数，通过试验我们得知有六种排列：123、132、213、231、312、321；而组合只有一种。即排列是分先后顺序的，而组合是不分次序的：如AB和BA是同一个组合。由于组合中的数无顺序要求，在此约定，不妨以“最小”的组合来表示。即以“123”来代表所有由1、2、3不同数码构成的组合。
v【学习任务7】N(N>=3)位同学去照相，每次照三个同学，共可照出多少张不全相同的照片？每张照片中都是谁?
v
【问题分析】
v
这是一个组合问题，即从N个元素中每次取3个元素的组合。如果设这N个同学的代号分别为：1，2，3，……N，则问题变为从这N个数字任取三个的组合。按照上面“最小”组合是123，“最大”组合是789。
v
我们用三重循环来实现，循环变量I，J，K分别代表取出来的三个同学，则其取值范围是：
v I：1
～ N-2
v J：I+1
～ N-1
v
K：I+2 ～
N
v
【程序清单】
v INPUT N
v T = 0
v FOR I = 1 TO N -
2
v FOR J = I + 1 TO N -
1
v FOR K = J + 1 TO
N
v PRINT I, J, K
v T = T + 1
v NEXT K
v NEXT J
v NEXT I
v
PRINT ＂共可照出＂；
T；＂张不同的照片。＂
v END
v
如果考虑每个人在照片中的位置，又有多少张不同的照片呢?
v
对于数字的排列组合问题很容易用穷举法来实现，程序简单、易懂。但如果需要排列的数字较多时，这样做比较麻烦。
v
【学习任务8】警察局抓了
A，B，C，D四名偷窃嫌疑犯，其中有一人是小偷。审问中
A说：“我不是小偷。”B说：“C是小偷。”C说：“小偷肯定是D。”D说：“C在冤枉人。”现在已经知道四个人中三人说的是真话，一人说的是假话，问到底谁是小偷。
v
【问题分析】
v
这个题目是逻辑推理题，常用的方法是用穷举法把各种可能的组合都列举出来，然后根据题目的条件排除不合乎要求的组合或选择需要的组合。
v
方法1
用A、B、C、D四个变量存放A，B，C，D四个人是不是小偷的信息；0表示这个变量代表的人不是小偷；1表示的是小偷。如：A=0，说明A不是小偷，若A=1说明 A是小偷。以A,B，C，D四个变量作为循环变量构造四重循环，每重循环都从0到1，这样就可以把谁是小偷的各种情况都列举出来。
v
题目给出的其他条件可以用有关的表达式进行表示：
v
四个人中有一名小偷：A+B+C+D=1
v
A说的话： A<>1．
v
B说的话： C=1，
v
C说的话： D=1，
v
D说的话： D<>1。
v
四句话中只有三句真话（逻辑值真为-1），所以A，B，C，D四句话的逻辑值相加等于-3。即：
v (A<>1)+(C=1)+(D=1)+(D<>1)=-3
v
根据分析，写出以下程序：
v
【程序清单】
v REM L10-11A
v FOR A = 0 TO 1
v FOR B = 0 TO 1
v FOR C = 0 TO 1
v FOR D = 0 TO 1
v IF (A+B+C+D=1) AND
((A<>1)+(C=1)+(D=1)+(D<>1)=-3)
THEN
v
IF A = 1
THEN PRINT ＂A＂;
’以下是输出结果
v IF B = 1 THEN
PRINT ＂B＂;
v IF C = 1 THEN PRINT
＂C＂;
v IF D = 1 THEN PRINT
＂D＂;
v
PRINT ＂是小偷＂
v END
IF
v NEXT D, C, B, A
v
END
v
方法2
把A,B,C,D四个人进行编号，号码分别为1，2，3，4。让变量X存放小偷的编号。X的值从1取到4，假设了他们中的某人是小偷的所有情况。四个人所说的话就可以分别写成：
v A说的话：X<>1,
v
B说的话：X=3，
v C说的话：X=4,
v
D说的话：X<>4或NOT(X=4)。
v
X的值使这四个逻辑式的值相加等于-3的时候，它就是小偷的编号。
v
这种解法程序十分简单。
v
【程序清单】
v REM L10-11B
v FOR X = 1 TO 4
v IF (X <> 1) + (X = 3) + (X = 4) +
(X <> 4) = -3 THEN
v PRINT CHR$(64+X);
＂是小偷＂: EXIT FOR
v
’将X的值转换为大写字母输出，退出循环
v END
IF
v NEXT X
v
END
穷举法的应用很广泛，在利用穷举法解题时，有时一一列举出的情况数目会大得惊人，所以应注意：尽可能将明显不符合的情况排除在外，以减少穷举的可能解的个数。在实现解题时列举的方法也不一定是单一的，要根据实际情况具体分析。
【练—练】
用穷举法编写下列题目的程序：
1．如果一个数从左边读和从右边读都是同一个数。例如：686就是一个回文数。编一程序，求出1000以内所有的既是回文数同时又是素数的自然数。
2．甲乙两个自然数的和、差、积、商四数加起来等于243，求甲乙两数。若它们的和、差、积、商四数之积等于94221，那么甲乙两数又各是多少?
