师大附中 信息学奥林匹克竞赛辅导——程序设计试题答案部分 第26页
例如，当n＝3，可能的方案有AAA、AAB、ABA、BAA、BAB等5种。试求：（1）当n＝15时，所有可能的方案数是多少？（2）当n＝10时，包含有8个字母A的方案数共有多少？（★★★） （提示：此题可以采用进制转换来解决。考虑到只包含了A与B两个字母，我们可以用二进制的0和1来代替，所以当全部是A时最小，此数为0，当全部是B时最大为2 n－1，我们让变量从0～2 n－1循环，然后将此数转换为相应的二进制数存储在数组中即可进行判断了。） （答案：（1）1597；
（2）36）
program e; var
n,m,s,i,j,count:longint; flag:boolean;
a:array[1..100] of integer; begin
writeln('input n:'); readln(n);
s:=1; count:=0;
for i:=1 to n do s:=s*2; for i:=0 to s-1 do begin m:=i;
for j:=1 to n do begin
a[j]:=m mod 2; m:=m div 2; end;
flag:=true;
for j:=1 to n-1 do
if (a[j]=1)and(a[j+1]=1) then
begin flag:=false; break; end; if flag=true then count:=count+1; end;
writeln(count); end.
program e; var
n,m,s,i,j,count,na:longint; flag:boolean;
a:array[1..100] of integer; begin
writeln('input n:'); readln(n);
s:=1; count:=0;
for i:=1 to n do s:=s*2; for i:=0 to s-1 do begin m:=i;
师大附中 信息学奥林匹克竞赛辅导——程序设计试题答案部分 第27页
for j:=1 to n do begin
a[j]:=m mod 2; m:=m div 2; end;
flag:=true;
for j:=1 to n-1 do
if (a[j]=1)and(a[j+1]=1) then
begin flag:=false; break; end; na:=0;
for j:=1 to n do if a[j]=0 then na:=na+1;
if (flag=true)and(na=8) then count:=count+1; end;
writeln(count); end.
16. 给定自然数1到n的集合和自然数m（m>n），求各元素之和等于m的子集。（设n=20，m＝48）。
（1）共有多少个符合上述条件的子集？（2）符合上述条件且子集元素数目为5的子集有多少？
（★★★）
（提示：集合的元素不能重复，此题可分3～9个元素类别集合讨论，下面给出第2问的源程序） （答案：①1674；
②488）
program e1;
const m=48; var
a,b,c,d,e,f,g,count:integer; begin
writeln; count:=0;
for a:=1 to trunc(m/5) do
for b:=a+1 to trunc((m-1)/4) do for c:=b+1 to trunc((m-1-2)/3) do for d:=c+1 to trunc((m-1-2-3)/2) do for e:=d+1 to 20 do
if (a+b+c+d+e=m) then inc(count); writeln('count5=',count); end.
（以下程序设计试题来自《全国青少年信息学奥林匹克联赛――培训习题与解答（中学）》） 1、 计算1×2＋3×4＋5×6＋……＋49×50的值。
（答案：21450） program e;
（★）
师大附中 信息学奥林匹克竞赛辅导——程序设计试题答案部分 第28页
var
i,x,s:longint; begin
writeln; s:=0; x:=0;
for i:=1 to 25 do begin x:=x+2; s:=s+x*(x-1); end; writeln(s); end.
2、 给定一串整数数列，求出所有的递增和递减子序列的数目。例如数列7、2、6、9、8、3、5、2、
1可分为（7，2）、（2，6，9）、（9，8，3）、（3，5）、（5，2，1）五个子序列，答案就是5。我们称2、9、3、5为转折元素。 ★★）
program e; var
a:array[1..9] of integer; i,j,k,n:integer; begin
writeln('input 9 number'); for i:=1 to 9 do read(a[i]); n:=1;
for i:=2 to 9-1 do
if ((a[i]a[i-1])and(a[i]>a[i+1])) then n:=n+1; writeln(n:8); end.
3、 将1～9这9个数字分成三组（每个数字只能使用一次），分别组成三个三位数，且这三个三位数
的值构成1：2：3的比例，试求出所有满足条件的三个三位数。 （分析：注意下面源程序所采用的算法，非常好）
（答案：（192、384、576）、（219、438、657）、（273、546、819）、（327、654、981）） program e;
var
a:array[0..9] of integer; i,g,s,b,k,t:integer; begin writeln;
for i:=100 to 333 do begin
for k:=0 to 9 do a[k]:=0; k:=i;
g:=k mod 10; s:=(k div 10) mod 10; b:=k div 100; a[g]:=1; a[s]:=1; a[b]:=1; k:=2*i;
g:=k mod 10; s:=(k div 10) mod 10; b:=k div 100; a[g]:=1; a[s]:=1; a[b]:=1; k:=3*i;
g:=k mod 10; s:=(k div 10) mod 10; b:=k div 100; a[g]:=1; a[s]:=1; a[b]:=1;
（★★★）
（★
师大附中 信息学奥林匹克竞赛辅导——程序设计试题答案部分 第29页
t:=0;
for k:=1 to 9 do t:=t+a[k];
if t=9 then writeln(i:4,i*2:4,i*3:4); end; end.
4、 回文算术：任给一个三位数abc，算出abc与cba之和。若该和数不是回文数（回文数的定义是
从左读和从右读一样，如5、121、1221等），再按上述方法求和。以此类推，直到得到回文形式的和数或者和数的位数已经超过15位时中止计算。
（★★★）
(分析：注意此题中处理回文数判断的方法和处理数组高精度加法的方法) program e; var
a,b:array[1..20] of integer; x,i,m:integer; hw:boolean; begin
writeln; write('abc='); readln(x); for i:=1 to 15 do a[i]:=0;
a[1]:=x mod 10; a[2]:=(x div 10) mod 10; a[3]:=x div 100; m:=3; hw:=false;
while (hw=false)and(m<15) do begin
for i:=1 to m do b[i]:=a[m-i+1]; i:=1;
while (i<=m)and(a[i]=b[i]) do i:=i+1; if i>m then hw:=true else begin
for i:=m downto 1 do write(a[i]); write('+');
for i:=m downto 1 do write(b[i]); write('=');
for i:=1 to m do
begin a[i]:=a[i]+b[i]; a[i+1]:=a[i+1]+a[i] div 10; a[i]:=a[i] mod 10; end; if a[m+1]>0 then m:=m+1;
for i:=m downto 1 do write(a[i]); writeln; end; end;
if hw then writeln('success!') else writeln('Fail!'); end.
5、 求一个n×n数阵中的马鞍数，输出它的位置。所谓马鞍数，是指在行上最小而在列上最大的数。
（★★）
（测试数据：（矩阵1）
（矩阵2）
师大附中 信息学奥林匹克竞赛辅导——程序设计试题答案部分 第30页
15 11 22 17 13
4 9 3 1 10
14 23 21 24 19
25 16 18 12 20
7 8 5 6 2
11 5 3 17 13
4 9 22 16 10
2 23 21 24 19
7 1 18 12 20
8 25 15 6 14
program e; const n=5; var
i,j,min,x,y:integer; flag:boolean;
a:array[1..n,1..n] of integer; begin
writeln; writeln('input ',n,'*',n,' integer number:'); for i:=1 to n do for j:=1 to n do read(a[i,j]); flag:=false; for i:=1 to n do begin
min:=a[i,1]; x:=i; y:=1; for j:=1 to n do
if a[i,j] if a[j,y]>a[x,y] then break; if (j=n)and(a[x,y]>a[n,y]) then begin write(a[x,y],'(',x,',',y,')'); flag:=true; end; end; if flag=false then writeln('No find!'); end. 6、 数学黑洞6174。已知：一个任意的四位正整数（全相同的除外，如1111）。将数字重新组合成一 个最大的数和最小的数相减，重复这个过程，最多七步，必得6174。即：7641－1467＝6174。将永远出不来。 求证：所有四位数数字（全相同的除外），均能得到6174。输出掉进黑洞的步数。 （★★★） program e18; var a:array[1..4] of integer; i,j,d,k:integer; begin writeln('input a si wei shu:'); read(d); if (d mod 1111<>0) then while d<>6174 do begin