南京市小學(xué)生信息學(xué)競(jìng)賽初賽復(fù)習(xí) 知識(shí)要點(diǎn)

1、2015南京市小學(xué)生信息學(xué)競(jìng)賽初賽復(fù)習(xí)知識(shí)要點(diǎn)、典型題（版本）一、知識(shí)要點(diǎn)1. 二分查找；2. 循環(huán)數(shù)組；3. 排序、新型排序；4. 字符串：分離單詞從文件中讀入；5. 進(jìn)制窮舉；窮舉的優(yōu)化（丑數(shù)）；6. 生成法求全排列；7. 組合取數(shù)；8. 遞推迭代深入題目；9. 圖形打??；10. 高精度計(jì)算；11. 數(shù)學(xué)類問(wèn)題；數(shù)論問(wèn)題；C（M，N）；12. 回溯；13. 貪心；14. 表達(dá)式計(jì)算；15. 文件操作；二、一些典型題目、經(jīng)典算法（及源程序）1. 排序、查找、二分（1）冒泡排序（已做，需練習(xí)）【程序清單】DIM AS INTEGER NINPUT NDIM AS INTEGER A(N), I

2、, FFOR I = 1 TO NINPUT A(I)NEXT IJ = 1DO F = 0 FOR I = 1 TO N - J IF A(I) > A(I+1) THEN SWAP A(I), A(I+1) F = 1 END IF NEXT I J = J + 1LOOP UNTIL F = 0FOR I = 1 TO N PRINT A(I);NEXT ISLEEP : END（2）二分查找（已做）【程序清單】dim as integer ninput ndim as integer a(n), i, j, x, mfor i = 1 to n input a(i)next if

3、or i = 1 to n-1 for j = i+1 to n if a(i) > a(j) then swap a(i), a(j) next jnext ifor i = 1 to n print a(i); " "next iprintL = 1 : r = ninput "x= ", xdo while L <= Rm = (L+R) 2 if x = a(m) then print "found" sleep : end end ifif x < a(m) thenR = m - 1elseL = m +

4、 1end ifloopprint "Not found!"sleep : end（3）帶二分查找的插入排序（已做，需練習(xí)）【程序清單】DIM AS INTEGER ninput nDIM AS INTEGER a(n), tail, L, R, minput a(1)for i = 2 to n input xL = 1 : R = i-1 : m = (L+R) 2Do while x <> a( m ) and (L <= R) if x > a(m) then L = m + 1elseR = m 1 end ifm = (L+R) 2 lo

5、opif x <> a(m) then for j = i-1 to L step -1 a(j+1) = a(j) next j a(L) = xelsefor j = i-1 to m step -1 a(j+1) = a(j) next j a(m) = xend ifnext iFOR i = 1 TO n PRINT a(i);NEXT iPRINTSLEEP : END2. 報(bào)數(shù)問(wèn)題、循環(huán)數(shù)組（1）夏令營(yíng)旗手（JS2010，第一題）（已做）【問(wèn)題描述】2010年江蘇省“信息與未來(lái)”小學(xué)生夏令營(yíng)將在常州市局前街小學(xué)進(jìn)行，該校的何老師得知本校營(yíng)員小明同學(xué)被營(yíng)委會(huì)選為夏令營(yíng)的

6、小旗手，就準(zhǔn)備到他家去通知他。由于他不是本班的學(xué)生，所以何老師不知道小明家住在什么地方，只從其他同學(xué)那里得知，小明住在未來(lái)小區(qū)一幢不超過(guò)100層的高樓中，但在哪一層不清楚。其他同學(xué)提供了三條有用的信息：1）小明家的樓層號(hào)是一個(gè)素?cái)?shù)；2）該樓層號(hào)化為二進(jìn)制數(shù)后，其中1的個(gè)數(shù)是偶數(shù)；3）滿足以上兩個(gè)條件中，樓層號(hào)最大的一個(gè)。請(qǐng)你寫一個(gè)程序，計(jì)算并輸出滿足條件（1、2）的樓層個(gè)數(shù)總數(shù)及小明家的樓層號(hào)?！据斎搿勘绢}無(wú)輸入。【輸出】?jī)蓚€(gè)整數(shù)，即樓層個(gè)數(shù)總數(shù)和小明家的樓層號(hào)。（2）狐貍找兔子(hide.bas)（已做）【問(wèn)題描述】圍繞著山頂有10個(gè)洞，一只兔子和一只狐貍各住一個(gè)洞，狐貍總想吃掉兔子。一天，

7、兔子對(duì)狐貍說(shuō)：你想吃我有一個(gè)條件，就是第一次隔一個(gè)洞找我，第二次隔兩個(gè)洞找我，以后依此類推，次數(shù)不限。若能找到我，你就可以飽餐一頓，在沒(méi)有找到我之前不能停止。狐貍一想只有10個(gè)洞，尋找的次數(shù)又不限，哪有找不到的道理，就答應(yīng)了條件。結(jié)果就是沒(méi)找著?，F(xiàn)請(qǐng)你編寫一個(gè)程序，假定狐貍找了1000次，兔子躲在哪個(gè)洞里才安全。（3）循環(huán)報(bào)數(shù)()（已做，需練習(xí)）【問(wèn)題描述】 現(xiàn)有N個(gè)人圍成一圈（N為輸入的數(shù)據(jù)），按1M的間隔報(bào)數(shù)（M也是一個(gè)輸入的數(shù)據(jù)）。根據(jù)報(bào)數(shù)的結(jié)果發(fā)現(xiàn)，第一個(gè)出列的人是1號(hào)，第二個(gè)出列的人是2號(hào)，第三個(gè)出列的人是3號(hào)，最后一個(gè)出列的人是N號(hào)。問(wèn)原來(lái)這N個(gè)人的排列位置是怎樣的？【輸入】 兩個(gè)

8、整數(shù)N和M，表示人數(shù)和報(bào)數(shù)的間隔?！据敵觥恳恍泄睳個(gè)數(shù)，即這N個(gè)人原來(lái)的排列順序。（4）環(huán)繞數(shù)(round.bas)（已做，需練習(xí)）【問(wèn)題描述】一個(gè)環(huán)繞數(shù)有如下三個(gè)特點(diǎn)：a) 每個(gè)數(shù)字指示了它下一個(gè)數(shù)字的位置（自左向右數(shù)，數(shù)到末尾后，再繞到最左位往右數(shù)）；b) 組成這個(gè)環(huán)繞數(shù)的數(shù)字只輪到一次；c) 當(dāng)所有數(shù)字都輪過(guò)一次后，正好回到第一次開(kāi)始所取到的那個(gè)數(shù)字。例如，3162就是一個(gè)環(huán)繞數(shù)：l 取該數(shù)任一數(shù)字作為開(kāi)始，如取1；l 由此數(shù)字開(kāi)始向右數(shù)1位，輪到了數(shù)字6；l 由6向右數(shù)，數(shù)到2時(shí)繞回到3，再向左數(shù)共數(shù)6位，就輪到了數(shù)字3；l 由3向右數(shù)3位，便輪到了數(shù)字2；l 由2繞回到3再向右數(shù)，共

9、數(shù)2位，于是回到1。【任務(wù)】求以3開(kāi)頭的四位數(shù)中，共有幾個(gè)環(huán)繞數(shù)，分別為多少？（5）2N個(gè)好人與壞人問(wèn)題（已做，需練習(xí)）【問(wèn)題描述】有N個(gè)好人與N個(gè)壞人首尾相接地站成一圈（N為輸入的一個(gè)整數(shù)，且前N個(gè)人為好人，后N個(gè)人為壞人），按照?qǐng)?bào)數(shù)間隔M進(jìn)行1到M地循環(huán)報(bào)數(shù)（即每報(bào)到M的人就出列），但M未知。你的任務(wù)是求出一個(gè)最小的報(bào)數(shù)間隔M，使得最先報(bào)出的N個(gè)人都是壞人。【輸出】 一個(gè)整數(shù)，表示N?！据敵觥?一個(gè)整數(shù)，即所求出的報(bào)數(shù)間隔M?！据斎霕永?3【輸出樣例】 53. 排序、新型排序、復(fù)雜排序（已做，需練習(xí)）（1）命名那個(gè)數(shù)字（ namenum.bas ）【問(wèn)題描述】在威斯康辛州牛大農(nóng)場(chǎng)經(jīng)營(yíng)者之

10、中，都習(xí)慣于請(qǐng)會(huì)計(jì)部門用連續(xù)數(shù)字給母牛打上烙印。但是，母牛用手機(jī)時(shí)并沒(méi)感到這個(gè)系統(tǒng)的便利,它們更喜歡用它們喜歡的名字來(lái)呼叫它們的同伴，而不是用像這個(gè)的語(yǔ)句“C'mon, #4734, get along”。請(qǐng)寫一個(gè)程序來(lái)幫助可憐的牧牛工將一只母牛的烙印編號(hào)翻譯成一個(gè)可能的名字。因?yàn)槟概儸F(xiàn)在都有手機(jī)了，使用那標(biāo)準(zhǔn)的按鍵的排布來(lái)把收到從數(shù)目翻譯到文字（除了“Q”和“Z”而外）：2: A,B,C 5: J,K,L 8: T,U,V 3: D,E,F 6: M,N,O 9: W,X,Y 4: G,H,I 7: P,R,S可接受的名字都被放在這樣一個(gè)叫作"dict.txt"

11、的文件中，它包含一連串的少于 5000個(gè)可接受的牛名字（所有的名字都是大寫的）。收到母牛的編號(hào)返回那些能從編號(hào)翻譯出來(lái)并且在字典中的名字。舉例來(lái)說(shuō)，編號(hào) 4734 能產(chǎn)生的下列各項(xiàng)名字：GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDIGREG GREH GREI GRFG GRFH GRFI GSDG GSDH GSDI GSEG GSEH GSEIGSFG GSFH GSFI HPDG HPDH HPDI HPEG HPEH HPEI HPFG HPFH HPFIHRDG HRDH HRDI HREG HREH HREI

12、HRFG HRFH HRFI HSDG HSDH HSDIHSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH IPEIIPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH IRFIISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH ISFI碰巧，81個(gè)中只有一個(gè)“GREG”是有效的（在字典中）?，F(xiàn)在，請(qǐng)你寫一個(gè)程序來(lái)對(duì)給出的編號(hào)打印出所有的有效名字，如果沒(méi)有則輸出“NONE”。編號(hào)可能有12位數(shù)字?！据斎搿浚?)單獨(dú)的一行包含一個(gè)編號(hào)（長(zhǎng)度可能從1到12

13、）。【輸出】（ ）以字典順序輸出一個(gè)有效名字的不負(fù)列表，一行一個(gè)名字。【樣例輸入】4734【樣例輸出】GREG（2）分?jǐn)?shù)線劃定(score.bas)（已做，需練習(xí)）【問(wèn)題描述】世博會(huì)志愿者的選拔工作正在 A 市如火如荼地進(jìn)行。為了選拔最合適的人才，A 市對(duì)所有報(bào)名的選手進(jìn)行了筆試，筆試分?jǐn)?shù)達(dá)到面試分?jǐn)?shù)線的選手方可進(jìn)入面試。面試分?jǐn)?shù)線根據(jù)計(jì)劃錄取人數(shù)的150%劃定，即如果計(jì)劃錄取m名志愿者，則面試分?jǐn)?shù)線為排名第m*150%（向下取整）名的選手的分?jǐn)?shù)，而最終進(jìn)入面試的選手為筆試成績(jī)不低于面試分?jǐn)?shù)線的所有選手?，F(xiàn)在就請(qǐng)你編寫程序劃定面試分?jǐn)?shù)線，并輸出所有進(jìn)入面試的選手的報(bào)名號(hào)和筆試成績(jī)?！据斎搿枯斎?/p>

14、文件名為 score.in。第一行，兩個(gè)整數(shù)n，m（5 n5000，3 mn），中間用一個(gè)空格隔開(kāi)，其中n 表示報(bào)名參加筆試的選手總數(shù)，m 表示計(jì)劃錄取的志愿者人數(shù)。輸入數(shù)據(jù)保證m*150%向下取整后小于等于n。第二行到第 n+1 行，每行包括兩個(gè)整數(shù)，中間用一個(gè)空格隔開(kāi)，分別是選手的報(bào)名號(hào)k（1000k9999）和該選手的筆試成績(jī)s（1s100）。數(shù)據(jù)保證選手的報(bào)名號(hào)各不相同?！据敵觥枯敵鑫募?score.out。第一行，有兩個(gè)整數(shù)，用一個(gè)空格隔開(kāi)，第一個(gè)整數(shù)表示面試分?jǐn)?shù)線；第二個(gè)整數(shù)為進(jìn)入面試的選手的實(shí)際人數(shù)。從第二行開(kāi)始，每行包含兩個(gè)整數(shù)，中間用一個(gè)空格隔開(kāi)，分別表示進(jìn)入面試的選手的報(bào)名

15、號(hào)和筆試成績(jī)，按照筆試成績(jī)從高到低輸出，如果成績(jī)相同，則按報(bào)名號(hào)由小到大的順序輸出。【輸入輸出樣例】6 31000 903239 882390 957231 841005 951001 8888 51005 952390 951000 901001 883239 88【樣例說(shuō)明】m*150% = 3*150% = 4.5，向下取整后為4。保證4 個(gè)人進(jìn)入面試的分?jǐn)?shù)線為88，但因?yàn)?8有重分，所以所有成績(jī)大于等于88 的選手都可以進(jìn)入面試，故最終有5 個(gè)人進(jìn)入面試。（3）三值排序（）（已做，需練習(xí)）【問(wèn)題描述】同學(xué)們已經(jīng)學(xué)過(guò)若干種排序方法，也解過(guò)不少有關(guān)排序的問(wèn)題?，F(xiàn)在，我們來(lái)看一種三值排序問(wèn)題

16、，即給你一個(gè)數(shù)字序列，該序列中只有三種不同的值。這種序列在我們?nèi)粘Ｉ钪幸材芤?jiàn)到，例如，當(dāng)我們給某項(xiàng)競(jìng)賽的優(yōu)勝者按金銀銅牌排序的時(shí)候，就會(huì)出現(xiàn)這樣的序列。在我們這個(gè)任務(wù)中，可能的值只有三種：1，2和3。我們用交換的方法，把它們排成升序序列。現(xiàn)在，請(qǐng)你寫一個(gè)程序，計(jì)算出當(dāng)給定一個(gè)長(zhǎng)度為N的、由1、2、3組成的數(shù)字序列后，將該序列排成升序所需要的最少交換次數(shù)?！据斎搿挎I盤輸入：第一行是一個(gè)整數(shù)，表示N（1<=N<=1000）；接下來(lái)的第二行到N+1行，每行輸入一個(gè)1到3之間的整數(shù)?！据敵觥科聊惠敵鲆粋€(gè)數(shù)字，表示排成升序所需要的最少交換次數(shù)?！緲永斎搿?221333231【樣例輸出】4

17、4. 字符串（已做，需練習(xí)）（1）分離單詞要求從文件中讀入英文句子或段落，再分離單詞。5. 數(shù)位分離、進(jìn)制轉(zhuǎn)換（已做，需練習(xí)）（1）將二進(jìn)制數(shù)化為十進(jìn)制數(shù)，包含小數(shù)。（2）將十進(jìn)制數(shù)化為二進(jìn)制數(shù)，包含小數(shù)。（3）如果一個(gè)十進(jìn)制數(shù)是回文數(shù)，把它轉(zhuǎn)換成二進(jìn)制數(shù)后仍為回文數(shù)，這個(gè)數(shù)稱為絕對(duì)回文數(shù)。找出11，500以內(nèi)的絕對(duì)回文數(shù)。（4）求最大公約數(shù)與最小公倍數(shù)（已做）【問(wèn)題描述】輸入二個(gè)二進(jìn)制整數(shù)（長(zhǎng)度不超過(guò)20位），求出其最大公約數(shù)與最小公倍數(shù)，并用二進(jìn)制數(shù)輸出。例如：輸入：11，100輸出：1 1100【輸入】?jī)蓚€(gè)二進(jìn)制數(shù)。【輸出】用二進(jìn)制數(shù)表示的最大公約數(shù)與最小公倍數(shù)（4）進(jìn)制數(shù)（已做）【問(wèn)題

18、描述】給出一個(gè)正整數(shù)N（1=N=1023），將其化為10位二進(jìn)制數(shù)，然后計(jì)算出二進(jìn)制數(shù)中的“1”的個(gè)數(shù)，若1的個(gè)數(shù)為奇數(shù)，則在最高位前加一個(gè)1，否則加一個(gè)0，最后將在此基礎(chǔ)上形成一個(gè)11位二進(jìn)制數(shù)，用3個(gè)十六進(jìn)制數(shù)輸出。例如：輸入23，化為二進(jìn)制數(shù)為：0000010111，因?yàn)?的個(gè)數(shù)為4，在最高位前加0，得到00000010111。輸出：0H，1H，7H【輸入格式】鍵盤輸入。一個(gè)正整數(shù)N?！据敵龈袷健扛鶕?jù)形成的11位二進(jìn)制數(shù)，用3個(gè)十六進(jìn)制數(shù)輸出。【樣例】輸入：453輸出：5H，CH，5H（5）數(shù)列（）（已做）【問(wèn)題描述】給定一個(gè)正整數(shù)k(3k15),把所有k的方冪及所有有限個(gè)互不相等的k的

19、方冪之和構(gòu)成一個(gè)遞增的序列，例如，當(dāng)k=3時(shí)，這個(gè)序列是：1，3，4，9，10，12，13，（該序列實(shí)際上就是：30，31，30+31，32，30+32，31+32，30+31+32，）請(qǐng)你求出這個(gè)序列的第N項(xiàng)的值（用10進(jìn)制數(shù)表示）。例如，對(duì)于k=3，N=100，正確答案應(yīng)該是981?！据斎胛募枯斎胛募equence.in 只有1行，為兩個(gè)正整數(shù)k和N（k、N的含義與上述的問(wèn)題描述一致，且3k15，10N1000）?！据敵鑫募枯敵鑫募equence.out 為計(jì)算結(jié)果，是一個(gè)正整數(shù)（在所有的測(cè)試數(shù)據(jù)中，結(jié)果均不超過(guò)2.1*109）。（整數(shù)前不要有空格和其他符號(hào)）。【輸入樣例】 3,1

20、00【輸出樣例】981（6）海明碼（hamming.bas）【問(wèn)題描述】給出 N，B 和 D：找出 N 個(gè)編碼（1 <= N <= 64），每個(gè)編碼有 B 位（1 <= B <= 8），使得兩兩編碼之間至少有 D 個(gè)單位的“海明距離”（1 <= D <= 7）?！昂Ｃ骶嚯x”是指對(duì)于兩個(gè)編碼，他們的二進(jìn)制表示法中的不同二進(jìn)制位的數(shù)目?？聪旅娴膬蓚€(gè)編碼 0x554 和 0x234 之間的區(qū)別（0x554 表示一個(gè)十六進(jìn)制數(shù)，每個(gè)位上分別是 5，5，4）： 0x554 = 0101 0101 0100 0x234 = 0010 0011 0100 不同的二進(jìn)制位:

21、 xxx xx因?yàn)橛形鍌€(gè)位不同，所以“海明距離”是 5。【輸入】輸入文件名為，文件中只有一行，包括 N, B, D?！据敵觥枯敵鑫募麨?，其中共有N 個(gè)編碼（用十進(jìn)制表示），要排序，十個(gè)一行。如果有多解，你的程序要輸出這樣的解：假如把它化為 2B 進(jìn)制的數(shù)，它的值要最小。【樣例輸入】16,7,3【樣例輸出】0 7 25 30 42 45 51 52 75 7682 85 97 102 120 1276. 進(jìn)制窮舉、復(fù)雜窮舉、窮舉的優(yōu)化（1）丑數(shù)(humble.bas)（已做，需練習(xí)）（）【問(wèn)題描述】對(duì)于一個(gè)給定的素?cái)?shù)集合 S = p1, p2, ., pK（也就是說(shuō)，p1、p2、pk都是給定的

22、素?cái)?shù)），考慮那些質(zhì)因數(shù)全部屬于S 的數(shù)的集合這個(gè)集合中的數(shù)包括：p1, p1*p2, p1*p1, p1*p2*p3,。稱由這些數(shù)構(gòu)成的集合為相應(yīng)S的丑數(shù)集合。注意：規(guī)定 1 不是丑數(shù)。你的任務(wù)是對(duì)于輸入的集合S，去尋找丑數(shù)集合中第N個(gè)丑數(shù)。【輸入】(humble.in)第1行：兩個(gè)由空格隔開(kāi)的整數(shù)K 和 N，此處1<= K<=100，1<=N<=100,000；第 2 行：K個(gè)由空格隔開(kāi)的整數(shù)，它們都是集合S的元素?！据敵觥?humble.out)一行，輸出第N個(gè)丑數(shù)?！据斎霕永? 192 3 5 7【輸出樣例】277. 生成法求全排列（已做，需練習(xí)）【程序清單】D

23、IM AS INTEGER N, I, SINPUT NDIM AS INTEGER A(n)FOR I=1 TO N A(i)=INEXT IDO S=S+1 FOR I=1 TO NPRINT A(i); NEXT I PRINT FOR I=N TO 2 STEP -1 IF A(i-1)<A(i) THEN M=I-1:EXIT FOR NEXT I IF I=1 THEN EXIT DOI=N DO IF A(i)>A(m) THEN SWAP A(i),A(m):EXIT DO I=I-1LOOPI=M+1J=N DO SWAP A(i),A(j)I=I+1 J=J-1

24、 LOOP UNTIL I>=JLOOPPRINT SSLEEP : END8. 組合取數(shù)（已做，需練習(xí)）【程序清單】DIM AS INTEGER N, R, S, I, JINPUT N，RDim AS INTEGER b(r)S = 0FOR I = 0 TO R 產(chǎn)生初始的、也是第一種排列 B（I）=INEXT IDO WHILE B(0)=0S=S+1FOR I = 1 TO R 打印當(dāng)前這一組組合的排列情況PRINT B（I）；“ ”；NEXT IPRINTJ=RDO WHILE B(J)=NR+ J 若允許R=N，則要改一下條件，否則會(huì)出現(xiàn)問(wèn)題J=J-1LOOPB（J）=B（

25、J）+1FOR I = J+1 TO R B（I）=B（I-1）+1NEXT ILOOPPRINT “S=”；SSLEEP : END9. 遞推迭代深入（1）求數(shù)組元素（已做）已知給出任意一個(gè)自然數(shù)(N<=100)，輸出滿足下列條件的數(shù)組元素及不同方案數(shù)，條件是：1) 數(shù)組元素由各不相同的自然數(shù)組成；2) 最后一個(gè)元素必為N；3) 每一個(gè)元素都不小于它前面一個(gè)元素的平方（第一個(gè)元素除外）；4) 數(shù)組中包含的元素個(gè)數(shù)可以不相同，但至少要有一個(gè)元素；例如：輸入：N=1輸出：數(shù)組: (1)K=1 用K記錄不同的方案數(shù)又如： N=5數(shù)組： (5)，(1，2，5)，(1，5)， (2,5) K=4

26、（2）回文數(shù)列（已做，需練習(xí)）【問(wèn)題描述】對(duì)一個(gè)正整數(shù)K，求出K的所有拆分，并統(tǒng)計(jì)輸出其中回文數(shù)列的個(gè)數(shù)。所謂回文數(shù)列是指該數(shù)列中的所有數(shù)字，從左向右或從右向左看都相同。例如，K=4時(shí)，有如下的拆分： 4 = 1 + 1 + 1 + 1 回文數(shù)列1 = 1 + 1 + 2= 1 + 2 + 1 回文數(shù)列2= 2 + 1 + 1= 2 + 2 回文數(shù)列3= 1 + 3= 3 + 1因此，回文數(shù)列共有3個(gè)。【輸入】一個(gè)正整數(shù)K（1<K26）。【輸出】滿足條件的回文數(shù)列的個(gè)數(shù)?！据斎霕永?【輸出樣例】3（3）排序集合（）（已做，需練習(xí)）【問(wèn)題描述】對(duì)于集合N=1,2,N的子集，定義一個(gè)稱為“

27、小于”的關(guān)系：設(shè)S1=X1,X2,Xi，(X1<X2<<Xi)，S2=Y1,Y2,Yj，(Y1<Y2<<Yj)，如果存在一個(gè)k，（0<=k<=mini,j），使得X1=Y1，Xk=Yk，且k=i或X(k+1)<Y(k+1)，則稱S1“小于”S2。你的任務(wù)是：對(duì)于任意的n（n<=31）及k（k<2n），求出第k小的子集?！据斎搿?sort.in) 輸入文件僅一行，包含兩個(gè)用空格隔開(kāi)的自然數(shù)，n和k?！据敵觥?sort.out) 輸出文件僅一行，是該子集的元素，由小到大排列?？占敵??！据斎胼敵鰳永浚?3 4： 1 2 310.

28、 圖形打?。?）螺旋方陣（JS2010，T5，10分）（已做）【問(wèn)題描述】輸入一個(gè)正整數(shù)N（1<=N<=20）后，可以得到一個(gè)N*N的數(shù)字螺旋方陣，分別求該方陣中的主對(duì)角線與副對(duì)角線上的數(shù)字之和S、P，輸出S、P的差。例如：N=5，得到的數(shù)字螺旋方陣如下：12345161718196152425207142322218131211109其中，主對(duì)角線從左上角到右下角，得到的數(shù)字之和為：S=1+17+25+21+9=73；副對(duì)角線從右上到左下，得到的數(shù)字之和：P=5+19+25+23+13=85，S-P=-12。【輸入】一個(gè)整數(shù)N?！据敵觥恐鲗?duì)角線與副對(duì)角線上數(shù)字和的差。【樣例】 見(jiàn)

29、問(wèn)題中的舉例。11. 高精度計(jì)算（1）印度國(guó)王的棋盤（JS2010，T3，10分）（已做，需練習(xí)）【問(wèn)題描述】印度國(guó)王使用的棋盤有N*N個(gè)格子（N無(wú)限大），現(xiàn)在從第一個(gè)格子開(kāi)始放麥粒，第一個(gè)格子放1粒，第二個(gè)格子放2粒，第三個(gè)格子放4粒，第N個(gè)格子放2(N-1)粒麥粒。請(qǐng)你編程計(jì)算從第K格至第M格共有多少粒麥粒?！据斎搿恳恍?，兩個(gè)整數(shù)K，M（4<=K<M<=100）?！据敵觥抗灿卸嗌倭｛溋＃ńY(jié)果不超過(guò)6位時(shí)，直接輸出結(jié)果；結(jié)果超過(guò)6位時(shí)，只輸出結(jié)果的最高3位和最低3位，以逗號(hào)分隔）。12. 數(shù)學(xué)類問(wèn)題（數(shù)論問(wèn)題）(1)數(shù)學(xué)作業(yè)(math.bas)（已做）【問(wèn)題描述】小明的數(shù)學(xué)

30、老師布置了一堆數(shù)學(xué)題作為作業(yè)，這些數(shù)學(xué)題有一個(gè)共同的特點(diǎn)，就是都是要求計(jì)算出C(N,M)中不同質(zhì)因子的個(gè)數(shù)。Steven請(qǐng)你幫他寫一個(gè)程序，來(lái)幫助他盡快地完成這些作業(yè)。C(N,M)即求在N個(gè)數(shù)中選M個(gè)數(shù)的組合數(shù)?！据斎敫袷健?math.in)輸入文件中只有一行，其中有兩個(gè)整數(shù)，表示N和M(1<=N, M<=50000)?！据敵龈袷健?math.out) 輸出一個(gè)整數(shù)，表示C(N,M)中質(zhì)因子的個(gè)數(shù)?！据斎霕永? 3【輸出樣例】 2（2）細(xì)胞分裂(cell.bas)【問(wèn)題描述】Hanks 博士是BT (Bio-Tech，生物技術(shù)) 領(lǐng)域的知名專家。現(xiàn)在，他正在為一個(gè)細(xì)胞實(shí)驗(yàn)做準(zhǔn)備工

31、作：培養(yǎng)細(xì)胞樣本。Hanks 博士手里現(xiàn)在有N 種細(xì)胞，編號(hào)從1N，一個(gè)第i 種細(xì)胞經(jīng)過(guò)1 秒鐘可以分裂為Si 個(gè)同種細(xì)胞（Si 為正整數(shù)）。現(xiàn)在他需要選取某種細(xì)胞的一個(gè)放進(jìn)培養(yǎng)皿，讓其自由分裂，進(jìn)行培養(yǎng)。一段時(shí)間以后，再把培養(yǎng)皿中的所有細(xì)胞平均分入M 個(gè)試管，形成M 份樣本，用于實(shí)驗(yàn)。Hanks 博士的試管數(shù)M 很大，普通的計(jì)算機(jī)的基本數(shù)據(jù)類型無(wú)法存儲(chǔ)這樣大的M 值，但萬(wàn)幸的是，M 總可以表示為m1的m2次方，即 ，其中m1、m2均為基本數(shù)據(jù)類型可以存儲(chǔ)的正整數(shù)。注意，整個(gè)實(shí)驗(yàn)過(guò)程中不允許分割單個(gè)細(xì)胞，比如某個(gè)時(shí)刻若培養(yǎng)皿中有4 個(gè)細(xì)胞，Hanks 博士可以把它們分入2 個(gè)試管，每試管內(nèi)2

32、個(gè)，然后開(kāi)始實(shí)驗(yàn)。但如果培養(yǎng)皿中有5個(gè)細(xì)胞，博士就無(wú)法將它們均分入2 個(gè)試管。此時(shí)，博士就只能等待一段時(shí)間，讓細(xì)胞們繼續(xù)分裂，使得其個(gè)數(shù)可以均分，或是干脆改換另一種細(xì)胞培養(yǎng)。為了能讓實(shí)驗(yàn)盡早開(kāi)始，Hanks 博士在選定一種細(xì)胞開(kāi)始培養(yǎng)后，總是在得到的細(xì)胞“剛好可以平均分入M 個(gè)試管”時(shí)停止細(xì)胞培養(yǎng)并開(kāi)始實(shí)驗(yàn)?，F(xiàn)在博士希望知道，選擇哪種細(xì)胞培養(yǎng)，可以使得實(shí)驗(yàn)的開(kāi)始時(shí)間最早?！据斎搿枯斎胛募麨?cell.in，共有三行。第一行有一個(gè)正整數(shù) N，代表細(xì)胞種數(shù)。第二行有兩個(gè)正整數(shù)m1、m2，以一個(gè)空格隔開(kāi)，即表示試管的總數(shù)M。第三行有 N 個(gè)正整數(shù)，第i 個(gè)數(shù)Si 表示第i 種細(xì)胞經(jīng)過(guò)1 秒鐘可以分

33、裂成同種細(xì)胞的個(gè)數(shù)?！据敵觥枯敵鑫募?cell.out 共一行，為一個(gè)整數(shù)，表示從開(kāi)始培養(yǎng)細(xì)胞到實(shí)驗(yàn)?zāi)軌蜷_(kāi)始所經(jīng)過(guò)的最少時(shí)間（單位為秒）。如果無(wú)論 Hanks 博士選擇哪種細(xì)胞都不能滿足要求，則輸出整數(shù)-1?！据斎胼敵鰳永?1】12 13-1【輸入輸出樣例1 說(shuō)明】經(jīng)過(guò) 1 秒鐘，細(xì)胞分裂成3 個(gè)；經(jīng)過(guò)2 秒鐘，細(xì)胞分裂成9 個(gè)；?？梢钥闯?，無(wú)論怎么分裂，細(xì)胞的個(gè)數(shù)都是奇數(shù)，因此永遠(yuǎn)不能分入2 個(gè)試管。【輸入輸出樣例 2】224 130 122【輸入輸出樣例2 說(shuō)明】第 1 種細(xì)胞最早在3 秒后才能均分入24 個(gè)試管，而第2 種最早在2 秒后就可以均分（每試管144/(241)=6 個(gè)）。故實(shí)驗(yàn)最早可以在2 秒后開(kāi)始。【數(shù)據(jù)范圍】對(duì)于 50%的數(shù)