计算机算法设计及分析课程设计报告.doc

-
. z
成 绩 评 定 表
学生
吴旭东
班级**
1309010236
专 业
信息与计算科学
设计
将2^k * 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：
左上的子棋盘〔假设不存在特殊方格〕----则将该子棋盘右下角的那个方格假设为特殊方格
右上的子棋盘〔假设不存在特殊方格〕----则将该子棋盘左下角的那个方格假设为特殊方格
左下的子棋盘〔假设不存在特殊方格〕----则将该子棋盘右上角的那个方格假设为特殊方格
右下的子棋盘〔假设不存在特殊方格〕----则将该子棋盘左上角的那个方格假设为特殊方格
当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上一样的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。
。

-
. z
*include<>
int tile=1;
int board[100][100];
void chessBoard(int tr, int tc, int dr, int dc, int size)
{
if(size==1)
return;
int t=tile++;
int s=size/2;
if(dr<tr+s && dc<tc+s)
chessBoard(tr, tc, dr, dc, s);
else
{
board[tr+s-1][tc+s-1]=t;
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
{
board[tr+s-1][tc+s]=t;
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
{
board[tr+s][tc+s-1]=t;
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
{
board[tr+s][tc+s]=t;
chessBoard(tr+s, tc+s, tr+s, tc+s, s);
}
}
int main()
{
int size;
cout<<"输入棋盘的size(大小必须是2的n次幂): ";
cin>>size;
int inde*_*,inde*_y;
-
. z
cout<<"输入特殊方格位置的坐标: ";
cin>>inde*_*>>inde*_y;
chessBoard(0,0,inde*_*,inde*_y,size);
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
cout<<board[i][j]<<"\t";
cout<<endl; 
} 
}


设T〔n〕是算法ChessBoard覆盖一个2^k*2^k棋盘所需要的时间，则从算法
-
. z
的分治策略可知，T(k)满足如下递归方程T(k)={O(1) k=0
4T(k-1)+O〔1〕k>0
解得此递归方程可得T(k)=O〔4^k〕。由于覆盖一个2^k*2^k棋盘所需的L型
牌个数为〔4^k — 1〕/3,故算法ChessBoard是一个在渐进意义下最优的算法.
-
.