棋盤覆蓋問題python

A. 棋盤覆蓋問題的理解

本人剛好寫了此題，還用JavaSwing謝了程序界面。
內容太多了你進我博客看吧：
http://blog.sina.com.cn/s/blog_67cf65ab0100qt4z.html

B. 棋盤覆蓋問題，求c語言數組遞歸的解答，和思路

intsupersum(intn){if(n==1)return1;elsereturnn*n+supersum(n-1);}

C. [image]100 棋盤覆蓋問題，求c語言數組遞歸的解答，和思路

棋盤覆蓋問題

問題描述：在一個2k×2k 個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。

代碼：#include<stdio.h>

int tile=0;//整型變數，記錄L型骨牌的數量 int Matrix[100][100];//定義數據結構

void ChessBoard(int tr,int tc,int dr,int dc,int size)

{//tr和tc分別是棋盤左上角方格的行號、列號；dr和dc分別是特殊方格的行號、列號 if(size==1) return; int t=tile++;//L型骨牌號，初值為0 int s=size/2;//分割棋盤

if(dr<tr+s&&dc<tc+s)//用L型骨牌號覆蓋左上角子棋盤 ChessBoard(tr,tc,dr,dc,s);// 特殊方格在此棋盤中 else

{//特殊方格不在此棋盤中用 ,t號L型骨牌覆蓋右下角 Matrix[tr+s-1][tc+s-1]=t; // 覆蓋本子棋盤中的其餘方格 ChessBoard(tr,tc,tr+s-1,tc+s-1,s); }

if(dr<tr+s&&dc>=tc+s)//用L型骨牌號覆蓋右上角子棋盤 ChessBoard(tr,tc,dr,dc,s);// 特殊方格在此棋盤中 else

{//特殊方格不在此棋盤中用 ,t號L型骨牌覆蓋左下角 Matrix[tr+s-1][tc+s]=t;// 覆蓋本子棋盤中的其餘方格 ChessBoard(tr,tc+s,tr+s-1,tc+s,s); }

if(dr>=tr+s&&dc<tc+s)//用L型骨牌號覆蓋左下角子棋盤 ChessBoard(tr+s,tc,dr,dc,s);// 特殊方格在此棋盤中 else

{//特殊方格不在此棋盤中用 ,t號L型骨牌覆蓋右上角 Matrix[tr+s][tc+s-1]=t;// 覆蓋本子棋盤中的其餘方格 ChessBoard(tr+s,tc,tr+s,tc+s-1,s); }

if(dr>=tr+s&&dc>=tc+s)//用L型骨牌號覆蓋右上角子棋盤 ChessBoard(tr+s,tc+s,dr,dc,s);// 特殊方格在此棋盤中 else

{//特殊方格不在此棋盤中用 ,t號L型骨牌覆蓋左上角 Matrix[tr+s][tc+s]=t;// 覆蓋本子棋盤中的其餘方格 ChessBoard(tr+s,tc+s,tr+s,tc+s,s); }

}

int main() { int size,r,c,row,col; //memset(Matrix,0,sizeof(Matrix)); for(int i=0;i<=100;i++)//初始化 為零 { for(int j=0;j<=100;j++) { Matrix[i][j]=0; } } scanf("%d",&size);//輸入棋盤大小 scanf("%d%d",&row,&col);//輸入特殊方格位置 ChessBoard(0,0,row,col,size); for (r = 0; r < size; r++)//輸出棋盤覆蓋結果 { for (c = 0; c < size; c++) { printf("%2d ",Matrix[r][c]); } printf(" "); } return 0; }

輸出結果：

D. 棋盤覆蓋問題演算法，pree pascal,幫一下//

type arr1=array[1..65] of integer;
arr2=array[1..65] of arr1;
var board:arr2; tile:integer; size,dr,dc:integer;
procere chessboard(tr,tc:integer; dr,dc:integer; var size:integer);
var t,s:integer;
begin
if (size=1) then exit;
t:=tile; inc(tile);
s:=size div 2;
if (dr<tr+s)and(dc<tc+s) then chessboard(tr,tc,dr,dc,s) else begin
board[tr+s-1,tc+s-1]:=t;
chessboard(tr,tc,tr+s-1,tc+s-1,s);
end;
if (dr<tr+s) and (dc>=tc+s) then chessboard(tr,tc+s,dr,dc,s)
else begin board[tr+s-1][tc+s]:=t;
chessboard(tr,tc+s,tr+s-1,tc+s,s); end;
if (dr>=tr+s) and (dc<tc+s) then chessboard(tr+s,tc+s,dr,dc,s) else begin
board[tr+s][tc+s]:=t; chessboard(tr+s,tc,tr+s,tc+s-1,s); end;
if (dr>=tr+s) and (dc>=tc+s) then chessboard(tr+s,tc+s,dr,dc,s)
else begin board[tr+s][tc+s]:=t; chessboard(tr+s,tc+s,tr+s,tc+s,s); end;
end;
procere prt1(n:integer);
var I,j:integer;
begin
for I:=1 to n do begin
for j:=1 to n do write(board[i,j]:3);
writeln;
end;
end;
begin
writeln('input size(4/8/16/64):');
readln(size); writeln('input the position of special block(x,y):');
readln(dr,dc); board[dr][dc]:=-1;
tile:=1; chessboard(1,1,dr,dc,size); prt1(size);
end.

E. 求NOIP2007普及組初賽試題（棋盤覆蓋問題）的程序解析，比如程序的思路以及每步的作用

聲明：本文使用的代碼和例子的來源：《計算機演算法設計與分析》（王曉東編著，電子工業出版社）。我對代碼做了少許修改，使可以在tc的圖形模式下看到題目的結果。

題目：在一個(2^k)*(2^k)個方格組成的棋盤上，有一個特殊方格與其他方格不同，稱為特殊方格，稱這樣的棋盤為一個特殊棋盤。現在要求對棋盤的其餘部分用L型方塊填滿（註：L型方塊由3個單元格組成。即圍棋中比較忌諱的愚形三角，方向隨意），切任何兩個L型方塊不能重疊覆蓋。L型方塊的形態如下：

■■*■■***■*■
■******■*■■*■■

題目的解法使用分治法，即子問題和整體問題具有相同的形式。我們對棋盤做一個分割，切割一次後的棋盤如圖1所示，我們可以看到棋盤被切成4個一樣大小的子棋盤，特殊方塊必定位於四個子棋盤中的一個。假設如圖1所示，特殊方格位於右上角，我們把一個L型方塊（灰色填充）放到圖中位置。這樣對於每個子棋盤又各有一個「特殊方塊」，我們對每個子棋盤繼續這樣分割，知道子棋盤的大小為1為止。
用到的L型方塊需要（4^k-1)/3 個，演算法的時間是O（4^k)，是漸進最優解法。

F. 棋盤覆蓋問題的演算法分析

設T(k)是演算法ChessBoard覆蓋一個2^k×2^k棋盤所需時間，從演算法的劃分
策略可知，T(k)滿足如下遞推式：
T(k) = 1 當k=0時
T(k) = 4T(k-1) 當k>0時
解此遞推式可得T(k)=O(4^k)。

G. 棋盤覆蓋問題的演算法實現

下面討論棋盤覆蓋問題中數據結構的設計。
（1）棋盤：可以用一個二維數組board[size][size]表示一個棋盤，其中，size=2^k。為了在遞歸處理的過程中使用同一個棋盤，將數組board設為全局變數；
（2）子棋盤：整個棋盤用二維數組board[size][size]表示，其中的子棋盤由棋盤左上角的下標tr、tc和棋盤大小s表示；
（3）特殊方格：用board[dr][dc]表示特殊方格，dr和dc是該特殊方格在二維數組board中的下標;
（4） L型骨牌：一個2^k×2^k的棋盤中有一個特殊方格，所以，用到L型骨牌的個數為(4^k-1)/3，將所有L型骨牌從1開始連續編號，用一個全局變數t表示。
設全局變數t已初始化為0，分治法求解棋盤覆蓋問題的演算法用C++語言描述如下：
void ChessBoard(int tr, int tc, int dr, int dc, int size)
{
int s, t1; //t1表示本次覆蓋所用L型骨牌的編號
if (size == 1) return; //棋盤只有一個方格且是特殊方格
t1 = ++t; // L型骨牌編號
s = size/2; // 劃分棋盤
if (dr < tr + s && dc < tc + s) //特殊方格在左上角子棋盤中
ChessBoard(tr, tc, dr, dc, s); //遞歸處理子棋盤
else{ //用 t1號L型骨牌覆蓋右下角，再遞歸處理子棋盤
board[tr + s - 1][tc + s - 1] = t1;
ChessBoard(tr, tc, tr+s-1, tc+s-1, s);
}
if (dr < tr + s && dc >= tc + s) //特殊方格在右上角子棋盤中
ChessBoard(tr, tc+s, dr, dc, s); //遞歸處理子棋盤
else { //用 t1號L型骨牌覆蓋左下角，再遞歸處理子棋盤
board[tr + s - 1][tc + s] = t1;
ChessBoard(tr, tc+s, tr+s-1, tc+s, s);
}
if (dr >= tr + s && dc < tc + s) //特殊方格在左下角子棋盤中
ChessBoard(tr+s, tc, dr, dc, s); //遞歸處理子棋盤
else { //用 t1號L型骨牌覆蓋右上角，再遞歸處理子棋盤
board[tr + s][tc + s - 1] = t1;
ChessBoard(tr+s, tc, tr+s, tc+s-1, s);
}
if (dr >= tr + s && dc >= tc + s) //特殊方格在右下角子棋盤中
ChessBoard(tr+s, tc+s, dr, dc, s); //遞歸處理子棋盤
else { //用 t1號L型骨牌覆蓋左上角，再遞歸處理子棋盤
board[tr + s][tc + s] = t1;
ChessBoard(tr+s, tc+s, tr+s, tc+s, s);
}
}

H. 棋盤覆蓋問題的演算法可以採用什麼設計來實現

Const dist:array[1..4,1..2] of longint =((-1,0),(0,-1),(0,1),(1,0)); Var f:array[1..50,1..50,1..2] of longint; a,t:array[0..51,0..51] of boolean; m,n,k,i,j,x,y,ans:longint; function find(i,j:longint):boolean; Var k,x,y:longint; begin for k:=1 to 4 do begin x:=i+dist[k,1];y:=j+dist[k,2]; if a[x,y] and t[x,y] then begin t[x,y]:=false; if (f[x,y,1]=0) or find(f[x,y,1],f[x,y,2]) then begin f[x,y,1]:=i; f[x,y,2]:=j; exit(true); end; end; end; exit(false); end; Begin fillchar(a,sizeof(a),0); read(n,m,k); for i:=1 to n do for j:=1 to m do a[i,j]:=true; for i:=1 to k do begin read(x,y); a[x,y]:=false; end; fillchar(f,sizeof(f),0); ans:=0; for i:=1 to n do for j:=1 to m do if odd(i+j) and a[i,j] then begin fillchar(t,sizeof(t),1); if find(i,j) then inc(ans); end; writeln(ans); end.

I. 求noip2007普及組Pascal語言試題

第十三屆全國青少年信息學奧林匹克聯賽初賽試題
（ 普及組 Pascal 語言 二小時完成）
● ● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●●

一、 單項選擇題（共20題，每題1.5分，共計30分。每題有且僅有一個正確答案。）

1． 在以下各項中，（ ）不是CPU的組成部分。
A．控制器 B．運算器 C．寄存器 D．主板

2．在關系資料庫中，存放在資料庫中的數據的邏輯結構以（ ）為主。
A．二叉樹 B．多叉樹 C．哈希表 D．二維表

3．在下列各項中，只有（ ）不是計算機存儲容量的常用單位。
A．Byte B．KB C．UB D．TB

4．ASCII碼的含義是（ ）。
A．二→十進制轉換碼 B．美國信息交換標准代碼
C．數字的二進制編碼 D．計算機可處理字元的唯一編碼

5．一個完整的計算機系統應包括（ ）。
A．系統硬體和系統軟體 B．硬體系統和軟體系統
C．主機和外部設備 D．主機、鍵盤、顯示器和輔助存儲器

6．IT的含義是（ ）。
A．通信技術 B．信息技術 C．網路技術 D．信息學

7．LAN的含義是（ ）。
A．網際網路 B．區域網 C．廣域網 D．城域網

8．冗餘數據是指可以由其它數據導出的數據。例如，資料庫中已存放了學生的數學、語文和英語的三科成績，如果還存放三科成績的總分，則總分就可以看作冗餘數據。冗餘數據往往會造成數據的不一致。例如，上面4個數據如果都是輸入的，由於操作錯誤使總分不等於三科成績之和，就會產生矛盾。下面關於冗餘數據的說法中，正確的是（ ）。
A．應該在資料庫中消除一切冗餘數據
B．用高級語言編寫的數據處理系統，通常比用關系資料庫編寫的系統更容易消除冗餘數據
C．為了提高查詢效率，在資料庫中可以保留一些冗餘數據，但更新時要做相容性檢驗
D．做相容性檢驗會降低效率，可以不理睬資料庫中的冗餘數據

9．在下列各軟體，不屬於NOIP競賽（復賽）推薦使用的語言環境有（ ）。
A．gcc B．g++ C．Turbo C D．Free Pascal

10．以下斷電後仍能保存數據的有（ ）。
A．硬碟 B．高速緩存 C．顯存 D．RAM
11．在下列關於計算機語言的說法中，正確的有（ ）。
A．高級語言比匯編語言更高級，是因為它的程序的運行效率更高
B．隨著Pascal、C等高級語言的出現，機器語言和匯編語言已經退出了歷史舞台
C．高級語言比匯編語言程序更容易從一種計算機上移植到另一種計算機上
D．C是一種面向對象的高級計算機語言

12．近20年來，許多計算機專家都大力推崇遞歸演算法，認為它是解決較復雜問題的強有力的工具。在下列關於遞歸演算法的說法中，正確的是（ ）。
A．在1977年前後形成標準的計算機高級語言「FORTRAN77」禁止在程序使用遞歸，原因之一是該方法可能會佔用更多的內存空間
B．和非遞歸演算法相比，解決同一個問題，遞歸演算法一般運行得更快一些
C．對於較復雜的問題，用遞歸方式編程一般比非遞歸方式更難一些
D．對於已經定義好的標准數學函數 sin(x)，應用程序中的語句「y=sin(sin(x));」就是一種遞歸調用

13．一個無法靠自身的控制終止的循環成為「死循環」，例如，在C語言程序中，語句「while(1) printf(「*」);」就是一個死循環，運行時它將無休止地列印*號。下面關於死循環的說法中，只有（ ）是正確的。
A．不存在一種演算法，對任何一個程序及相應的輸入數據，都可以判斷是否會出現死循環，因而，任何編譯系統都不做死循環檢查
B．有些編譯系統可以檢測出死循環
C．死循環屬於語法錯誤，既然編譯系統能檢查各種語法錯誤，當然也應該能檢查出死循環
D．死循環與多進程中出現的「死鎖」差不多，而死鎖是可以檢測的，因而，死循環也可以檢測的

14．在Pascal語言中，表達式 （23 or 2 xor 5）的值是（ ）。
A．18 B．1 C．23 D．32

15．在Pascal語言中，判斷整數a等於0或b等於0或c等於0的正確的條件表達式是（ ）。
A．not ((a<>0) or (b<>0) or (c<>0))
B．not ((a<>0) and (b<>0) and (c<>0))
C．not ((a=0) and (b=0)) or (c<>0)
D．(a=0) and (b=0) and (c=0)

16．地面上有標號為A、B、C的三根柱，在A柱上放有10個直徑相同中間有孔的圓盤，從上到下依次編號為1，2，3……，將A柱上的部分盤子經過B柱移入C柱，也可以在B柱上暫存。如果B柱上的操作記錄為「進、進、出、進、進、出、出、進、進、出、進、出、出」。那麼，在C柱上，從下到上的編號為（ ）。
A．2 4 3 6 5 7 B．2 4 1 2 5 7 C．2 4 3 1 7 6 D．2 4 3 6 7 5

17．與十進制數1770對應的八進制數是（ ）。
A．3350 B．3351 C．3352 D．3540

18．設A=B=True，C=D=False，一下邏輯運算表達式值為假的有（ ）。
A．(「A∧B)∨(C∧D∨A) B．「(((A∧B)∨C)∧D)
C．A∧(B∨C∨D)∨D D．(A∧(D∨C))∧B

19．(2070)16 + (34)8 的結果是（ ）。
A．（8332）10 B．（208A）16 C．（100000000110）2 D．(20212)8

20．已知7個節點的二叉樹的先根遍歷是1 2 4 5 6 3 7（數字為節點的編號，以下同），中根遍歷是4 2 6 5 1 7 3，則該二叉樹的後根遍歷是（ ）。
A．4 6 5 2 7 3 1 B．4 6 5 2 1 3 7 C．4 2 3 1 5 4 7 D．4 6 5 3 1 7 2

二、問題求解（共2題，每題5分，共計10分）。

1、（子集劃分）將n個數（1，2，…，n）劃分成r個子集。每個數都恰好屬於一個子集，任何兩個不同的子集沒有共同的數，也沒有空集。將不同劃分方法的總數記為S(n,r)。例如，S(4,2)=7，這7種不同的劃分方法依次為{(1),(234)}，{(2),(134)}，{(3),(124)}，{(4),(123)}，{(12),(34)}，{(13),(24)}，{(14),(23)}。當n=6，r=3時，S(6,3)=______________。
（提示：先固定一個數，對於其餘的5個數考慮S(5,3)與S(5,2)，再分這兩種情況對原固定的數進行分析。）

2、（最短路線）某城市的街道是一個很規整的矩形網路（見下圖），有7條南北向的縱街，5條東西向的橫街。現要從西南角的A走到東北角的B，最短的走法共有多少種？___________
B

A

三、閱讀程序寫結果（共4題，每題8分，共計32分。）
1、program j301;
var i,a,b,c,x,y:integer;
p:array[0..4] of integer;
begin
y:=20;
for i:=0 to 4 do read(p[i]);
readln;
a:=(p[0]+p[1])+(p[2]+p[3]+p[4]) div 7;
b:=p[0]+p[1] div ((p[2]+p[3]) div p[4]);
c:=p[0]*p[1] div p[2];
x:=a+b-p[(p[3]+3) mod 4];
if (x>10)
then y:=y+(b*100-a) div (p[p[4] mod 3]*5)
else
y:=y+20+(b*100-c) div (p[p[4] mod 3]*5);
writeln(x,',',y);
end.
{註：本例中，給定的輸入數據可以避免分母為0或數組元素下表越界。}
輸入：6 6 5 5 3 輸出：______________________

2、program j302;
var a,b:integer;
var x,y:^integer;
procere fun(a,b:integer);
var k:integer;
begin k:=a; a:=b; b:=k; end;
begin
a:=3; b:=6;
x:=@a; y:=@b;
fun(x^,y^);
writeln(a,',',b);
end.
輸出：_______________________________

3、program j303;
var a1:array[1..50] of integer;
var i,j,t,t2,n,n2:integer;
begin
n:=50;
for i:=1 to n do a1[i]:=0;
n2:=round(sqrt(n));
for i:=2 to n2 do
if (a1[i]=0) then
begin
t2:=n div i;
for j:=2 to t2 do a1[i*j]:=1;
end;
t:=0;
for i:=2 to n do
if (a1[i]=0) then
begin
write(i:4); inc(t);
if (t mod 10=0) then writeln;
end;
writeln;
end.
輸出：_____________________________________________
_____________________________________________

4、Program j304;
Type str1=string[100];
Str2=string[200];
Var
S1:str1; s2:str2;
Function isalpha(c:char):Boolean;
Var i:integer;
Begin
i:=ord(c);
if ((i>=65) and (i<=90)) or ((i>=97) and (i<=122)) then
isalpha:=true
else isalpha:=false;
end;
function isdigit(c:char):Boolean;
var i:integer;
begin
i:=ord(c); if (i>=48) and (i<=57) then isdigit:=true
else isdigit:=false;
end;
procere expand(s1:str1;var s2:str2);
var i,j:integer; a,b,c:char;
begin
j:=1; c:=char(1); i:=0;
while (i<=ord(s1[0])) do
begin inc(i); c:=s1[i];
if c='-' then begin {1}
a:=s1[i-1]; b:=s1[i+1];
if (isalpha(a) and isalpha(b)) or (isdigit(a) and isdigit(b)) then begin
dec(j);
while (ord(upcase(a))<ord(upcase(s1[i+1]))) do
begin
s2[j]:=a; inc(j); inc(a); end;
end
else
begin s2[j]:=c; inc(j); end;
end{1}
else begin s2[j]:=c; inc(j); end; end; s2[0]:=char(j-2); end;
begin readln(s1); expand(s1,s2); writeln(s2);
end.

輸入：wer2345d-h454-82qqq 輸出：__________________________
四、完善程序（前4空，每空2.5分，後6空，每空3分，共28分）。
1、（求字元的逆序）下面的程序的功能是輸入若干行字元串，每輸入一行，就按逆序輸出該行，最後鍵入-1終止程序。
請將程序補充完整。
Program j401;
type str1=string[100];
var line:str1; kz:integer;
procere reverse(var s:str1);
var I,j:integer; t:char;
begin
i:=1; j:=length(s);
while (i<j) do begin
t:=s[i]; s[i]:=s[j]; s[j]:=t;
__________;____________ ;
end;
end;
begin
writeln(『continue? -1 for end.』);
readln(kz);
while ( ___________)do
begin
readln(line);
__________;
writeln(line);
writeln(『continue? -1 for end.』);
readln(kz);
end;
end.

2 2 3 3
2 -1 1 3
4 1 1 5
4 4 5 5
2、（棋盤覆蓋問題）在一個2k×2 k個方格組成的棋盤中恰有一個方格與其它方格不同（圖中標記為-1的方格），稱之為特殊方格。現用L型（佔3個小方格）紙片覆蓋棋盤上除特殊方格的所有部分，各紙片不得重疊，於是，用到的紙片數恰好是（4 k-1）/3。在下表給出的一個覆蓋方案中，k=2，相同的3各數字構成一個紙片。
下面給出的程序使用分治法設計的，將棋盤一分為四，依次處理左上角、右上角、左下角、右下角，遞歸進行。請將程序補充完整。

Program j402;
type arr1=array[1..65] of integer;
arr2=array[1..65] of arr1;
var board:arr2; tile:integer; size,dr,dc:integer;
procere chessboard(tr,tc:integer; dr,dc:integer; var size:integer);
var t,s:integer;
begin
if (size=1) then ____________;
t:=tile; inc(tile);
s:=size div 2;
if then chessboard(tr,tc,dr,dc,s) else begin
board[tr+s-1]:=t;
______________;
end;
if (dr<tr+s) and (dc>=tc+s) then chessboard(tr,tc+s,dr,dc,s)
else begin board[tr+s-1][tc+s]:=t;
______________; end;
if (dr>=tr+s) and (dc<tc+s) then chessboard(tr+s,tc+s,dr,dc,s) else begin
board[tr+s][tc+s]:=t;
______________; end;
if (dr>=tr+s) and (dc>=tc+s) then chessboard(tr+s,tc+s,dr,dc,s)
else begin board[tr+s][tc+s]:=t;
______________; end;
end;
procere prt1(n:integer);
var I,j:integer;
begin
for I:=1 to n do begin
for j:=1 to n do write(board[i][j]:3);
writeln;
end;
end;
begin
writeln(『input size(4/8/16/64):』);
readln(size); writeln(『input the position of special block(x,y):』);
readln(dr,dc); board[dr][dc]:=-1;
tile:=1; chessboard(1,1,dr,dc,size); prt1(size);
end.