图形化N后问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
深 圳 大 学
实 验 报 告
课程名称: 算法
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
与分析
实验序号: 实验1
实验名称: 图形化N后问题
班 级: 计算机3 姓 名: 卢志敏
同 组 人: 实验日期: 2008 年 12 月 20 日
教师签字:
一、实验目的与要求
1、输入N值;
2、用回溯法求N后问题的所有解，并在图形界面输出其所有向量解;(30%)
3、单击某个向量解给出其图形化的解布局;(35%,包含界面设计) 4、使用Estimate(蒙特卡罗方法)算法，随机取n=2~3条路径估算 回朔法的效率并加以分析、验证。(10%)
二、实验环境
VC6.0
三、实验步骤
(1)回溯算法的实现
(a)为解决这个问题，我们把棋盘的横坐标定为i，纵坐标定为j,i和j的取值范围是
从,到,。当某个皇后占了位置(i,j)时，在这个位置的垂直方向、水平方向和斜线方向都不
能再放其它皇后了。用语句实现，可定义如下三个整型数组:a[8],b[15],c[24]。其中:
a[j-1]=1 第j列上无皇后
a[j-1]=0 第j列上有皇后
b[i+j-2]=1 (i,j)的对角线(左上至右下)无皇后
b[i+j-2]=0 (i,j)的对角线(左上至右下)有皇后
c[i-j+7]=1 (i,j)的对角线(右上至左下)无皇后
c[i-j+7]=0 (i,j)的对角线(右上至左下)有皇后
(b)为第i个皇后选择位置的算法如下:
for(j=1;j<=8;j++) /*第i个皇后在第j行*/
if ((i,j)位置为空)) /*即相应的三个数组的对应元素值为1*/
{占用位置(i,j) /*置相应的三个数组对应的元素值为0*/
if i<8
为i+1个皇后选择合适的位置;
else 输出一个解
}
(2)图形存取
在Turbo C语言中，图形的存取可用如下
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
函数实现:
size=imagesize(x1,y1,x2,y2) ;返回存储区域所需字节数。
arrow=malloc(size);建立指定大小的动态区域位图，并设定一指针arrow。
getimage(x1,y1,x2,y2,arrow);将指定区域位图存于一缓冲区。
putimage(x,y,arrow,copy)将位图置于屏幕上以(x，y)左上角的区域。
(3)源程序
#include
#include
#include
#include
char n[3]={'0','0'};/*用于
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
第几组解*/
int a[8],b[15],c[24],i;
int h[8]={127,177,227,277,327,377,427,477};/*每个皇后的行坐标*/
int l[8]={252,217,182,147,112,77,42,7}; /*每个皇后的列坐标*/
void *arrow;
void try(int i)
{int j;
for (j=1;j<=8;j++)
if (a[j-1]+b[i+j-2]+c[i-j+7]==3) /*如果第i列第j行为空*/
{a[j-1]=0;b[i+j-2]=0;c[i-j+7]=0;/*占用第i列第j行*/
putimage(h[i-1],l[j-1],arrow,COPY_PUT);/*显示皇后图形*/
delay(500);/*延时*/
if(i<8) try(i+1);
else /*输出一组解*/
{n[1]++;if (n[1]>'9') {n[0]++;n[1]='0';}
bar(260,300,390,340);/*显示第n组解*/
outtextxy(275,300,n);
delay(3000);
}
a[j-1]=1;b[i+j-2]=1;c[i-j+7]=1;
putimage(h[i-1],l[j-1],arrow,XOR_PUT);/*消去皇后，继续寻找下一组解*/
delay(500);
}}
int main(void)
{int gdrive=DETECT,gmode,errorcode;
unsigned int size;
initgraph(&gdrive,&gmode,"");
errorcode=graphresult();
if (errorcode!=grOk)
{printf("Graphics error\n");exit(1);}
rectangle(50,5,100,40);
rectangle(60,25,90,33);
/* 画皇冠 */
line(60,28,90,28);line(60,25,55,15);
line(55,15,68,25);line(68,25,68,10);
line(68,10,75,25);line(75,25,82,10);
line(82,10,82,25);line(82,25,95,15);
line(95,15,90,25);
size=imagesize(52,7,98,38); arrow=malloc(size);
getimage(52,7,98,38,arrow); /* 把皇冠保存到缓冲区 */
clearviewport();
settextstyle(TRIPLEX_FONT, HORIZ_DIR, 4);
setusercharsize(3, 1, 1, 1);
setfillstyle(1,4);
for (i=0;i<=7;i++) a=1;
for (i=0;i<=14;i++) b=1;
for (i=0;i<=23;i++) c=1;
for (i=0;i<=8;i++) line(125,i*35+5,525,i*35+5); /* 画棋盘 */
for (i=0;i<=8;i++) line(125+i*50,5,125+i*50,285);
try(1); /* 调用递归函数 */
delay(3000);
closegraph();
free(arrow);
}
实验结论:本实验有一定难度，最后还是勉强完成了，实验过程中体会到了回溯算法的
过程，其运行效率比普通算法要高。
浙公网安备 33021202002483