文档介绍：算法简介
算法是一组(有限个)规则,它为某个特定问题提供了解决问题的运算序列。在信息学竞赛中,就是计算机解题的过程。在这个过程中,无论是形成解题思路还是编写算法,都是在实施某种算法。前者是推理实现的算法,后者是操作实现的算法。
计算机解题的核心是算法设计。一个算法应该具有以下五个重要特征:
①  有穷性:一个算法必须能在执行有限步之后结束;
②  确切性:算法的每一步骤必须确切定义;
③ 输入:一个算法有零个或多个输入,以描述运算对象的初始情况。所谓0个输入是指算法本身给出了初始条件;
④ 输出:一个算法有一个或多个输出,以反映对输入数据处理后的结果。没有输出的算法是毫无意义的;
⑤  可行性:算法原则上能够精确的运行,而且其运算规模是可以承受的。
为了获得一个既有效又优美的算法,必须首先了解一些基本的常用算法设计思路。下面,我们就对构成算法所依据的一些基本方法展开讨论,如递推法,递归法,枚举法,分治法,模拟法,贪心法等。
高精度算法及优化
胡苗坤
高精度运算需处理的几个问题
高精度计算中需要处理好以下几个问题:
(1)数据的接收和存贮方法
数据的接收和存贮:当输入的数很长时,可用字符串方式输入,这样可输入数字很长的数,利用字符串函数和操作运算,将每一位数取出,存入数组中,另一种方法是直接用循环加数组方法输入数据。
(2)计算结果位数的确定
位数的确定(利用对数函数)L=trunc(ln(x)/ln(10))+1,定义数组a(L);
(3)进位、借位处理
加法进位:a[i]:=a[i]+b[i],若a[i]>0则a[i]:=a[i]-10,a[I+1]:=a[I+1]
减法借位:若a[i]<b[i]则a[I+1]:=a[I+1]-1,a[i]:=a[i]+10,a[i]:=a[i]-b[i]
乘法进位:y:=a[i]*b[i]+c,c:=y div 10,a[i]:=y-c*10(或a[i]:=y mod 10)
(4)商和余数的求法
视被除数和除数的位数情况进行处理
高精度加法
算法实现:
设la+lb=c,首先把la,lb作为字符串读入;
然后把la,lb字符串转换成数组a,b;
实现方式:
For I:=length(la) downto 1 do a[length(la)-I+1]:=ord(la[i])-48;
最后c[i]:=la[i]+lb[i];
进位处理:首先定义一变量y,y初始值为0,运算时通过以下方式实现:
C[i]:=a[i]+b[i]+y
Y:=c[i] div 10
C[i]:=c[i] mod 10
高精度减法
算法实现:
设la+lb=c,首先把la,lb作为字符串读入;
然后把la,lb字符串转换成数组a,b;
实现方式:
For I:=length(la) downto 1 do a[length(la)-I+1]:=ord(la[i])-48;
最后c[i]:=la[i]-lb[i];{交换后使la>lb}
借位处理:
若a[i]<b[i]则
a[I+1]:=a[I+1]-1;
a[i]:=a[i]+10;
c[i]:=a[i]-b[i];
高精度乘法
算法实现:
1、设la+lb=c,首先把la,lb作为字符串读入;
2、然后把la,lb字符串转换成数组a,b;
实现方式:
For I:=length(la) downto 1 do a[length(la)-I+1]:=ord(la[i])-48;
3、位数确定:设被乘数为a,乘数为b,它们的位数分别为lena,lenb,所以积的位数最长是lena+lenb;
4、进位处理:乘法是加法的变形,所以先设变量y为进位数初始值为0;
x;:=a[i]*b[j];y:=x div 10;z:=x mod 10;
K:=I+j-1;c[k]:=c[k]+z;{处理本位};
C[k+1]:=c[k+1]+c[k] div 10 +y;{处理进位}
C[k]:=c[k] mod 10;
高精度除法
算法分析:
做除法时,每一次商的值都在0~9,每次求的余数连接以后的若干位得到新的被除数,继续做除法。因此在做高精度除法时,要涉及到乘法运算和减法运算,还有移位处理。当然,为了程序简洁,可以避免高精度乘法,用0~9反复减法取代来得到商的值。当然,高精度除法还可以分为:高精度除以高精度数、高精度除以单精度数。
注:在此介绍的是高精度数除以单精度数,取得是商不包括小数部分。
扩大进位制实现优化
用整数数组每一个元素表示一个十进制整数的方法存在的缺点是:如果十进制的位数很多,则对应的数组的长度会很长,并增加了高精度计算的时间。     如果用一个元素记录2位数字、3位数字或更多位数字,则数组的长度可以明显缩小,但是还要考虑数的取值范