棋盤中的棋盤—淺談棋盤的分割思想

《棋盤中的棋盤—淺談棋盤的分割思想》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、棋盤中的棋盤——淺談棋盤的分割思想復(fù)旦大學(xué)附屬中學(xué)俞鑫【摘要】現(xiàn)在的信息學(xué)競(jìng)賽題目，經(jīng)常以某種數(shù)學(xué)模型作為出題媒介,使題目充滿樂(lè)趣性和深厚的數(shù)學(xué)底蘊(yùn)，而棋盤就是其中一種重要的數(shù)學(xué)模型。本文著重對(duì)棋盤的一種重要思想——棋盤的分割思想進(jìn)行分析，并引入兩道典型例題，說(shuō)明棋盤分割應(yīng)遵循的規(guī)律，使讀者能對(duì)紛繁復(fù)雜的棋盤分割有一定的了解。【關(guān)鍵詞】數(shù)學(xué)模型棋盤算法思想【正文】引言信息學(xué)是一門綜合性的學(xué)科，也是一門充滿樂(lè)趣的學(xué)科。棋盤，作為一個(gè)重要的數(shù)學(xué)模型，以其趣味性和復(fù)雜的數(shù)學(xué)特性經(jīng)常受到出題者的青睞。因此，深入

2、研究棋盤中蘊(yùn)含的算法思想對(duì)于一名信息學(xué)愛(ài)好者而言是十分必要的。在此，我將著重說(shuō)明棋盤屮的…種重要思想一一棋盤的分割思想。對(duì)于一個(gè)mXn的棋盤，它所含的子棋盤共有CmXCn個(gè)，而其分割方法更是不計(jì)其數(shù)。巧妙地對(duì)棋盤進(jìn)行分割,可以解決許多種類的棋盤問(wèn)題。子棋盤2ir///J子棋盤3例一；棋盤覆蓋（證與問(wèn)軀丿題目描述:在一個(gè)2kX2k方格組成的棋盤中，若恰有一個(gè)方格與其他方格不在棋盤覆蓋問(wèn)題中，我們要用以下4種不同形態(tài)的L型骨牌覆蓋同，則稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。顯然特殊-個(gè)給定的特殊棋盤

3、上除特殊方格以外的所有方格，且任何2個(gè)L型骨牌不得重疊覆蓋。易知，在任何一個(gè)2kX2k的棋盤覆蓋中，用道的L型骨牌個(gè)數(shù)恰為（43）/3?，F(xiàn)求一種覆蓋方法。4種不同形態(tài)的L型骨牌輸入：笫一行為k（棋盤的尺寸），第二行為x,y（1Wx,yW2^,分別表示特殊方格所在行與列。輸出：共2玄行，每行2玄個(gè)數(shù)，分別表示覆蓋該格的L型的編號(hào)（特殊格用0表示）。樣例：輸入：212輸出：43354455由棋盤尺寸為2kX2k,我們可以想到將其分割成四個(gè)尺寸為21X21的子棋盤是，由于含特殊方格的了棋盤與其它了棋盤不同，問(wèn)

4、題還是沒(méi)有解決。只耍稍作思考，我們就可以發(fā)現(xiàn),只要將L型如圖放置在棋盤的中央，就可以使四個(gè)子棋盤都變成特殊棋盤。此時(shí)問(wèn)題也變成了四個(gè)相同的子問(wèn)題，只需運(yùn)用簡(jiǎn)單的遞歸就可以解決這道問(wèn)題了。二位數(shù)組num:覆蓋該格的L型的編號(hào)，下文所說(shuō)的對(duì)方格賦值即對(duì)其對(duì)應(yīng)的num賦值。x1,y1:當(dāng)前棋盤左上角方格的行號(hào)與列號(hào)x2,y2:當(dāng)前棋盤右下角方格的行號(hào)與列號(hào)x3,y3:當(dāng)前棋盤中特殊格的行號(hào)與列號(hào)ck:當(dāng)前棋盤的尺寸(2ckx2ck)cnum:當(dāng)前L型骨牌的編號(hào)初始值：x1V1x2V2x3V3ckcnum112

5、k2kXVk1開(kāi)始時(shí)，將num[x,y]設(shè)為0當(dāng)ck=O時(shí)：棋盤尺寸為1X1,該格為已賦值的特殊格，不進(jìn)行任何操作。當(dāng)ck>0時(shí)：設(shè)xm為(x1+x2+1)/2,ym為(y1+y2+1)/2,比較x3與xm,y3與ym的大小就能知道特殊格所在子棋盤的位置，將另外產(chǎn)個(gè)子棋盤中靠近棋盤中央的?個(gè)方格賦值為cnum,y1ymy2x1xmx2并分別作為這三個(gè)了棋盤的特殊格。隨后cnum增加1。再對(duì)這四個(gè)棋盤分別進(jìn)行遞歸處理。時(shí)間復(fù)雜度：0(4k)空間復(fù)雜度:0(4/()由于覆蓋一個(gè)2gk棋盤所需的L型骨牌個(gè)數(shù)為

6、(4/<-1)/3,故該算法是一個(gè)在漸進(jìn)意義下最優(yōu)的算法。GAMERS.PAS小住將棋盤分割成子棋盤，要遵循以下兩點(diǎn)：1?分割出的棋盤要與原棋盤盡可能相像。2.將原棋盤分割后盡量不耍留下剩余部分。但如果分割后必定留下剩余部分又該如何呢？下面這道例題就是用來(lái)解答這個(gè)問(wèn)題的。例二,，孔朗棋問(wèn)龜（寵衣么％勺丿題口描述：在一個(gè)無(wú)限大的棋盤的節(jié)點(diǎn)上有一些棋子，這些棋子構(gòu)成一個(gè)mXn的矩形（m為高度，n為寬度J11WmjWIOOO）。你可以用一個(gè)棋子跳過(guò)另-個(gè)相鄰的棋子，被跳過(guò)的棋子將被移去，請(qǐng)你求出最少能剩下幾個(gè)

7、棋子?！跻环N移動(dòng)方法輸入：m,n輸出：最少能剩下的棋子數(shù)樣例：輸入：34輸出：2下而是一種走法:1B□□?r???????Hx??????7■?■■■■r>r?■>?^■1□a□■□□□I3□□■i■E0B■□□由于或n=1的情況比較特殊，我們先處理m,n^2的情況。為了敘述方便，我們稱由棋子所在格子組成的棋盤為“真棋盤”。通過(guò)樣例，我們可以發(fā)現(xiàn)，對(duì)于圖(a)中位于4、5、6格的連續(xù)三個(gè)棋子,若第1、2、3格上無(wú)棋了而第7、8、9格上均有棋子的話，則可以通過(guò)圖(b)的操作將這三個(gè)棋子移去。我們稱4、5、

8、6三顆棋子為模18■■W2(O3KO模:塊1塊1。???圖(b)ffl(a)但是經(jīng)過(guò)一些嘗試后，我們發(fā)現(xiàn)只使用模塊1對(duì)mXn的真棋盤進(jìn)行分割效果并不理想。原因在于模塊1每次對(duì)連續(xù)3行同時(shí)進(jìn)行處理，當(dāng)m不是3的倍數(shù)時(shí)，分割后總會(huì)留下剩余部分。（必須注意的是，圖中用藍(lán)框框起來(lái)的部分，必須等到其左邊的棋子被去除后，才能成為模塊1。）鄉(xiāng)僉口crrmnnnnnEEC因此，我們需要對(duì)剩余部分進(jìn)行處理。我們發(fā)現(xiàn)，當(dāng)m不為3的倍數(shù)時(shí)，總是留下1行或2行剩余