大數(shù)組合數(shù)學(xué)算法-acm-資料下載頁(yè)
2025-07-23 20:45本頁(yè)面
【正文】 e(‘k=’)。 {輸入項(xiàng)數(shù) k} ? read(k)。 ? until k in [1..m]。 ? total:=0。 {拆分?jǐn)?shù)初始化 } ? For i:=1 to m div k do {試選 1。 M，分別作為第一項(xiàng)的值 } ? begin ? ans[1]:=i。 ? solve(1,i,i)。 {i作為第 1項(xiàng)的值，遞歸搜索首項(xiàng)為 i的所有拆分方案 } ? end。 ? readln。 ? End. ? End. 求普通母函數(shù)的系數(shù)序列 ? 如果已經(jīng)求得普通母函數(shù)，可以通過(guò)展開(kāi)多項(xiàng)式的辦法確定其系數(shù)序列。這個(gè)系數(shù)序列對(duì)研究組合問(wèn)題有相當(dāng)重要的意義。 ? 下面我們來(lái)編寫(xiě)一個(gè)程序從一個(gè)指定文件中讀入普通母函數(shù)。文件格式為：每行表示一個(gè)多項(xiàng)式，按冪次數(shù)遞增的順序輸入各項(xiàng)。每項(xiàng)系數(shù)在前，指數(shù)在后，各項(xiàng)間以空格隔開(kāi)，每行最后加00，表示一個(gè)多項(xiàng)式輸入結(jié)束。行間的回車(chē)表明多項(xiàng)式之間的連乘關(guān)系。 算法分析 ? 用－單鏈表 P存儲(chǔ)普通型母函數(shù)的展開(kāi)式，鏈結(jié)點(diǎn)存儲(chǔ)當(dāng)前項(xiàng)，結(jié)點(diǎn)形式為 ? 初始時(shí)， P為 程序清單 ? Program multiply ? Type ? link=^node。 {指針 } ? node＝ record {項(xiàng)結(jié)點(diǎn) } ? time: integer。 {次冪 } ? a: real。 {系數(shù) }； ? next： link {指向下項(xiàng)的指針 } ? end； ? Var ? p,r :link。 {P－－存儲(chǔ)以前各多項(xiàng)式的展開(kāi)式； r－－加入當(dāng)前多項(xiàng)式后展開(kāi)的結(jié)果 } ? f: text。 {輸入文件 } ? Procedure init； {文件讀前準(zhǔn)備 } ? Var str： string； ? Begin ? write(‘File Name=’)。 ? readln(str)。 ? Assign(f,str)。 ? reset(f)。 ? End。 ? Procedure free(p:link)。 {釋放 P鏈 } ? Begin ? if pnil then begin ? free(p^.next)。 ? dispose(p)。 ? end。 ? End。 ? Procedure add(time:integer。 a:real。r:link)。 ? {通過(guò)合并同類(lèi)項(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 begin ? New(t)。 ? t^.time:=time。 ? t^.a:=a。 ? t^.next:=r^.next。 ? r^.next:=t。 ? End。 ? Else add(time, a, r^.next) {往下遞歸合并 } ? End。 ? Procedure proceed。 {計(jì)算若干多項(xiàng)式之積 } ? Var ? time ： integer； ? a： real； ? t： link； ? Begin ? new（ p）； ? new（ p^.next） 。{中間 p鏈初始化 } ? p^.next^.time:=0。 p^.:=1。 ? p^.next^.next:=nil。 ? read(f,a,time)。 {讀入第 1個(gè)多項(xiàng)式的首項(xiàng) } ? while not eof(f) do ? begin ? new(r)。 r^.next:=nil。 {展開(kāi)式初始化 } ? repeat {aXtime乘以 p鏈上的各項(xiàng)，并合并同類(lèi)項(xiàng)，結(jié)果存入 r鏈 } ? if a0 then begin ? t:=p^.next。 ? while tnil do begin ? add(time+t^.time, a*t^.a, r)。 ? t:=t^.next。 ? end。 ? end。 ? read(f,a,time) {讀入當(dāng)前多項(xiàng)式的下一項(xiàng) } ? until (a=0) or eof(f)。 ? Read(f,a,time)。 {再讀下一項(xiàng) } ? if not eof（ f） {若當(dāng)前項(xiàng)不是最后一項(xiàng)，則將當(dāng)前展開(kāi)的結(jié)果轉(zhuǎn)賦給 p，釋放以前各多項(xiàng)式的展開(kāi)式 } ? then begin ? t:=p； p:=r。 free(t)。 ? end。 ? End。 ? End。 ? Procedure print(r:link)。 {打印結(jié)果 } ? Begin ? if rnil then begin ? write(‘a(chǎn)’,r^.time, ‘_’,r^.a:3:0,’ ‘)。 ? print(r^.next)。 ? end。 ? End。 ? Begin ? init。 {文件讀前準(zhǔn)備 } ? proceed。 {展開(kāi)多項(xiàng)式 } ? print（ r^.next） 。 {打印展開(kāi)式各項(xiàng)系數(shù) } ? writeln； ? End。 結(jié)束語(yǔ) ? 組合數(shù)學(xué)中的算法很多，有一定的難度 ? 希望大家在掌握組合數(shù)學(xué)基本概念和基本原理的基礎(chǔ)上，適當(dāng)作一些中等難度的題目。
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1