归纳法及应用[终稿]

《归纳法及应用[终稿]》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、归纳法及其应用一、概述归纳法是我们解决数学问题时经常用到的，它是我们探究问题木质的一种常用方法，在信息学奥赛中也经常用到，尤其是在解决一些规律性很强的数学问题或者线性表、数字方阵等问题时,更是不可或缺。因为这类问题一般都可以通过对数组下标的控制來实现対整个数组的操作和対问题的推导，所以需要通过分析归纳出数组下标具体的变化规律來。下面通过一些实例谈谈如何归纳和控制数纟FI下标的变化。二、归纳法在解决线性表方面的应用(一维)例]、计算S二1!+2!+3!+…+n!(nW50),其中“！”表示阶乘,例如：5!二5*4*3*

2、2*1,输入正整数N,输出计算结果S。[问题分析]本题很明显是考察高精度运算的，高精度运算的关键就是数组下标的变化。本题涉及髙精度加法和乘法运算，为了提高效率，在计算当前项的值时采用递推迭代的方法，即k!=(k-l)!*k。卜•面的程序屮使用两个一维数纽s和f分别存储到当项为止的和与当前项的值。[程序清单]programexl(input,output);constmaxlen=100;typearraytype^array[0.・maxlen]ofIongint;vari,n:integer;f,s:arrayty

3、pe;proceduremul(vara:arraytype;k:longint);{a存储(kT)!,再乘以k}vari:longint;beginfori:=0tomaxiendof[i]:二f[i]*k;fori:=0tomaxlen-1dobegina[i+l]:=a[i+l]+a[i]div10;a[i]:二a[i]mod10endend;procedureadd(vara:arraytype;b:arraytype);{a:二a+b,前若十项的和再加当前项}vari:longint;beginfori:=

4、0tomaxlendoa[i]:=a[i]+b[i];fori:=0tomaxlenTdoifa[i]>二10thenbegina[i+l]:=a[i+l]+l;a[i]:=a[i]-10endend;procedureprint(a:arraytype);vari,j:Iongint;begini:二max1en;while(i>0)and(a[i]=0)doi:=i~l;forj:=idownto0dowrite(a[j])end;beginwriteCInputn:;readln(n);fori:=0tomax

5、lendos[i]:=0;fori:=1tomaxlendof[i]:=0;f[o]:=l;fori:=1tondobeginmul(f,i);add(s,f);end;print(s);writelnend.例2、回文数[问题描述]若一个数(首位不为零)从左向右读与从右向左读都是一样，我们就将其称Z为回文数。例如：给定一个十进制数56,将56加65(即把56倒过來)，得到121是一个回文数。乂如：对于十进制数87：STEP1：87+78=165STEP2：165+561=726STEP3：726+627二1353S

6、TEP4：1353+3531=4884在这里的一步是指进行了-•次十进制的加法，上例最少用了4步得到回文数4884o写一个程序，给定一个N（2<=N<=16）进制数M,求最少经过儿步（儿次N进制加法）可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible!”样例输入：N=9M二87样例输出：STEP=6[问题分析]本题的核心是高精度加法和回文数的判断，具体处理起来可以分为4个部分：1、对读入数据的处理。本题中的数据进制是可变的(2WNW16),所以用整型数(即十进制数)不是很方便

7、，因为会岀现A~F,考虑一般情况，我们可以采用字符串读入，再对数据作示期加工，把它的每一位都分离开来，存入一个数组digit里，数组invert始终存放数组digit的倒序，为的是方便后面做一次高精度加法运算，变量len记录了数据的位数。对丁•字母A~F只要转化成10〜15便行了。2、高精度加法运算。N进制的高精度与十进制的高精度运算完全一样，只是在进位的时候除以N进位和取余数。也就是说每一位加和存储时仍采用十进制数值，进位后的每一位可能是0〜15。做加法的次数以30次为限。3、回文数的判断。判断是否构成冋文数吋也一

8、样用十进制，逐对比较对称的两个数位上的数字，看它们是否相等。4、输出结果。如果当前的数是回文数(step<30),则输出步数；否则输出“Impossible”。[程序清单]programex2(input,output);constmax二1000;typeairaytype二array[1・•max]oflongint;vari,n,len,