1、ACM國際大學生程序設計競賽主講王樹林當有一個很大的整數要運算時, 如何算?例如: 一個一佰位數的數字.int 最大只能到232約十個位數的十進制數.先看大數加法.就是改成手動去算加法, 而不是由計算機算.123456789123+ 234123467890方法一: 使用數組(array)例如: int a100, b100, sum100;然后sumi=ai+bi+c記住, c 是進位(carry), 這邊我們要自行處理.輸入成字符串再把字符串分解成數組中各個元素.需要一個parse字符串的子程序.void parse(char *s, int *a)int i,j;j=strlen(s);

2、for(i=0;i<j;i+)aj-1-i=s0-30;void add(int *a, int *b, int *sum)int i,c;c=0;for(i=0;i<100;i+)sumi=ai+bi+c;if(sumi>=10)sumi=sumi-10;c=1; else c=0;array 改成byte的元素. (省空間)更省? 一個元素就可以到255, 256才進位.用bool用link list 方式(可以讓輸入的數字更大)其他?同樣的原理.現將一些關鍵算法的實現方法描述如下大數的一些簡單計算的算法1、大數加法運算的實現算法(1)將A、B按位對齊(2)低位開始逐位相

3、加(3)對結果做進位調整2、大數減法運算實現算法(1)將A、B按位對齊(2)低位開始逐位相減(3)對結果做借位調整3、大數乘法運算實現算法(1)引入sum2 、sum1中間過渡量(2)在n的每一位上處理m(3)通過每一層循環實現乘法的加法化(4)對結果做進位調整4、大數除法運算的算法實現(1)引入al來標識a的長度, bl來標識b的長度(2)測算a和b的長度(3)高位開始對位做減法并完成借位(4)高位開始逐位計算商(5)整理商, 產生余數;5、大數取模運算的算法實現在取模運算中用到了上面的除法運算只需返回余數即可。ACDBX=Y=).()()(2)(2).()(2)(2)2)(2(,2,259

4、.13log2/22/2/2/2/2/nOnOnTBDBDACCDBAACXYnOnTBDCBADACDCBAXYDCYBAXnnnnnnnn題意本題目給三個數字t,a,b(都比2147483647小)問(ta - 1)/(tb -1)是大小于100位數或是否為整數若小于100位數就印該值。題意范例Sample Input2 9 32 3 221 42 7123 911 1Sample Output(29-1)/(23-1) 73(23-1)/(22-1) is not an integer with less than 100 digits.(2142-1)/(217-1) 18952884

5、496956715554550978627384117011154680106(123911-1)/(1231-1) is not an integer with less than 100 digits.解法1t=1Its easy to see that its answer isnt a integer with less than 100 digits.2a=bIts easy to see that its answer is 1.3if(a %b != 0) Its answer isnt a integer with less than 100 digits.證明令(ta - 1

6、)/(tb -1) = n, n是整數證明a%b=0(ta - 1)/ (tb - 1) = t(a-b) +t(a-2b)+t(a-3b)+t(a-nb)因為一定除的進(這是我們的假設)所以a-nb = 0,a%b = 0p->q, -q->-p, a%b!=0,就不會是整數。令x=tb, a/b=y, y是正整數(ta - 1)/(tb -1) = (xy-1)/(x-1)(xy-1)/(x-1) = x(y-1)+x(y-2)+x(y-3)+.+x0x(y-1) > x(y-2)+x(y-3)+.+x0x(y-1) 加上x(y-2)+x(y-3)+.+x0 最多進一位數

7、。Log10(x(y-1) = log10(t(a-b) = (a-b)*log10(t)if(a-b)*log10(t) >=99),就一定會大于100位數若沒有大于100位數有可能等于100位數所以要算出來。5、(xy-1)/(x-1) = x(y-1)+x(y-2)+x(y-3)+.+x0將這個值算出來.討論這題目一定要先判斷位數如果大于100位就不用算了不然會超過時間且要用比較好的方法算真正的值若用大數除法會太慢所以改成(xy-1)/(x-1) = x(y-1)+x(y-2)+x(y-3)+.+x0這樣的方式來算比較快!int random(int p201) /隨機產生一個20

8、0位的數p1=1; /低位1為保證該素數為奇數int i;for (i=2;i<=200;i+) pi=rand()*10/RAND_MAX;while (p200=0) /高位不能為0保證素數達到要求的長度p200=rand()*10/RAND_MAX;return 0;int multiply(int m101,int n201,int product301)/兩因子m 、n乘積product int sum1102,sum2102,i,j,k,s; / sum2 、sum1中間過渡量for (i=1; i<=101;i+)sum2i=0;/ sum2所有位置零for (j=1

9、;j<201;j+)/在n的每一位上處理m for(i=1;i<=101;i+)sum1i=0; /sum1所有位置零for (i=1;i<=nj;i+)/通過每一層循環實現乘法的加法化 for (s=1;s<101;s+)sum2s=ms+sum1s;for (k=1;k<=101; k+)sum1k=sum2k;for (k=j;k<=100+j;k+) productk=sum2k-j+1+productk;/即是實現了乘法過程中的加法for (i=1;i<301;i+)/進位處理j=producti/10;producti+1+=j;produ

10、cti-=j*10;return 0;int cmp(int a301, int ab, int b201, int bb) /比較兩個數的大小 int i, result;result = 0; / a = b;for(i = 300; i > ab; i-)if(ai != 0) return 1;for(i = 0; i < bb; i+) if(aab - i > bbb - i) result = 1; / a > b;break;if(aab - i < bbb - i) result = -1; / a < b;break;return res

11、ult;void division(int a301, int b201, int c301, int d201)/除法函數300位除200位,c為商d為余數int al, bl, t301; / al用來標識a的長度, bl用來標識b的長度int i, j, al2;for(i = 0; i < 301; i+) ci = 0;/商置零if(i < 202) di = 0;/余數置零ti = ai;for(i = 300; i > 0; i-)/測算a的長度if(ai != 0) al = i;break;for(i = 200; i > 0; i-)/測算b的長度i

12、f(bi != 0) bl = i;break;al2 = al;for(i = 0; i < al - bl + 1; i+)/高位開始 while(cmp(t, al2, b, bl)!=-1)/比較a、b首位大小 for(j = 0; j < bl; j+)tal2 - j -= bbl - j;/對位做減法for(j = 1; j < 301; j+)if(tj < 0)/完成借位 tj += 10;tj + 1-;cal - bl + 1 - i+;/高位開始逐位計算商al2-;for(i = 0; i< 201; i+) di = ti;/產生余數組合

13、數學研究的主要內容是依據一定的規則來安排某些事務的有關數學問題。這些問題包括四個方面1。這種安排是否存在即存在性問題2。如果符合要求的安排是存在的那么這樣的安排又有多少即計數問題3。怎樣構造這種安排即算法構造問題4。如果給出了最優化標準又怎樣得到得到最優安排。實際生活中的各種問題有些可以當機立斷判定其有解還是無解。但也有不少問題一時難以判定。例如宴會上奇數位客人能否在晚會上與他人握手奇數次。競賽時不可能出現專門判定某個問題有解或無解的試題。但往往會在測試數據中加入無解的數據。如果一個組合問題的解是存在的自然會問有多少不同的解。例如將8個“車”放在8×8的國際象棋棋盤上如果他們兩兩不能

14、互吃那么稱8個“車”處于一個安全狀態。顯然這種安全狀態是存在的。問有多少種不同的安全狀態。這就是一個計數問題。信息學競賽中一般分為兩種類型一種是計算某種特性的對象有多少另一種是枚舉類型把所有具有某種特性的對象都列舉出來。一個組合問題已經判定解是存在的甚至已經推知有多少解但關鍵還在于把解構造出來有的哪怕出一個解也好。如魔方問題正交拉丁問題。一個問題的構造性算法可能不止一種自然面臨如何擇優如何改進使得答案盡快地解出來。比如動態規劃和線性規劃問題的解決方法。1 從組合學基本概念基本原理出發的常規方法容斥原理Polya原理鴿籠原理遞歸方法生成函數方法2 通常與問題所涉及的組合數學概念無關的非常規方法。

15、主要用于解那些需要獨立思考見解獨到和有所創新的問題。數學歸納法證明n個元素的集合其子集恰為2n個一一對應技術 將一個問題轉化為另一種有常規算法的問題模式。例如8“車”問題有多少個不同的安全狀態。8個車處于安全狀態當且僅當它們處于不同的8行和8列上。用一個排列a1a2a8對應于一個安全狀態使ai表示第i行的ai列上放置一個車。這種對應顯然是一對一的。因此安全狀態的總數等于這8個數的全排列的總數8=40320。從不同的角度討論計數問題以建立組合等式例如對沒有三條對角線交于一點的凸多邊形計算各邊及對角線所組成的互不重疊的區域個數。區域總數為Cn4Cn12各區域頂點總數包括重復計數角度1角度2所有區域

16、的內角和的總和的等式兩邊同除以180度得兩式相減得區域總數運用奇偶性整除性等數論性質進行存在性問題的分析與推理。例子設n位客人在晚會上每人與他人握手d次d是奇數證明n是偶數。需要用計算機求解的組合試題一般有兩種類型1。能夠用簡明正確的組合公式揭示問題。2。不能對給定問題建立數學模型或雖然有數學模型但運用該數學模型求解有困難。在求解枚舉類型問題時會遇到此類問題。回溯方法是一種常用的解題策略。例子一個n×n的國際象棋棋盤上放置n個皇后使其不能相互攻擊即任何兩個皇后都不能處在棋盤的同一行同一列同一條斜線上試問有多少中擺法一如何求n皇后問題1 狀態state狀態是指問題求解過程中每一步的狀況

17、。n皇后問題中某行皇后所在列位置i即為該皇后問題的一個狀態。2 算符operator算符是把問題的一個狀態變換到另一個狀態的方法代號。n皇后的一種擺法對應n個元素的排列方案a1a2,an必須滿足條件不產生對角線攻擊和列攻擊。3。結點node用以表明某狀態特征及關聯方式的基本信息單元。結點的數據結構一般為記錄類型。Type node=recordoperator : 算符類型state狀態類型end;Var stackarray1。maxdepth of node節點數不超過maxdepth的一條路徑orVarstack: array1.20 of integer;當n4時初始狀態空棋盤試放的順

18、序是從左至右自上而下××××求解n皇后問題無非就是做兩件事1。從左至右逐條樹枝地構造和檢查解答樹t2。檢查t的節點是否對應問題的目標狀態。為了加快檢查速度一般規定1。在擴展一個分支節點前進行檢查如果它不滿足約束條件則不再構造以它為根節點的子樹2。已處理過的節點若以后不會再用則不必保留即回溯過程中經過的節點不再保留。遞歸過程makeL1 分配一個連續的數組區域stack1.maxdepth順序存放棧中表目即當前路徑的節點。2 棧頂指針L作遞歸程序make的值參數指出待擴展節點在當前路徑序列stack中的順序算符作make過程的局部變量。Program se

19、archVar stack:array1.maxdepth of node;.Procedure make(L:integer);Var Beginmake(L+1); End; makeBeginmake(1);End;一個售貨亭前排著2N個人的隊伍等候購物假定他們都購買價值5元的同一貨物。其中N個人持5元貨幣N個人持10元貨幣而售貨員開始發售貨物時沒有零錢。問有多少種排隊方式可使售貨員能依次順利地出售貨物而不出現找不出錢的局面。1 鴿籠原理n1只鴿子飛回n鴿籠子至少一個鴿籠含有不少于2只鴿子。數學描述mm>=1個元素分成n個組那么總有一個組至少含有元素個數為m/n。上取整。例子13個

20、人的小組至少有13/12=2人生日在同一個月。用紅籃兩種顏色去涂n個頂點完全圖的邊每邊涂且僅涂一種顏色得到的圖叫做2色完全圖記為kn用 表示這樣的正整數即當時任何一個2色完全圖kn或者含有紅色完全圖kp或者含有藍色完全圖kg兩者必居其一而當 存在2色完全圖kn它不含紅色完全子圖kp和藍色完全圖kg這個數就稱之為Ramsey數。確定Ramsey數是很難的問題。到目前為止主要還是研究 精確求得的數值為數甚少gpgpngpngp一對常數p和g對應一個常數n使得n個人中或有p個人互相認識或者有g個人互相不認識這個n的最小值用 表示顯然gp下面估計 的上界可改進為遞歸邊界gpProgram ramsey

21、uses crt;Const maxn=50;Typertype=array1.maxn, 1.maxn of integer;Var r: rtype; ramsey數組a, b :integer; ramsey數的兩個參數Procedure init; 輸入ramsey數的兩個參數Beginclrscr;repeat write(a=);readln(a);until (a>1) and (a<=maxn);repeat write(b=);readln(b);until (b>1) and (b<=maxn);end;Procedure mainvar I, j

22、:integer;Beginfor i:=2 to a do rI,2:=I; 建立遞歸邊界for i:=2 to b do r2,i:=I;for i:=3 to a do for j:=3 to b do if (odd(ri-1,j) or (odd(rI,j-1) then rI,j:=ri-1,j+rI,j-1else rI,j:=ri-1,j+rI,j-1-1;writeln(R(,a,b,)=,ra,b);end;Begininit; 輸入參數a和bmain; 計算和輸出ramsey數rabEnd程序只能估計上界一些運行結果與精確值有一定誤差。要準確計算Ramsey數只要將程序返

23、回的整數值逐一遞減。直至遞減后的n值所對應的kn圖中出現了不含紅色完全子圖kp或藍色完全子圖kg的情形則n+1就是精確的RAMSEY數了。兩個基本計數原理加法原理乘法原理排列問題線排列 從n個不同的元素中取r個按次序排列稱為從n中取r個排列其排列數記為Pnr圓排列 從集合Sa1,a2,an的n個不同元素中取出r個元素按照某種次序排成一個圓圈稱這樣的排列為圓排列。重排列無限有限重排列一般地把r只彩色球放到n個編號不同的盒子中去的方法種數是組合Cnr非重組合重組合H(nr) 或者C(n+r-1,r)某機要部門安裝了電子鎖。m個工作人員每人發一張磁卡卡上有開鎖的密碼特征。為了確保安全規定至少要有n個

24、人同時使用各自的磁卡才能將鎖打開。現在需要你計算一下電子鎖上至少要有多少種特征每個人的磁卡上至少有幾個特征。如果特征的編號以小寫英文字符表示將每個人的磁卡的特征編號打印出來。要求輸出的電子鎖的總特征數最少。題意告訴我們至少要有n個人在場并同時使用磁卡才能將鎖打開。換言之任意n1個人在一起至少缺少一種開鎖的密碼特征故不能打開電子鎖剩下的m-(n-1)個人中的任意一個人到場就一定能將鎖打開。故電子鎖至少應有Cmmn1中特征。對于任何一個工作人員來說其余m1個人中任意n1個人在場至少缺少一個這個工作人員磁卡上具有的特征而無法打開鎖。所以每個人至少要有Cm-1,n-1種特征。雖然通過組合數學知識是能夠

25、求出電子鎖的最少總特征數和每個人磁卡的最少特征數。但題目還要求枚舉出電子鎖的所有特征。并輸出m張磁卡。計算出特征數12.,#m 表示工作人員編號ab等小寫字母表示磁卡的特征編號超過26個用aabaca.表示。m4N2Make(1,0)開始遞歸二項展開式從組合學角度看相當于(x+y)(x+y)共n個括號相乘相當于n個無區別的球放到xy兩個編號不同的盒子中每個盒子放入的球數不限。二項式定理從二項式展開出發人們自然會想到研究多項展開式普通母函數下式稱為序列 ai 的普通母函數1 天平稱物問題設有質量分別為n1克n2克,nk克的整數值砝碼欲稱i克的物體。物體在左砝碼在右共有多少中不同的稱法設有ai種方

26、法稱i克物體則a0a1,ai作系數序列的母函數是這是因為每個括號(1+xnj)如提供1表示nj克砝碼沒有用上如果提供xnj表示nj砝碼用上了。右邊多項展開式中的每一個xi表示可稱出i克物體其系數便是i克物體的方案數。例子共有1克2克3克4克的砝碼各一枚問能稱出哪幾種重量有幾種可能方案2 允許重復的組合問題設有幾種相異物體。如果允許重復即每種物體的可取數依次為則從中取 個物體的可重復的組合數 為多少整數拆分就是把一個整數分解成若干整數的和。不定方程的解非負整數解的個數題目輸入正整數m和k輸出將m拆分成k項整數和的所有方案。由交換律產生的諸個方案算作同一個方案例如m6k3時123613262136

27、算作1236Program IntegersplitingConst maxm=100;Var k,M: integer; 項數數和ans : array1.maxm of integer; 存儲方案Total : integer; 拆分數Procedure printvar I : integer;begin inc(total); 累計拆分數write(ans No., total:4,:);for i:=1 to k-1 do write(ansi, +); 拆分方案writeln(ansk), =, m)end;Procedure Solve(step, index,sum: inte

28、ger);step形成的項數index第step項的值sum第1.Step項的和var i: integerBeginif step=k then 若拆分成k項且數和為M則打印拆分方案若k項的數和不等于M則執行空語句if sum=m then print elsefor i:=index to m do 否則還未拆分第k項。在index.M之間選擇某值i使得前step項的數和加上i后小于等于MIf sum+i<=m thenbeginansstep+1:=I; i值作為第step項solve(step+1,I,sum+i) 遞歸搜索下一項的值endEnd;Var i:integer;Be

29、ginrepeat write(M=); 輸入數和Mread(m);until m in 1.maxm;repeat write(k=); 輸入項數kread(k);until k in 1.m;total:=0; 拆分數初始化For i:=1 to m div k do 試選1。M分別作為第一項的值beginans1:=i;solve(1,i,i); i作為第1項的值遞歸搜索首項為i的所有拆分方案end;readln;End.End.如果已經求得普通母函數可以通過展開多項式的辦法確定其系數序列。這個系數序列對研究組合問題有相當重要的意義。下面我們來編寫一個程序從一個指定文件中讀入普通母函數。

30、文件格式為每行表示一個多項式按冪次數遞增的順序輸入各項。每項系數在前指數在后各項間以空格隔開每行最后加00表示一個多項式輸入結束。行間的回車表明多項式之間的連乘關系。用單鏈表P存儲普通型母函數的展開式鏈結點存儲當前項結點形式為初始時P為Program multiplyType link=node; 指針noderecord 項結點time: integer; 次冪a: real; 系數nextlink 指向下項的指針endVarp,r :link; P存儲以前各多項式的展開式r加入當前多項式后展開的結果f: text; 輸入文件Procedure init文件讀前準備Var strstring

31、Beginwrite(File Name=);readln(str);Assign(f,str);reset(f);End;Procedure free(p:link); 釋放P鏈Beginif p<>nil then beginfree(p.next);dispose(p);end;End;Procedure add(time:integer; a:real;r:link);通過合并同類項將aXtime鏈入r鏈Var tlinkBeginif r.next=nil 若次冪time最大則aXtime加入r鏈尾then beginnew(r.next);r.next.time:=time;r.next.a:=a; r.next.next:=nil;end;Else if r.next.time=tim