蚂蚁爬杆求解程序 - - Powered by Discuz!

标题: 蚂蚁爬杆求解程序 [打印本页]

作者: 51黑tt 时间: 2016-3-5 20:04
标题: 蚂蚁爬杆求解程序
//看了前面的鬼魂方法,不用编程甚至不用计算就得出结果
//但我是一个编程初学者,一切只是为了练习, 我花一点时间用C++做一下吧

#include <iostream>
using namespace std;

//常量设置
const int APOS=0;    //A点位置
const int BPOS=27; //B点位置
const int MAXANT=5;//最大蚂蚁数
const int SPEED=1; //速度

//全局变量
//初始位置已知量(必须是奇数)
int poslist[MAXANT]={3,7,11,17,23};

//用五位2进制表示5只蚂蚁的开始方向 00000-11111 ,共32种
enum ANTFLAG{
ANTFLAG1 =    0x1,
ANTFLAG2 =    0x2,
ANTFLAG3 =    0x4,
ANTFLAG4 =    0x8,
ANTFLAG5 =    0x10
//ANTFLAG6 =    0X20 //假如有更多只
//...
};
int antflist[]={ANTFLAG1,ANTFLAG2,ANTFLAG3,ANTFLAG4,ANTFLAG5};

//根据2进制数求蚂蚁的起开始方向
int StartDir(int val1,int val2){
int ir=(antflist[val1]&val2) ? 1:-1;
return ir;
}

class Ant;

//蚂蚁类
class Ant{
private:
int    m_id;                   //蚂蚁id编号(0-4)
bool m_life;             //生命状态,初始:1离开杆后:0
int    m_pos;                //木杆上坐标(0-27)
int    m_dir;                //方向(1,-1)
int    m_speed;          //速度(1)
int    m_time;             //爬行时间(0- ?)
public:
static int count;//现有蚁数
static int antlist[MAXANT];//存储每个蚂蚁的位置
public:
Ant();
void Init();//蚂蚁初始化
int    GetId(){return m_id;}//获得ID编号
int    GetTime(){return m_time;}//返回时间
void SetDir(int val){ m_dir=StartDir(m_id,val);}//初始方向
void CheckLife(); //检测生命状态
void ChangeDir(); //相遇改变方向
void RunPos();    //每秒后的位置
void Print(){cout < < "id: " < <m_id < < " pos: " < <m_pos
< < " dir: " < < m_dir < < " time: " < <m_time < <endl;}
};//end ANT

Ant::Ant(){ m_id=count;Init();count++;}

void Ant::Init(){
      m_pos=poslist[m_id];
m_speed=SPEED;
m_life=1;
m_time=0;
}

void Ant::CheckLife (){
if(m_life){
if(m_pos <APOS || m_pos> BPOS)
{
m_life=0;
count--;
}
else
m_time++;
}
}

void Ant::ChangeDir(){if(m_life){m_dir*=-1;}}

void Ant::RunPos(){
if(m_life)
   m_pos+=m_dir*m_speed;
   antlist[m_id]=m_pos;
}

//一个作用蚂蚁类的类
class FunAnt{
public:
int lasttime;             //最后一只蚂蚁离开的时间
Ant ants[MAXANT];    //蚂蚁对象数组共5只
public:
FunAnt(){}

      //设置蚂蚁初始方向
void Funsetdir(int d){
for(int i=0; i <MAXANT;i++)
ants[i].SetDir(d);
}
//屏幕输出所有蚂蚁信息
void print(){
for(int i=0;i <MAXANT;i++)
ants[i].Print();
}

//一直到最后一只蚂蚁离开木杆,输出每只蚂蚁所用时间
void Run()
{
while(ants[0].count){
   for(int i=0;i <MAXANT;i++)
   {
   ants[i].RunPos();    //移动蚂蚁位置
                           ants[i].CheckLife();//检测蚂蚁是否在杆上
   }
   ChangeDir();//检测,如果蚂蚁相遇改变方向,
}
lasttime=ants[0].GetTime();
            for(int i=1; i <MAXANT;i++)
{
bool b=lasttime <ants[i].GetTime();
if(b){lasttime=ants[i].GetTime();}
}
print();
}

//检测相邻蚂蚁位置函数,如果位置相同就调用改变方向函数
void ChangeDir(){
for(int i=0;i <MAXANT-1;i++)
{
if(ants[0].antlist[i]==ants[0].antlist[i+1])
{
ants[i].ChangeDir();
ants[i+1].ChangeDir();
}
}
}
};

int Ant::antlist[]={3,7,11,17,23};
int Ant::count=0;

//////////////////////////////////////////
void main(){
int    maxlist[32]; //存储32次的结果数组
for(int i=0;i <32;i++){
Ant::count =0;
FunAnt a1;
      a1.Funsetdir(i);
a1.Run();
maxlist[i]=a1.lasttime;
cout < < "lasttime: " < <a1.lasttime < <endl;
}
int min,max;
min=max=maxlist[0];
for(int i=0;i <32 ;i++)
{
  if(max <maxlist[i])
max=maxlist[i];
  if(min> maxlist[i])
  min=maxlist[i];
}
cout < < "max: " < <max < <endl
< < "min: " < <min < <endl;
  }//end main

作者: 51黑tt 时间: 2016-3-5 20:04
“蚂蚁爬杆求解程序”中最关键的行为就是如何执行爬杆游戏。法应当如何实现。
玩游戏本身是一个过程，包括从开始、进行中、到最后游戏结束。我们运用分析法进一步细化分解这个过程，这样得到若干个步骤：
1、设定好各只蚂蚁的初始状态（位置、头的朝向等）；
2、开始游戏，让所有还在木杆上的蚂蚁按既定速度连续爬行；
3、如果某只蚂蚁爬出了木杆范围，则从游戏中将其排除；
4、如果有蚂蚁碰头了，则让碰头的蚂蚁同时调头；
5、一直循环重复上述步骤，直到所有蚂蚁都爬出木杆范围。

上述步骤，除了第2步外，都很容易用程序代码来实现。因为程序的执行是一种离散的方式，要精确地模拟蚂蚁连续爬行是不可能的；我们需要将蚂蚁的爬行动作离散化；而程
序设计中的通行做法就是分割时间片断，让蚂蚁每次都爬行一小段时间；当这个时间间隔足够小时，就能近似地模拟实际的爬行过程。于是我们将第2步改造为蚂蚁爬行incTime
长的时间，而到了第5步，在继续循环前要在游戏的总执行时间上增加incTime长的增量。

蚂蚁爬杆问题中通过分析法设计的CreepingGame类行为

CreepingGame类的java源码如下：

/*
  * CreepingGame蚂蚁爬行游戏，定义了相关的规则和玩法
  */
public class CreepingGame {

private Stick stick;
private List <Ant> antsOnStick;
private List <Ant> antsOutofStick;
private int currentTime;
private boolean gameOver;

public CreepingGame() {
antsOnStick = new ArrayList <Ant> ();
antsOutofStick = new ArrayList <Ant> ();
currentTime = 0;
gameOver = false;
}

public void setStick(Stick stick) {
this.stick = stick;
}

public void addAntOnStick(Ant ant) throws CreepingException {
if (stick == null)
throw new CreepingException( "Stick not set yet! ");
else if (stick.isOutofRange(ant.getPosition()))
throw new CreepingException( "The ant is out of stick! ");
antsOnStick.add(ant);
}

/**
  * 依照游戏规则，检测是否有蚂蚁碰头了，一旦碰头则两者要同时调头
  */
private void applyCollisionRule(List <Ant> ants) {
List <Ant> antsTobeCheck = new ArrayList <Ant> ();

antsTobeCheck.addAll(ants);
while (!antsTobeCheck.isEmpty()){
Ant antTobeCheck = antsTobeCheck.get(0);
antsTobeCheck.remove(antTobeCheck);
Ant antAtSamePosition = null;
for (Ant ant : antsTobeCheck){
if (ant.isAtCollisionWith(antTobeCheck)){
antAtSamePosition = ant;
break;
}
}
if (antAtSamePosition != null){
antTobeCheck.changeCreepDirection();
antAtSamePosition.changeCreepDirection();
antsTobeCheck.remove(antAtSamePosition);
}
}
}

/**
  * 以合适的时间间隔来推动游戏的进行
  */
public void drivingGame(int incTime) {
currentTime += incTime;

for (Ant ant : antsOnStick){
ant.creeping(incTime);
if (stick.isOutofRange(ant.getPosition()))
antsOutofStick.add(ant);
}

for (Ant ant : antsOutofStick){
if (antsOnStick.contains(ant))
antsOnStick.remove(ant);
}

//“所有蚂蚁都爬出木杆范围”是游戏结束的标准
if (antsOnStick.isEmpty())
gameOver = true;
else{
applyCollisionRule(antsOnStick);
};
}

/**
  * 从头至尾玩一次游戏
  */
public void playGame(int incTime){
currentTime = 0;
gameOver = false;
while (!gameOver){
drivingGame(incTime);
}
}

public int getPlayTime() {
return currentTime - 0;
}

}

本案例中，遇到的数值都正好是整数，所以只要将每次循环的incTime设为1就可以计算出精确的结果值。但是如果这些数值是带小数的实数，那么为了尽量求得准确的答案，
incTime要设置成类似0.00001的较小数。这样将严重拖累程序的执行效率（循环次数过多）。
为了提高程序的执行效率，先要定位程序性能的瓶颈；我们发现playGame()方法中的while循环才是瓶颈之所在，于是要继续针对这个循环来做深入分析。while循环次数过多，
是因为incTime的值过小；而之所以给incTime设置较小数，是为了给程序一个机会来判断是否出现了蚂蚁碰头、或爬出木杆的事件（蚂蚁碰头将精确地发生在某个时间点，
incTime值过大会使得程序计算可能错过这个点）。这样，我们重新将前面以固定间隔incTime来循环执行drivingGame(incTime)的问题，转化成每次循环前如何计算一个时间值
incTime（不固定），用它来执行drivingGame(incTime)，使得推进游戏前进过程中，不会错过出现蚂蚁碰头、或爬出木杆事件的时间点。最后我们改造while循环，变成先计算
出现下一个蚂蚁碰头或爬出木杆事件所要经历的最短时间incTime，再以此时间值来推动游戏前进一个时段drivingGame(incTime)。
改造后的CreepingGame类playGame()方法的示例源码如下：

public void playGame(){
currentTime = 0;
gameOver = false;

while (!gameOver){
/**
* 计算出现下一个蚂蚁碰头或爬出木杆的事件所要经历的最短时间incTime
*/
int incTime ＝ calcTimeForNextOccurrence();

drivingGame(incTime);
}
}

有兴趣的读者不妨尝试一下编写calcTimeForNextOccurrence()的实现代码。
通过运用分析法，我们实现了“蚂蚁爬杆求解程序”中最关键的行为——CreepingGame类的playGame()方法。接下来，我们要考虑如何利用游戏室PlayRoom类来求得游戏执行
playGame的最小、最大时间。期间，我们将运用到综合思维法。

欢迎光临 (http://www.51hei.com/bbs/)