开心的时刻信息学奥林匹克竞赛辅导——程序设计试题答案部分 第46页
（测试数据：25！＝15511210043330985984000000；） program e; var
a,b,c:array[0..1000] of byte; n,i,j,k:integer; procedure cheng; var
i,j,k:integer; begin
for i:=1 to a[0] do for j:=1 to b[0] do begin
c[i+j-1]:=c[i+j-1]+(a[i]*b[j] mod 10);
c[i+j]:=c[i+j]+(a[i]*b[j] div 10)+(c[i+j-1] div 10); c[i+j-1]:=c[i+j-1] mod 10; end; end;
procedure shuchu; var
i:integer; begin
while c[c[0]]=0 do dec(c[0]);
for i:=c[0] downto 1 do write(c[i]); end;
{============main=========} begin
writeln; writeln('input n(<=100):'); readln(n); c[1]:=1; for i:=1 to n do begin
j:=1000;
while c[j]=0 do dec(j); a[0]:=j;
for k:=j downto 1 do begin a[k]:=c[k]; c[k]:=0; end;
b[1]:=i mod 10; b[2]:=(i div 10) mod 10; b[3]:=(i div 100) mod 10; b[0]:=3; cheng; end;
write(n,'!='); shuchu; end.
6、 编程计算Xn，其中X、n的值由键盘输入（必须为正整数并且X<50、n<10）。
（测试数据：X＝49，n＝9； 答案：1628413597910449） program e; var
a,b,c:array[0..1000] of byte; x,n,i,j,k:integer; procedure cheng; var
i,j,k:integer; begin
for i:=1 to a[0] do for j:=1 to b[0] do begin
c[i+j-1]:=c[i+j-1]+(a[i]*b[j] mod 10);
c[i+j]:=c[i+j]+(a[i]*b[j] div 10)+(c[i+j-1] div 10); c[i+j-1]:=c[i+j-1] mod 10;
信息学奥林匹克竞赛辅导——程序设计试题答案部分 第47页
end; end;
procedure shuchu; var
i:integer; begin
while c[c[0]]=0 do dec(c[0]);
for i:=c[0] downto 1 do write(c[i]); end;
{============main=========} begin
writeln; writeln('input x(<50) and n(<10):'); readln(x,n); c[1]:=1; for i:=1 to n do begin
j:=1000;
while c[j]=0 do dec(j); a[0]:=j;
for k:=j downto 1 do begin a[k]:=c[k]; c[k]:=0; end;
b[1]:=x mod 10; b[2]:=(x div 10) mod 10; b[3]:=(x div 100) mod 10; b[0]:=3; cheng; end;
write(x,'^',n,'='); shuchu; end.
7、 求789789?789（共29组789）除以79的商和余数。
（答案：余数8 商：999733911126316189607328847835176949100重复一次9997339） program e;
const w=3*29; m=79; var
a,b:array[0..w] of integer; x,i,j:integer; begin
writeln; a[0]:=0;
for i:=1 to 29 do begin a[3*i-2]:=7; a[3*i-1]:=8; a[3*i]:=9; end; i:=0; j:=1; repeat
x:=a[i]*100+a[i+1]*10+a[i+2]; b[j]:=x div m; j:=j+1;
a[i]:=(x mod m) div 100; a[i+1]:=((x mod m) div 10) mod 10; a[i+2]:=(x mod m) mod 10; i:=i+1; until i=w-1;
b[j]:=(a[w-1]*10+a[w]) div m;
writeln('yu shu:',(a[w-1]*10+a[w]) mod m); write('shang:'); if b[1]=0 then
for i:=2 to j-1 do write(b[i]) else
for i:=1 to j-1 do write(b[i]); writeln; end. 8、
排列与组合程序设计试题
（有关排列与组合的基本理论和公式：
信息学奥林匹克竞赛辅导——程序设计试题答案部分 第48页
加法原理：做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类
中办法中有m2种不同的方法，……，杂第n类办法中有mn种不同方法。那么完成这件事共有N＝m1＋m2＋…＋mn种不同的方法，这一原理叫做加法原理。
乘法原理：做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有
m2种不同的方法，……，做第n步有mn种不同的方法，那么完成这件事共有 N＝m1×m2×…×mn种不同的方法，这一原理叫做乘法原理。
公式：阶乘公式n!?n?(n?1)?(n?2)?3?2?1，规定0！＝1；
n全排列公式Pn?n!
选排列公式Pn?n(n?1)(n?2)?(n?m?1)?mn!mmm、P?C?Pnnm
(n?m)!n!?(n?1)! n 圆排列：n个不同元素不分首位围成一个圆圈达到圆排列，则排列数为：
mn
Pnmn(n?1)(n?2)?(n?m?1)n!0组合数公式C?m?、规定Cn??1
Pmm!m!(n?m)!012nmn?mmmm?1、Cn、Cn?Cn?Cn???Cn?2n） Cn?Cn?1?Cn?Cn
加法原理、乘法原理、排列、组合练习：
1. 用数字0、1、2、3能组成多少个三位数：
（提示：先确定百位数，只能是1、2、3之间的数字；再确定十位数，可以为0、1、2、3任何一个；最后确定个位数，可以为0、1、2、3任何一个。根据乘法原理，共有3×4×4＝48个。） 2. 有编号为1、2、3、4、5的五本书需要摆放在书架上，问有多少种不同的摆放方案数。
5（提示：此题为全排列，故摆放方案总数为P5?5!?120中。也可以按乘法原理思考，即摆放第
一本书有5种选择，摆放第二本数有4种选择，??，最后结果为5×4×3×2×1即5！） 3. 有编号为1、2、3、4、5的五本书需要任选3本书摆放在书架上，问有多少种不同方案。
（提示：可以根据选排列公式计算，也可以根据乘法原理计算，答案为5×4×3＝60） 4. 有编号为1、2、3、4、5的五本书需要任选3本书，问有多少种方法。
（提示：此题为组合问题，答案为C5?35?4?3＝10） 3!5. 五种不同颜色的珠子串成一串，问有多少种不同的方法。
（提示：此题属于圆排列问题，答案为（5－1）！＝24）
6. 把两个红球、两个蓝球、三个黄球摆放在球架上，问有多少种方案。
（提示：摆放方案总数为（2＋2＋3）！种，但是两个红球一样，所以要除以2！，同理两个蓝球，
除以2！，三个黄球，除以3！，即摆放方案总数为
(2?2?3)!?210）
2!?2!?3!1、 排列算法。有N本不同的书摆放在书架上，设其编号分别为1、2、3、??、N，编程求解这N本
书的不同摆放方案和摆放方案总数。
（算法分析：此问题的实质即求N个元素的全排列。以N＝3为例，人工可以得到按字典顺序排列的排列方案如下，123、132、213、231、312、321。由此我们发现，每一个排列方式总是在其前
信息学奥林匹克竞赛辅导——程序设计试题答案部分 第49页
一个排列的基础上通过顺序逆转而得到。由此我们得到给定一个排列P1P2P3??Pn之后生成下一个排列的算法如下：
S1：求满足关系式P（J－1）
S4：将PI与Pn互换，P（I－1）与P（n－1）互换，??，得到从PI到Pn部分的顺序逆转。 由上面算法所得到的就是所求排列的下一个排列。
下面源程序的算法即是通过此方法得以实现。举例说明，如239876541，按字典顺序排列下一个应该是241356789，按照上面的算法，我们给与验证。
（1）I＝3； （2）J＝8； （3）交换P（3－1）与P（8）的值，得249876531； （4）交换P（3）与P（9）、P（4）与P（8）、P（5）与P（7）、P（6）与P（6）的值，顺序逆转的操作到此为止，由此得到241356789。与预期结果相吻合。） program e;
const maxn=10; var
plan:array[1..maxn] of byte; i,j,n,total:integer; procedure print; begin
inc(total);
write('(',total:5,'):');
for i:=1 to n do write(plan[i]:5); writeln; end;
procedure findi; begin i:=n;
while(i>1)and(plan[i] procedure findj; begin j:=n; while plan[j] procedure change; var k,h:integer; begin k:=plan[i-1]; plan[i-1]:=plan[j]; plan[j]:=k; for k:=i to ((n+i) div 2) do begin h:=plan[k]; plan[k]:=plan[n+i-k]; plan[n+i-k]:=h; end; end; begin write('please input n:'); readln(n); total:=0; for i:=1 to n do plan[i]:=i; print; repeat findi; if i>1 then begin findj; change; print; end; until i<=1; writeln('total ways =',total); 信息学奥林匹克竞赛辅导——程序设计试题答案部分 第50页 end. （备注：生成排列的方法很多，比较常用的还有标志位法，可以用一个数组C作为标志数组，另一个数组A存放排列好的元素，凡数组A中用过的元素，数组C中相应下标的位置成TRUE或数字1，否则置成FALSE或数字0。） 2、 组合算法。有N本不同的书摆放在书架上，设其编号分别为1、2、3、??、N，现要从其中取出 R本书，编程求解其不同的组合方案和方案总数。 （算法分析：此问题的实质即求N个元素中取出R个元素的组合方案。组合是没有元素先后顺序之分的，只在于元素的选择不同。先来观察一个具体的例子，当N＝5，R＝3时，其组合方案为： （1）1，2，3 （2）1，2，4 （3）1，2，5 （4）1，3，4 （5）1，3，5 （6）1，4，5 （7）2，3，4 （8）2，3，5 （9）2，4，5 （10）3，4，5 从上面的组合方案可以看出：每一次的方案数都是在前一方案的基础上进行的。具体操作如下：S1：每次都先让最后的元素增加1，直到增加到N为止（如上例中的（1）（2）（3）方案，最后一个元素的变化为由3增加到4再增加到5为止）。 S2：这时最后的元素不能再增加了，那么增加它前面的元素，（如上例中的（4），把倒数第二个元素的2增加1到3，那么此时把这个元素后面的所有元素依次增加1即可得到新的组合方案。再重复上面的操作即可得到全部的组合方案。 注意：在每个元素进行加1的操作中，最后一位数最大可达到N，倒数第二位最大只能达到 N－1，依此类推??，倒数第K位（K≤N）不得超过N－K＋1。） program e; const maxn=10; var plan:array[1..maxn] of byte; i,j,n,r,total:integer; procedure print; begin inc(total); write('(',total:5,'):'); for i:=1 to r do write(plan[i]:5); writeln; end; begin write('please input n and r:'); readln(n,r); total:=0; for i:=1 to r do plan[i]:=i; print; repeat i:=r; while (i>0)and(plan[i]=n+i-r) do dec(i); if i>0 then begin inc(plan[i]); for j:=i+1 to r do plan[j]:=plan[j-1]+1; print; end;
