大數(shù)組合數(shù)學(xué)算法-acm(編輯修改稿)

　

【文章內(nèi)容簡介】 3 殊途同歸方法 ? 從不同的角度討論計數(shù)問題，以建立組合等式 例如，對沒有三條對角線交于一點(diǎn)的凸多邊形，計算各邊及對角線所組成的互不重疊的區(qū)域個數(shù)。 區(qū)域總數(shù)為 C（ n， 4）＋ C（ n－ 1， 2） ? 各區(qū)域頂點(diǎn)總數(shù)（包括重復(fù)計數(shù)） ? 角度 1： ? 角度 2：所有區(qū)域的內(nèi)角和的總和的等式 ? 兩邊同除以 180度得 ? 兩式相減得區(qū)域總數(shù) 4 數(shù)論方法 ? 運(yùn)用奇偶性，整除性等數(shù)論性質(zhì)進(jìn)行存在性問題的分析與推理。 ? 例子：設(shè) n位客人，在晚會上每人與他人握手 d次， d是奇數(shù)，證明 n是偶數(shù)。 回溯方法 ? 需要用計算機(jī)求解的組合試題一般有兩種類型： 1。能夠用簡明正確的組合公式揭示問題。 2。不能對給定問題建立數(shù)學(xué)模型或雖然有數(shù)學(xué)模型但運(yùn)用該數(shù)學(xué)模型求解有困難。在求解枚舉類型問題時，會遇到此類問題。 ? 回溯方法是一種常用的解題策略。 N皇后問題 ? 例子，一個 n n的國際象棋棋盤上放置 n個皇后，使其不能相互攻擊，即任何兩個皇后都不能處在棋盤的同一行同一列同一條斜線上，試問有多少中擺法？ ? 一 如何求 n皇后問題 1 狀態(tài)（ state） 狀態(tài)是指問題求解過程中每一步的狀況。 n皇后問題中，某行皇后所在列位置 i即為該皇后問題的一個狀態(tài)。 ? 2 算符（ operator） 算符是把問題的一個狀態(tài)變換到另一個狀態(tài)的方法代號。 n皇后的一種擺法對應(yīng) n個元素的排列方案（ a1， a2， …,an ） 必須滿足條件 ：不產(chǎn)生對角線攻擊和列攻擊。 3。 結(jié)點(diǎn)（ node） 用以表明某狀態(tài)特征及關(guān)聯(lián)方式的基本信息單元。結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一般為記錄類型。 Type node=record operator : 算符類型； state： 狀態(tài)類型； end。 Var stack： array[1。 maxdepth] of node； {節(jié)點(diǎn)數(shù)不超過 maxdepth的一條路徑 } or Var stack: array[1..20] of integer。 當(dāng) n＝ 4時，初始狀態(tài)：空棋盤， 試放的順序是從左至右，自上而下 （ ） ? 求解 n皇后問題，無非就是做兩件事： ? 1。 從左至右逐條樹枝地構(gòu)造和檢查解答樹 t； ? 2。檢查 t的節(jié)點(diǎn)是否對應(yīng)問題的目標(biāo)狀態(tài)。為了加快檢查速度，一般規(guī)定： ? 1。 在擴(kuò)展一個分支節(jié)點(diǎn)前進(jìn)行檢查，如果它不滿足約束條件，則不再構(gòu)造以它為根節(jié)點(diǎn)的子樹； ? 2。 已處理過的節(jié)點(diǎn)若以后不會再用，則不必保留，即回溯過程中經(jīng)過的節(jié)點(diǎn)不再保留。 棧 — 重要的數(shù)據(jù)結(jié)構(gòu) ? 遞歸過程 make（ L） ? 1 分配一個連續(xù)的數(shù)組區(qū)域stack[1..maxdepth]順序存放棧中表目，即當(dāng)前路徑的節(jié)點(diǎn)。 ? 2 棧頂指針 L作遞歸程序make的值參數(shù)，指出待擴(kuò)展節(jié)點(diǎn)在當(dāng)前路徑序列stack中的順序，算符作make過程的局部變量。 算法框架 ? Program search ? Var ? stack:array[1..maxdepth] of node。 ? …….. ? Procedure make(L:integer)。 ? Var … ? Begin ? make(L+1)。 ? End。 {make} ? Begin ? …… ? make(1)。 ? …… ? End。 作為練習(xí) ? 一個售貨亭前排著 2N個人的隊伍等候購物，假定他們都購買價值 5元的同一貨物。其中 N個人持 5元貨幣， N個人持 10元貨幣，而售貨員開始發(fā)售貨物時沒有零錢。問有多少種排隊方式可使售貨員能依次順利地出售貨物，而不出現(xiàn)找不出錢的局面。 從鴿籠原理到 Ramsey理論 ? 1 鴿籠原理： n＋ 1只鴿子飛回 n鴿籠子至少一個鴿籠含有不少于 2只鴿子。 數(shù)學(xué)描述： m（ m=1）個元素分成 n個組，那么總有一個組至少含有元素個數(shù)為[m/n]。上取整。 例子： 13個人的小組至少有 [13/12]=2人生日在同一個月。 2 Ramsey問題和 Ramsey數(shù) ? 用紅籃兩種顏色去涂 n個頂點(diǎn)完全圖的邊，每邊涂且僅涂一種顏色，得到的圖叫做 2色完全圖，記為 kn Ramsey數(shù) ? 用 表示這樣的正整數(shù)，即當(dāng) ? 時，任何一個 2色完全圖 kn， 或者含有紅色完全圖 kp，或者含有藍(lán)色完全圖 kg，兩者必居其一；而當(dāng) 存在 2色完全圖 kn它不含紅色完全子圖 kp和藍(lán)色完全圖 kg， 這個數(shù)就稱之為 Ramsey數(shù)。 ? 確定 Ramsey數(shù)是很難的問題。到目前為止，主要還是研究 ，精確求得的數(shù)值為數(shù)甚少 ），（ gp? ），（ gpn ??），（ gpn ??），（ gp?另一種表述 ? 一對常數(shù) p和 g對應(yīng)一個常數(shù) n，使得 n個人中或有 p個人互相認(rèn)識，或者有 g個人互相不認(rèn)識，這個 n的最小值用 表示 ? 顯然 ），（ gp?Ramsey數(shù)上界估計公式 ? 下面估計 的上界 ? 可改進(jìn)為： ? 遞歸邊界 ），（ gp?上界估計程序 ? Program ramsey ? uses crt。 ? Const maxn=50。 ? Type ? rtype=array[1..maxn, 1..maxn] of integer。 ? Var r: rtype。 {ramsey數(shù)組 } ? a, b :integer。 {ramsey數(shù)的兩個參數(shù) } ? Procedure init。 {輸入 ramsey數(shù)的兩個參數(shù) } ? Begin ? clrscr。 ? repeat write(‘a(chǎn)=’)。 ? readln(a)。 ? until (a1) and (a=maxn)。 ? repeat write(‘b=’)。 ? readln(b)。 ? until (b1) and (b=maxn)。 ? end。 ? Procedure main ? var I, j :integer。 ? Begin ? for i:=2 to a do r[I,2]:=I。 {建立遞歸邊界 } ? for i:=2 to b do r[2,i]:=I。 ? for i:=3 to a do ? for j:=3