约瑟夫问题和八皇后问题求解

经典算法问题

《数据结构》课程设计

实验报告

题目约瑟夫问题和八皇后问题求解学院计算机科学系

专业计算机科学与技术

班级（4）

学号2009210570

学生姓名万奔

同组成员杨再财谭献龙

指导教师蔡霞

编写日期2010年11月

目录

经典算法问题

一、问题描述 (1)

二、问题分析 (1)

三、数据结构描述 (2)

四、算法设计 (2)

五、详细程序清单 (5)

六、程序运行结果 (9)

七、心得体会 (11)

八、参考资料 (11)

经典算法问题

一、问题描述

1、约瑟夫问题描述

编号为1，2… n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。

2、八皇后问题描述

在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相"冲"

（在每一横列竖列斜列只有一个皇后）。设计程序输出所有可能的解。

3、界面设计模块问题描述

设计一个菜单式界面，让用户可以选择要解决的问题，同时可以退出程序。界面要求简洁明了，大方得体，便于用户的使用，同时，对于用户的错误选择可以进行有效的处理。

二、问题分析

本人负责的是为用户设计菜单界面，使用户可以根据菜单进行选择其中的某个问题进行处理。对于一个菜单界面，首先要求界面简单明了，使得用户可以轻松通过界面知道如何获取自己想要的操作。其次，我们不能保证用户每次的选择都是有效的，即用户的选择是在我们提供的服务范围之内，所以要设计容错操作，即当用户的选择超出我们提供的范围时，提示用户重新选择。最后，要保证用户选择相应的操作后，程序能正确的按照用户的选择运行下去，完成用户的要求。并且有退出功能。

1

经典算法问题

三、数据结构描述

1、int choice;

//记录用户的选择，然后选择相应的操作。

2、typedef struct LNode{

int data;

int code;

struct LNode *next

}node,*linklist;

//约瑟夫环问题单链表结构。

3、int a[8]; //棋盘列状态

int b[15]; //棋盘主对角线状态

int c[15]; //棋盘从对角线状态

int d[8][8]; //存放棋盘

2

经典算法问题

3 四、算法设计

1.程序功能模块图

2. 算法设计

/*---------------------------- 主菜单 ----------------------------*/

void menu(){

printf(" 欢迎登入\n");

printf(" **************************************************\n");

printf(" 1.约瑟夫环问题 *\n");

printf(" 2.八皇后问题运果 *\n");

printf(" 3.退出 *\n");

printf(" ****************************************************\n"); }

主菜单

约瑟夫问题 八皇后问题 Exit(0)退出 Creat

start(

)创

建单

循环

链表 Chulie()在单循环链表中出列 建立主函数lianbiao()并输入人数 Queen start()棋盘初始化 Putchess()进入递归函数 Show()输出整个棋盘结果 Check()判断一个点是否能放棋子 TakePosit ion()如无冲突，就占据一个棋格 Leaveposi tion()将前一次放置的棋子移走

经典算法问题

/*----------------------------Main：主函数。----------------------------*/ void main()

{

int choice;

menu();

printf(" 请选择:");

scanf("%d",&choice);

while(choice)

{

switch(choice)

{

case 1: lianbiao();getch();break;

case2: Queenstart();putchess(1);getch();break;

case 3: exit(0);

default:printf(" 选择无效，请重新选择!");getch();break;

}

menu();

printf(" 请选择：");

scanf("%d",&choice);

}

}

4

经典算法问题

五、详细程序清单

#include<stdio.h>

#include<conio.h>

#include<malloc.h>

//八皇后问题

int count;int m,n;

int a[8];

int b[15];

int c[15];

int d[8][8];

int check(int i,int j);

void putchess(int i);

void takeposition(int i, int j);

void leaveposition(int i, int j);

void show( void );

void Queenstart(void)

{

count = 0;

for(m=0;m<8;m++)

{

a[m]=0;

for(n=0;n<8;n++)

{ d[m][n]=0; }

}

for(m=0;m<15;m++)

{

b[m]=0;

c[m]=0;}

}

void putchess(int i)

{

int j;

if(i<8)

{

for(j=1;j<=8;j++)

{

if(1==check(i,j))

{

takeposition(i,j);

putchess(i+1);

leaveposition(i,j);

}

5

经典算法问题

}

}

else if(8==i)

{

for(j=1;j<=8;j++)

{

if(1==check(i,j))

{

takeposition(i,j);

show();

leaveposition(i,j);

}

}

}

}

int check(int i,int j)

{

if(0==a[j-1] && 0==b[i+j-2] && 0==c[i-j+7]) {

return 1;

}

else

{

return 0;

}

}

void takeposition(int i, int j)

{

a[j-1]=1;

b[i+j-2]=1;

c[i-j+7]=1;

d[i-1][j-1]=1;

}

void leaveposition(int i, int j)

{

a[j-1]=0;

b[i+j-2]=0;

c[i-j+7]=0;

d[i-1][j-1]=0;

}

void show( )

{

count++;

printf(" %d\n",count);

6

经典算法问题

for(m=0;m<8;m++)

{

for(n=0;n<8;n++)

{

if(0==d[m][n])

printf("*");

else

printf("@");

}

printf("\n");

}

printf("\n");

}

//约瑟夫环问题

typedef struct LNode{

int data;

int code;

struct LNode *next

}node,*linklist;;

linklist creatstart(linklist L,int number)

{

int m,i;

linklist s,p;

s=L;

for(i=1;i<=number;i++)

{

p=(linklist)malloc(sizeof(node));

if(!p) exit(0);

p->data=i;

printf("please inp …… 此处隐藏：3858字，全部文档内容请下载后查看。喜欢就下载吧 ……