高精度讲义.pptVIP

高精度算法基础篇 三、运算过程 例：35+86竖式相加 　　35 +　 86 ------- 1----- 1 -----1--------- 21 -------------- 121 三、运算过程 （1）运算顺序：两个数靠右对齐；从低位向高位运算；先计算低位再计算高位； （2）运算规则：同一位的两个数相加再加上从低位来的进位，成为该位的和；这个和去掉向高位的进位就成为该位的值；如上例：3+8+1=12，向前一位进1，本位的值是2；可借助MOD、DIV运算完成这一步； （3）最后一位的进位：如果完成两个数的相加后，进位位值不为0，则应添加一位； （4）如果两个加数位数不一样多，则按位数多的一个进行计算； 分析： 分析： 例：高精度加法 输入两个整数x，y，输出它们的和。（0≤x,y≤ 10100) 算法: (用st读入两个数） 1、输入st，记录长度lx；将st中每个元素转化为整数反向保存在数组X[ ]中； 2、输入st，记录长度ly；将st中每个元素转化为整数反向保存在数组Y[ ]中； 3、如果lxly，则lx?ly（取最大长度保存在lx中） 4、求和并放在数组h[ ]中。 4-1、h[I]?h[I]+x[I]+y[I] 4-2、h[I+1]?h[I] div 10 4-3、h[I]?h[I] mod 10 5、反向输出。 样程 Program ex; var st:string; x,y,h:array [0..101] of integer; lx,ly,I:integer; begin for I:=1 to 101 do begin x[I]:=0;y[I]:=0;h[I]:=0;end; write(‘x=‘);readln(st);lx:=length(st); for I:=lx downto 1 do x[lx-I]:=ord(st[I])-ord(‘0’); write(‘y=‘);readln(st);ly:=length(st); for I:=ly downto 1 do y[ly-I]:=ord(st[I])-ord(‘0’); if lxly then lx:=ly; for I:=0 to lx do begin h[I]:=h[I]+x[i]+y[i]; h[I+1]:=h[I] div 10; h[I]:=h[I] mod 10; end; if h[lx]=0 then lx:=lx-1; write(‘h=‘); for I:=lx to 0 do write(h[I]); readln; End. 优化 以上的方法的有明显的缺点： （1）浪费空间：一个整型变量（-32768~32767）只存放一位（0~9）； （2）浪费时间：一次加减只处理一位； 针对以上问题，我们做如下优化：一个数组元素存放四位数；（integer的最大范围是32767，5位的话可能导致出界）。 优化 改进算法： （1）运算时：不再逢十进位，而是逢万进位（mod 10000; div 10000); （2）输出时：最高位直接输出，其余各位，要判断是否足够4位，不足部分要补0；例如：求得的和是这样三段的数， 输出时，应该是100232345而不是1232345。 高精度算法提升篇 求回文数 若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回文数。例如：给定一个10进制数56，将56加65（即把56从右向左读），得到的121是一个回文数。又如，对于10进制数87： STEP1：87+78=165 STEP2：165+561=726 STEP3：726+627=1353 STEP4：1353+3531=4884 在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。 写一个程序，给定一个N（2≤N≤10，N=16）进制数m，m的位数上限为20。求最少经过几步可以得到回文数。如果在30步以内（包括30步）不可能得到回文数，则输出“impossible” 1.将数串s转化为整数数组m 设数串s=s1‥sp，串长为p。其中si为第p-i+1位n进制数（1≤i≤p）。我们将s转化为整数数组m=m[p]‥m[1]，其中m[i]对应第i位n进制数。 type mtype=array[1..100]of integer； var m：mtype； 按下述方法将s转化为整数数组m： p←length(s)；{计算s的串长} for i←1 to p do {从最高