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

数据结构 课程设计 实验报告 题 目 约瑟夫问题和八皇后问题求解 学 院 专 业 班 级 学 号 学生姓名 同组成员 指导教师 编写日期 2010 年 7 月 16 日 目目 录录 一 一 问题问题描述描述 1 二 二 问题问题分析分析 1 三 三 数数据据结结构构描述描述 2 四 算法四 算法设计设计 2 五 五 详细详细程序程序清清单单 5 六 程序六 程序运运行行结结果果 9 七 七 心得体会心得体会 11 八 八 参考资料参考资料 11 1 一 问题描述一 问题描述 1 约瑟夫问题描述 编号为 1 2 n 的 n 个人按顺时针方向围坐一圈 每人持有一个密码 正整数 一开始任选一个正整数作为报数的上限值 m 从第一个人开始 按顺时针方向自 1 开始顺序报数 报到 m 时停止报数 报 m 的人出列 将 他的密码作为新的 m 值 从他的顺时针方向上的下一个开始重新从 1 报数 如此下去 直至所有人全部出列为止 设计一个程序求出出列顺序 2 八皇后问题描述 在一个 的棋盘里放置 个皇后 要求每个皇后两两之间不相 冲 在每一横列竖列斜列只有一个皇后 设计程序输出所有可能的解 3 界面设计模块问题描述 设计一个菜单式界面 让用户可以选择要解决的问题 同时可以退出 程序 界面要求简洁明了 大方得体 便于用户的使用 同时 对于用户 的错误选择可以进行有效的处理 二 问题分析二 问题分析 本人负责的是为用户设计菜单界面 使用户可以根据菜单进行选择其中的 某个问题进行处理 对于一个菜单界面 首先要求界面简单明了 使得用户可 以轻松通过界面知道如何获取自己想要的操作 其次 我们不能保证用户每次 的选择都是有效的 即用户的选择是在我们提供的服务范围之内 所以要设计 容错操作 即当用户的选择超出我们提供的范围时 提示用户重新选择 最后 要保证用户选择相应的操作后 程序能正确的按照用户的选择运行下去 完成 用户的要求 并且有退出功能 2 三 数据结构描述三 数据结构描述 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 存放棋盘 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 将 前一次放 置的棋子 移走 4 Main 主函数 void main int choice menu printf 请选择 scanf d 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 5 5 详细程序清单详细程序清单 include include include 八皇后问题 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 6 leaveposition i j 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 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 7 count printf d n count 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 idata i printf please input the code of number d i scanf d p next NULL s next p s p s next L next return s 8 void chulie linklist L int number int turn i j linklist p s printf please input the start code scanf d p L printf the turn out of the circle is for i 1 i number 1 i for j 1 jnext printf d p next data turn p next code s p next p next s next free s printf d p next data printf n void lianbiao int number linklist L L linklist malloc sizeof node if L exit 0 printf please input the number of people scanf d L creatstart L number chulie L number 主菜单 void menu printf 欢迎登入 n printf n printf 1 约瑟夫环问题 n printf 2 八皇后问题运行结果 n printf 3 退出 n printf n 9 Main 主函数 void main int choice menu printf 请选择 scanf d while choice switch choice case 1 lianbiao getch break case 2 Queenstart putchess 1 getch break case 3 exit 0 default printf 选择无效 请重新选择 getch break menu printf 请选择 scanf d 六 程序运行结果六 程序运行结果 1 主菜单界面 10 2 约瑟夫问题运行结果 3 八皇后问题运行结果 4 退出界面 按下任意键退出 11 7 心得体会心得体会 通过本次数据结构课程设计 让我又重新温故了大二上半学期所学的数据 结构知识 本次实验本人负责的是程序汇总和八皇后问题的设计 实验过程可 谓困难重重 因为将近一个学期荒废了数据结构 对数据结构的知识或多或少 有些遗忘 现在现学现卖 实是有些难度 不过 我和我的组员不畏困难 努 力学习 互相交流 终于还是把一个完整的 能实现实验要求的程序写了出来 总的来说真是获益匪浅 最深的感受有如下三点 首先 通过本次实验 我不但对以前所学的数据结构知道有了一系列的温 故 而且 在设计八皇后的实验过程中 我对以前的知识的应用又有了提高 可谓更上一层楼 以前所困扰我的函数递归问题 现在对我来说貌似也是可以 理解了 也学习了许多新的知识与编程的思想 我深深感受到 思想对一个问 题编程有多么重要 理解了程序思想 在难的程序也可以是迎刃而解 所以 在今后的学习中 我要更加注重程序思想的培养 多读程序 多写程序 其次 通过实验 我发现我自身许多的不足之处 比如基本功的不扎实 有些很简单 对别人来说几乎是常识的程序语法 我写起来有时也会出错或者 忘记 用一句成语来形容 就是眼高手低 想想自己应该都懂 可是做起来却 困难重重 再加上我的粗心与急躁 我想 没有我队友的帮助与指出 我是很 难以完成这个程序的 也更谈不上一个组长所要