锐客网

  1. 首页 > 睿知 > it技术 > >

贪心策略java实现代码 贪心策略是什么( 三 )

IT技术算法


将机器3从15到17的时间段分配给作业1
总时间为：17
*/
系统框图如下 java实现五子棋程序 可以实现人人对战 人机对战 简单功能 悔棋 认输一、实验题目
五子棋游戏 。
二、问题分析
五子棋是双人博弈棋类益智游戏，由围棋演变而来，属纯策略型 。棋盘通常15*15，即15行，15列，共225个交叉点，即棋子落点；棋子由黑白两色组成，黑棋123颗 ， 白棋122颗 。游戏规则为黑先白后 ， 谁先五子连成一条直线谁赢，其中直线可以是横的、纵的、45度、135度 。
本次Java编程我的目的是现实人机对战，即游戏者一方是人，另一方计算机 。这就要求程序不仅要具备五子棋的基本界面 ， 还要编程指导计算机与人进行对弈 。为了使程序尽可能智能，我采用了贪心策略、传统搜索算法、极大极小博弈树算法，对应游戏玩家的3个等级：简单、中等、困难 。
三、功能设计
我的程序基本功能是实现人机对弈五子棋 。人和电脑交替下棋，谁先五子连成一条直线谁就赢 。下面是我程序的功能模块：
1.等级设置
核心功能是实现不同策略与算法的对比运用，纯贪心策略实现简单等级对手 ， 直接搜索算法实现中等等级对手，极大极小博弈树算法实现困难等级对手 。对应程序中的3选1单选按钮 。
2.悔棋功能
模拟栈机制实现人悔棋，不限步长的悔棋 。对应程序中的悔棋按钮 。
3.棋面绘制
根据不同机计算机的屏幕分辨率，绘制逼真的棋盘 。
4.图片引入
两张古典的人物图片，生动模拟对弈双方 。人物图片旁的黑白棋钵图片显示黑白棋归属 。
5.背景设置
支持用户选择背景，包括棋盘、棋盘边框、窗口边框 ， 彰显个性 。
6.音乐播放
下棋时有棋子落地的声音 ， 一方胜利时有五子连成一片的声音 。同时在设置背景时相应的改变整个对弈过程中的背景音乐 。
7.时间显示
在棋盘正上方有一模拟文本框显示当前棋局用时 。
8.其他小功能
支持和棋、认输、开启新游戏、退出游戏等操作 。
四、数据结构与算法设计
数据结构部分
1.当前棋局的存储结构
我的五子棋程序选择通常用到的15行*15列棋盘，可以开二维数组PositionFlag = new int[15][15]，PositionFlag[i][j]为0表示(i,j)点尚无棋，为1表示(i,j)点是人的棋子，为2表示(i,j)点是机器的棋子 。之所以选择二维数组，主要原因有两点：
1.本程序需要频繁随机访问15*15的交叉点，对应查询该点状态以及改变该点状态，随机访问是数组的特点 。
2.15*15=225开二维数组的内存需求相对现在内存为2G及以上的计算机完全可以接受，且数组实现简单、操作方便 。
基于以上两点 ， 尽管创建动态的顺序表—链表可能可以节省少量内存（可以只存当前有棋的点，原数组对应位置为0的点可以不存），但选择数组的优势完全在上述两点体现了出来 。
2.实现悔棋操作的数据结构
由于每次悔棋只需回退当前几步，后进先出原则，这正是栈这种典型数据结构的设计思想，于是我选择栈 。我自己先写了用自定义数组模拟的栈，但由于是学Java语言且由于悔棋的存储空间需要随当前步数增大而增大（由于每局最多下225步，即最多要悔225步，所以自己开个225的数组完全可以避免存储空间自增长的问题且内存完全可以接受 ， 之所以不用自定义数组而用ArrayList类主要是为了尝试Java中STL的用法），所有我最终改为用Java类库中的ArrayList类 。
确定用ArrayList类实现栈机制后就必须考虑每个ArrayList单元具体存储什么 。刚开始我存储的是当前的棋局 ， 即整个局面，而每个局面对应一个二维数组，这样是很占用内存的 。试想一下，在最坏情况下，225个ArrayList单元 ， 每个单元存放一个15*15的二维数组 ， 尽管225*15*15在Java的内存管理机制下不会爆栈，但也是极不划算的 。之所以说不划算，是因为有更好的解决方案 。由于每次悔棋只是在回退倒数一步 ， 多步悔棋只需循环回退 ， 所以可以只存储当前棋局最后一步的下法，对应一个二维点，完全可以自定义一个二维坐标类chessOneStep 。

推荐阅读


上一篇：mongodb建立索引树，mongodb如何建立索引

下一篇：包含phpajaxmysql实时的词条