关于棋盘覆盖问题的算法C++ 当文网提供Word文件下载.docx
- 文档编号:3032653
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:15
- 大小:23.85KB
关于棋盘覆盖问题的算法C++ 当文网提供Word文件下载.docx
《关于棋盘覆盖问题的算法C++ 当文网提供Word文件下载.docx》由会员分享,可在线阅读,更多相关《关于棋盘覆盖问题的算法C++ 当文网提供Word文件下载.docx(15页珍藏版)》请在冰点文库上搜索。
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);
}
dc>
=tc+s)
chessBoard(tr,tc+s,dr,dc,s);
board[tr+s-1][tc+s]=t;
chessBoard(tr,tc+s,tr+s-1,tc+s,s);
if(dr>
=tr+s&
chessBoard(tr+s,tc,dr,dc,s);
board[tr+s][tc+s-1]=t;
chessBoard(tr+s,tc,tr+s,tc+s-1,s);
chessBoard(tr+s,tc+s,dr,dc,s);
board[tr+s][tc+s]=t;
chessBoard(tr+s,tc+s,tr+s,tc+s,s);
}
voidmain()
intsize;
cout<
<
"
输入棋盘的size(大小必须是2的n次幂):
"
;
cin>
>
size;
intindex_x,index_y;
输入特殊方格位置的坐标:
index_x>
index_y;
chessBoard(0,0,index_x,index_y,size);
for(inti=0;
i<
i++)
for(intj=0;
j<
j++)
cout<
board[i][j]<
\t"
cout<
endl;
}
关于棋盘覆盖问题的算法(C++)
//程序说明:
1):
讲一下代码拷贝到vc6.0(或其他支持的IDE环境)下,执行后会生成一个
//input.txt文件,打开将里面的参数换成你想设计的再执行程序就OK了!
//2):
如果对代码理解不透,建议使用但不调试,检测每一步的执行情况
//3):
本程序仅供学习参考使用,用完请删除
stdio.h>
fstream.h>
iomanip.h>
stdlib.h>
inttile=0;
//定义全局变量tile表示L型骨牌编号
int**chessarr;
//定义全局变量chessarr表示棋盘数组
voidchessboard(introw0,intcol0,intsize,intsprow,intspcol);
//棋盘覆盖函数
//row0,col0为棋盘左上角位置,sprow,spcol为特殊方格位置
//size为棋盘规模
voidchessboard(introw0,intcol0,intsize,intsprow,intspcol)//棋盘覆盖函数
if(size==1)return;
//如果棋盘规模=1,返回
//分割棋盘
intt=++tile;
//L型骨牌编号加1
//处理左上角子棋盘
if(sprow<
row0+s&
spcol<
col0+s)
chessboard(row0,col0,s,sprow,spcol);
chessarr[row0+s-1][col0+s-1]=t;
chessboard(row0,col0,s,row0+s-1,col0+s-1);
//处理右上角子棋盘
spcol>
=col0+s)
chessboard(row0,col0+s,s,sprow,spcol);
chessarr[row0+s-1][col0+s]=t;
chessboard(row0,col0+s,s,row0+s-1,col0+s);
//处理左下角子棋盘
if(sprow>
=row0+s&
chessboard(row0+s,col0,s,sprow,spcol);
chessarr[row0+s][col0+s-1]=t;
chessboard(row0+s,col0,s,row0+s,col0+s-1);
//处理右下角子棋盘
chessboard(row0+s,col0+s,s,sprow,spcol);
chessarr[row0+s][col0+s]=t;
chessboard(row0+s,col0+s,s,row0+s,col0+s);
intk,x,y;
//阶数及特殊点位置
inti,j,n;
//棋盘规模为n*n
ifstreamin("
input.txt"
);
//打开输入文件
if(in.fail())
cout<
theinput.txtisnotexist!
exit
(1);
in>
k>
x>
y;
//读入阶数k和特殊方格位置
in.close();
//关闭输入文件
if(k<
1)
K<
1,Errorinput.txt!
exit
(1);
for(i=0,n=1;
k;
n*=2;
//在堆内存中建立棋盘数组,填充特殊方格
if((chessarr=newint*[n])==NULL)
Can'
tallocatemorememory,terminating."
<
endl;
for(i=0;
n;
i++)
if((chessarr[i]=newint[n])==NULL)
chessarr[x-1][y-1]=0;
//填写特殊方格
tile=0;
chessboard(0,0,n,x-1,y-1);
//进行棋盘覆盖,左上角位置0,0;
棋盘宽度n;
特殊点x,y
ofstreamout("
output.txt"
//创建输出文件
//同时输出到文件和屏幕
for(j=0;
j++)
out<
setw(5)<
chessarr[i][j];
out.close();
//关闭输出文件
//释放内存
for(i=0;
delete[]chessarr[i];
delete[]chessarr;
return;
矩阵快速乘法
矩阵相乘在3D变换中是被频繁用到的一种计算,但在矩阵相乘过程中用到了大量的乘法运算,而cpu中运算单元对于乘法的效率是比较低的,远低于加法运算,所以,如果能找到一种用加法来替代乘法的方法实现矩阵相乘,将能大大提高我们程序的效率。
我们的确有这种方法,这就是网上甚为流行的斯特拉森矩阵乘法,它是由v.斯特拉森在1969年提出的一个方法。
下面对其进行详细介绍.
一,推导
对于二阶矩阵
A=[a11a12]
[a21a22]
B=[b11b12]
[b21b22]
先计算下面7个量
(1)
x1=(a11+a22)*(b11+b22);
x2=(a21+a22)*b11;
x3=a11*(b12-b22);
x4=a22*(b21-b11);
x5=(a11+a12)*b22;
x6=(a21-a11)*(b11+b12);
x7=(a12-a22)*(b21+b22);
再设C=AB。
根据矩阵相乘的规则,C的各元素为
(2)
c11=a11*b11+a12*b21
c12=a11*b12+a12*b22
c21=a21*b11+a22*b21
c22=a21*b12+a22*b22
比较
(1)
(2),C的各元素可以表示为(3)
c11=x1+x4-x5+x7
c12=x3+x5
c21=x2+x4
c22=x1+x3-x2+x6
根据以上的方法,以及分块矩阵相乘的性质,我们就可以计算4阶矩阵了,先将4阶矩阵A和B划分成四块2阶矩阵,分别利用公式计算它们的乘积,再使用
(1)(3)来计算出最后结果。
A4=[ma11ma12]
[ma21ma22]
B4=[mb11mb12]
[mb21mb22]
其中
ma11=[a11a12]
ma12=[a13a14]
[a23a24]
ma21=[a31a32]
[a41a42]
ma22=[a33a34]
[a43a44]
mb11=[b11b12]
[b21b22]
mb12=[b13b14]
[b23b24]
mb21=[b31b32]
[b41b42]
mb22=[b33b34]
[b43b44]
二,实现
typedeffloatMatrix22[2][2];
typedeffloatMatrix44[4][4];
inlinevoidMatrix22MulMatrix22(Matrix22c,constMatrix22&
a,constMatrix22&
b)
floatx1=(a[0][0]+a[1][1])*(b[0][0]+b[1][1]);
floatx2=(a[1][0]+a[1][1])*b[0][0];
floatx3=a[0][0]*(b[0][1]-b[1][1]);
floatx4=a[1][1]*(b[1][0]-b[0][0]);
floatx5=(a[0][0]+a[0][1])*b[1][1];
floatx6=(a[1][0]-a[0][0])*(b[0][0]+b[0][1]);
floatx7=(a[0][1]-a[1][1])*(b[1][0]+b[1][1]);
c[0][0]=x1+x4-x5+x7;
c[0][1]=x3+x5;
c[1][0]=x2+x4;
c[1][1]=x1+x3-x2+x6;
inlinevoidMatrix44MulMatrix44(Matrix44c,constMatrix44&
a,constMatrix44&
Matrix22x[7];
//(ma11+ma22)*(mb11+mb22)
Matrix22a0={a[0][0]+a[2][2],a[0][1]+a[2][3],a[1][0]+a[3][2],a[1][1]+a[3][3]};
Matrix22b0={b[0][0]+b[2][2],b[0][1]+b[2][3],b[1][0]+b[3][2],b[1][1]+b[3][3]};
Matrix22MulMatrix22(x[0],a0,b0);
//(ma21+ma22)*mb11
Matrix22a1={a[2][0]+a[2][2],a[2][1]+a[2][3],a[3][0]+a[3][2],a[3][1]+a[3][3]};
Matrix22b1={b[0][0],b[0][1],b[1][0],b[1][1]};
Matrix22MulMatrix22(x[1],a1,b1);
//ma11*(mb12-mb22)
Matrix22a2={a[0][0],a[0][1],a[1][0],a[1][1]};
Matrix22b2={b[0][2]-b[2][2],b[0][3]-b[2][3],b[1][2]-b[3][2],b[1][3]-b[3][3]};
Matrix22MulMatrix22(x[2],a2,b2);
//ma22*(mb21-mb11)
Matrix22a3={a[2][2],a[2][3],a[3][2],a[3][3]};
Matrix22b3={b[2][0]-b[0][0],b[2][1]-b[0][1],b[3][0]-b[1][0],b[3][1]-b[1][1]};
Matrix22MulMatrix22(x[3],a3,b3);
//(ma11+ma12)*mb22
Matrix22a4={a[0][0]+a[0][2],a[0][1]+a[0][3],a[1][0]+a[1][2],a[1][1]+a[1][3]};
Matrix22b4={b[2][2],b[2][3],b[3][2],b[3][3]};
Matrix22MulMatrix22(x[4],a4,b4);
//(ma21-ma11)*(mb11+mb12)
Matrix22a5={a[2][0]-a[0][0],a[2][1]-a[0][1],a[3][0]-a[1][0],a[3][1]-a[1][1]};
Matrix22b5={b[0][0]+b[0][2],b[0][1]+b[0][3],b[1][0]+b[1][2],b[1][1]+b[1][3]};
Matrix22MulMatrix22(x[5],a5,b5);
//(ma12-ma22)*(mb21+mb22)
Matrix22a6={a[0][2]-a[2][2],a[0][3]-a[2][3],a[1][2]-a[3][2],a[1][3]-a[3][3]};
Matrix22b6={b[2][0]+b[2][2],b[2][1]+b[2][3],b[3][0]+b[3][2],b[3][1]+b[3][3]};
Matrix22MulMatrix22(x[6],a6,b6);
//第一块
c[0][0]=x[0][0][0]+x[3][0][0]-x[4][0][0]+x[6][0][0];
c[0][1]=x[0][0][1]+x[3][0][1]-x[4][0][1]+x[6][0][1];
c[1][0]=x[0][1][0]+x[3][1][0]-x[4][1][0]+x[6][1][0];
c[1][1]=x[0][1][1]+x[3][1][1]-x[4][1][1]+x[6][1][1];
//第二块
c[0][2]=x[2][0][0]+x[4][0][0];
c[0][3]=x[2][0][1]+x[4][0][1];
c[1][2]=x[2][1][0]+x[4][1][0];
c[1][3]=x[2][1][1]+x[4][1][1];
//第三块
c[2][0]=x[1][0][0]+x[3][0][0];
c[2][1]=x[1][0][1]+x[3][0][1];
c[3][0]=x[1][1][0]+x[3][1][0];
c[3][1]=x[1][1][1]+x[3][1][1];
//第四块
c[2][2]=x[0][0][0]-x[1][0][0]+x[2][0][0]+x[5][0][0];
c[2][3]=x[0][0][1]-x[1][0][1]+x[2][0][1]+x[5][0][1];
c[3][2]=x[0][1][0]-x[1][1][0]+x[2][1][0]+x[5][1][0];
c[3][3]=x[0][1][1]-x[1][1][1]+x[2][1][1]+x[5][1][1];
三,分析
在标准的定义算法中我们需要进行n*n*n次乘法运算,新算法中我们需要进行7log2n次乘法,对于最常用的4阶矩阵:
原算法新算法
加法次数4872(48次加法,24次减法)
乘法次数6449
需要额外空间16*sizeof(float)28*sizeof(float)(+2*4*7*sizeof(float))
新算法要比原算法多了24次减法运算,少了15次乘法。
但因为浮点乘法的运算速度要远远慢于加/减法运算,所以新算法的整体速度有所提高。
四,其他
这里列出了按通常公式计算矩阵乘法的函数,以作参考。
感谢我的女朋友帮我完成了这两个函数:
)值得一提的是我女朋友是学文科的,从不知道什么是矩阵,当然也没写过程序,但在我稍微指点了一下后,等我洗漱完回来,她已经写好了,经检查测试通过,把她高兴的...
inlinevoidMatrix22MulMatrix22_(Matrix22c,constMatrix22&
c[0][0]=a[0][0]*b[0][0]+a[0][1]*b[1][0];
c[0][1]=a[0][0]*b[0][1]+a[0][1]*b[1][1];
c[1][0]=a[1][0]*b[0][0]+a[1][1]*b[1][0];
c[1][1]=a[1][0]*b[0][1]+a[1][1]*b[1][1];
inlinevoidMatrix44MulMatrix44_(Matrix44c,constMatrix44&
c[0][0]=a[0][0]*b[0][0]+a[0][1]*b[1][0]+a[0][2]*b[2][0]+a[0][3]*b[3][0];
c[0][1]=a[0][0]*b[0][1]+a[0][1]*b[1][1]+a[0][2]*b[2][1]+a[0][3]*b[3][1];
c[0][2]=a[0][0]*b[0][2]+a[0][1]*b[1][2]+a[0][2]*b[2][2]+a[0][3]*b[3][2];
c[0][3]=a[0][0]*b[0][3]+a[0][1]*b[1][3]+a[0][2]*b[2][3]+a[0][3]*b[3][3];
c[1][0]=a[1][0]*b[0][0]+a[1][1]*b[1][0]+a[1][2]*b[2][0]+a[1][3]*b[3][0];
c[1][1]=a[1][0]*b[0][1]+a[1][1]*b[1][1]+a[1][2]*b[2][1]+a[1][3]*b[3][1];
c[1][2]=a[1][0]*b[0][2]+a[1][1]*b[1][2]+a[1][2]*b[2][2]+a[1][3]*b[3][2];
c[1][3]=a[1][0]*b[0][3]+a[1][1]*b[1][3]+a[1][2]*b[2][3]+a[1][3]*b[3][3];
c[2][0]=a[2][0]*b[0][0]+a[2][1]*b[1][0]+a[2][2]*b[2][0]+a[2][3]*b[3][0];
c[2][1]=a[2][0]*b[0][1]+a[2][1]*b[1][1]
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 关于棋盘覆盖问题的算法C+ 当文网提供 关于 棋盘 覆盖 问题 算法 C+ 提供