【正文】 0]==0) //高位不能為 0，保證素?cái)?shù)達(dá)到要求的長度 ? p[200]=rand()*10/RAND_MAX。 ? return 0。 ? } 乘法運(yùn)算 ? int multiply(int m[101],int n[201],int product[301])//兩因子 m 、 n，乘積 product ? { int sum1[102],sum2[102],i,j,k,s。 // sum2 、 sum1中間過渡量 ? for (i=1。 i=101。i++){sum2[i]=0。}// sum2所有位置零 ? for (j=1。j201。j++)//在 n的每一位上處理 m ? { for(i=1。i=101。i++)sum1[i]=0。 //sum1所有位置零 ? for (i=1。i=n[j]。i++)//通過每一層循環(huán)，實(shí)現(xiàn)乘法的加法化 ? { for (s=1。s101。s++) ? sum2[s]=m[s]+sum1[s]。 ? for (k=1。k=101。 k++) ? sum1[k]=sum2[k]。 ? } ? for (k=j。k=100+j。k++) ? product[k]=sum2[kj+1]+product[k]。//即是實(shí)現(xiàn)了乘法過程中的加法 ? } ? for (i=1。i301。i++)//進(jìn)位處理 ? {j=product[i]/10。 ? product[i+1]+=j。 ? product[i]=j*10。 ? } ? return 0。 ? } 比較兩個(gè)數(shù)的大小 ? int cmp(int a[301], int ab, int b[201], int bb) //比較兩個(gè)數(shù)的大小 ? { int i, result。 ? result = 0。 // a == b。 ? for(i = 300。 i ab。 i) ? if(a[i] != 0) return 1。 ? for(i = 0。 i bb。 i++) ? { if(a[ab i] b[bb i]) ? { result = 1。 // a b。 ? break。 ? } ? if(a[ab i] b[bb i]) ? { result = 1。 // a b。 ? break。 ? } ? } ? return result。 ? } 除法運(yùn)算 ? void division(int a[301], int b[201], int c[301], int d[201]) ? //除法函數(shù)， 300位除 200位 ,c為商， d為余數(shù) ? { ? int al, bl, t[301]。 // al用來標(biāo)識(shí) a的長度 , bl用來標(biāo)識(shí) b的長度 ? int i, j, al2。 ? for(i = 0。 i 301。 i++) ? { c[i] = 0。//商置零 ? if(i 202) d[i] = 0。//余數(shù)置零 ? t[i] = a[i]。 ? } ? for(i = 300。 i 0。 i)//測(cè)算 a的長度 ? if(a[i] != 0) ? { al = i。 ? break。 ? } ? for(i = 200。 i 0。 i)//測(cè)算 b的長度 ? if(b[i] != 0) ? { bl = i。 ? break。 ? } 除法運(yùn)算（續(xù)） ? 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++) ? t[al2 j] = b[bl j]。//對(duì)位做減法 ? for(j = 1。 j 301。 j++) ? if(t[j] 0)//完成借位 ? { t[j] += 10。 ? t[j + 1]。 ? } ? c[al bl + 1 i]++。//高位開始逐位計(jì)算商 ? } ? al2。 ? } ? for(i = 0。 i 201。 i++) d[i] = t[i]。//產(chǎn)生余數(shù) ? } 組合數(shù)學(xué)研究對(duì)象 ? 組合數(shù)學(xué)研究的主要內(nèi)容是依據(jù)一定的規(guī)則來安排某些事務(wù)的有關(guān)數(shù)學(xué)問題。這些問題包括四個(gè)方面： 1。 這種安排是否存在，即存在性問題； 2。如果符合要求的安排是存在的，那么這樣的安排又有多少，即計(jì)數(shù)問題； 3。怎樣構(gòu)造這種安排，即算法構(gòu)造問題； 4。如果給出了最優(yōu)化標(biāo)準(zhǔn)，又怎樣得到得到最優(yōu)安排。 1。存在性問題 ? 實(shí)際生活中的各種問題，有些可以當(dāng)機(jī)立斷判定其有解還是無解。但也有不少問題一時(shí)難以判定。 ? 例如，宴會(huì)上，奇數(shù)位客人能否在晚會(huì)上與他人握手奇數(shù)次。 ? 競(jìng)賽時(shí)不可能出現(xiàn)專門判定某個(gè)問題有解或無解的試題。但往往會(huì)在測(cè)試數(shù)據(jù)中加入無解的數(shù)據(jù)。 2。 計(jì)數(shù)問題 ? 如果一個(gè)組合問題的解是存在的，自然會(huì)問有多少不同的解。 ? 例如，將 8個(gè)“車”放在 8 8的國際象棋棋盤上，如果他們兩兩不能互吃，那么稱 8個(gè)“車”處于一個(gè)安全狀態(tài)。顯然這種安全狀態(tài)是存在的。問有多少種不同的安全狀態(tài)。 這就是一個(gè)計(jì)數(shù)問題。 信息學(xué)競(jìng)賽中一般分為兩種類型：一種是計(jì)算某種特性的對(duì)象有多少；另一種是枚舉類型，把所有具有某種特性的對(duì)象都列舉出來。 3。 構(gòu)造性算法 ? 一個(gè)組合問題，已經(jīng)判定解是存在的，甚至已經(jīng)推知有多少解，但關(guān)鍵還在于把解構(gòu)造出來，有的哪怕出一個(gè)解也好。如魔方問題，正交拉丁問題。 4。 優(yōu)化問題 ? 一個(gè)問題的構(gòu)造性算法可能不止一種，自然面臨如何擇優(yōu)，如何改進(jìn)，使得答案盡快地解出來。比如動(dòng)態(tài)規(guī)劃和線性規(guī)劃問題的解決方法。 組合問題的基本解題方法 ? 1 從組合學(xué)基本概念基本原理出發(fā)的常規(guī)方法 容斥原理 Polya原理 鴿籠原理 遞歸方法 生成函數(shù)方法 ? 2 通常與問題所涉及的組合數(shù)學(xué)概念無關(guān)的非常規(guī)方法。主要用于解那些需要獨(dú)立思考見解獨(dú)到和有所創(chuàng)新的問題。 ? 數(shù)學(xué)歸納法 證明 n個(gè)元素的集合，其子集恰為 2n個(gè) ? 一一對(duì)應(yīng)技術(shù) 將一個(gè)問題轉(zhuǎn)化為另一種有常規(guī)算法的問題模式。例如， 8“車”問題有多少個(gè)不同的安全狀態(tài)。 8個(gè)車處于安全狀態(tài)當(dāng)且僅當(dāng)它們處于不同的 8行和8列上。用一個(gè)排列 a1， a2， … ， a8，對(duì)應(yīng)于一個(gè)安全狀態(tài)，使 ai表示第 i行的 ai列上放置一個(gè)車。這種對(duì)應(yīng)顯然是一對(duì)一的。因此，安全狀態(tài)的總數(shù)等于這 8個(gè)數(shù)的全排列的總數(shù) 8！ =40320。 ?