pascal竞赛中的高精度.pptVIP

竞赛中的高精度 --类型化高精度数 高精度算法 高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除,乘方,阶乘,开方等运算. 高精度数的表示方法 例如：2009我们可以表示为 常用的高精度运算法 高精度加法 例如：2009+8019=10028 算法思想：模拟  正整数的和 ［问题描述］ 已知两个正整数N和M （N,M10^100) ，请求出这两个正整数的和。［输入格式］：第一行为第一个整 数N,第二行为第二个整数M。［输出格式］：仅一行，输出这两个整数的和。 高精度数类型化 Type hp=array[0..200] of integer; Var n,m,sum:hp; Begin init(n); init(m); add(sum,n,m); print(sum); End. 参考程序 高精度乘单精度 例如：2009*8=16152 算法思想：模拟 高精度数类型化 参考程序 高精度乘高精度 例如：2009*19=38171 算法思想：模拟  正整数的积 ［问题描述］ 已知两个正整数N和M （N,M10^100) ，请求出这两个正整数的积。［输入格式］：第一行为第一个整 数N,第二行为第二个整数M。［输出格式］：仅一行，输出这两个整数的积。 高精度数类型化 Type hp:array[0..202] of integer; Var n,m,sum:hp; Begin init(n); init(m); mul(ans,n,m); print(ans); End. 参考程序 竞赛中的高精度 --实例分析 问题分析 本题是攀天梯的变形题，对于小学生来说，直接发现其数学本质，难度很大，可以教学生列出一系列数据找规律： 参考程序 Type hp=array[0..201] of integer; var ans:array[1..201] of hp; n,i:integer; begin readln(n); ans[1,0]:=1; ans[1,1]:=1; //初始化ans[1] ans[2,0]:=1; ans[2,1]:=2; //初始化ans[2] for i:=3 to n do add(ans[i], ans[i-1], ans[i-2]); print( ans[n] ); End. 参考程序 国王与麦子(nhoi2004x) 问题描述： 传说古代印度有个喜欢下棋的国王叫舍罕，而宰相达依尔是个聪明的大臣，发明了国际象棋。国王玩得爱不惜手，决定奖赏宰相。达依尔说：陛下，我别无他求，请你在这张棋盘的第一个格子里赏我一粒麦子；在第２个格子里赏我2粒麦子；在第３个格子里赏我４粒麦子；在第４个格子里赏我８粒麦子……依此类推直到64个格子，按这张棋盘上各格应赏的麦子全赏给我吧。 国王听了，觉得达依尔的要求并不高，说道：你能如愿以偿的。然而，国王却不知道这个数字是多么巨大啊！ 你能帮助国王算算第n个格子的麦子数量吗？（提示：1本题可采用高精度运算来解题；2若在Pascal中只使用一个变量存放麦子数，则至少须将其说明为Longint型。） 输入格式： 从键盘输入正整数n （n65）。 输出格式： 在屏幕输出第n个格子的麦子数量，注意不能以科学记数法表示。 问题分析 本题题意说得很明显：即第i个格子等于i-1中的两倍。最后答案为N个格子的和。 a[i]:=a[i-1]*2 ans:=a[1]+a[2]+…+a[n] 本题说得很明显，精度超出longint;故需用高精度。 第一步：高精度乘单精度 第二步：高精度加高精度 进一步分析： n=1 1=2^1-1 n=2 1+2=3=2^2-1 n=3 1+2+4=7=2^3-1 n=4 1+2+4+8=2^4-1 …… 即问题是求2^n-1的值。 参考程序一 Type hp=array[0..100] of integer; var ans:array[1..65] of hp; n,i:integer; total:hp; begin readln(