pascal競(jìng)賽中的高精度

1、競(jìng)賽中的高精度 -類(lèi)型化高精度數(shù)高精度算法 高精度算法是用計(jì)算機(jī)對(duì)于超大數(shù)據(jù)的一種模擬加,減,乘,除,乘方,階乘,開(kāi)方等運(yùn)算.例如：一個(gè)很大的數(shù)字N = 10 100, 很顯然這樣的數(shù)字無(wú)法在計(jì)算機(jī)中正常存儲(chǔ). 于是, 我們想到了辦法,將這個(gè)數(shù)字拆開(kāi),拆成一位一位的 或者是四位四位的存儲(chǔ)到一個(gè)數(shù)組中, 用一個(gè)數(shù)組去表示一個(gè)數(shù)字.這樣這個(gè)數(shù)字就被稱(chēng)謂是高精度數(shù)。高精度數(shù)的表示方法 例如：2009我們可以表示為9002 為了更清楚的記錄數(shù)組中高精度數(shù)的位數(shù)，將數(shù)組改進(jìn)為：12345649002012345 顯然： 我們初始化高精數(shù)時(shí)要逆序（旋轉(zhuǎn)）放入數(shù)組中。 輸出高精度數(shù)時(shí)，要根據(jù)位數(shù)，倒序輸出數(shù)

2、組。常用的高精度運(yùn)算法高精度加法高精度乘單精度高精度乘高精度競(jìng)賽中的實(shí)例分析高精度加法 例如：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; / 進(jìn)位 ci:=ci mod 10; /本位End; 求c0 正整數(shù)的和正整數(shù)的和 問(wèn)題描述 已知兩個(gè)正整數(shù)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; / 進(jìn)位 ci:=ci mod 10;End; /高位進(jìn)位,并求c08 乘方問(wèn)題描述求n個(gè)相同乘數(shù)乘積的運(yùn)算叫做乘方。 形如： 數(shù)學(xué)上我們也把它稱(chēng)之為整數(shù)指數(shù)冪整數(shù)指數(shù)冪 。現(xiàn)在已知指數(shù)n和底數(shù)a, 求這個(gè)整數(shù)指數(shù)冪。輸入格式：第一行有兩個(gè)整 數(shù)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結(jié)論：結(jié)論： 第第i位與第位與第j位相乘，位相乘， 本位是本位是i+j-1位，進(jìn)位是位，進(jìn)位是i+j 正整數(shù)的積正整數(shù)的積 問(wèn)題描述 已知兩個(gè)正整數(shù)N和M （N,M0 then ans0:=len else ans0:=len-1;end;參考程序競(jìng)賽中的高精度 -實(shí)例分析取糖果（取糖果（nhoi2007X)問(wèn)題描述：?jiǎn)栴}描述： 琦琦很喜歡交朋友，在動(dòng)

6、物公園玩了半天就認(rèn)識(shí)了幾個(gè)跟她大小相近的朋友，這幾個(gè)朋友跟她都有一個(gè)共同的愛(ài)好：喜歡吃糖，而且她們今天都帶了很多糖果準(zhǔn)備邊玩邊吃。為了表示大家的友誼，這幾個(gè)好朋友就決定邊玩游戲邊分享她們的糖果。她們先把自己所有的糖果全部拿出來(lái)合成一堆，然后通過(guò)搶答的方式來(lái)獎(jiǎng)勵(lì)糖果：搶答的問(wèn)題是：規(guī)定每次只可以取1顆或2顆糖，如果不考慮糖果的不同，取N顆糖共有多少種取法？（注：“先取1顆再取2顆”與“先取2顆再取1顆”視為不同的兩種取法）由一位小朋友說(shuō)出N的值，然后一齊搶答。哪個(gè)小朋友能最快正確回答這個(gè)問(wèn)題就獎(jiǎng)勵(lì)1顆糖。 哈哈！琦琦最后得到了最多的糖果。因?yàn)樗致斆?，想出?dāng)取1顆糖時(shí)只有一種取法，取2顆糖時(shí)有

7、2種取法（每次取1顆一次取2顆），取3顆糖時(shí)就有3種取法（每次取1顆先取1顆再取2顆先取2顆再取1顆），取4顆糖時(shí)就有5種取法，根據(jù)規(guī)律就能快速計(jì)出取N顆糖的取法數(shù)。當(dāng)其他小朋友還苦思冥想時(shí)琦琦就早已把答案推出來(lái)了。 你知道琦琦是找到了什么規(guī)律來(lái)算的嗎？請(qǐng)編程序來(lái)幫她算得更快些。 輸入格式：輸入格式： 輸入文件只有1行，為要取的糖的顆數(shù)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.參考程序國(guó)王與麥子國(guó)王與麥子(nhoi2004x)

9、問(wèn)題描述：?jiǎn)栴}描述： 傳說(shuō)古代印度有個(gè)喜歡下棋的國(guó)王叫舍罕，而宰相達(dá)依爾是個(gè)聰明的大臣，發(fā)明了國(guó)際象棋。國(guó)王玩得愛(ài)不惜手，決定獎(jiǎng)賞宰相。達(dá)依爾說(shuō)：陛下，我別無(wú)他求，請(qǐng)你在這張棋盤(pán)的第一個(gè)格子里賞我一粒麥子；在第個(gè)格子里賞我2粒麥子；在第個(gè)格子里賞我粒麥子；在第個(gè)格子里賞我粒麥子依此類(lèi)推直到64個(gè)格子，按這張棋盤(pán)上各格應(yīng)賞的麥子全賞給我吧。國(guó)王聽(tīng)了，覺(jué)得達(dá)依爾的要求并不高，說(shuō)道：你能如愿以?xún)數(shù)?。然而，?guó)王卻不知道這個(gè)數(shù)字是多么巨大??！你能幫助國(guó)王算算第n個(gè)格子的麥子數(shù)量嗎？（提示：本題可采用高精度運(yùn)算來(lái)解題；若在Pascal中只使用一個(gè)變量存放麥子數(shù)，則至少須將其說(shuō)明為L(zhǎng)ongint型。）輸入格

10、式：輸入格式：從鍵盤(pán)輸入正整數(shù)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.參考程序義務(wù)植樹(shù)義務(wù)植樹(shù) (nhoi2008)問(wèn)題描述：?jiǎn)栴}描述： 3月12日植樹(shù)節(jié)到了，小明的班主任帶著全班同學(xué)到白云山義務(wù)植樹(shù)。小明心里想還沒(méi)有去過(guò)白云山呢，這下可以好好玩一下。好不容易到了白云山，找到預(yù)先安排好的地方，班主任把工具分發(fā)下去，拿出一張圖紙(如圖1)展示給大家看，并說(shuō)明要求：我們班所有同學(xué)植的樹(shù)要成一個(gè)等腰三角形，等

14、腰三角形的兩條腰上按順序都是植1棵樹(shù)，其他位置植樹(shù)棵數(shù)等于它的左上角和右上角所植樹(shù)的和。全班同學(xué)一定不能弄錯(cuò)，要分工協(xié)作，發(fā)揚(yáng)團(tuán)結(jié)互助的精神，把這次植樹(shù)活動(dòng)做好。小明負(fù)責(zé)本小組植樹(shù)棵數(shù)的計(jì)算，例如第i行第j個(gè)位置應(yīng)植多少棵樹(shù)。小明認(rèn)真看了一下圖紙，傻眼了，這該怎么計(jì)算?。吭瓉?lái)還想好好玩一玩，這下可慘了。你能幫助小明完成計(jì)算任務(wù)嗎？輸入格式：輸入格式：輸入文件只有1行：i和j兩個(gè)數(shù)(1=i,j=101，j=i)，中間隔一個(gè)空格，表示植樹(shù)位置為第i行第j個(gè)位置(從左往右數(shù)第j個(gè))。輸出格式：輸出格式：輸出文件只有一個(gè)數(shù)：所求位置上應(yīng)植數(shù)的棵數(shù)。樣例樣例1樣例樣例2輸入樣例3 25 3輸出樣例26問(wèn)

15、題分析本題實(shí)質(zhì)是求楊輝三角。轉(zhuǎn)化轉(zhuǎn)化111121133114641看表格規(guī)律： ai,j:=ai-1,j-1+ai-1,j ai,1:=1; ai,i:=1;數(shù)據(jù)規(guī)模：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.參考程序 階乘和階乘和 【問(wèn)題描述】 已知正整數(shù)N（N=100）,設(shè)S=1!+2!+3!+.N!。其中!表示階乘,即N!=1*2*3*(N-1)*N，如:3!=1*2*3=6。請(qǐng)編程實(shí)現(xiàn)：輸入正整數(shù)N,輸出計(jì)算結(jié)果S的值。【輸入樣例】sum.in4【輸出樣例】sum.out33【問(wèn)

18、題描述問(wèn)題描述】 一個(gè)整數(shù)的數(shù)字乘積根是這樣得到的：將此整數(shù)中的非零數(shù)字相乘，得到的結(jié)果再重復(fù)上述運(yùn)算，直到只有一位數(shù)為止，此一位數(shù)即為原整數(shù)的數(shù)字乘根。例如：整數(shù)99， 99 9 X 9 = 81 8 X 1 = 8 8 即為99的乘積根?！据斎敫袷捷斎敫袷健?輸入文件(cheng.in)的數(shù)據(jù)只有一個(gè)n位的整數(shù)。（n=255）【輸出格式輸出格式】 輸出文件只有一個(gè)一位數(shù)，即n的乘積根。 乘積根乘積根 樣例樣例1樣例樣例2輸入樣例991023輸出樣例86高精度除單精度求商高精度除單精度求余高精度數(shù)排序毛怪和大眼仔毛怪和大眼仔 (eyes) 【問(wèn)題描述問(wèn)題描述】 怪獸公司是怪物世界中最大的企業(yè)

19、，他們主要的業(yè)務(wù)就是要躲進(jìn)小孩子睡房?jī)?nèi)的衣柜 里，在他們臨睡時(shí)大嚇?biāo)麄円环?收集兒童的尖叫聲以保持自己的能量。怪物集團(tuán)主要的成員 有掌管一切的蟹總裁，多管閑事的蛇頭接待員，喜歡挖苦人的變色龍怪物，還有其中一只最大只的藍(lán)毛怪物詹士和他的助手大眼仔。通往人類(lèi)世界的睡房衣柜的門(mén)按照1n的順序排好，連好在生產(chǎn)線上，線上頭尾相接成為一個(gè)圈，順時(shí)針轉(zhuǎn)動(dòng)，怪獸們就是從這些門(mén)到達(dá)人類(lèi)世界嚇唬小孩子，收集小孩叫聲的能量的。 在一次任務(wù)中，毛怪和大眼仔發(fā)現(xiàn)了一個(gè)秘密，原來(lái)收集到小孩笑聲的能量比驚嚇叫聲的能量大好多倍，于是，他們的現(xiàn)在任務(wù)是收集他們以前嚇過(guò)的小孩的笑聲，要找到他們以前嚇過(guò)的小孩也不是那么容易，因?yàn)殚T(mén)

20、太多了，要是進(jìn)錯(cuò)了，那小孩不是他們自己嚇過(guò)的，便又只能收集到哭喊聲了。毛怪他們?nèi)ゲ樗麄円郧斑M(jìn)過(guò)的門(mén)的編號(hào)，可是公司的數(shù)據(jù)庫(kù)系統(tǒng)已經(jīng)自動(dòng)給門(mén)號(hào)加密了，門(mén)號(hào)的數(shù)字跟他們以前進(jìn)的不一樣，都變大了，而且有些大得很離譜，不過(guò)大眼仔記性好，發(fā)現(xiàn)了一個(gè)規(guī)律，他按照拿到的門(mén)號(hào)，從生產(chǎn)線的第一個(gè)門(mén)開(kāi)始數(shù)，繞著生產(chǎn)線的圈子，數(shù)到新門(mén)號(hào)的數(shù)字停下來(lái)，那個(gè)門(mén)便是以前他們進(jìn)過(guò)的。毛怪按照大眼仔的說(shuō)法，拿著的新門(mén)號(hào)是23，生產(chǎn)線上一共有15扇門(mén)，于是，他開(kāi)始數(shù)1，2，315，1，2，3，剛好在8號(hào)門(mén)停下來(lái)，于是開(kāi)門(mén)進(jìn)去，發(fā)現(xiàn)果然是他們以前嚇過(guò)的小孩，非常開(kāi)心，于是毛怪和大眼仔便誠(chéng)心的把他哄得開(kāi)心的笑了，回來(lái)之后，毛怪又去

21、領(lǐng)新的門(mén)號(hào)，站在生產(chǎn)線上逐個(gè)門(mén)的數(shù)，可是這樣子效率太差了，要是能快速的知道究竟是哪個(gè)門(mén)就好了，你能想到法子幫助毛怪嗎？ 【輸入格式輸入格式】 第一、二行分別讀入正整數(shù)N和M，分別是生產(chǎn)線上門(mén)的總數(shù)和毛怪領(lǐng)到的新門(mén)號(hào)，其中N、M滿(mǎn)足2 N 108，2 M 101000【輸出格式輸出格式】 對(duì)應(yīng)舊的門(mén)號(hào)，文件只有一行（包括換行符）。樣例樣例1樣例樣例2輸入樣例7911108輸出樣例29【問(wèn)題描述】 工商部門(mén)查獲了有N個(gè)人正在販賣(mài)注水豬肉,現(xiàn)在要你對(duì)這N個(gè)人的注水豬肉的數(shù)量從大到小的排序,并且算出這N個(gè)人的注水豬肉總和(單位為.斤)我們姑且稱(chēng)這些販賣(mài)者為”豬王”吧. 【輸入文件buss.in】 輸入的第一行是一個(gè)1到1000的整數(shù)N，表示總共有N位豬王參加了爭(zhēng)霸賽。以下依次給出每位豬王的描述，一位豬王的描述占據(jù)兩行，第一行為一個(gè)僅由小寫(xiě)字母組成的長(zhǎng)度不超過(guò)13的字符串，代表這個(gè)豬王的名字，第二行一個(gè)整數(shù)(非負(fù)數(shù)，102000)，代表這個(gè)豬王的注水豬肉總斤數(shù)。注意，這個(gè)整數(shù)的首位沒(méi)有不必要的0。所有豬王販賣(mài)的注水豬肉數(shù)量的總長(zhǎng)度不會(huì)超過(guò)2000?！据敵鑫募uss.out】 依次輸出按照注水豬肉多少?gòu)拇蟮叫∨藕眯虻母魑回溬u(mài)者的依次輸出按照注水豬肉多少?gòu)拇蟮叫∨藕眯虻母魑回溬u(mài)者的名字，每個(gè)名字占據(jù)單獨(dú)的一行。不能有任何多余的字符。若幾名字，每個(gè)名字占