【学习任务6】找出一个自然数N( 1 ≤ N ≤ 15，且N为奇数)，要求找出这样的 N个连续的正整数，使得前(N+1)／2个正整数的平方和等于后(N-1)／2个正整数的平方和。

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，那么甲乙两数又各是多少?