归纳法及应用

第 1 页 共 37 页

归纳法及其应用

一、概述

归纳法是我们解决数学问题时经常用到的，它是我们探究问题本质的一种常用方法，在信息学奥赛中也经常用到，尤其是在解决一些规律性很强的数学问题或者线性表、数字方阵等问题时，更是不可或缺。因为这类问题一般都可以通过对数组下标的控制来实现对整个数组的操作和对问题的推导，所以需要通过分析归纳出数组下标具体的变化规律来。下面通过一些实例谈谈如何归纳和控制数组下标的变化。

二、归纳法在解决线性表方面的应用（一维） 例1、计算S=1！+2！+3！+?+n！（n≤50），其中“！”表示阶乘，例如：5！=5*4*3*2*1，输入正整数N，输出计算结果S。

[问题分析]

本题很明显是考察高精度运算的，高精度运算的关键就是数组下标的变化。本题涉及高精度加法和乘法运算，为了提高效率，在计算当前项的值时采用递推迭代的方法，即k!=(k-1)！*k。下面的程序中使用两个一维数组s和f分别存储到当项为止的和与当前项的值。

[程序清单]

program ex1(input,output); const maxlen=100;

type arraytype=array [0..maxlen] of longint; var i,n:integer; f,s:arraytype;

procedure mul(var a:arraytype; k:longint);{a存储(k-1)!，再乘以k} var i:longint; begin

for i:=0 to maxlen do f[i]:=f[i]*k; for i:=0 to maxlen-1 do begin

a[i+1]:=a[i+1]+a[i] div 10; a[i]:=a[i] mod 10 end end;

procedure add(var a:arraytype;b:arraytype);{a:=a+b，前若干项的和再加当前项} var i:longint; begin

for i:=0 to maxlen do a[i]:=a[i]+b[i]; for i:=0 to maxlen-1 do if a[i]>=10 then

第 2 页 共 37 页

begin

a[i+1]:=a[i+1]+1; a[i]:=a[i]-10 end end;

procedure print(a:arraytype); var i,j:longint; begin

i:=maxlen;

while (i>0) and (a[i]=0) do i:=i-1; for j:=i downto 0 do write(a[j]) end; begin

write('Input n:'); readln(n);

for i:=0 to maxlen do s[i]:=0; for i:=1 to maxlen do f[i]:=0; f[0]:=1;

for i:=1 to n do begin

mul(f,i); add(s,f); end;

print(s); writeln end.

例2、回文数 [问题描述]

若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回文数。例如：给定一个十进制数56，将56加65（即把56倒过来），得到121是一个回文数。又如：对于十进制数87：

STEP1：87+78 = 165 STEP2：165+561 = 726 STEP3：726+627 = 1353 STEP4：1353+3531 = 4884

在这里的一步是指进行了一次十进制的加法，上例最少用了4步得到回文数4884。写一个程序，给定一个N（2<=N<=16）进制数M，求最少经过几步（几次N进制加法）可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible！”

样例输入：

N = 9 M= 87 样例输出：

第 3 页 共 37 页

STEP=6

[问题分析]

本题的核心是高精度加法和回文数的判断，具体处理起来可以分为4个部分： 1、对读入数据的处理。本题中的数据进制是可变的（2≤N≤16），所以用整型数（即十进制数）不是很方便，因为会出现A~F，考虑一般情况，我们可以采用字符串读入，再对数据作后期加工，把它的每一位都分离开来，存入一个数组digit里，数组invert始终存放数组digit的倒序，为的是方便后面做一次高精度加法运算，变量len记录了数据的位数。对于字母A~F只要转化成10~15便行了。

2、高精度加法运算。N进制的高精度与十进制的高精度运算完全一样，只是在进位的时候除以N进位和取余数。也就是说每一位加和存储时仍采用十进制数值，进位后的每一位可能是0~15。做加法的次数以30次为限。

3、回文数的判断。判断是否构成回文数时也一样用十进制，逐对比较对称的两个数位上的数字，看它们是否相等。

4、输出结果。如果当前的数是回文数（step<30），则输出步数；否则输出“Impossible”。

[程序清单]

program ex2(input,output); const max=1000;

type arraytype=array [1..max] of longint; var i,n,len,step:longint; str:string;

digit,invert:arraytype;

function judge(var digit:arraytype;len:longint):boolean;{回文数的判断} var i,j:longint; begin

i:=1; j:=len;

while (i

begin

i:=i+1; j:=j-1 end;

if i

write('Input n:'); readln(n);

write('Input number:'); readln(str);

for i:=1 to max do digit[i]:=0; len:=length(str);

第 4 页 共 37 页

for i:=1 to len do if str[i]>='A'

then digit[len+1-i]:=ord(str[i])-ord('A')+10

else digit[len+1-i]:=ord(str[i])-ord('0'); {以上为输入处理} step:=0;

while (step<30) and not(judge(digit,len)) do {步数<30，且未出现回文数，则做} begin

for i:=1 to len do invert[i]:=digit[len+1-i]; for i:=1 to len do digit[i]:=digit[i]+invert[i]; for i:=1 to len do

if digit[i]>=n then

begin digit[i+1]:=digit[i+1]+1; digit[i]:=digit[i]-n end; if digit[len+1]>0 then len:=len+1; step:=step+1 end;

if step=30 {判断并做相应输出} then writeln('Impossible!') else writeln('STEP=',step) end.

例3、读入自然数m和n，0≤m＜n≤1000，判断分数m/n是有限小数还是循环小数。如果m/n是有限小数，则输出分数的值；如果m/n为循环小数，则把循环部分括在括号中打印输出。 如输入：3 7，则输出0.（428571）。

[问题分析]

如果m/n是有限小数，则反复进行除法运算后余数必定会成为0；如果m/n不是有限小数，则反复进行除法运算时，当第y次的余数与前面第x次的余数相等，也就可以确定为循环部分，前面的非循环部分为1~x-1位，循环部分为x位到y-1位的部分。输出时将循环部分用括号括起来输出。

数组POS以余数作下标存放余数的位置代码（小数点以后位数的位置），数组QUOT以位置代码为下标存放商的某一位数，m/n的整数部分始终为0，所以m为第一个余数。

如果本题没有m＜n这个限制条件，也一样做，只要先把k:=m div n，m:=m mod n，先输出k便行了。

[程序清单]

program ex3(input,output); const maxn=1000;

var i,m,n,r,tail:integer;

quot,pos:array [0..maxn] of integer;