pascal竞赛中的高精度

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

2、组。常用的高精度运算法高精度加法高精度乘单精度高精度乘高精度竞赛中的实例分析高精度加法 例如：2009+8019=10028 算法思想：模拟49002 2009 + 8019 10028 模拟49108+582001For i:=1 to 4 do begin ci:=ci+ai+bi; / 本位 ci+1:=ci+1+ c i div 10; / 进位 ci:=ci mod 10; /本位End; 求c0 正整数的和正整数的和 问题描述 已知两个正整数N和M （N,Mb0 then len:=a0 else len:=b0; for i:=1 to len do begin sumi:=su

3、mi+ai+bi; sumi+1:=sumi+1+sumi div 10; sumi:=sumi mod 10; end; if sumlen+10 then sum0:=len+1 else sum0:=len;end;procedure print(ans:hp);var i:integer;begin for i:=ans0 downto 1 do write(ansi);end;参考程序高精度乘单精度 例如：2009*8=16152 算法思想：模拟49102 2019 + 8 16152 模拟472 8016*525161For i:=1 to 4 do c i :=ai*b /逐位相

4、乘For i:=1 to 4 do begin ci+1:=ci+1+ ci div 10; / 进位 ci:=ci mod 10;End; /高位进位,并求c08 乘方问题描述求n个相同乘数乘积的运算叫做乘方。 形如： 数学上我们也把它称之为整数指数幂整数指数幂 。现在已知指数n和底数a, 求这个整数指数幂。输入格式：第一行有两个整 数n, a( n,a0 do begin len:=len+1; clen+1:=clen div 10; clen:=clen mod 10; end; c0:=len;end;procedure print(ans:hp);var i:integer;beg

5、in for i:=ans0 downto 1 do write(ansi);end;参考程序高精度乘高精度 例如：2009*19=38171 算法思想：模拟49002 2009 + 19 18081 2009 38171模拟191*517183结论：结论： 第第i位与第位与第j位相乘，位相乘， 本位是本位是i+j-1位，进位是位，进位是i+j 正整数的积正整数的积 问题描述 已知两个正整数N和M （N,M0 then ans0:=len else ans0:=len-1;end;参考程序竞赛中的高精度 -实例分析取糖果（取糖果（nhoi2007X)问题描述：问题描述： 琦琦很喜欢交朋友，在动

6、物公园玩了半天就认识了几个跟她大小相近的朋友，这几个朋友跟她都有一个共同的爱好：喜欢吃糖，而且她们今天都带了很多糖果准备边玩边吃。为了表示大家的友谊，这几个好朋友就决定边玩游戏边分享她们的糖果。她们先把自己所有的糖果全部拿出来合成一堆，然后通过抢答的方式来奖励糖果：抢答的问题是：规定每次只可以取1颗或2颗糖，如果不考虑糖果的不同，取N颗糖共有多少种取法？（注：“先取1颗再取2颗”与“先取2颗再取1颗”视为不同的两种取法）由一位小朋友说出N的值，然后一齐抢答。哪个小朋友能最快正确回答这个问题就奖励1颗糖。 哈哈！琦琦最后得到了最多的糖果。因为她十分聪明，想出当取1颗糖时只有一种取法，取2颗糖时有

7、2种取法（每次取1颗一次取2颗），取3颗糖时就有3种取法（每次取1颗先取1颗再取2颗先取2颗再取1颗），取4颗糖时就有5种取法，根据规律就能快速计出取N颗糖的取法数。当其他小朋友还苦思冥想时琦琦就早已把答案推出来了。 你知道琦琦是找到了什么规律来算的吗？请编程序来帮她算得更快些。 输入格式：输入格式： 输入文件只有1行，为要取的糖的颗数N。（0Nb0 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; i

8、f sumlen+10 then sum0:=len+1 else sum0:=len;end;procedure print(ans:hp);procedure print(ans:hp);var i:integer;begin for i:=ans0 downto 1 do write(ansi);end;begin readln(n); ans1,0:=1; ans1,1:=1; ans2,0:=1; ans2,1:=2; for i:=3 to n do add(ansi,ansi-1,ansi-2); print(ansn);end.参考程序国王与麦子国王与麦子(nhoi2004x)

9、问题描述：问题描述： 传说古代印度有个喜欢下棋的国王叫舍罕，而宰相达依尔是个聪明的大臣，发明了国际象棋。国王玩得爱不惜手，决定奖赏宰相。达依尔说：陛下，我别无他求，请你在这张棋盘的第一个格子里赏我一粒麦子；在第个格子里赏我2粒麦子；在第个格子里赏我粒麦子；在第个格子里赏我粒麦子依此类推直到64个格子，按这张棋盘上各格应赏的麦子全赏给我吧。国王听了，觉得达依尔的要求并不高，说道：你能如愿以偿的。然而，国王却不知道这个数字是多么巨大啊！你能帮助国王算算第n个格子的麦子数量吗？（提示：本题可采用高精度运算来解题；若在Pascal中只使用一个变量存放麦子数，则至少须将其说明为Longint型。）输入格

10、式：输入格式：从键盘输入正整数n （n0 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);procedure add(var sum:hp; a,b:hp);var i,len:integer;begin fillchar(sum,sizeof(sum),0); if a0b0 then len:=a0 else len:=b0; for i:=1 to len do begin sumi:=sumi+ni+mi; su

11、mi+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(var c:hp; a:hp; b:integer);procedure mul(var c:hp; a:hp; b:integer);var len,i:integer;begin

12、 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);procedure print(total:hp);var i:integer;begin for i:=total0 downto

13、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)展示给大家看，并说明要求：我们班所有同学植的树要成一个等腰三角形，等

14、腰三角形的两条腰上按顺序都是植1棵树，其他位置植树棵数等于它的左上角和右上角所植树的和。全班同学一定不能弄错，要分工协作，发扬团结互助的精神，把这次植树活动做好。小明负责本小组植树棵数的计算，例如第i行第j个位置应植多少棵树。小明认真看了一下图纸，傻眼了，这该怎么计算啊？原来还想好好玩一玩，这下可惨了。你能帮助小明完成计算任务吗？输入格式：输入格式：输入文件只有1行：i和j两个数(1=i,j=101，j=i)，中间隔一个空格，表示植树位置为第i行第j个位置(从左往右数第j个)。输出格式：输出格式：输出文件只有一个数：所求位置上应植数的棵数。样例样例1样例样例2输入样例3 25 3输出样例26问

15、题分析本题实质是求杨辉三角。转化转化111121133114641看表格规律： ai,j:=ai-1,j-1+ai-1,j ai,1:=1; ai,i:=1;数据规模：i,jb0 then len:=a0 else len:=b0; for i:=1 to len do begin sumi:=sumi+ai+bi; sumi+1:=sumi+1+sumi div 10; sumi:=sumi mod 10; end; if sumlen+10 then sum0:=len+1 else sum0:=len;end;procedure print(ans:hp);procedure print

16、(ans:hp);var i:integer;begin for i:=ans0 downto 1 do write(ansi);end;BeginBegin readln(n,m); readln(n,m); ans1,1,0:=1; ans1,1,1:=1; ans1,1,0:=1; ans1,1,1:=1; for i:=2 to n do for i:=2 to n do for j:=1 to i do for j:=1 to i do if (j=1) or(j=i) then if (j=1) or(j=i) then begin begin ansi,j,0:=1; ansi,

17、j,0:=1; ansi,j,1:=1; ansi,j,1:=1; end end else else add(ansi,j,ansi-1,j-1,ansi-1,j); add(ansi,j,ansi-1,j-1,ansi-1,j); print( ansn,m ); print( ansn,m );End.End.参考程序 阶乘和阶乘和 【问题描述】 已知正整数N（N=100）,设S=1!+2!+3!+.N!。其中!表示阶乘,即N!=1*2*3*(N-1)*N，如:3!=1*2*3=6。请编程实现：输入正整数N,输出计算结果S的值。【输入样例】sum.in4【输出样例】sum.out33【问

18、题描述问题描述】 一个整数的数字乘积根是这样得到的：将此整数中的非零数字相乘，得到的结果再重复上述运算，直到只有一位数为止，此一位数即为原整数的数字乘根。例如：整数99， 99 9 X 9 = 81 8 X 1 = 8 8 即为99的乘积根。【输入格式输入格式】 输入文件(cheng.in)的数据只有一个n位的整数。（n=255）【输出格式输出格式】 输出文件只有一个一位数，即n的乘积根。 乘积根乘积根 样例样例1样例样例2输入样例991023输出样例86高精度除单精度求商高精度除单精度求余高精度数排序毛怪和大眼仔毛怪和大眼仔 (eyes) 【问题描述问题描述】 怪兽公司是怪物世界中最大的企业

19、，他们主要的业务就是要躲进小孩子睡房内的衣柜 里，在他们临睡时大吓他们一番,收集儿童的尖叫声以保持自己的能量。怪物集团主要的成员 有掌管一切的蟹总裁，多管闲事的蛇头接待员，喜欢挖苦人的变色龙怪物，还有其中一只最大只的蓝毛怪物詹士和他的助手大眼仔。通往人类世界的睡房衣柜的门按照1n的顺序排好，连好在生产线上，线上头尾相接成为一个圈，顺时针转动，怪兽们就是从这些门到达人类世界吓唬小孩子，收集小孩叫声的能量的。 在一次任务中，毛怪和大眼仔发现了一个秘密，原来收集到小孩笑声的能量比惊吓叫声的能量大好多倍，于是，他们的现在任务是收集他们以前吓过的小孩的笑声，要找到他们以前吓过的小孩也不是那么容易，因为门

20、太多了，要是进错了，那小孩不是他们自己吓过的，便又只能收集到哭喊声了。毛怪他们去查他们以前进过的门的编号，可是公司的数据库系统已经自动给门号加密了，门号的数字跟他们以前进的不一样，都变大了，而且有些大得很离谱，不过大眼仔记性好，发现了一个规律，他按照拿到的门号，从生产线的第一个门开始数，绕着生产线的圈子，数到新门号的数字停下来，那个门便是以前他们进过的。毛怪按照大眼仔的说法，拿着的新门号是23，生产线上一共有15扇门，于是，他开始数1，2，315，1，2，3，刚好在8号门停下来，于是开门进去，发现果然是他们以前吓过的小孩，非常开心，于是毛怪和大眼仔便诚心的把他哄得开心的笑了，回来之后，毛怪又去

21、领新的门号，站在生产线上逐个门的数，可是这样子效率太差了，要是能快速的知道究竟是哪个门就好了，你能想到法子帮助毛怪吗？ 【输入格式输入格式】 第一、二行分别读入正整数N和M，分别是生产线上门的总数和毛怪领到的新门号，其中N、M满足2 N 108，2 M 101000【输出格式输出格式】 对应旧的门号，文件只有一行（包括换行符）。样例样例1样例样例2输入样例7911108输出样例29【问题描述】 工商部门查获了有N个人正在贩卖注水猪肉,现在要你对这N个人的注水猪肉的数量从大到小的排序,并且算出这N个人的注水猪肉总和(单位为.斤)我们姑且称这些贩卖者为”猪王”吧. 【输入文件buss.in】 输入的第一行是一个1到1000的整数N，表示总共有N位猪王参加了争霸赛。以下依次给出每位猪王的描述，一位猪王的描述占据两行，第一行为一个仅由小写字母组成的长度不超过13的字符串，代表这个猪王的名字，第二行一个整数(非负数，102000)，代表这个猪王的注水猪肉总斤数。注意，这个整数的首位没有不必要的0。所有猪王贩卖的注水猪肉数量的总长度不会超过2000。【输出文件buss.out】 依次输出按照注水猪肉多少从大到小排好序的各位贩卖者的依次输出按照注水猪肉多少从大到小排好序的各位贩卖者的名字，每个名字占据单独的一行。不能有任何多余的字符。若几名字，每个名字占