日韩超清精品不卡视频,十八禁免费视频无码网站,亚洲免费黄色电影

標(biāo)題: 螞蟻爬桿求解程序 [打印本頁]

作者: 51黑tt 時(shí)間: 2016-3-5 20:04
標(biāo)題: 螞蟻爬桿求解程序
//看了前面的鬼魂方法,不用編程甚至不用計(jì)算就得出結(jié)果
//但我是一個(gè)編程初學(xué)者,一切只是為了練習(xí), 我花一點(diǎn)時(shí)間用C++做一下吧

#include <iostream>
using namespace std;

//常量設(shè)置
const int APOS=0;    //A點(diǎn)位置
const int BPOS=27; //B點(diǎn)位置
const int MAXANT=5;//最大螞蟻數(shù)
const int SPEED=1; //速度

//全局變量
//初始位置已知量(必須是奇數(shù))
int poslist[MAXANT]={3,7,11,17,23};

//用五位2進(jìn)制表示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};

//根據(jù)2進(jìn)制數(shù)求螞蟻的起開始方向
int StartDir(int val1,int val2){
int ir=(antflist[val1]&val2) ? 1:-1;
return ir;
}

class Ant;

//螞蟻類
class Ant{
private:
int    m_id;                   //螞蟻id編號(hào)(0-4)
bool m_life;             //生命狀態(tài),初始:1離開桿后:0
int    m_pos;                //木桿上坐標(biāo)(0-27)
int    m_dir;                //方向(1,-1)
int    m_speed;          //速度(1)
int    m_time;             //爬行時(shí)間(0- ?)
public:
static int count;//現(xiàn)有蟻數(shù)
static int antlist[MAXANT];//存儲(chǔ)每個(gè)螞蟻的位置
public:
Ant();
void Init();//螞蟻初始化
int    GetId(){return m_id;}//獲得ID編號(hào)
int    GetTime(){return m_time;}//返回時(shí)間
void SetDir(int val){ m_dir=StartDir(m_id,val);}//初始方向
void CheckLife(); //檢測(cè)生命狀態(tài)
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;
}

//一個(gè)作用螞蟻類的類
class FunAnt{
public:
int lasttime;             //最后一只螞蟻離開的時(shí)間
Ant ants[MAXANT];    //螞蟻對(duì)象數(shù)組共5只
public:
FunAnt(){}

      //設(shè)置螞蟻初始方向
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();
}

//一直到最后一只螞蟻離開木桿,輸出每只螞蟻所用時(shí)間
void Run()
{
while(ants[0].count){
   for(int i=0;i <MAXANT;i++)
   {
   ants[i].RunPos();    //移動(dòng)螞蟻位置
                           ants[i].CheckLife();//檢測(cè)螞蟻是否在桿上
   }
   ChangeDir();//檢測(cè),如果螞蟻相遇改變方向,
}
lasttime=ants[0].GetTime();
            for(int i=1; i <MAXANT;i++)
{
bool b=lasttime <ants[i].GetTime();
if(b){lasttime=ants[i].GetTime();}
}
print();
}

//檢測(cè)相鄰螞蟻位置函數(shù),如果位置相同就調(diào)用改變方向函數(shù)
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]; //存儲(chǔ)32次的結(jié)果數(shù)組
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 時(shí)間: 2016-3-5 20:04
“螞蟻爬桿求解程序”中最關(guān)鍵的行為就是如何執(zhí)行爬桿游戲。法應(yīng)當(dāng)如何實(shí)現(xiàn)。
玩游戲本身是一個(gè)過程，包括從開始、進(jìn)行中、到最后游戲結(jié)束。我們運(yùn)用分析法進(jìn)一步細(xì)化分解這個(gè)過程，這樣得到若干個(gè)步驟：
1、設(shè)定好各只螞蟻的初始狀態(tài)（位置、頭的朝向等）；
2、開始游戲，讓所有還在木桿上的螞蟻按既定速度連續(xù)爬行；
3、如果某只螞蟻爬出了木桿范圍，則從游戲中將其排除；
4、如果有螞蟻碰頭了，則讓碰頭的螞蟻同時(shí)調(diào)頭；
5、一直循環(huán)重復(fù)上述步驟，直到所有螞蟻都爬出木桿范圍。

上述步驟，除了第2步外，都很容易用程序代碼來實(shí)現(xiàn)。因?yàn)槌绦虻膱?zhí)行是一種離散的方式，要精確地模擬螞蟻連續(xù)爬行是不可能的；我們需要將螞蟻的爬行動(dòng)作離散化；而程
序設(shè)計(jì)中的通行做法就是分割時(shí)間片斷，讓螞蟻每次都爬行一小段時(shí)間；當(dāng)這個(gè)時(shí)間間隔足夠小時(shí)，就能近似地模擬實(shí)際的爬行過程。于是我們將第2步改造為螞蟻爬行incTime
長的時(shí)間，而到了第5步，在繼續(xù)循環(huán)前要在游戲的總執(zhí)行時(shí)間上增加incTime長的增量。

螞蟻爬桿問題中通過分析法設(shè)計(jì)的CreepingGame類行為

CreepingGame類的java源碼如下：

/*
  * CreepingGame螞蟻爬行游戲，定義了相關(guān)的規(guī)則和玩法
  */
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);
}

/**
  * 依照游戲規(guī)則，檢測(cè)是否有螞蟻碰頭了，一旦碰頭則兩者要同時(shí)調(diào)頭
  */
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);
}
}
}

/**
  * 以合適的時(shí)間間隔來推動(dòng)游戲的進(jìn)行
  */
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);
}

//“所有螞蟻都爬出木桿范圍”是游戲結(jié)束的標(biāo)準(zhǔn)
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;
}

}

本案例中，遇到的數(shù)值都正好是整數(shù)，所以只要將每次循環(huán)的incTime設(shè)為1就可以計(jì)算出精確的結(jié)果值。但是如果這些數(shù)值是帶小數(shù)的實(shí)數(shù)，那么為了盡量求得準(zhǔn)確的答案，
incTime要設(shè)置成類似0.00001的較小數(shù)。這樣將嚴(yán)重拖累程序的執(zhí)行效率（循環(huán)次數(shù)過多）。
為了提高程序的執(zhí)行效率，先要定位程序性能的瓶頸；我們發(fā)現(xiàn)playGame()方法中的while循環(huán)才是瓶頸之所在，于是要繼續(xù)針對(duì)這個(gè)循環(huán)來做深入分析。while循環(huán)次數(shù)過多，
是因?yàn)閕ncTime的值過��；而之所以給incTime設(shè)置較小數(shù)，是為了給程序一個(gè)機(jī)會(huì)來判斷是否出現(xiàn)了螞蟻碰頭、或爬出木桿的事件（螞蟻碰頭將精確地發(fā)生在某個(gè)時(shí)間點(diǎn)，
incTime值過大會(huì)使得程序計(jì)算可能錯(cuò)過這個(gè)點(diǎn)）。這樣，我們重新將前面以固定間隔incTime來循環(huán)執(zhí)行drivingGame(incTime)的問題，轉(zhuǎn)化成每次循環(huán)前如何計(jì)算一個(gè)時(shí)間值
incTime（不固定），用它來執(zhí)行drivingGame(incTime)，使得推進(jìn)游戲前進(jìn)過程中，不會(huì)錯(cuò)過出現(xiàn)螞蟻碰頭、或爬出木桿事件的時(shí)間點(diǎn)。最后我們改造while循環(huán)，變成先計(jì)算
出現(xiàn)下一個(gè)螞蟻碰頭或爬出木桿事件所要經(jīng)歷的最短時(shí)間incTime，再以此時(shí)間值來推動(dòng)游戲前進(jìn)一個(gè)時(shí)段drivingGame(incTime)。
改造后的CreepingGame類playGame()方法的示例源碼如下：

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

while (!gameOver){
/**
* 計(jì)算出現(xiàn)下一個(gè)螞蟻碰頭或爬出木桿的事件所要經(jīng)歷的最短時(shí)間incTime
*/
int incTime ＝ calcTimeForNextOccurrence();

drivingGame(incTime);
}
}

有興趣的讀者不妨嘗試一下編寫calcTimeForNextOccurrence()的實(shí)現(xiàn)代碼。
通過運(yùn)用分析法，我們實(shí)現(xiàn)了“螞蟻爬桿求解程序”中最關(guān)鍵的行為——CreepingGame類的playGame()方法。接下來，我們要考慮如何利用游戲室PlayRoom類來求得游戲執(zhí)行
playGame的最小、最大時(shí)間。期間，我們將運(yùn)用到綜合思維法。

歡迎光臨 (http://www.torrancerestoration.com/bbs/)