从八皇后问题的解决方案看面向过程和面向对象.pdf

第26卷第4 常熟理工学院学报（自然科学） Vol.26No.4 2012年4月 JournalofChangshuInstituteTechnology（NaturalSciences） Apr.,2012 从八皇后问题的解决方案看面向过程和面向对象 宋东兴，殷旭东 （常熟理工学院 计算机科学与工程学院，江苏 常熟 215500） 摘 要：通过八皇后问题的解的分析，讨论了面向过程的解决方案和面向对象解决方案的不 同，比较了面向过程设计思想和面向对象设计思想的区别和联系，提出程序设计教学要从面向过 程逐步过渡到面向对象，片面强调一面而忽视另一面都是不可取的. 关键词：八皇后；面向过程；面向对象；对象；解决方案 中图分类号：TP312 文献标识码：A 文章编号：1008-2794 （2012 ）04-0120-05 著名数学家高斯在1850 年提出：在8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个 皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？此即八皇后问题. 八皇后问题可以采用面 向过程和面向对象两种不同的解决方案. [1] 在众多针对“软件危机”的解决方案中，面向对象编程是一种优秀的方法，国内大多数高校的计算机专 业都开设了面向对象的程序设计课程，有的学校大一就直接进入面向对象教学. 然而要完全抛弃传统的面 向过程方法，只接受面向对象方法并不科学，宏观上的面向对象思想从微观上看仍然是面向过程在实现，离 开面向过程的铺垫而直接进入面向对象，学生理解起来往往比较困难，实际教学效果也不理想. 笔者通过八 皇后问题的求解案例，分析比较面向过程和面向对象的不同，提出程序设计教学要从面向过程循序渐进到 面向对象. 1 面向过程的分析方法 1.1 基本思想 以过程作为分析的主题，着重强调一个系统中发生的过程以及由一个过程的结果输出作为下一个过程 输入的数据流动，通过信息流及其状态转换来认识系统，采用的是“自顶向下，逐步求精”的思维方法，核心思 想是：以事件为中心，分析解决问题的步骤，然后用函数把这些步骤一步一步实现，使用时依次调用就可以了. 1.2 八皇后问题的面向过程的解决方案 需要使用各种数据结构来保持棋子的位置，算法通过系统地控制每一个数据结构的数值，检测每个新 位置是否符合没有皇后攻击其他皇后的原则来解决问题. 1.2.1 穷举法 解决八皇后问题的关键在于： （1）找到合理的数据结构存放棋子的摆放位置. 收稿日期：2012-02-23 作者简介：宋东兴（1973—），男，江苏高邮人，讲师，研究方向：计算机网络技术，图像处理，软件工程. 120 宋东兴，殷旭东：从八皇后问题的解决方案看面向过程和面向对象 121 [2] （2 ）要有合理的冲突检查算法 .采用的方法是，先把8 个棋子摆在棋盘上，每行摆一个，然后去检查这种 摆放是否有冲突，如果没有冲突，即找到了一种解决方案. 首先是如何存放棋子的摆放位置.可以设想一下，当8 个棋子摆放好之后，每个棋子的位置都有一个行 值和列值，由于每行只有一个棋子，就可以从第0 行开始依次记录每个棋子的列值，8 个棋子的列值依次排列 构成一个数字序列，例，它表示第0 行棋子摆放在第2 列，第1行棋子摆放在第4 列，以此类推，这 样一种摆放方式对应一个8 位的8 进制数，用一个一维数组来存放这样一个8 进制数77777777 穷举了所有的摆放方式. 接下来对每种摆放情况做冲突检查，若不冲突就是一个解. 0 1 2 3 4 5 6 7