黃金分割與經(jīng)典算法

1、. .美，無(wú)處不在淺談“黃金分割和信息學(xué)的聯(lián)系*一中 楊思雨摘要本文主要介紹了“黃金分割與信息學(xué)競(jìng)賽的聯(lián)系及其在一些信息學(xué)問(wèn)題中的應(yīng)用，全文可以分為四個(gè)局部。第一局部引言，主要介紹了“黃金分割的由來(lái)及其和各領(lǐng)域的聯(lián)系，進(jìn)而提出探索黃金分割與信息學(xué)競(jìng)賽的聯(lián)系。第二局部中逐漸深入的分析了一個(gè)例題，最終提醒了問(wèn)題本質(zhì)上與黃金分割數(shù)的聯(lián)系，說(shuō)明了黃金分割數(shù)在一些數(shù)學(xué)性較強(qiáng)的題目中有著廣泛的應(yīng)用。第三局部通過(guò)分析另一個(gè)例題，介紹了一種優(yōu)選法“黃金分割法。第四局部指出黃金分割與信息學(xué)競(jìng)賽聯(lián)系密切，總結(jié)全文。關(guān)鍵字黃金分割 信息學(xué) 聯(lián)系目錄引言1例題一2例題二5總結(jié)7參考文獻(xiàn)7附錄8程序描述10引言早在古希

2、臘時(shí)期，人們就發(fā)現(xiàn)了“黃金分割。兩千多年前，數(shù)學(xué)家歐多克斯提出了這樣的問(wèn)題：如圖1，線段AB上有一點(diǎn)P，將線段AB分割為兩段AP和PB，假設(shè)它們長(zhǎng)度之比恰好等于整條線段AB與較長(zhǎng)一段AP的長(zhǎng)度之比，那么P點(diǎn)應(yīng)該在線段AB什么位置呢？圖 1我們不妨假設(shè)線段AP的長(zhǎng)度為1，設(shè)線段PB的長(zhǎng)度為x，那么線段AB的總長(zhǎng)度就是1+x。由，得到方程。解出，記為，它的近似值為0.618。而相應(yīng)的，線段AB的長(zhǎng)度就是，記為。在這之后，人們圍繞這個(gè)比值開(kāi)展了許多研究，意大利著名的藝術(shù)家、科學(xué)家達(dá)·芬奇還把命名為“黃金分割數(shù)Golden Section Number。有趣的是，人們發(fā)現(xiàn)黃金分割在自然界和其

3、它各個(gè)領(lǐng)域中到處可見(jiàn)。例如，人的肚臍是人體總長(zhǎng)的黃金分割點(diǎn)，人的膝蓋又是肚臍到腳跟的黃金分割點(diǎn)；在有些植物的莖上，相鄰葉柄之間的夾角是137º28,這恰好是把圓周分為1:0.618的兩條半徑的夾角。此外，黃金分割也被看作是美的化身，人們認(rèn)為符合黃金分割比例的事物都非常協(xié)調(diào)，富有美感。這就使得它在建筑、繪畫(huà)、雕塑、攝影和音樂(lè)等藝術(shù)領(lǐng)域也有著很廣泛的應(yīng)用，例如：在古希臘帕忒農(nóng)神廟的設(shè)計(jì)中就存在著許多組黃金分割比；而在荷蘭畫(huà)家梵高的作品"岸邊的漁船"中，整幅畫(huà)的寬和高分別被桅桿和地平線分成兩局部，這樣的分割也正好符合了黃金分割比例。其實(shí)，在信息學(xué)也蘊(yùn)含著這樣的微妙，本文

4、就將通過(guò)兩個(gè)例題，介紹信息學(xué)和黃金分割的一些聯(lián)系。例題一取石子游戲(STONE)有兩堆石子，數(shù)量任意，可以不同。游戲開(kāi)場(chǎng)由兩個(gè)人輪流取石子。游戲規(guī)定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時(shí)取走一樣數(shù)量的石子。最后把石子全部取完者為勝者?，F(xiàn)在給出初始的兩堆石子的數(shù)目，如果輪到你先取，假設(shè)雙方都采取最好的策略，問(wèn)最后你是勝者還是敗者。輸入輸出要求輸入文件由假設(shè)干行，表示假設(shè)干種石子的初始情況，其中每一行中包含兩個(gè)非負(fù)整數(shù)a和b，表示兩堆石子的數(shù)目，a和b均不大于 1,000,000,000。輸出文件對(duì)應(yīng)也是假設(shè)干行，每行包含一個(gè)數(shù)字1或0，如果最后你是勝

5、利者，那么為1，反之，那么為0。樣例輸入和相應(yīng)輸出樣例一輸入輸出6 100樣例二輸入輸出2 18 44 7010問(wèn)題描述有兩堆石子，游戲開(kāi)場(chǎng)后，由兩個(gè)人輪流取石子，每次有兩種取法：一是在任意一堆中取走任意數(shù)目的石子；二是可以在兩堆中同時(shí)取走一樣數(shù)量的石子。最后把石子全部取完的人是勝者?，F(xiàn)在給出初始的兩堆石子的數(shù)目a和b0a,b109，假設(shè)雙方都采取最好的策略，判斷先手是否有必勝策略。算法一問(wèn)題中，兩堆石子的個(gè)數(shù)a和b決定了最后的勝負(fù)。因此，我們用(a,b)作為表示當(dāng)前局面的“狀態(tài)。通過(guò)建立博弈樹(shù)，判斷給出的初始狀態(tài)(a,b)是必勝還是必?cái)?。需要注意的是，由于?guī)那么中兩個(gè)石子堆并沒(méi)有差異，因此狀

6、態(tài)(a,b)和狀態(tài)(b,a)實(shí)際上是等價(jià)的。0, 01, 20, 21, 01, 10, 10, 00, 00, 11, 00, 10, 00, 0來(lái)看一個(gè)例子，游戲開(kāi)場(chǎng)時(shí)，兩堆石子的數(shù)目分別是1和2，那么初始狀態(tài)為(1,2)，自頂向下構(gòu)造出的博弈樹(shù)如圖2其中，重復(fù)子狀態(tài)可以只擴(kuò)展一個(gè)。圖 2接下來(lái)，就可以分三種情況，判斷各個(gè)狀態(tài)的勝負(fù)情況：(1) 如果一個(gè)狀態(tài)沒(méi)有子狀態(tài)，根據(jù)規(guī)那么判斷勝負(fù)；(2) 如果一個(gè)狀態(tài)至少有一個(gè)子狀態(tài)先手?jǐn)。敲丛摖顟B(tài)先手勝；0, 01, 20, 21, 01, 10, 10, 00, 00, 11, 00, 10, 00, 0敗敗敗敗敗敗勝勝勝勝勝(3) 如果一個(gè)

7、狀態(tài)的所有子狀態(tài)都是先手勝，那么改狀態(tài)先手?jǐn)　D 3這樣，我們就可以得出初始狀態(tài)的勝負(fù)情況如圖3。具體實(shí)現(xiàn)時(shí)，可以采用動(dòng)態(tài)規(guī)劃或記憶化搜索解決。這個(gè)算法的空最壞情況下查詢的次數(shù)約為2+log1/108 間復(fù)雜度為O(N2)，時(shí)間復(fù)雜度為O(N 3)。附程序stone_1.pas。算法二顯然上面的算法并不能有效的解決此題。我們需要進(jìn)一步挖掘游戲規(guī)那么的特點(diǎn)。根據(jù)兩種取石子的方法，可以發(fā)現(xiàn)如果狀態(tài)(a,b)是先手?jǐn)?，就能得到下面幾種狀態(tài)必為先手勝：(1) 狀態(tài)(a,i)其中，ib或狀態(tài)(i,b)其中，ia；(2) 狀態(tài)(a+i,b+i)其中，i0。也就是說(shuō)，每個(gè)正整數(shù)在所有先手?jǐn)顟B(tài)中將出現(xiàn)且只出

8、現(xiàn)一次，同時(shí)任何兩個(gè)必?cái)顟B(tài)中兩堆石子的差值各不一樣。根據(jù)這個(gè)特點(diǎn)，我們可以構(gòu)造出所有的先手?jǐn)顟B(tài)。首先，最小的先手?jǐn)顟B(tài)是(0,0)，根據(jù)上面的規(guī)律，之后的先手?jǐn)顟B(tài)中就不再存在某一堆為0個(gè)石子的情況，同時(shí)也不會(huì)出現(xiàn)兩堆石子個(gè)數(shù)相等的情況。因此，第二種先手?jǐn)〉臓顟B(tài)中較小的一堆石子個(gè)數(shù)將是尚未出現(xiàn)的最小的整數(shù)1，而這種狀態(tài)中兩堆石子個(gè)數(shù)的差也是尚未出現(xiàn)的差值中最小的一個(gè)。這樣，第二種先手必?cái)〉臓顟B(tài)就是(1,2)。由此，我們得到了構(gòu)造所有先手?jǐn)顟B(tài)的方法：開(kāi)場(chǎng)時(shí)只有(0,0)一個(gè)先手?jǐn)顟B(tài)；第i次構(gòu)造時(shí)，先找出在的先手?jǐn)顟B(tài)中沒(méi)有出現(xiàn)的最小的整數(shù)a，那么新產(chǎn)生的先手?jǐn)顟B(tài)就是(a,a+i)。這個(gè)

9、算法的時(shí)間復(fù)雜度和空復(fù)雜度均為O(N)。附程序stone_2.pas。算法三雖然算法二的時(shí)空復(fù)雜度相對(duì)算法一有了巨大的進(jìn)步，但由于此題數(shù)據(jù)規(guī)模巨大，仍然沒(méi)有方法徹底解決。而這時(shí)，我們的分析也陷入如了僵局。那么就讓我們先從小規(guī)模的情況開(kāi)場(chǎng)分析。序號(hào)ii狀態(tài)(a,b)11.6180(1,2)23.2361(3,5)34.8541(4,7)46.4721(6,10)58.0902(8,13)9971613.1799(1613,2610)9981614.7979(1614,2612)9991616.4160(1616,2615)10001618.0340(1618,2618)表 2序號(hào)i必?cái)顟B(tài)(a,

10、b)a / ib / i1(1,2)1.00002.00002(3,5)1.50002.50003(4,7)1.33332.33304(6,10)1.50002.50005(8,13)1.60002.6000997(1613,2610)1.61792.6179998(1614,2612)1.61722.6172999(1616,2615)1.61762.61761000(1618,2618)1.61802.6180表 1表1中列出了一些構(gòu)造出來(lái)的必?cái)顟B(tài)表中小數(shù)保存四位精度，下同?？梢园l(fā)現(xiàn)，后面構(gòu)造出來(lái)的狀態(tài)中，較小一堆的石子數(shù)a與狀態(tài)序號(hào)i的比值十分接近！這提示我們，也許a的值與i有一定的關(guān)

11、系。所以，我們反過(guò)來(lái)觀察i與a之間的關(guān)系。在表2列出的小規(guī)模情況中，第i個(gè)必?cái)顟B(tài)中較小一堆的石子數(shù)a都恰好等于i的整數(shù)局部。于是我們提出了這樣的猜想：第i個(gè)必?cái)顟B(tài)是 (i , (+1)i ) 本文中x表示x的整數(shù)局部，x表示x的小數(shù)局部。可以證明，這個(gè)猜想是正確的1。因此，我們得出結(jié)論，對(duì)于狀態(tài)(a,b)其中，ab，如果且，那么先手必?cái)?，否那么先手必勝。這樣算法的時(shí)空復(fù)雜度均為常數(shù)級(jí)的，問(wèn)題得到了圓滿的解決。附程序stone_3.pas。解題小結(jié)表3將上述三個(gè)算法進(jìn)展了比較。算法一是解決博弈問(wèn)題的常規(guī)方法，同時(shí)定義了狀態(tài)；算法二，深入挖掘了游戲規(guī)那么，找出了其中的特性；算法三那么通過(guò)分析一

12、些小規(guī)模的數(shù)據(jù)，找到了常數(shù)級(jí)的算法。通過(guò)這樣不斷的分析和挖掘，終于找到了問(wèn)題本質(zhì)上與黃金分割的聯(lián)系，發(fā)現(xiàn)了這樣一個(gè)博弈問(wèn)題中蘊(yùn)含的美。時(shí)間復(fù)雜度空間復(fù)雜度根本算法算法一O(N3)O(N 2)根據(jù)博弈樹(shù)進(jìn)展動(dòng)歸算法二O(N)O(N)構(gòu)造必?cái)顟B(tài)算法三O(1)O(1)直接判斷勝負(fù)情況表 3例題二登山問(wèn)題(EXPLORER)【問(wèn)題描述】一些OIer準(zhǔn)備去翻越OI Mountain，一條雄偉的山脈。但是開(kāi)場(chǎng)登山之前，OIers希望先知道這條山脈的最高點(diǎn)的位置。山脈的橫截面都是一樣的，而且最高點(diǎn)兩側(cè)，山的高度也依次遞減。OIer們可以使用衛(wèi)星探測(cè)系統(tǒng)來(lái)測(cè)量某一具體位置上山的高度。每次，他們發(fā)出指令Exp

13、lorer(x)，這時(shí)衛(wèi)星就會(huì)返回山脈橫截面中，坐標(biāo)為x的位置上，山的海拔高度。但是由于和衛(wèi)星通信總是很慢L，OIers希望能夠在40次內(nèi)找出那個(gè)最高點(diǎn)。你能做到么？【如何調(diào)用交互庫(kù)】測(cè)試庫(kù)提供三個(gè)函數(shù)：Start，Ask，Answer，它們的作用和用法如下：Ø Start()必須首先調(diào)用，用它來(lái)獲得實(shí)數(shù)L的值。Ø Ask(X)的作用是詢問(wèn)，用它來(lái)獲得函數(shù)f(x)的值。Ø Answer(Ans)用來(lái)告訴測(cè)試庫(kù)你得到的答案。，表示你的程序判斷函數(shù)f(x)在Ans處取到最大值。你的程序不得自行終止且不得任何文件?！緦?duì)Pascal程序員的提示】你的程序應(yīng)當(dāng)使用以下語(yǔ)句引

14、用測(cè)試庫(kù)：uses tools_p;測(cè)試庫(kù)提供的函數(shù)/過(guò)程原型為：function Start:double;function Ask(x:double):double;procedure Answer(ans:double);【對(duì)C+程序員的提示】你程序頭加上一行：#include “tools_c.h并且在RHIDE中設(shè)置Option->Linker為tools_c.o測(cè)試庫(kù)提供的函數(shù)原型為：double Start();double Ask(double x);double Answer(double ans);【數(shù)據(jù)說(shuō)明】如果問(wèn)題中區(qū)間范圍為0,2，f(x)=-(x-1)2+10

15、，那么一種可能總分值的調(diào)用方法如下：Pascal選手的調(diào)用方法C+選手的調(diào)用方法說(shuō)明Start;Start();返回值2，表示區(qū)間長(zhǎng)度Ask(0);Ask(0);返回值9，表示f(0)=9Ask(1.5);Ask(1.5);返回值9.75Ask(1);Ask(1);返回值10Ask(2);Ask(2);返回值9Answer(1);Answer(1);返回結(jié)果，完畢程序注意，該例子只是對(duì)庫(kù)函數(shù)的使用說(shuō)明，并沒(méi)有算法上的意義。這里L(fēng)最大為104，要求最后返回的答案與最高點(diǎn)橫坐標(biāo)誤差不超過(guò)10-3。山的高度在0, 8848.13這個(gè)區(qū)間內(nèi)。【如何測(cè)試你的程序】Ø 在當(dāng)前目錄下建立文件exp

16、lorer.in，其中包含一個(gè)實(shí)數(shù)L，表示為函數(shù)f(x)的定義域?yàn)?L,我們的交互庫(kù)將會(huì)自動(dòng)生成的值。Ø 運(yùn)行你的程序Ø 運(yùn)行完畢后，交互庫(kù)將會(huì)把整個(gè)對(duì)話記錄在文件explorer.log中【如何了解錯(cuò)誤信息】如果對(duì)話文件explorer.log中包行一行或多行以Error:開(kāi)頭的信息，那么表示你的程序在運(yùn)行過(guò)程中發(fā)生了錯(cuò)誤。具體的錯(cuò)誤信息如下所示。Error: Input file explorer.in not found交互庫(kù)在當(dāng)前目錄下沒(méi)有發(fā)現(xiàn)輸入文件explorer.in。Error: Start must call first!你的程序沒(méi)有初始化交互庫(kù)。Erro

17、r: You have called Start twice你的程序嘗試屢次調(diào)用Start函數(shù)。Error: Parameter is out of range你的程序調(diào)用Ask函數(shù)的參數(shù)不再內(nèi)。Error: You have called Ask more than 60 times你的程序過(guò)多的調(diào)用了Ask函數(shù)超過(guò)60次。問(wèn)題描述單峰函數(shù)2f(x)在區(qū)間0,L上有極大值，要求通過(guò)一系列查詢，找到這個(gè)極大值的橫坐標(biāo)x0。每次查詢中，向交互庫(kù)3提供一個(gè)查詢點(diǎn)t，交互庫(kù)將返回f(t)。數(shù)據(jù)范圍：0<L104，要求查詢次數(shù)不超過(guò)40次，且計(jì)算結(jié)果與最優(yōu)點(diǎn)x0誤差不得超過(guò)10-3。算法分析對(duì)于

18、區(qū)間內(nèi)的兩個(gè)不同的查詢點(diǎn)，我們將函數(shù)值較大的稱為好點(diǎn)，將函數(shù)值較小的稱為差點(diǎn)。下面，我們將說(shuō)明，最優(yōu)點(diǎn)和好點(diǎn)必在差點(diǎn)的同側(cè)。證明首先需要明確，最優(yōu)點(diǎn)顯然不會(huì)與差點(diǎn)重合。如果最優(yōu)點(diǎn)與好點(diǎn)重合，那么命題顯然成立。圖 4如果最優(yōu)點(diǎn)并不在好點(diǎn)的位置，那么將存在下面兩種情況：(1) 如圖4(a)，好點(diǎn)與差點(diǎn)分別位于最優(yōu)點(diǎn)的兩側(cè)，此時(shí)命題顯然成立；(2) 如圖4(b)，好點(diǎn)與差點(diǎn)位于最優(yōu)點(diǎn)同側(cè)；此時(shí)，由于f(x)是單峰函數(shù)，離最優(yōu)點(diǎn)較近的查詢點(diǎn)必然是好點(diǎn)，因而最優(yōu)點(diǎn)與好點(diǎn)仍在差點(diǎn)同側(cè)。證畢。上面的結(jié)論，提示我們，可以通過(guò)比較目標(biāo)區(qū)間內(nèi)的兩個(gè)查詢點(diǎn)位置上的函數(shù)值，刪去一局部目標(biāo)區(qū)間。這樣逐步縮小目標(biāo)范圍，不

19、斷逼近最優(yōu)點(diǎn)，直到到達(dá)允許的誤差范圍內(nèi)為止。原題中，允許的誤差范圍是原區(qū)間長(zhǎng)度的千萬(wàn)分之一，為了保證精度，我們需要將區(qū)間范圍縮小為原來(lái)的1/108。如何盡快的縮小目標(biāo)范圍，就成了我們需要研究的問(wèn)題。而解決這個(gè)問(wèn)題的關(guān)鍵，就是合理的選擇查詢點(diǎn)的位置。下面我們就來(lái)分析一下具體應(yīng)該如何選取查詢點(diǎn)的位置。設(shè)當(dāng)前目標(biāo)范圍為a,b，兩個(gè)查詢點(diǎn)為x1與x2，x1<x2。在查詢之前，我們無(wú)法預(yù)先知道兩個(gè)查詢點(diǎn)孰好孰差，也就是說(shuō)兩個(gè)查詢點(diǎn)成為差點(diǎn)的可能性是一樣的。因此我們無(wú)法確定終究會(huì)去掉哪一段區(qū)間范圍。所以，我們?cè)诎才挪樵凕c(diǎn)時(shí)應(yīng)該使它們關(guān)于當(dāng)前目標(biāo)范圍的中點(diǎn)對(duì)稱，即應(yīng)使x1a=b-x2。這是我們?cè)诓樵冞^(guò)

20、程中應(yīng)遵循的第一個(gè)原那么對(duì)稱原那么?！皩?duì)稱原那么是十分常用的，例如我們經(jīng)常在一些查找中使用的“二分法，就完全符合這個(gè)原那么。我們也就很容易想到使用二分法來(lái)解決此題：每次在當(dāng)前目標(biāo)范圍中點(diǎn)附近，選擇兩個(gè)非常接近的查詢點(diǎn)，并且根據(jù)這兩個(gè)查詢點(diǎn)的函數(shù)值，確定最優(yōu)點(diǎn)的范圍，縮小目標(biāo)區(qū)間。這樣每次可以舍去接近原區(qū)間一半長(zhǎng)度的局部，為了保證精度，我們需要進(jìn)展的查詢次數(shù)就在2log2108左右，約為54次，達(dá)不到題目中的要求。通過(guò)分析，我們可以發(fā)現(xiàn)造成查詢次數(shù)較多的原因是，每次為了去掉區(qū)間的一半，都需要重新進(jìn)展兩次查詢；而實(shí)際上，原來(lái)的好點(diǎn)仍然處在當(dāng)前的區(qū)間中，二分法卻并沒(méi)有利用到它的函數(shù)值信息。由此，我們

21、想到，每次可以只在當(dāng)前區(qū)間中進(jìn)展一次查詢，并與原來(lái)的好點(diǎn)進(jìn)展比較，得出新的好點(diǎn)和差點(diǎn)，進(jìn)而繼續(xù)縮小目標(biāo)范圍。由于我們每次選擇的查詢點(diǎn)要滿足對(duì)稱原那么，因此，最開(kāi)場(chǎng)選擇的兩個(gè)查詢點(diǎn)的位置就決定了后面每次可以舍取得區(qū)間長(zhǎng)度。我們發(fā)現(xiàn)，如果像二分法中一樣，讓x1與x2都盡量靠近，這樣一次可以舍去整個(gè)因素范圍a,b的將近50%，但是接下來(lái)每次只能舍去很小的一局部了，反而不利于較快地逼近最優(yōu)點(diǎn)。這個(gè)情況又提示我們：最好每次舍去的區(qū)間都在全區(qū)間中占同樣的比例我們不妨稱之為"成比例的舍去"原那么。圖 5 按照上述兩個(gè)原那么，如圖5所示，設(shè)第一次和第二次查詢分別在x1點(diǎn)和x2點(diǎn)，

22、x1<x2，那么在第一次比較結(jié)果后，由對(duì)稱性，舍去的區(qū)間長(zhǎng)度都等于b-x2。不妨設(shè)x1是好點(diǎn)，x2是差點(diǎn)，舍去的是(x2,b)。再設(shè)第三次試驗(yàn)安排在x3點(diǎn)，那么x3點(diǎn)應(yīng)在a,x2中與x1點(diǎn)對(duì)稱的位置上。同時(shí)x3點(diǎn)應(yīng)在x1點(diǎn)左側(cè)，否那么x3點(diǎn)與x1點(diǎn)比較查詢結(jié)果后被舍去的將與上次舍去的是同樣的長(zhǎng)度，而不是同樣的比例，違背“成比例的舍去原那么。由此可知，x3點(diǎn)與x1點(diǎn)比較后，被舍去的區(qū)間長(zhǎng)度都等于x2-x1。于是按照“成比例地舍去原那么，我們得到等式：經(jīng)過(guò)變形、化簡(jiǎn)可得這個(gè)等式和引言中關(guān)于線段分割的方程十分類似，這說(shuō)明，x2正處于區(qū)間a,b的黃金分割點(diǎn)上。也就是說(shuō)，查詢點(diǎn)安排在區(qū)間的黃金分割

23、點(diǎn)處較為妥當(dāng)。因此，我們也將這種逼近最優(yōu)值的方法稱為“黃金分割法。效率分析由于每次查詢點(diǎn)都在當(dāng)前目標(biāo)區(qū)間的黃金分割點(diǎn)處，每次保存下來(lái)的區(qū)間和原來(lái)區(qū)間的長(zhǎng)度比都是:1。因此，最壞情況下查詢的次數(shù)約為2+log1/108，恰好在40次之內(nèi)，可以圓滿的解決問(wèn)題。附程序explorer.pas。解題小結(jié)在這個(gè)問(wèn)題中，我們擺脫了“二分法思想的束縛，充分利用每次查詢的信息，提出了兩個(gè)選擇查詢點(diǎn)時(shí)需要遵循的原那么。而由于黃金分割所特有的神奇的比例性質(zhì)，恰好符合了“成比例的舍去原那么，為解決此題提供了出路?？偨Y(jié)上文中兩個(gè)例題的解決，都與“黃金分割數(shù)有著密切的聯(lián)系。例一構(gòu)造的數(shù)對(duì)中，蘊(yùn)藏著黃金分割數(shù)的規(guī)律。其實(shí)

24、信息學(xué)競(jìng)賽中，常常會(huì)出現(xiàn)一些數(shù)學(xué)性較強(qiáng)的題目。而黃金分割數(shù)，恰恰和構(gòu)造數(shù)列、矩陣等密切相關(guān)，也就往往會(huì)成為解決這類題目的鑰匙。例二中的解決中，黃金分割所特有的比例性質(zhì)使得它成為解決問(wèn)題的關(guān)鍵。而在一些類似的查詢問(wèn)題中，黃金分割都有著廣泛的應(yīng)用，理論上可以證明，上面介紹的黃金分割法，查詢的次數(shù)是各種優(yōu)選法中最優(yōu)的 具體證明參見(jiàn)“參考文獻(xiàn)6。當(dāng)然，黃金分割與信息學(xué)競(jìng)賽的聯(lián)系遠(yuǎn)不止這些，也還有很多微妙需要我們?nèi)ヌ剿骱桶l(fā)現(xiàn)。法國(guó)雕塑家羅丹曾說(shuō)過(guò)：“美，是無(wú)處不在的，對(duì)于我們的眼睛，缺少的不是美，而是發(fā)現(xiàn)。其實(shí)，只要勤于思考、勇于探索，每個(gè)人都可以擁有一雙善于發(fā)現(xiàn)美的慧眼。參考文獻(xiàn)1姜璐主編，"

25、;中國(guó)少年兒童百科全書(shū)科學(xué)·技術(shù)"，第2版，*教育，1994.12.2<美>Tobias Dantzig著，蘇仲湘譯，"數(shù)：科學(xué)的語(yǔ)言"，第1版，*教育，2000.123"數(shù)學(xué)手冊(cè)"編寫(xiě)組，"數(shù)學(xué)手冊(cè)"，第1版，人民教育，1979.054X維勇主編，"青少年信息學(xué)奧林匹克競(jìng)賽試題與解析*省19942004年"，第1版，*工業(yè)大學(xué)，2004.085駱驥，"淺析解“對(duì)策問(wèn)題的兩種思路從取石子問(wèn)題談起"，2002年國(guó)家集訓(xùn)隊(duì)論文，2002.026華羅庚，"優(yōu)選

26、學(xué)"，第1版，科學(xué)，1981.04附錄1例題一，算法三，猜想的證明。定義1.1 根據(jù)算法二構(gòu)造列數(shù)為2的矩陣A，使得必?cái)顟B(tài)依次為(A1,1,A1,2)，(A2,1,A2,2)，(A3,1,A3,2),。定義1.2 根據(jù)猜想構(gòu)造列數(shù)為2的矩陣B，其中，Bi,1=i，Bi,2=(+1)i 。引理1.1(Betty 定理)如果a和b是兩個(gè)正無(wú)理數(shù)，且滿足且P = x | x = at, tZ+，Q = x | x = bt, tZ+，那么P和Q是正整數(shù)集Z+的一個(gè)劃分，即證明對(duì)于任意正整數(shù)n，設(shè)P集合中小于n的元素的個(gè)數(shù)為x，同樣Q集合中小于n的個(gè)數(shù)為y。那么顯然有由于a, b都是無(wú)理數(shù)

27、，因此都不可能是整數(shù)，所以有那么考察x + yx + y = < = = n而n (x + y) = < 2綜上，有n 2 < x + y < nÞx + y = n 1那么可以知道，對(duì)于任意n，在P和Q集合中小于n的元素共有(n - 1)個(gè)；而小于(n + 1)的元素共有n個(gè)。所以，P, Q兩個(gè)集合中等于n的元素有且僅有1個(gè)！因此Z+中的每一個(gè)元素不是在P集合中，就是在Q集合中，不可能既不在P中也不在Q中，也不可能既在P中又在Q中。所以說(shuō)推論1.1 如果a和b是兩個(gè)正無(wú)理數(shù)，且滿足：那么任意正整數(shù)x，可以且只可以表示為at和bt中的一種形式。tZ+推論1.2

28、 任意正整數(shù)x都在矩陣B中出現(xiàn)且只出現(xiàn)一次。證明 由于有等式：根據(jù)推論1.1和定義1.2，推論1.2成立。引理1.2 對(duì)于任意的i>1，都有Bi,1是除矩陣B的前i-1行中數(shù)字外最小的正整數(shù)。證明 根據(jù)定義1.2，比Bi,1小的整數(shù)都應(yīng)出現(xiàn)在矩陣的前i-1行中。在矩陣第一列中，所有數(shù)字都可以表示成為t的形式。其中，比i小的數(shù)字個(gè)數(shù)為。同理，矩陣B的第二列中，比i小的數(shù)共有個(gè)。因此，在整個(gè)矩陣的前i-1行中出現(xiàn)的比i小的整數(shù)個(gè)數(shù)為同時(shí)，有因此，在整個(gè)矩陣的前i-1行中出現(xiàn)的比i小的整數(shù)個(gè)數(shù)為i-1，綜合推論1.2可以得出，Bi,1是除矩陣B中前i-1行中的數(shù)以外最小的正整數(shù)。定理1 矩陣A

29、和矩陣B等價(jià)，即對(duì)任意的i均有Ai,1=Bi,1且Ai,2=Bi,2。對(duì)行數(shù)i進(jìn)展歸納：當(dāng)i=1時(shí)，顯然有A1,1=B1,1，A1,2=B1,2。假設(shè)i<k是均有Ai,1=Bi,1且Ai,2=Bi,2。根據(jù)定義1.1，Ak,1是除掉矩陣A中前k-1行中數(shù)字外最小的正整數(shù)。而根據(jù)引理1.2，也有Bk,1是除掉矩陣B中前k-1行中數(shù)字外最小的正整數(shù)。根據(jù)歸納假設(shè)，有Ak,1=Bk,1根據(jù)算法二的構(gòu)造方法，有Ak,2=Ak,1+k。而根據(jù)定義1.2有Bk,2=(+1)k= k+k=Bk,1k因此，可以得出Ak,2=Bk,2綜上，定理成立，算法三中關(guān)于必?cái)顟B(tài)的猜想也成立。2 例題二，單峰函數(shù)的

30、定義根據(jù)題目，這里只給出存在極大值的單峰函數(shù)f(x)定義：設(shè)x0是區(qū)間a,b上的函數(shù)最大點(diǎn)，那么有(1) 對(duì)于任意的x1<x2<x0，都有f(x1)<f(x2)<f(x0)；(2) 對(duì)于任意的x0<x1<x2，都有f(x0)>f(x1)>f(x2)。3 例題二，交互庫(kù)C+程序員使用的交互庫(kù)：tools_c.hPascal程序員使用的交互庫(kù)：tools_p.ppu特別感謝，*省*市第一中學(xué)的周冬同學(xué)為此題編寫(xiě)交互庫(kù)。程序描述1 Stone_1.pasProgram Stone_Algorithm1;Const inf='stone.in&#

31、39;/輸入文件 outf='stone.out'/輸出文件 maxn=100;Var a,b:longint;/石子個(gè)數(shù) ans:array0.maxn,0.maxnof longint;/各個(gè)狀態(tài)的勝負(fù)情況function dfs(a,b:longint):longint;/深度搜索var i,t:longint;begin if ansa,b<>0 then begin/狀態(tài)(a,b)已經(jīng)計(jì)算過(guò) ansb,a:=ansa,b; dfs:=ansa,b; exit; end; if ansb,a<>0 then begin/狀態(tài)(b,a)已經(jīng)計(jì)算過(guò)

32、ansa,b:=ansb,a; dfs:=ansa,b; exit; end; for i:=1 to a do/在第一堆中取i個(gè)石子 begin t:=dfs(a-i,b); if t=1 then begin/有一個(gè)子狀態(tài)先手?jǐn)?ansa,b:=2; ansb,a:=2;/先手勝 dfs:=2; exit; end; end; for i:=1 to b do/在第二堆中取i個(gè)石子 begin t:=dfs(a,b-i); if t=1 then begin/有一個(gè)子狀態(tài)先手?jǐn)?ansa,b:=2; ansb,a:=2;/先手勝 dfs:=2; exit; end; end; for i:

33、=1 to a do/在兩堆石子中同時(shí)取走i個(gè) if i<=b then begin t:=dfs(a-i,b-i); if t=1 then begin/有一個(gè)子狀態(tài)先手?jǐn)?ansa,b:=2; ansb,a:=2;/先手勝 dfs:=2; exit; end; end else break; dfs:=1;/所有子狀態(tài)都先手勝，該狀態(tài)先手?jǐn)nd;Begin assign(input,inf); reset(input); assign(output,outf); rewrite(output); fillchar(ans,sizeof(ans),0);/初始化 ans0,0:=1;

34、/狀態(tài)(0,0)，先手?jǐn)?while not(seekeof) do/多組數(shù)據(jù) begin read(a,b);/讀入a,b ansa,b:=dfs(a,b);/進(jìn)展搜索 writeln(ansa,b-1);/輸出結(jié)果 end; close(input); close(output);End.2 Stone_2.pasProgram Stone_Algorithm2;Const inf='stone.in'/輸入文件 outf='stone.out'/輸出文件 maxn=1000000;Var a,b:longint;/石子個(gè)數(shù) f:array0.maxnof

35、boolean;/各整數(shù)是否出現(xiàn)procedure swap;/交換a和bvar t:longint;begin t:=a; a:=b; b:=t;end;procedure work;/計(jì)算過(guò)程var i,t:longint;begin fillchar(f,sizeof(f),0);/初始化 t:=0;/構(gòu)造出的比敗狀態(tài)的個(gè)數(shù) for i:=0 to a-1 do if not fi then begin/整數(shù)i尚未出現(xiàn) fi+t:=true; inc(t); end; if not(fa) and (a+t=b)/判斷 then writeln(0) else writeln(1);end;Begin assign(input,inf); reset(input); assign(output,outf); rewrite(output); while not(seekeof) do/多組數(shù)據(jù) begin read(a,b);/讀入a和b if a>b then swap;/ ab work;/計(jì)算過(guò)程