当前位置:首页 >> 其它课程 >> 数据结构课程设计 八皇后问题

数据结构课程设计 八皇后问题






第 一 章 八 皇 后 问 题 概 述 ....................................... - 1 1.1 课 题 的 描 述 ........................................... - 1 1.2 需 求 分 析 ...........................

.................. - 1 1.2.1 涉 及 到 的 知 识 ................................... - 1 1.2.2 模 块 的 功 能 要 求 ................................. - 1 1.2.3 软 硬 件 的 需 求 ................................... - 2 1.2.4 面 对 的 问 题 ..................................... - 2 1.3 概 要 设 计 ............................................. - 2 1.3.1 结 构 设 计 理 念 ................................... - 2 1.3.2 算 法 流 程 图 ..................................... - 3 1.4 详 细 设 计 和 实 现 ....................................... - 4 1.5 程 序 调 试 ............................................. - 6 1.5.1 问 题 思 考 及 改 进 设 想 ............................. - 6 1.5.2 运 行 与 测 试 ...................................... - 7 1.6 课 设 总 结 ............................................. - 9 第 二 章 n 阶 魔 阵 问 题 概 述 ..................................... - 10 2.1 课 题 的 描 述 .......................................... - 10 2.2 需 求 分 析 ............................................ - 10 2.2.1 涉 及 到 的 知 识 .................................. - 10 2.2.2 模 块 的 功 能 需 求 ................................ - 10 2.2.3 软 硬 件 的 需 求 .................................. - 10 2.2.4 面 对 的 问 题 .................................... - 10 2.3 概 要 设 计 ............................................ - 11 2.3.1 算 法 设 计 理 念 ................................... - 11 2.3.2 函 数 逻 辑 功 能 调 用 图 ............................ - 11 I

2.3.3 算 法 流 程 图 .................................... - 12 2.4 详 细 设 计 和 实 现 ...................................... - 12 2.4.1 代 码 编 写 及 详 细 设 置 ............................. - 12 2.5 程 序 调 试 ............................................ - 15 2.5.1 问 题 思 考 及 改 进 设 想 ............................ - 15 2.5.2 运 行 与 测 试 .................................... - 15 2.6 课 设 总 结 ............................................ - 18 参 考 文 献 .................................................... - 19 结 束 语 ...................................................... - 20 附 录 ...................................................... - 21 -

II

第 1 章 八皇后问题概述

第一章 八皇后问题概述
1.1 课题的描述
八皇后问题是一个古老而著名的问题,该问题是十九世纪著名的数学 家 高 斯 1850 年 提 出 的 。 八 皇 后 问 题 是 在 8*8 的 国 际 象 棋 棋 盘 上 , 安 放 8 皇 后 ,要 求 没 有 一 个 皇 后 能 够“ 吃 掉 ”任 何 其 他 一 个 皇 后 ,即 没 有 两 个 或 两 个 以上的皇后占据棋盘上的同一行、 同一列、或同一对角线。 到 了 现 代 ,随 着 计 算 机 技 术 的 飞 速 发 展 ,这 一 古 老 而 有 趣 的 数 学 游 戏 问 题 也 自 然 而 然 的 被 搬 到 了 计 算 机 上 。运 用 所 学 计 算 机 知 识 来 试 着 解 决 这 个 问 题 是 个 锻 炼 和 提 高 我 自 己 编 程 能 力 和 独 立 解 决 问 题 能 力 的 好 机 会 ,可 以 使 我 增强信心,为我以后的编程开个好头,故我选择了这个有趣的课题。

1.2 需求分析
1.2.1 涉及到的知识
本 次 课 程 设 计 中 , 用 到 的 主 要 知 识 有 : 递 归 法 的 运 用 , for 语 句 的 灵 活 运用,数据结构中树知识的灵活运用、栈及数组的有关知识的掌握。 要 求 熟 练 运 用 C++语 言 、 基 本 算 法 的 基 础 知 识 , 独 立 编 制 一 个 具 有 中 等 难 度 的 、解 决 实 际 应 用 问 题 的 应 用 程 序 。通 过 对 题 意 的 分 析 与 计 算 ,用 递 归 法 回 溯 法 及 枚 举 法 解 决 八 皇 后 是 比 较 适 合 的 。递 归 是 一 种 比 较 简 单 的 且 比 较 古 老 的 算 法 。回 溯 法 是 递 归 法 的 升 华 ,在 用 来 求 问 题 的 所 有 解 时 ,要 回 溯 到 根 ,且 根 结 点 的 所 有 子 树 都 已 被 搜 索 遍 才 结 束 。而 枚 举 法 ,更 是 一 种 基 础 易 懂 简 洁 的 方 法 。把 它 们 综 合 起 来 ,就 构 成 了 今 天 的 算 法 。不 论 用 什 么 法 做 这 个课题,重要的就是先搞清楚哪个位置是合法的放皇后的位置,哪个不能, 要先判断,后放置。

1.2.2 模块的功能要求
当 运 行 程 序 时 ,在 屏 幕 上 显 示 每 一 种 方 法 八 个 皇 后 的 相 对 位 置 ,要 用 比 较直观的界面显示。 : 定每一列放一个皇后, 会造成列上的冲突; 行: 列 规 不 当 第 I 行 被 某 个 皇 后 占 领 后 ,则 同 一 行 所 不 能 再 放 皇 后 ,要 把 以 I 为 下 标 的

-1-

经济管理学院本科课程设计论文

标 记 置 为 被 占 领 状 态 ;对 角 线 :对 角 线 有 两 个 方 向 。在 这 我 把 这 两 条 对 角 线 称 为 : 主 对 角 线 和 从 对 角 线 。 在 同 一 对 角 线 上 的 所 有 点 ( 设 下 标 为 (i,j)) , 要 么 (i+j)是 常 数 ,要 么 (i-j)是 常 数 。因 此 ,当 第 I 个 皇 后 占 领 了 第 J 列 后 , 要 同 时 把 以 (i+j)、 (i-j)为 下 标 的 标 记 置 为 被 占 领 状 态 。 用 数 组 a[I]: a [I]表 示 第 I 个 皇 后 放 置 的 列 ; I 的 范 围 : 1-8;对 角 线 数 组 :b[j](主 对 角 线 ),c[j]( 从 对 角 线 ) ,根 据 程 序 的 运 行 ,去 决 定 主 从 对 角线是否放入皇后。

1.2.3 软硬件的需求
( 1) 系 统 要 求 : win98 以 上 操 作 系 统 ; ( 2) 语 言 平 台 : tc++或 vc++6.0;

1.2.4 面对的问题
(1)列 : 规 定 每 一 列 放 一 个 皇 后 , 不 会 造 成 列 上 的 冲 突 ; 行:当第 I 行被某个皇后占领后,则同一行上的所有空格都不能再放皇 后,要把以 I 为下标的标记置为被占领状态; 对 角 线 :对 角 线 有 两 个 方 向 。在 这 我 把 这 两 条 对 角 线 称 为 :主 对 角 线 和 从 对 角 线 。在 同 一 对 角 线 上 的 所 有 点( 设 下 标 为 (i,j)) ,要 么 (i+j)是 常 数 , 要 么 (i-j)是 常 数 。 此 , 第 I 个 皇 后 占 领 了 第 J 列 后 , 同 时 把 以 (i+j)、 因 当 要 (i-j)为 下 标 的 标 记 置 为 被 占 领 状 态 。 ( 2) 使 用 数 据 结 构 的 知 识 , 用 递 归 法 解 决 问 : 。 数 组 a[I]: a [I]表 示 第 I 个 皇 后 放 置 的 列 ; I 的 范 围 : 1..8; 对 角 线 数 组 :b[j](主 对 角 线 ),c[j]( 从 对 角 线 ) ,根 据 程 序 的 运 行 ,去 决 定主从对角线是否放入皇后;

1.3 概要设计
1.3.1 结构设计理念
( 1) 从 n 列 开 始 摆 放 第 n 个 皇 后 ( 因 为 这 样 便 可 以 符 合 每 一 竖 列 一 个 皇后 的要求) ,先 测 试 当 前 位 置( n,m)是 否 等 于 0( 未 被 占 领 ) 。如 果 是 , 摆 放 第 n 个 皇 后 ,并 宣 布 占 领 ,接 着 进 行 递 归 ;如 果 不 是 ,测 试 下 一 个 位 置 ( n, m+1) 但 是 如 果 当 n<=8, m=8 时 , 发 现 此 时 已 无 法 摆 放 时 , 便 要 , 进 行 回 溯 。从 问 题 的 某 一 种 可 能 出 发 ,搜 索 从 这 种 情 况 能 出 发 ,继 续 搜 索 , 这种不断“回溯”的寻找解的方法,称为“回溯法” 。 ( 2) 使 用 数 组 实 现 回 溯 法 的 思 想 。 ( 3) 当 n>8 时 , 便 打 印 出 结 果 。
-2-

第 1 章 八皇后问题概述

1.3.2 算法流程图

图 1-1 算 法 流 程 图

-3-

经济管理学院本科课程设计论文

序 图 1-1

1.4 详细设计和实现
#include <conio.h> #include <math.h> #include <stdlib.h> #include <stdio.h> #include <iostream.h> #define QUEENS 8 int iCount = 0; int Site[QUEENS]; //!记 录 解 的 序 号 的 全 局 变 量 。 //!记 录 皇 后 在 各 行 上 的 放 置 位 置 的 全 局 数 组 。

void Queen(int n); //!递 归 求 解 的 函 数 。 void Output();//!输 出 一 个 解 。 int IsValid(int n);
-4-

第 1 章 八皇后问题概述

//!判 断 第 n 个 皇 后 放 上 去 之 后 , 是 否 有 〉 冲 突 。 void { cout<<" cout<<" Queen(0); } void Queen(int n) { int i; //!参 数 n 从 0 开 始 , 等 于 8 时 便 试 出 了 一 个 解 , 将 它 return; } /*-----------------Queen: 递 归 放 置 第 n 个 皇 后 , 程 序 的 核 心 !----------------*/ if(n == QUEENS) 输出并回溯。 { 依次试探。 { Site[n] = i; Queen(n + 1); }} //!在 该 行 的 第 i 行 上 放 置 皇 后 。 if(IsValid(n)) //!如 果 放 置 没 有 冲 突 , 就 开 始 下 一 行 的 试 探 。 Output(); for(i = 1 ; i <= QUEENS ; i++) //!n 还 没 到 8, 在 第 n 行 的 各 个 行 上 main() /*----------------------------Main : 主 函 数 。 ----------------------------*/ system("title 管 理 102 孙 海 龙 八 皇 后 问 题 "); "<<"八 皇 后 问 题 : "<<endl; "<<"------------------------------------- "<<endl; //!从 第 0 行 开 始 递 归 试 探 。

getch();//!按 任 意 键 返 回 。

int IsValid(int n) /*------IsValid: 判 断 第 n 个 皇 后 放 上 去 之 后 , 是 否 合 法 , 即 是 否 无 冲 突 。 ------*/ { int i; //!将 第 n 个 皇 后 的 位 置 依 次 于 前 面 n- 1 个 //!两 个 皇 后 在 同 一 列 上 , 返 回 0。 //!两 个 皇 后 在 同 一 对 角 线 上 , for(i = 0 ; i < n ; i++) 皇后的位置比较。 { return 0; if(abs(Site[i] - Site[n]) == (n - i)) 返 回 0。 return 0; } void Output()/*------------Output: 输 出 一 个 解 , 即 一 种 没 有 冲 突 的 放 置 方 案 。 ------------*/ {
-5-

if(Site[i] == Site[n])

}

return 1; //!没 有 冲 突 , 返 回 1。

经济管理学院本科课程设计论文

int i; printf("No.%-5d" , ++iCount); //!输 出 序 号 。 for(i = 0 ; i < QUEENS ; i++)//! 依 次 输 出 各 个 行 上 的 皇 后 的 位 置 , 即 所在的列数。 printf("%d " , Site[i]); cout<<” ” <<endl; }

1.5 程序调试
1.5.1 问题思考及改进设想
在完整程序调试时由于太急于求成导致程序进行循环时出现无法运行 的 问 题 ,逻 辑 错 误 导 致 程 序 死 循 环 或 不 循 环 或 循 环 一 小 部 分 ,后 经 细 心 改 正 后 才 把 调 试 工 作 做 完 。做 程 序 真 的 不 是 三 两 下 就 能 完 美 的 做 好 的 ,正 应 了 那 句话“心急吃不了热豆腐啊” 。 但 对 于 这 个 程 序 我 由 于 c++语 言 学 的 不 到 位 以 至 于 有 些 掺 杂 了 c 语 言 的 有 关 算 法 , 要 是 都 用 c++来 编 写 就 再 好 不 过 了 。 在 编 写 代 码 时 ,我 希 望 能 随 机 选 择 一 数 X(1~ 92)后 ,能 输 出 该 种 情 况 所 对 应 的 八 个 皇 后 的 摆 放 方 式 和 每 个 皇 后 所 在 的 位 置 ,但 想 了 好 久 ,就 是 无 法 实 现 。 而 且 , 当 92 种 情 况 都 输 出 时 , 前 面 的 几 十 种 情 况 无 法 看 到 , 要 想 让 摆 放 皇 后 的 图 形 和 所 在 具 体 的 位 置 一 起 输 出 ,就 得 修 改 程 序 让 使 她 们 一 个 一 个 地 输 出 ,这 样 显 然 比 较 麻 烦 。倘 若 有 一 种 既 能 把 八 皇 后 的 所 在 位 置 和 把 皇 后 所 有 情 况 连 续 输 出 ,我 感 觉 就 应 该 算 是 一 个 完 美 的 程 序 了 ,这 还 需 要 我 一 致的探索发掘下去才行。

-6-

第 1 章 八皇后问题概述

1.5.2 运行与测试
( 1) 由 于 在 编 写 代 码 时 漏 写 了 某 个 函 数 导 致 程 序 不 能 正 常 运 行 出 现 了 错 误提示;

图 1-1 错 误 警 告

( 2) 在 同 学 帮 助 下 成 功 的 运 行 了 该 程 序 ;

图 1-2 成 功 运 行

-7-

经济管理学院本科课程设计论文

( 3) 最 后 输 出 了 最 终 八 皇 后 问 题 的 结 果 。

图 1-3 输 出 八 皇 后 结 果

-8-

第 1 章 八皇后问题概述

1.6 课设总结
通过这次的课程设计,让我了解了八皇后这一经典的问题。同时让我更 好 地 掌 握 了 栈 思 想 以 及 一 维 数 组 等 等 知 识 ,以 及 一 些 书 本 上 没 有 的 东 西 , 这 对 我 以 后 的 学 习 生 涯 以 及 将 来 步 入 社 会 起 到 很 大 的 帮 助 。这 次 课 程 设 计 虽 然 花 了 我 很 多 时 间 和 精 力 , 但 很 值 得 ,因 为 它 对 我 能 力 提 高 起 到 很 大 帮 助 。 这 次 课 程 设 计 也 提 醒 我 以 前 知 识 的 匮 乏 ,它 给 我 敲 响 了 警 钟 ,让 我 意 识 到 自 己 基 础 的 不 扎 实 .当 然 这 次 实 验 还 是 有 很 多 问 题 的 。 比 如 程 序 设 计 的 界 面 不 够 好 , 一 些 程 序 并 非 自 己 所 写 ,而 是 修 改 某 些 程 序 而 成 ,但 这 些 不 该 ,在 下 次 课 程设计时不会再发生. 针 对 八 皇 后 这 个 课 题 ,也 许 表 层 只 局 限 于 对 八 个 皇 后 的 摆 放 ,但 还 可 以 对 更 多 的 情 况 进 行 探 讨 分 析 ,比 如 九 皇 后 ,十 皇 后 等 等 。在 报 告 正 文 中 已 经 多 次 提 到 关 于 N 皇 后 的 设 计 方 法 ,但 只 是 一 带 而 过 ,有 些 问 题 很 难 通 过 一 个 报告设计就轻而易举的得到解决,还需要花费更多的时间。

-9-

第 2 章 n 阶魔阵问题概述

第二章 n 阶魔阵问题概述
2.1 课题的描述
n 阶魔阵问题在我国古代被称作“纵横图” 其主要设计要求是对于给 , 定 的 一 个 奇 数 n, 构 造 一 个 n 阶 魔 阵 。 n 阶 魔 阵 是 一 个 n 阶 方 阵 , 其 元 素 由 自 然 数 1, 2, 3, ? , n^2 组 成 。 魔 阵 每 一 行 元 素 之 和 , 每 一 列 元 素 之 和 , 以及主,副对角线员素质和均相等。

2.2 需求分析
2.2.1 涉及到的知识
本次课程设计中,用到的主要知识有:二维数组的使用方法和一些基 本的设计思路以及数据结构与数据存储的的有关知识。

2.2.2 模块的功能需求
(1)void main( ) 函 数 , 主 函 数 , 调 用 以 下 子 函 数 , 实 现 魔 方 阵 填 充 与 输 出,实现问题要求功能; (2) void jishu( int n) 函 数 , n 为 奇 数 实 现 n 阶 魔 方 阵 ; (3) void out( int n, int a[MAX][MAX]) 函 数 , 此 函 数 用 以 调 整 方 阵 元 素 位 置 , 实 现 魔 方 阵 n*n 形 式 输 出 ( 4) void check( int n, int a[MAX][MAX]) 函 数 , 计 算 并 输 出 n 阶 魔 方 阵 每 行 、每 列 以 及 每 条 对 角 线 上 各 个 数 字 的 累 加 和 ,同 时 验 证 魔 方 阵 的 准 确 性。

2.2.3 软硬件的需求
( 1) 系 统 要 求 : win98 以 上 操 作 系 统 ; ( 2) 语 言 平 台 : tc++或 vc++6.0;

2.2.4 面对的问题
( 1) 每 列 每 行 以 及 主 副 对 角 线 元 素 之 和 相 等 ; ( 2) 要 求 输 出 结 果 的 格 式 要 具 有 n 阶 方 阵 的 形 式 。

- 10 -

经济管理学院本科课程设计论文

2.3 概要设计
2.3.1 算法设计理念
首 先 ,输 入 一 个 数 字 n( 1≤ n≤ 99),则 输 出 对 应 的 n 阶 魔 方 阵 ,并 输 出 每 一 行 、每 一 列 、每 条 对 角 线 上 各 个 数 字 累 加 和 。若 输 入 数 字 n 超 出 要 求 范 围 , 则 提 醒 用 户 重 新 输 入 n。 但若输入数字 0 时,操作结束,退出程序。 使用多维数组输出魔方阵,分别用 3 个子函数实现相应的功能。 输 入 形 式 : 数 字 n( 1≤ n≤ 99)。 输 出 形 式 : 1) 以 矩 阵 形 式 输 出 n( 1≤ n≤ 99)阶 魔 方 阵 ; ( ( 2)输 出 每 一 行 、每 一 列 、每 条 对 角 线 上 各 个 数 字 累 加 和 ;

2.3.2 函数逻辑功能调用图

图 2-1 逻 辑 功 能

- 11 -

第 2 章 n 阶魔阵问题概述

2.3.3 算法流程图

图 2-2 算 法 流 程 图

2.4 详细设计和实现

2.4.1 代码编写及详细设置
void jishu( int n) 函 数 , n 为 奇 数 实 现 n 阶 魔 方 阵 , 实 现 思 想 如 下 ; a.在 1 到 n2 的 数 字 中 , 选 择 1 开 始 填 充 魔 方 , 将 数 字 1 填 入 第 一 行 的 中 间 方 格 中 , 即 ( 0, n/2) 的 位 置 。 b.向 已 填 充 的 前 一 个 数 字 位 置 ( p, q) 的 左 上 角( p-1,q-1)填 入 下 一 个 数 字 ,如 果 出 现 以 下 情 况 ,则 修 改 填 充 位 置 : i) 若 填 充 位 置 超 出 上 边 界 , 则 修 改 为 下 边 界 的 相 应 位 置 , 即 把 p-1 修 改 为 n-1; ii) 若 填 充 位 置 超 出 左 边 界 , 则 修 改 为 最 右 边 的 相 应 位 置 , 即 把 q-1 改 为 n-1;iii)若 填 充 位 置 已 有 数 字 ,则 填 充 位 置 修 改 为 下 一 行 的 同 一 位 置 。 c.重 复 以 上 步 骤 , 直 至 将 n2 个 数 字 全 部 填 入 魔 方 中 。 最 后 调 用 函 数
- 12 -

经济管理学院本科课程设计论文

函 数 out( n,a)和 check( n,a) ,实 现 魔 方 阵 的 输 出 ,检 验 魔 方 阵 的 准 确 性。具体实现代码如下: void jishu(int n)/*奇 数 */ { int p,q,i,a[MAX][MAX]; p=0; q=(n-1)/2; a[0][q]=1;/*第 一 个 数 字 的 填 入 位 置 */ for(i=2;i<=n*n;i++) { p=(p-1+n)%n;/*计 算 填 入 的 位 置 */ q=(q-1+n)%n; if(a[p][q]>0)/*如 果 填 入 位 置 已 有 数 字 , 则 重 新 计 算 填 入 位 置 */ { p=(p+2)%n;/*由 于 前 面 p 减 了 1,因 此 p 应 该 加 1,才 能 表 示 下 一 行 */ q=(q+1)%n;/*由 于 前 面 q 减 了 1,因 此 q 应 该 加 1,才 能 表 示 同 一 列 */ } a[p][q]=i;/*填 入 数 字 */ } out(n,a);/*调 用 输 出 函 数 */ check(n,a);/*调 用 验 证 函 数 */ } (3) void out( int n, int a[MAX][MAX]) 函 数 , 此 函 数 用 以 调 整 方 阵 元 素 位 置 , 实 现 魔 方 阵 n*n 形 式 输 出 。 具 体 实 现 代 码 如 下 : void out(int n,int a[MAX][MAX])/*魔 方 矩 阵 输 出 函 数 */ { int p,q; for(p=0;p<=n-1;p++) { for(q=0;q<=n-1;q++) { cout<<setw(4)<<a[p][q]<<"";/*输 出 魔 方 矩 阵 的 结 果 */ }
- 13 -

第 2 章 n 阶魔阵问题概述

cout<<endl<<endl; } } ( 4) void check( int n, int a[MAX][MAX]) 函 数 , 计 算 并 输 出 n 阶 魔 方 阵 每 行 、每 列 以 及 每 条 对 角 线 上 各 个 数 字 的 累 加 和 ,同 时 验 证 魔 方 阵 的 准确性。具体实现代码如下: void check(int n,int a[MAX][MAX])/*魔 方 矩 阵 验 证 函 数 */ { int p,q,sum1=0,sum2=(n*n+1)*n/2,k; cout<<" 此 魔 方 阵 的 每 行 、 每 列 、 两 条 对 角 线 的 和 为 : "<<sum2<<endl;/*输 出 标 准 魔 方 阵 的 每 行 、 每 列 、 两 条 对 角 线 的 和 */ for(p=0;p<n;p++) { for(q=0;q<n;q++) { sum1=a[p][q]+sum1;/*计 算 矩 阵 横 行 纵 行 的 和 */ } if(sum1!=sum2)/*判 断 矩 阵 横 行 纵 行 的 和 是 否 与 标 准 相 同 */ { cout<<" 横 行 纵 行 计 算 结 果 与 标 准 不 符 , 请 修 改 程 序 错 误 "<<endl; break; } sum1=0; } for(k=0;k<n;k++) { sum1=a[k][k]+sum1;/*计 算 矩 阵 主 对 角 线 的 和 */ } if(sum1!=sum2)/*判 断 矩 阵 主 对 角 线 的 和 是 否 与 标 准 相 同 */ cout<<"主 对 角 线 计 算 结 果 与 标 准 不 符 , 请 修 改 程 序 错 误 "<<endl; sum1=0; for(k=0;k<n;k++) { sum1=a[k][n-k-1]+sum1;/*计 算 矩 阵 次 对 角 线 的 和 */
- 14 -

经济管理学院本科课程设计论文

} if(sum1!=sum2)/*判 断 矩 阵 次 对 角 线 的 和 是 否 与 标 准 相 同 */ cout<<"次 对 角 线 计 算 结 果 与 标 准 不 符 , 请 修 改 程 序 错 误 "<<endl; }

2.5 程序调试
2.5.1 问题思考及改进设想
就编写的程序而言,虽然能达到预期的结果,但总体结构还不够简洁, 不太容易去理解。许多问题还需要继续研究,许多技术还需要更多的改进。 去图书馆借了不少书, 去网上看了些资料, 是对大概的知识有了点了解, 也 只 但 还 是 很 难 着 手 于 写 代 码 ,后 来 就 按 照 老 师 说 的 ,先 搞 清 楚 原 理 ,再 考 虑 如 何 去 实 现 !后 来 又 去 上 网 查 看 相 关 资 料 ,又 到 图 书 馆 借 了 很 多 书 看 ,总 算 有 头 绪 了 。但 在 调 试 过 程 中 ,还 是 遇 到 了 很 多 困 难 ,后 来 通 过 了 很 多 同 学 的 帮 助才把问题解决了。

2.5.2 运行与测 试
( 1) 运 行 顺 利 没 有 发 现 错 误 。

图 2-3 准 确 运 行

- 15 -

第 2 章 n 阶魔阵问题概述

( 2) 输 入 1-99 阶 魔 阵 。

图 2-4 输 入 数 据

( 3) 当 输 入 超 出 范 围 时 , 提 示 输 入 有 误 。

图 2-5 输 入 有 误

- 16 -

经济管理学院本科课程设计论文

( 4) 当 输 入 的 魔 阵 阶 数 为 7 时 得 到 以 下 方 阵 。

图 2-6 正 常 输 入 ( 5) 当 输 入 0 时 该 程 序 结 束 运 行 。

图 2-7 结 束 运 行

- 17 -

第 2 章 n 阶魔阵问题概述

2.6 课设总结
在 编 程 实 现 的 过 程 中,我 进 一 步 掌 握 和 熟 悉 了 二 为 数 组 的 应 用,并 熟 悉 了将问题分解在组装的解决方法和函数的调用。 编 程 过 程 中 , 使 用 另 外 完 成 输 出 功 能 的 子 函 数 void out(int n,int a), 通过对其调用,大大节省了程序编写的复杂度,提高了效率。 在 实 现 奇 数 阶 魔 方 阵 时,遇 到 了 一 点 问 题,请 教 了 同 学,一 起 进 行 了 讨 论研究,最终解决了问题。 通 过 这 次 课 程 设 计 ,使 我 们 学 到 了 一 些 以 前 没 有 学 过 的 知 识 , 使 我 们 对 程序设计有了更深层次的认识和理解,懂得了灵活运用。

- 18 -

参考文献

参考文献
[1] [2] [3] [4] [5] [6] 刘 光 然 ; 数 据 结 构 实 践 训 练 教 程 ; 2009,4 李 春 葆 , 尹 为 民 , 李 蓉 蓉 ; 数 据 结 构 教 程 上 机 实 验 指 导 ; 2009, 1 胡 元 义 , 邓 亚 玲 , 徐 睿 林 ; 数 据 结 构 课 程 辅 导 ; 2003,3 邓 世 华 , 贾 伯 奇 , 黄 学 俊 ; 数 据 结 构 解 析 、 习 题 、 课 程 设 计 ; 2009,9 吕 凤 哲 ,C++语 言 程 序 设 计 ( 第 二 版 ) .北 京 : 电 子 工 业 出 版 社 ,2005 陈 慧 南 .数 据 结 构 — C++语 言 描 述 .北 京 :人 民 邮 电 出 版 社 ,2005.03

- 19 -

结束语

结束语
通 过 这 次 课 程 设 计 ,使 我 们 学 到 了 一 些 以 前 没 有 学 过 的 知 识 ,使 我 们 对 程序设计有了更深层次的认识和理解,懂得了灵活运用。 在 这 次 课 程 设 计 中 ,我 遇 到 了 不 少 问 题 , 包 括 程 序 上 的 和 课 程 设 计 的 撰 写 上 的 ,同 学 曾 给 过 我 许 多 帮 助 ,在 此 我 表 示 对 他 们 的 忠 心 的 感 谢 ,在 他 们 的 帮 助 下 我 才 能 够 顺 利 的 完 成 ,在 此 ,我 仅 以 文 字 的 形 式 表 示 忠 心 感 谢 ,感 谢 他们这么多天对我的帮助。

- 20 -


//n 阶 魔 阵 问 题 源 代 码 #include<iostream.h> #include<iomanip.h> #include<time.h> #define MAX 99/*矩阵最大为 99*99*/ void jishu(int n);



void out(int n,int a[MAX][MAX]);/*魔方矩阵输出函数*/ void check(int n,int a[MAX][MAX]);/*魔方矩阵验证函数*/ void main() { clock_t start,end; int n; while(n!=0)/*判断输出的数 n 是否为 0*/ {

cout<<"************************************************************** **********"<<endl; cout<<"*本程序用于输出 1 到 99 阶魔方阵,即将 1 到 n 平方的数填入 n*n(n 为奇数)的方阵中*"<<endl; cout<<"* *"<<endl; cout<<"* *"<<endl; 当输入 0 时本程序结束 使所有的横行,纵行以及对角线上所有数字之和相等

cout<<"************************************************************** **********"<<endl;
- 21 -

cout<<endl<<"请输入所输出的魔方阶数:"; cin>>n; while(n<1||n>99) { if(n==0) break;/*n=0 本程序结束*/ cout<<"超出范围,请重新输入:"; cin>>n; } if(n==0) break;/*n=0,本程序结束*/ cout<<"所得的魔方阵为:"<<endl; start=clock(); jishu(n); end=clock(); cout<<"所花费的时间为:"<<end-start<<"毫秒"<<endl; } cout<<"谢谢您的使用!"<<endl; }

void jishu(int n)/*奇数*/ { int p,q,i,a[MAX][MAX]; p=0; q=(n-1)/2; a[0][q]=1;/*第一个数字的填入位置*/ for(i=2;i<=n*n;i++)
- 22 -

{ p=(p-1+n)%n;/*计算填入的位置*/ q=(q-1+n)%n; if(a[p][q]>0)/*如果填入位置已有数字,则重新计算填入位置*/ { p=(p+2)%n;/*由于前面 p 减了 1,因此 p 应该加 1,才能表示下一行*/ q=(q+1)%n;/*由于前面 q 减了 1,因此 q 应该加 1,才能表示同一列*/ } a[p][q]=i;/*填入数字*/ } out(n,a);/*调用输出函数*/ check(n,a);/*调用验证函数*/ }

void out(int n,int a[MAX][MAX])/*魔方矩阵输出函数*/ { int p,q; for(p=0;p<=n-1;p++) { for(q=0;q<=n-1;q++) { cout<<setw(4)<<a[p][q]<<"";/*输出魔方矩阵的结果*/ } cout<<endl<<endl; } }

- 23 -

void check(int n,int a[MAX][MAX])/*魔方矩阵验证函数*/ { int p,q,sum1=0,sum2=(n*n+1)*n/2,k; cout<<"此魔方阵的每行、每列、两条对角线的和为:"<<sum2<<endl;/*输出标 准魔方阵的每行、每列、两条对角线的和*/ for(p=0;p<n;p++) { for(q=0;q<n;q++) { sum1=a[p][q]+sum1;/*计算矩阵横行纵行的和*/ } if(sum1!=sum2)/*判断矩阵横行纵行的和是否与标准相同*/ { cout<<"横行纵行计算结果与标准不符,请修改程序错误"<<endl; break; } sum1=0; } for(k=0;k<n;k++) { sum1=a[k][k]+sum1;/*计算矩阵主对角线的和*/ } if(sum1!=sum2)/*判断矩阵主对角线的和是否与标准相同*/ cout<<"主对角线计算结果与标准不符,请修改程序错误"<<endl; sum1=0; for(k=0;k<n;k++) {
- 24 -

sum1=a[k][n-k-1]+sum1;/*计算矩阵次对角线的和*/ } if(sum1!=sum2)/*判断矩阵次对角线的和是否与标准相同*/ cout<<"次对角线计算结果与标准不符,请修改程序错误"<<endl; }

- 25 -

I


更多相关文档:

数据结构课程设计八皇后问题

数据结构课程设计八皇后问题_工学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档数据结构课程设计八皇后问题_工学_高等教育_教育专区。目 录 第一章八...

数据结构课程设计 八皇后问题

数据结构课程设计 八皇后问题_其它课程_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档数据结构课程设计 八皇后问题_其它课程_初中教育_教育专区。八皇后...

数据结构课程设计-八皇后问题

5 1、数据结构课程设计任务书 1.1、题目八皇后 1.2、要求 设计程序解决八皇后问题,设计要求如下: 1:依次输出各种成功的放置方法; 2:画出棋盘的图形界面,并...

数据结构课程设计(八皇后问题)

数据结构课程设计 题 目 八皇后问题求解 羊庆衍 、刘天唱 学生姓名 指导教师 学院 信息学院 信科一班 2014 年 1 月 2 日 专业班级 完成时间 第一章...

八皇后问题数据结构课程设计报告

数据结构课程设计报告八皇后问题 设计任务书 课题 八皇后 名称 1. 2. 3. 4. 调研并熟悉八皇后的基本功能、数据流程与工作规程; 学习八皇后相关的算法和基于 ...

数据结构课程设计-八皇后问题

10 4、总结通过这次的课程设计, 我从中得到了许多经验和软件设计的一些新思路; 从这个八皇后问题 设计以及分析中,本人从中理解到了数据结构对于软件设计的重要性,...

数据结构课程设计(八皇后问题)

数据结构课程设计 八皇后问题 2012 年 3 月 2 日 数据结构课程设计课题: 课题:八皇后问题 学专年 院:计算机科学与信息工程学院 业:计算机科学与技术 级:2010 ...

数据结构课程设计-四、八、N皇后问题

(100) 数据结构与算法-课程设计 106014389 四、八、N 皇后问题 指导教师签名: 1 年 月 日 八皇后问题 摘 要 解决八皇后问题主要利用了递归法、回溯法,以及对...

八皇后问题课程设计报告

软件训练总结报告 软件设计部分一、题目分析本次我的课程设计的题目是八皇后问题...八皇后问题是一个比较有趣,也比较难求解的问题,我结合了数据结构的内容分 析,...

数据结构八皇后问题实习报告

数据结构八皇后问题实习报告_调查/报告_表格/模板_实用文档。数据结构八皇后问题...本课程设计本人的目的也是通过用 WIN-TC 程序设计平台将一个8*8的棋 盘上放...
更多相关标签:
数据结构八皇后问题 | 八皇后问题课程设计 | 八皇后数据结构 | 八皇后 课程设计 | 八皇后 树结构 | 八皇后问题 | 八皇后问题 c语言 | 八皇后问题c |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com