pascal竞赛中的高精度.ppt

1、竞赛中的高精度 -类型化高精度数,高精度算法,高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除,乘方,阶乘,开方等运算.,例如：一个很大的数字N = 10 100, 很显然这样的数字无法在计算机中正常存储.,于是, 我们想到了办法,将这个数字拆开,拆成一位一位的 或者是四位四位的存储到一个数组中, 用一个数组去表示一个数字.这样这个数字就被称谓是高精度数。,高精度数的表示方法,例如：2009我们可以表示为,为了更清楚的记录数组中高精度数的位数，将数组改进为：,显然： 我们初始化高精数时要逆序（旋转）放入数组中。 输出高精度数时，要根据位数，倒序输出数组。,高精度加法,例如：2009+8

2、019=10028 算法思想：模拟,2009 + 8019 10028,+,For i:=1 to 4 do begin ci:=ci+ai+bi; / 本位 ci+1:=ci+1+ c i div 10; / 进位 ci:=ci mod 10; /本位 End; 求c0,高精度数类型化,Type hp=array0.200 of integer; Var n,m,sum:hp; Begin init(n); init(m); add(sum,n,m); print(sum); End.,模块化,init/初始化高精度数 （即读入）,add/高精度加法 （即运算）,print/输出高精度数 （

3、即输出）,高精度乘单精度,例如：2009*8=16152 算法思想：模拟,2019 + 8 16152,*,For i:=1 to 4 do c i :=ai*b /逐位相乘 For i:=1 to 4 do begin ci+1:=ci+1+ ci div 10; / 进位 ci:=ci mod 10; End; /高位进位,并求c0,8,高精度乘高精度,例如：2009*19=38171 算法思想：模拟,2009 + 19 18081 2009 38171,*,结论： 第i位与第j位相乘， 本位是i+j-1位，进位是i+j,高精度数类型化,Type hp:array0.202 of inte

4、ger; Var n,m,sum:hp; Begin init(n); init(m); mul(ans,n,m); print(ans); End.,模块化,init/初始化高精度数 （即读入）,mul/高精度乘高精度 （即运算）,print/输出高精度数 （即输出）,竞赛中的高精度 -实例分析,国王与麦子(nhoi2004x) 问题描述： 传说古代印度有个喜欢下棋的国王叫舍罕，而宰相达依尔是个聪明的大臣，发明了国际象棋。国王玩得爱不惜手，决定奖赏宰相。达依尔说：陛下，我别无他求，请你在这张棋盘的第一个格子里赏我一粒麦子；在第个格子里赏我2粒麦子；在第个格子里赏我粒麦子；在第个格子里赏我粒麦

5、子依此类推直到64个格子，按这张棋盘上各格应赏的麦子全赏给我吧。 国王听了，觉得达依尔的要求并不高，说道：你能如愿以偿的。然而，国王却不知道这个数字是多么巨大啊！ 你能帮助国王算算第n个格子的麦子数量吗？（提示：本题可采用高精度运算来解题；若在Pascal中只使用一个变量存放麦子数，则至少须将其说明为Longint型。） 输入格式： 从键盘输入正整数n （n65）。 输出格式： 在屏幕输出第n个格子的麦子数量，注意不能以科学记数法表示。,问题分析,本题题意说得很明显：即第i个格子等于i-1中的两倍。最后答案为N个格子的和。 ai:=ai-1*2 ans:=a1+a2+an 本题说得很明显，精度

6、超出longint;故需用高精度。 第一步：高精度乘单精度 第二步：高精度加高精度 进一步分析： n=1 1=21-1 n=2 1+2=3=22-1 n=3 1+2+4=7=23-1 n=4 1+2+4+8=24-1 即问题是求2n-1的值。,参考程序一,Type hp=array0.100 of integer; var ans:array1.65 of hp; n,i:integer; total:hp; begin readln(n); ans1,0:=1; ans1,1:=1; /初始化ans1 for i:=2 to n do mul(ansi, ansi-1, 2); for i:

7、=1 to n do add(total,total,ansi); print( total ); End.,Var ans:array1.65 of longint; n,i:integer; total:longint; Begin readln(n); ans1:=1; for i:=2 to n do ansi:=ansi-1*2; for i:=1 to n do total:=total+ansi; write(total); End.,类型化 模块化,参考程序一,procedure mul(var c:hp; a:hp; b:integer); var len,i:integer

8、; begin fillchar(c,sizeof(c),0); len:=a0; for i:=1 to len do begin ci:=ci+ai*b; ci+1:=ci+1+ci div 10; ci:=ci mod 10; end; while clen+10 do begin len:=len+1; clen+1:=clen div 10; clen:=clen mod 10; end; c0:=len; end;,procedure add(var sum:hp; a,b:hp); var i,len:integer; begin fillchar(sum,sizeof(sum)

9、,0); if a0b0 then len:=a0 else len:=b0; for i:=1 to len do begin sumi:=sumi+ni+mi; sumi+1:=sumi+1+sumi div 10; sumi:=sumi mod 10; end; if sumlen+10 then sum0:=len+1 else sum0:=len; end;,参考程序,Pirnt( 省略）,参考程序二,type hp=array0.100 of integer; var ans:array1.65 of hp; n,i:integer; total:hp; procedure mul

10、(var c:hp; a:hp; b:integer); var len,i:integer; begin fillchar(c,sizeof(c),0); len:=a0; for i:=1 to len do begin ci:=ci+ai*b; ci+1:=ci+1+ci div 10; ci:=ci mod 10; end; while clen+10 do begin len:=len+1; clen+1:=clen div 10; clen:=clen mod 10; end; c0:=len; end;,procedure print(total:hp); var i:integ

11、er; begin for i:=total0 downto 2 do write(totali); write(total1-1); end; begin readln(n); ans1,0:=1; ans1,1:=2; for i:=2 to n do mul(ansi,ansi-1,2); print(ansn); end.,参考程序,义务植树 (nhoi2008) 问题描述： 3月12日植树节到了，小明的班主任带着全班同学到白云山义务植树。小明心里想还没有去过白云山呢，这下可以好好玩一下。好不容易到了白云山，找到预先安排好的地方，班主任把工具分发下去，拿出一张图纸(如图1)展示给大家看

12、，并说明要求： 我们班所有同学植的树要成一个等腰三角形，等腰三角形的两条腰上按顺序都是植1棵树，其他位置植树棵数等于它的左上角和右上角所植树的和。全班同学一定不能弄错，要分工协作，发扬团结互助的精神，把这次植树活动做好。 小明负责本小组植树棵数的计算，例如第i行第j个位置应植多少棵树。小明认真看了一下图纸，傻眼了，这该怎么计算啊？原来还想好好玩一玩，这下可惨了。你能帮助小明完成计算任务吗？ 输入格式： 输入文件只有1行：i和j两个数(1=i,j=101，j=i)，中间隔一个空格，表示植树位置为第i行第j个位置(从左往右数第j个)。 输出格式： 输出文件只有一个数：所求位置上应植数的棵数。,问题分析,本题实质是求杨辉三角。,转化,看表格规律： ai,j:=ai-1,j-1+ai-1,j ai,1:=1; ai,i:=1; 数据规模：i,j=100 高精度加法 时间复杂度：O(i*j*len),参考程序一,Var ans:array1.101,1.101