资源描述：
《pascal竞赛中的高精度.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、竞赛中的高精度--类型化高精度数高精度算法高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除,乘方,阶乘,开方等运算.例如：一个很大的数字N>=10^100,很显然这样的数字无法在计算机中正常存储.于是,我们想到了办法,将这个数字拆开,拆成一位一位的或者是四位四位的存储到一个数组中,用一个数组去表示一个数字.这样这个数字就被称谓是高精度数。高精度数的表示方法例如：2009我们可以表示为9002为了更清楚的记录数组中高精度数的位数，将数组改进为：12345649002012345显然：我们初始化高精数时要逆序（旋转）放入数组中。输出高精度数时，要根据位数，倒序输出数组。高精度加法
2、例如：2009+8019=10028算法思想：模拟490022009+8019—————10028模拟49108+582001Fori:=1to4dobeginc[i]:=c[i]+a[i]+b[i];//本位c[i+1]:=c[i+1]+c[i]div10;//进位c[i]:=c[i]mod10;//本位End;……求c[0]高精度数类型化Typehp=array[0..200]ofinteger;Varn,m,sum:hp;Begininit(n);init(m);add(sum,n,m);print(sum);End.模块化init//初始化高精度数（即读入）add//高精度加
3、法（即运算）print//输出高精度数（即输出）高精度乘单精度例如：2009*8=16152算法思想：模拟491022019+8—————16152模拟4728016*525161Fori:=1to4doc[i]:=a[i]*b//逐位相乘Fori:=1to4dobeginc[i+1]:=c[i+1]+c[i]div10;//进位c[i]:=c[i]mod10;End;……//高位进位,并求c[0]8高精度乘高精度例如：2009*19=38171算法思想：模拟490022009+1918081200938171模拟191*517183结论：第i位与第j位相乘，本位是i+j-1位，进位
4、是i+j高精度数类型化Typehp:array[0..202]ofinteger;Varn,m,sum:hp;Begininit(n);init(m);mul(ans,n,m);print(ans);End.模块化init//初始化高精度数（即读入）mul//高精度乘高精度（即运算）print//输出高精度数（即输出）竞赛中的高精度--实例分析国王与麦子(nhoi2004x)问题描述：传说古代印度有个喜欢下棋的国王叫舍罕，而宰相达依尔是个聪明的大臣，发明了国际象棋。国王玩得爱不惜手，决定奖赏宰相。达依尔说：陛下，我别无他求，请你在这张棋盘的第一个格子里赏我一粒麦子；在第２个格子里赏我
5、2粒麦子；在第３个格子里赏我４粒麦子；在第４个格子里赏我８粒麦子……依此类推直到64个格子，按这张棋盘上各格应赏的麦子全赏给我吧。国王听了，觉得达依尔的要求并不高，说道：你能如愿以偿的。然而，国王却不知道这个数字是多么巨大啊！你能帮助国王算算第n个格子的麦子数量吗？（提示：<1>本题可采用高精度运算来解题；<2>若在Pascal中只使用一个变量存放麦子数，则至少须将其说明为Longint型。）输入格式：从键盘输入正整数n（n<65）。输出格式：在屏幕输出第n个格子的麦子数量，注意不能以科学记数法表示。样例1样例2输入样例37输出样例7127问题分析本题题意说得很明显：即第i个格子等于
6、i-1中的两倍。最后答案为N个格子的和。a[i]:=a[i-1]*2ans:=a[1]+a[2]+…+a[n]本题说得很明显，精度超出longint;故需用高精度。第一步：高精度乘单精度第二步：高精度加高精度进一步分析：n=11=2^1-1n=21+2=3=2^2-1n=31+2+4=7=2^3-1n=41+2+4+8=2^4-1……即问题是求2^n-1的值。参考程序一Typehp=array[0..100]ofinteger;varans:array[1..65]ofhp;n,i:integer;total:hp;beginreadln(n);ans[1,0]:=1;ans[1,1
7、]:=1;//初始化ans[1]fori:=2tondomul(ans[i],ans[i-1],2);fori:=1tondoadd(total,total,ans[i]);print(total);End.Varans:array[1..65]oflongint;n,i:integer;total:longint;Beginreadln(n);ans[1]:=1;fori:=2tondoans[i]:=ans[i-1]*2;fori:=1tondotot
