大數(shù)運(yùn)算與組合數(shù)學(xué)

1、大數(shù)運(yùn)算與組合數(shù)學(xué)ACM1問題當(dāng)有一個(gè)很大的整數(shù)要運(yùn)算時(shí), 如何算?例如: 一個(gè)一佰位數(shù)的數(shù)字.int 最大只能到 232 約十個(gè)位數(shù)的十進(jìn)位數(shù)字.2最簡(jiǎn)單的方法先看大數(shù)加法.就是改成手動(dòng)去算加法, 而不是由電腦算. 123456789123 + 234123467890-3寫成電腦程式方法一: 使用陣列 (array)例如: int a100, b100, sum100;然後 sumi=ai+bi+c記住, c 是進(jìn)位(carry), 這邊我們要自行處理.4那輸入呢?輸入成字串再把字串分解成陣列中各個(gè)元素.需要一個(gè)parse字串的副程式.5void parse(char *s, int *a

2、) int i,j; j=strlen(s); for(i=0;ij;i+) aj-1-i=s0-30; void add(int *a, int *b, int *sum) int i,c; c=0; for(i=0;i=10) sumi=sumi-10; c=1; else c=0; 6改進(jìn)array 改成 byte的元素. (省空間)更省? 一個(gè)元素就可以到255, 256才進(jìn)位.用bool用link list 方式(可以讓輸入的數(shù)字更大)其他?7減法? 乘法? 除法?同樣的原理.8大數(shù)運(yùn)算現(xiàn)將一些關(guān)鍵算法的實(shí)現(xiàn)方法描述如下：大數(shù)的一些簡(jiǎn)單計(jì)算的算法1、大數(shù)加法運(yùn)算的實(shí)現(xiàn)算法(1)將A、

3、B按位對(duì)齊；(2)低位開始逐位相加；(3)對(duì)結(jié)果做進(jìn)位調(diào)整；2、大數(shù)減法運(yùn)算實(shí)現(xiàn)算法(1)將A、B按位對(duì)齊；(2)低位開始逐位相減；(3)對(duì)結(jié)果做借位調(diào)整；9大數(shù)運(yùn)算3、大數(shù)乘法運(yùn)算實(shí)現(xiàn)算法(1)引入sum2 、sum1中間過渡量；(2)在n的每一位上處理m；(3)通過每一層循環(huán)，實(shí)現(xiàn)乘法的加法化；(4)對(duì)結(jié)果做進(jìn)位調(diào)整；4、大數(shù)除法運(yùn)算的算法實(shí)現(xiàn)(1)引入al來標(biāo)識(shí)a的長(zhǎng)度, bl來標(biāo)識(shí)b的長(zhǎng)度；(2)測(cè)算a和b的長(zhǎng)度；(3)高位開始，對(duì)位做減法，并完成借位；(4)高位開始逐位計(jì)算商(5)整理商, 產(chǎn)生余數(shù);5、大數(shù)取模運(yùn)算的算法實(shí)現(xiàn) 在取模運(yùn)算中用到了上面的除法運(yùn)算，只需返回余數(shù)即可。10

4、大整數(shù)的乘法ACDBX=Y=11例子題意： 本題目給三個(gè)數(shù)字t,a,b(都比2147483647小)，問(ta - 1)/(tb -1)是大小於100位數(shù)或是否為整數(shù)，若小於100位數(shù)，就印該值。題意範(fàn)例：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) 95676273841176(123911-1)/(1231-1) is not an integer wit

5、h less than 100 digits. 12例子解法：1）t=1 Its easy to see that its answer isnt a integer with less than 100 digits.2）a=b Its easy to see that its answer is 1.3）if(a %b != 0) Its answer isnt a integer with less than 100 digits.証明：令(ta - 1)/(tb -1) = n, n是整數(shù)，証明a%b=0(ta - 1)/ (tb - 1) = t(a-b) +t(a-2b)+t(a-

6、3b)+t(a-nb)因?yàn)橐欢ǔ倪M(jìn)(這是我們的假設(shè))，所以a-nb = 0, a%b = 0 p-q, -q-p, a%b!=0,就不會(huì)是整數(shù)。13例子令x=tb, a/b=y, y是正整數(shù)，(ta - 1)/(tb -1) = (xy-1)/(x-1)(xy-1)/(x-1) = x(y-1)+x(y-2)+x(y-3)+.+x0 x(y-1) x(y-2)+x(y-3)+.+x0 x(y-1) 加上 x(y-2)+x(y-3)+.+x0 最多進(jìn)一位數(shù)。Log10(x(y-1) = log10(t(a-b) = (a-b)*log10(t)if(a-b)*log10(t) =99),就一定

7、會(huì)大於100位數(shù)若沒有大於100位數(shù)，有可能等於100位數(shù)，所以要算出來。5、(xy-1)/(x-1) = x(y-1)+x(y-2)+x(y-3)+.+x0 將這個(gè)值算出來.14例子討論： 這題目一定要先判斷位數(shù)，如果大於100位就不用算了，不然會(huì)超過時(shí)間，且要用比較好的方法算真正的值，若用大數(shù)除法，會(huì)太慢，所以改成(xy-1)/(x-1) = x(y-1)+x(y-2)+x(y-3)+.+x0，這樣的方式來算，比較快! 15隨機(jī)產(chǎn)生一個(gè)200位的數(shù)int random(int p201) /隨機(jī)產(chǎn)生一個(gè)200位的數(shù)p1=1; /低位1為保證該素?cái)?shù)為奇數(shù)int i; for (i=2;i=2

8、00;i+) pi=rand()*10/RAND_MAX;while (p200=0) /高位不能為0，保證素?cái)?shù)達(dá)到要求的長(zhǎng)度p200=rand()*10/RAND_MAX;return 0;16乘法運(yùn)算int multiply(int m101,int n201,int product301)/兩因子m 、n，乘積productint sum1102,sum2102,i,j,k,s; / sum2 、sum1中間過渡量for (i=1; i=101;i+)sum2i=0;/ sum2所有位置零for (j=1;j201;j+)/在n的每一位上處理m for(i=1;i=101;i+)sum1

9、i=0; /sum1所有位置零for (i=1;i=nj;i+)/通過每一層循環(huán)，實(shí)現(xiàn)乘法的加法化 for (s=1;s101;s+) sum2s=ms+sum1s; for (k=1;k=101; k+) sum1k=sum2k;for (k=j;k=100+j;k+) productk=sum2k-j+1+productk;/即是實(shí)現(xiàn)了乘法過程中的加法for (i=1;i ab; i-)if(ai != 0) return 1;for(i = 0; i bbb - i) result = 1; / a b;break;if(aab - i bbb - i) result = -1; / a

10、 b;break;return result;18除法運(yùn)算void division(int a301, int b201, int c301, int d201)/除法函數(shù)，300位除200位,c為商，d為余數(shù)int al, bl, t301; / al用來標(biāo)識(shí)a的長(zhǎng)度, bl用來標(biāo)識(shí)b的長(zhǎng)度int i, j, al2;for(i = 0; i 301; i+)ci = 0;/商置零if(i 0; i-)/測(cè)算a的長(zhǎng)度if(ai != 0)al = i;break;for(i = 200; i 0; i-)/測(cè)算b的長(zhǎng)度if(bi != 0)bl = i;break;19除法運(yùn)算（續(xù)）al2

11、 = 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;/對(duì)位做減法for(j = 1; j 301; j+)if(tj 0)/完成借位 tj += 10;tj + 1-;cal - bl + 1 - i+;/高位開始逐位計(jì)算商al2-;for(i = 0; i=1）個(gè)元素分成n個(gè)組，那么總有一個(gè)組至少含有元素個(gè)數(shù)為m/n。上取整。例子：13個(gè)人的小組至少有13/12=2人生日在同一個(gè)月。412 Ramsey問題和

12、Ramsey數(shù)用紅籃兩種顏色去涂n個(gè)頂點(diǎn)完全圖的邊，每邊涂且僅涂一種顏色，得到的圖叫做2色完全圖，記為kn42Ramsey數(shù)用 表示這樣的正整數(shù)，即當(dāng)時(shí)，任何一個(gè)2色完全圖kn，或者含有紅色完全圖kp，或者含有藍(lán)色完全圖kg，兩者必居其一；而當(dāng) 存在2色完全圖kn它不含紅色完全子圖kp和藍(lán)色完全圖kg，這個(gè)數(shù)就稱之為Ramsey數(shù)。確定Ramsey數(shù)是很難的問題。到目前為止，主要還是研究 ，精確求得的數(shù)值為數(shù)甚少43另一種表述一對(duì)常數(shù)p和g對(duì)應(yīng)一個(gè)常數(shù)n，使得n個(gè)人中或有p個(gè)人互相認(rèn)識(shí)，或者有g(shù)個(gè)人互相不認(rèn)識(shí)，這個(gè)n的最小值用 表示顯然44Ramsey數(shù)上界估計(jì)公式下面估計(jì) 的上界 可改進(jìn)為：

13、遞歸邊界45上界估計(jì)程序Program ramseyuses crt;Const maxn=50;Type rtype=array1.maxn, 1.maxn of integer;Var r: rtype; ramsey數(shù)組 a, b :integer; ramsey數(shù)的兩個(gè)參數(shù)46Procedure init; 輸入ramsey數(shù)的兩個(gè)參數(shù)Begin clrscr; repeat write(a=); readln(a); until (a1) and (a1) and (b=maxn); end;47Procedure mainvar I, j :integer;Begin for i:

14、=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-1 else rI,j:=ri-1,j+rI,j-1-1; writeln(R(,a,b,)=,ra,b); end;Begin init; 輸入?yún)?shù)a和b main; 計(jì)算和輸出ramsey數(shù)r（a，b）End；程序只能估計(jì)上界，一些運(yùn)行結(jié)果與精確值有一定誤差。要準(zhǔn)確計(jì)算Ramsey數(shù)，只要將程序返回的整數(shù)值逐一

15、遞減。直至遞減后的n值所對(duì)應(yīng)的kn圖中出現(xiàn)了不含紅色完全子圖kp或藍(lán)色完全子圖kg的情形，則n+1就是精確的RAMSEY數(shù)了。48排列組合與計(jì)數(shù)問題兩個(gè)基本計(jì)數(shù)原理 加法原理 乘法原理排列問題 線排列 從n個(gè)不同的元素中，取r個(gè)按次序排列，稱為從n中取r個(gè)排列，其排列數(shù)記為P（n，r） 圓排列 從集合Sa1,a2,an的n個(gè)不同元素中，取出r個(gè)元素按照某種次序排成一個(gè)圓圈，稱這樣的排列為圓排列。 重排列 無限49有限重排列 一般地，把r只彩色球放到n個(gè)編號(hào)不同的盒子中去的方法種數(shù)是50組合 C（n，r）非重組合 重組合H(n，r) 或者C(n+r-1,r)51ACM賽題某機(jī)要部門安裝了電子鎖。

16、m個(gè)工作人員每人發(fā)一張磁卡，卡上有開鎖的密碼特征。為了確保安全，規(guī)定至少要有n個(gè)人同時(shí)使用各自的磁卡才能將鎖打開?，F(xiàn)在需要你計(jì)算一下，電子鎖上至少要有多少種特征，每個(gè)人的磁卡上至少有幾個(gè)特征。如果特征的編號(hào)以小寫英文字符表示，將每個(gè)人的磁卡的特征編號(hào)打印出來。要求輸出的電子鎖的總特征數(shù)最少。52解題分析題意告訴我們，至少要有n個(gè)人在場(chǎng)并同時(shí)使用磁卡才能將鎖打開。換言之，任意n1個(gè)人在一起，至少缺少一種開鎖的密碼特征，故不能打開電子鎖，剩下的m-(n-1)個(gè)人中的任意一個(gè)人到場(chǎng)，就一定能將鎖打開。故電子鎖至少應(yīng)有C（m，mn1）中特征。對(duì)于任何一個(gè)工作人員來說，其余m1個(gè)人中任意n1個(gè)人在場(chǎng)，至

17、少缺少一個(gè)這個(gè)工作人員磁卡上具有的特征而無法打開鎖。所以每個(gè)人至少要有C（m-1,n-1）種特征。53雖然通過組合數(shù)學(xué)知識(shí)是能夠求出電子鎖的最少總特征數(shù)和每個(gè)人磁卡的最少特征數(shù)。但題目還要求枚舉出電子鎖的所有特征。并輸出m張磁卡。54計(jì)算出特征數(shù)1，2，.,#m 表示工作人員編號(hào)a，b等小寫字母表示磁卡的特征編號(hào)，超過26個(gè)，用aa，ba，ca，.表示。5556575859m4N2Make(1,0)開始遞歸60母函數(shù)二項(xiàng)展開式從組合學(xué)角度看，相當(dāng)于(x+y)(x+y)共n個(gè)括號(hào)相乘相當(dāng)于n個(gè)無區(qū)別的球，放到x，y兩個(gè)編號(hào)不同的盒子中，每個(gè)盒子放入的球數(shù)不限。二項(xiàng)式定理61從二項(xiàng)式展開出發(fā)，人們

18、自然會(huì)想到研究多項(xiàng)展開式：62普通母函數(shù)：下式稱為序列 ai 的普通母函數(shù)1 天平稱物問題：設(shè)有質(zhì)量分別為n1克，n2克,，nk克的整數(shù)值砝碼，欲稱i克的物體。物體在左，砝碼在右，共有多少中不同的稱法？設(shè)有ai種方法稱i克物體，則a0，a1，,ai，作系數(shù)序列的母函數(shù)是63這是因?yàn)槊總€(gè)括號(hào)(1+xnj)如提供1，表示nj克砝碼沒有用上；如果提供xnj，表示nj砝碼用上了。右邊多項(xiàng)展開式中的每一個(gè)xi表示可稱出i克物體，其系數(shù)便是i克物體的方案數(shù)。例子：共有1克，2克，3克，4克的砝碼各一枚，問能稱出哪幾種重量？有幾種可能方案？642 允許重復(fù)的組合問題 設(shè)有幾種相異物體。如果允許重復(fù)，即每種物

19、體的可取數(shù)依次為則從中取 個(gè)物體的可重復(fù)的組合數(shù) 為多少？653 整數(shù)拆分整數(shù)拆分就是把一個(gè)整數(shù)分解成若干整數(shù)的和。不定方程的解，非負(fù)整數(shù)解的個(gè)數(shù) 666768枚舉整數(shù)拆分題目：輸入正整數(shù)m和k， 輸出將m拆分成k項(xiàng)整數(shù)和的所有方案。 由交換律產(chǎn)生的諸個(gè)方案算作同一個(gè)方案，例如m6， k3時(shí) 1236 1326 2136算作123669Program IntegersplitingConst maxm=100;Var k,M: integer; 項(xiàng)數(shù)，數(shù)和 ans : array1.maxm of integer; 存儲(chǔ)方案 Total : integer; 拆分?jǐn)?shù)Procedure prin

20、t var I : integer; begin inc(total); 累計(jì)拆分?jǐn)?shù) write(ans No., total:4,:); for i:=1 to k-1 do write(ansi, +); 拆分方案 writeln(ansk), =, m) end;70Procedure Solve(step, index,sum: integer); step形成的項(xiàng)數(shù)；index第step項(xiàng)的值；sum第1.Step項(xiàng)的和 var i: integerBegin if step=k then 若拆分成k項(xiàng)，且數(shù)和為M，則打印拆分方案；若k項(xiàng)的數(shù)和不等于M，則執(zhí)行空語句 if sum=m

21、 then print else for i:=index to m do 否則還未拆分第k項(xiàng)。在index.M之間選擇某值i，使得前step項(xiàng)的數(shù)和加上i后小于等于M71If sum+i=m then begin ansstep+1:=I; i值作為第step項(xiàng) solve(step+1,I,sum+i) 遞歸搜索下一項(xiàng)的值 endEnd;Var i:integer;Begin repeat write(M=); 輸入數(shù)和M read(m); until m in 1.maxm; repeat write(k=); 輸入項(xiàng)數(shù)k read(k); until k in 1.m; total:=

22、0; 拆分?jǐn)?shù)初始化72For i:=1 to m div k do 試選1。M，分別作為第一項(xiàng)的值 begin ans1:=i; solve(1,i,i); i作為第1項(xiàng)的值，遞歸搜索首項(xiàng)為i的所有拆分方案 end; readln;End.End.73求普通母函數(shù)的系數(shù)序列如果已經(jīng)求得普通母函數(shù)，可以通過展開多項(xiàng)式的辦法確定其系數(shù)序列。這個(gè)系數(shù)序列對(duì)研究組合問題有相當(dāng)重要的意義。 下面我們來編寫一個(gè)程序從一個(gè)指定文件中讀入普通母函數(shù)。文件格式為：每行表示一個(gè)多項(xiàng)式，按冪次數(shù)遞增的順序輸入各項(xiàng)。每項(xiàng)系數(shù)在前，指數(shù)在后，各項(xiàng)間以空格隔開，每行最后加00，表示一個(gè)多項(xiàng)式輸入結(jié)束。行間的回車表明多項(xiàng)式

23、之間的連乘關(guān)系。74算法分析 用單鏈表P存儲(chǔ)普通型母函數(shù)的展開式，鏈結(jié)點(diǎn)存儲(chǔ)當(dāng)前項(xiàng)，結(jié)點(diǎn)形式為初始時(shí)，P為75程序清單Program multiplyType link=node; 指針 noderecord 項(xiàng)結(jié)點(diǎn) time: integer; 次冪 a: real; 系數(shù)； next：link 指向下項(xiàng)的指針 end；76Var p,r :link; P存儲(chǔ)以前各多項(xiàng)式的展開式； r加入當(dāng)前多項(xiàng)式后展開的結(jié)果 f: text; 輸入文件Procedure init；文件讀前準(zhǔn)備Var str：string；Begin write(); readln(str); Assign(f,str);

24、 reset(f);End;77Procedure free(p:link); 釋放P鏈Begin if pnil then begin free(p.next); dispose(p); end;End;78Procedure add(time:integer; a:real;r:link);通過合并同類項(xiàng)，將aXtime鏈入r鏈Var t：link；Begin if r.next=nil 若次冪time最大，則aXtime加入r鏈尾 then begin new(r.next); r.next.time:=time; r.next.a:=a; r.next.next:=nil; end;Else if r.next.time=time 將aXtime并入r中次冪為time的項(xiàng) then begin r.next.a:=r.next.a+a; if r.next.a=0 then begin 刪除r中為0的項(xiàng) t:=r.next; r.next:=r.next.next; dispose(t); end; end;Else if (r.next.timetime) and (timer.time) 若time次冪在r的相鄰項(xiàng)之間，則在中間插入aXtime then begin79New(t); t.time:=time; t.a:=a; t.next