算法合集之類比思想在解題中的應(yīng)用-資料下載頁
2025-01-09 19:42本頁面
【正文】 BEGIN FOR i:=k TO Trunc(Sqrt(l)) DO IF l mod i=0 THEN { 如果 i是 l的約數(shù) } P(i,l div i)。 { 把 l/i分解成不小于 i的若干個整數(shù)的積 } inc(total)。 { 若 l不再分解成更小的整數(shù)，則得到一個解 } END。 { 主過程 } 作者：張力 類比思想在解題中的應(yīng)用 第 12 頁 共 13 頁 BEGIN init。 { 初始化 } P(2,n)。 { 把 n分解為不小于 2的若干個整數(shù)的積 } writeln(total1)。 { 輸出解的總數(shù)減一，除去 n=n 的情況 } END. []: PROGRAM p2。 { 因數(shù)分解的母函數(shù)算法的程序 } VAR n : LONGINT。 total : LONGINT。 { 解的總數(shù) } PROCEDURE init。 { 初始化，讀入 n } BEGIN readln(n)。 END。 PROCEDURE work。 { 主過程 } TYPE TForm = array[1..1500] of RECORD { 多項(xiàng)式類型 } s,exp:LONGINT。 { s為系數(shù)， exp為冪指數(shù)上 ln(x)的自變量 x } END。 VAR i : LONGINT。 F1,F2,F3 : TForm。 top1,top2,top3 : INTEGER。 { 對應(yīng)于多項(xiàng)式 F1， F2， F3的長度 } PROCEDURE AddForm(p:LONGINT)。 { 計(jì)算 F1 = F1 * （ 1+xln(p)+x2ln(p)+x3ln(p)+... ） } { 對于多項(xiàng)式 F1 所有項(xiàng) xln（ p） ，只保存滿足 p是 n約數(shù)的項(xiàng) } VAR j,k,l,m:LONGINT。 BEGIN j:=1。 { j = pi } m:=n。 WHILE m mod p=0 DO { 當(dāng) m含有因子 p， j*p是 n的約數(shù)的時候 } BEGIN m:=m div p。 j:=j*p。 { 以下計(jì)算多項(xiàng)式 F1*xln(j)，并把它與 F2歸并（暫存在 F3 中） } l:=1。 top3:=0。 fillchar(F3,sizeof(F3),0)。 FOR k:=1 TO top1 DO IF m mod F1[k].exp=0 THEN { m 含有因子 F1[k].exp，將 F1中的第 k項(xiàng)與 xln(j)的乘積歸并入 F3 } BEGIN WHILE (l=top2) and (F2[l].expF1[k].exp*j) DO { 將 F2 冪指數(shù)小于 ln(j*F1[k].exp)的項(xiàng)先歸并入 F3 } BEGIN inc(top3)。 F3[top3]:=F2[l]。 inc(l)。 END。 inc(top3)。 IF F2[l].exp=F1[k].exp*j THEN { 合并同類項(xiàng) } 作者：張力 類比思想在解題中的應(yīng)用 第 13 頁 共 13 頁 BEGIN F3[top3].exp:=F2[l].exp。 F3[top3].s:=F3[top3].s+F1[k].s。 inc(l)。 END ELSE BEGIN F3[top3].s:=F1[k].s。 F3[top3].exp:=F1[k].exp*j。 END。 END。 WHILE (l=top2) DO { 將 F2 中沒有歸并的部分并入 F3 中 } BEGIN inc(top3)。 F3[top3]:=F2[l]。 inc(l)。 END； F2:=F3。 top2:=top3； { 將歸并的結(jié)果保存到 F2，即 F2=F2 + F1*xln(j) } END。 F1:=F2。 top1:=top2。 { 將多項(xiàng)式乘法的最后的結(jié)果保存到 F1 } END。 BEGIN fillchar(F1,sizeof(F1),0)。 top1:=1。 F1[1].s:=1。 F1[1].exp:=1。 { F1 = 1 } top2:=top1。 F2:=F1。 { F2 = F1 = 1 } FOR i:=2 TO trunc(sqrt(n)) DO IF n mod i=0 THEN { 如果 i是 n的約數(shù) } BEGIN AddForm(i)。 { F1=F1*（ 1+xln(i)+x2ln(i)+x3ln(i)+...+x[ln(n)/ln(i)]） } IF i*in THEN { 如果 i不是 n的平方根， n/i也是 n的約數(shù) } AddForm(n div i)。 { F1 = F1*（ 1+xln(n/i)+x2ln(n/i)+... ） } END。 i:=top1。 WHILE (i0) and (F1[i].expn) DO dec(i)。 { i的 ln(n)次冪的系數(shù)就是解的總數(shù) } IF i=0 THEN total:=0 else total:=F1[i].s。 END。 { 主程序 } BEGIN init。 { 初始化 } work。 { 計(jì)算 } writeln(total)。 { 輸出 } END
試題試卷相關(guān)推薦
鄂ICP備17016276號-1