初賽試題分析與解答

1、試題分析與解答一、選擇題 二、問題求解1、 分析：根據(jù)（1）樹的構(gòu)造算法：根據(jù)給定的n 個(gè)權(quán)值W1，W2，Wnn 棵二叉樹的集合 F=T1，T2，Tn，其中每棵二叉樹 Ti 中只有一個(gè)權(quán)值為 Wi 的根結(jié)點(diǎn)，其左右為空。（2）在 F 中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為左右構(gòu)造一棵新的二叉樹，并置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右上根結(jié)點(diǎn)權(quán)值之和。（3）（4）在 F 中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入到F 中。重復(fù)（2）、（3），直到 F 中只有一棵樹為止，則這棵樹便是樹。由題設(shè)中的條件和上述樹的構(gòu)造算法，到本題的二叉樹如下。因此，其最小帶權(quán)路徑長度WPL=4*2+3*3+4*1+7*2+8*

2、2+2*4=59：WPL=592、 分析根據(jù) Kathy 函數(shù)的定義，有：f(1)=1=(1)2f(2)=f(1)=1f(3)=3=(11)2f(4)=f(2)= 1f(5)=2f(3)-f(1)=5=(101)2 f(6)=f(3)= 3f(7)=3f(3)-2f(1)=7=(111)2 f(8)=f(4)=1f(9)=2f(5)-f(2)=9=(1001)2可以從簡單情況分析入手，當(dāng) f(n)=n 時(shí)，將函數(shù)值轉(zhuǎn)化為二進(jìn)制數(shù)，由此，可以猜測，當(dāng) f(n)=n 時(shí)，其函數(shù)值 n 轉(zhuǎn)化為二進(jìn)制后得到的二進(jìn)制串為回文串（從左到右讀和從右到左讀時(shí)兩串為同一個(gè)串），事實(shí)上，利用數(shù)學(xué)方法可以證明，當(dāng)

3、n 轉(zhuǎn)化為二進(jìn)制數(shù)，若得到的二進(jìn)制串為回文串時(shí)，滿足f(n)=n。問題轉(zhuǎn)化為求整數(shù) 1 到 30 之間有多少個(gè)整數(shù)轉(zhuǎn)化成二進(jìn)串后，該二進(jìn)制串為回文串，則有多少個(gè)整數(shù)滿足 f(n)=n。：9三、閱讀程序，寫出程序運(yùn)行結(jié)果。1、 分析：容易看出是用而分發(fā)求 ab mod c。也就是 993294 mod 10=3294 mod 10，而 34 mod 10=1，所以 3294 mod 10=32 mod 10=9。2、分析：a 的變化是 1，2，3，4，5，m，b 的變化是 1，1+2，1+2+3，1+2+m。這里 m 是最小滿足1+2+m=n 的數(shù)。N=215377，即 m(m+1)/2=415

4、377 的最小整數(shù)解。M=911。3、分析：數(shù)組 a 裝的是 kmp 中的 next 數(shù)組。然后根據(jù) next 的定義寫出a 數(shù)組的數(shù)值。：7 11 12 13 14 154、分析：發(fā)現(xiàn) xi的是 i 的最小質(zhì)約數(shù)，如果 i 是質(zhì)數(shù)則 xi=0。wi表示 i* wi。一旦 wi=1 則表示 n!1) 第一個(gè)循環(huán)所有的 xi2) 第二個(gè)循環(huán)把 i 的指數(shù)往 i 的約數(shù)的指數(shù)上加，最后達(dá)到的目的是：如果 i 是合數(shù)，則 wi=0。也就是把所有的合數(shù)都分解了。程序最后輸出的是w2, w3, w5,也就是 2，3，5 的指數(shù)實(shí)際上就是輸出n!中有多少個(gè) 2、3、 5 的因子。計(jì)算機(jī) n!有多少個(gè) 2

5、的因子比較簡單：n/2+n/4+n/8+,同理可以計(jì)算有多少個(gè) 3、5的因子。：1）18 8 42）290 144 71四、完善程序1、 多項(xiàng)式相加算法本題是一道非常簡單的利用一維數(shù)組對(duì)兩個(gè)多項(xiàng)式 A（X）和 B（X）進(jìn)行加法合并的問題。其算法思路是，設(shè)置兩個(gè)指針變量 p，q 分別指向 A（X）和 B（X）的每一項(xiàng)，對(duì)兩個(gè)多項(xiàng)式的每一項(xiàng)指數(shù)進(jìn)行比較，若兩個(gè)項(xiàng)的指數(shù)相等，則將兩項(xiàng)的系數(shù)相加，得到 C（X）的新項(xiàng)，若A（X）中該項(xiàng)的指數(shù)大于 B（X）中的項(xiàng)，則直接將A（X）中的的該項(xiàng)并入到 C（X）中，直到兩個(gè)多項(xiàng)式中的每一項(xiàng)都并入完成為止，若出現(xiàn)某個(gè)多項(xiàng)式已全部并入，而另一多項(xiàng)式還有剩余項(xiàng)沒有并

6、入，則直接將該多項(xiàng)式中的剩余項(xiàng)并入到 C（X）的末尾。過程N(yùn)ewtermr 用于生成一個(gè)新的系數(shù)為 C，指數(shù)為 e 的項(xiàng)，第空和第空用于對(duì) cf ,c1 進(jìn)行賦值， 因此分別填上 cf:=free 和 c1:=free-1, 第空用于判定多項(xiàng)式項(xiàng)數(shù)是否已大于其最大定義項(xiàng)數(shù) (maxterms), 若大于則判定溢出， 第 空進(jìn)行兩個(gè)多項(xiàng)式的系數(shù)相加， 應(yīng)填寫 c:= termsp.coef+ termsq.coef,第空用于移動(dòng) q 指針，應(yīng)填寫 q:=q+1。：freemaxterms cf:=freec:= termsp.coef + termsq.coef q:=q+1c1:=free-1

7、2、獻(xiàn)禮本題是一道統(tǒng)計(jì)題，要求統(tǒng)計(jì)出正三角形中三塊一定大小的全等形的劃分總數(shù)。本題的難度在于圖形為三角形，分割成的全等形是由旋轉(zhuǎn)而成的。這在思維方式上有一定的，所以本題的關(guān)鍵在于克服思維，將轉(zhuǎn)換關(guān)系弄清楚，問題也就基本得到解決了。另外，在編程實(shí)現(xiàn)上也要盡量提高效率。解答本題的第一步是找到旋轉(zhuǎn)后的代數(shù)表達(dá)式，通過觀察可知將當(dāng)前坐標(biāo)為（x，y）的三角形逆時(shí)針旋轉(zhuǎn) 2/3 后得到的新坐標(biāo)為（n+1）-（y+1） div 2，x*2-y），因此題目中的第、空的填寫內(nèi)容就非常清楚，即為當(dāng)前坐標(biāo)為（x,y）的三角形旋轉(zhuǎn) 2/3 后得到的新坐標(biāo)值，為了減少重復(fù)計(jì)算，還應(yīng)得到順時(shí)針旋轉(zhuǎn) 2 /3 后得到的坐標(biāo)

8、， 這里可以通過兩次逆時(shí)針旋轉(zhuǎn)得到， 即 px:=tgnx,ny.nx;py:=tgnx,ny.ny。第空用于確定三角形的相鄰三角形的 y 坐標(biāo)值，根據(jù)倒、立三角形到相鄰圖形的坐標(biāo)矢量常量的定義，y:=j+trij mod 2,k,2,即為第空應(yīng)填寫內(nèi)容。找到轉(zhuǎn)換關(guān)系后，問題可以說已經(jīng)解決了一半，本題要求的是解的總數(shù)，采用搜索方法求解，在枚舉的同時(shí)就進(jìn)行減枝判斷。在解答中，應(yīng)該把每一個(gè)位置及其經(jīng)過順時(shí)針、逆時(shí)針旋轉(zhuǎn)后的位置看為一個(gè)有機(jī)整體，而不應(yīng)只是離散的。一種可行的方法是每枚舉到一個(gè)填寫位置，便將其及經(jīng)過逆時(shí)針、順時(shí)針旋轉(zhuǎn)后的位置標(biāo)記下來，以防止重復(fù)。可以僅標(biāo)記出當(dāng)前路徑上的每個(gè)三角形，而確定三角形是否可以填寫時(shí)只需判斷它或其經(jīng)過旋轉(zhuǎn)后的位置是否已經(jīng)標(biāo)記。如果仔細(xì)看圖便能發(fā)現(xiàn)，標(biāo)語的第二個(gè)字必須填寫在（2，2）格中，而第三個(gè)字則填寫在（2，1）或（2，3）格中。前三個(gè)字的兩種填發(fā)具有軸對(duì)稱的特點(diǎn)，而以下的填寫是圍繞此展開的，因此也相應(yīng)地具有對(duì)稱性，對(duì)于左右相鄰對(duì)稱的兩個(gè)三角形只取其一以減少重復(fù)搜索，所以在枚舉過程中可以減少一半的重復(fù)搜索，故