切换到窄版

 找回密码
 立即注册
搜索
Stage1st»论坛 › 主论坛 › 游戏论坛 › 大家帮我一个忙,我在找游戏里的数学迷题 ...
12
返回列表 发新帖
楼主: crono

大家帮我一个忙,我在找游戏里的数学迷题

[复制链接]
堕落耶和华
发表于 2003-10-16 21:56 | 显示全部楼层
最初由 focus 发布
[B]回朔简单
（1）：假设当前状态为(A,m,B,n)--即A瓶有m，B瓶有n--记录下这个状态
下一步一共只有这几种可能性
A倒空
B倒空
A装满
B装满
A倒入B
B倒入A
依次探索上面几种动作，比如A倒空，状态变成(A,0,B,n)。然后察看这个状态有没有被记录过，如果状态没有被记录过，就记录下这个状态，然后回到（1），如果记录过，就回到(A,m,B,n),探索第二种动作……直到成功或者退回初始状态（A,0,B,0），后者代表无解。 [/B]


女皇的路径判断条件有问题...
这些描述中前4项是容器的状态,后2项是动作选择
而这6项不是独立互斥的
A倒入B可以和A倒空或者B装满同时存在,
而且这6项也没有覆盖所有情况
可以存在A空B也未满的...
回复

使用道具 举报

focus
     
发表于 2003-10-16 22:00 | 显示全部楼层
最初由 堕落耶和华 发布
[B]女皇的路径判断条件有问题...
这些描述中前4项是容器的状态,后2项是动作选择
而这6项不是独立互斥的
A倒入B可以和A倒空或者B装满同时存在,
而且这6项也没有覆盖所有情况
可以存在A空B也未满的... [/B]


是你没看懂吧……6个都是原子动作，不能再分了，而且正好涵盖了所有情况
回复

使用道具 举报

堕落耶和华
发表于 2003-10-16 22:03 | 显示全部楼层
最初由 focus 发布
[B]是你没看懂吧……6个都是原子动作，不能再分了，而且正好涵盖了所有情况 [/B]


简单~女皇可以试试用你的（A,m,B,n）表示法来表示你说的5,6两个情况看...
回复

使用道具 举报

focus
     
发表于 2003-10-16 22:11 | 显示全部楼层
简单，设A的容量为M，B的容量为N （MN都是已知的）
第5种情况：
假若m>(N-n)，结果是（A,m-(N-n),B,N）
假若m<=(N-n)，结果是（A,0,B,n+m）
回复

使用道具 举报

Demitri
发表于 2003-10-16 22:15 | 显示全部楼层
最初由 focus 发布
[B]回朔简单
（1）：假设当前状态为(A,m,B,n)--即A瓶有m，B瓶有n--记录下这个状态
下一步一共只有这几种可能性
A倒空
B倒空
A装满
B装满
A倒入B
B倒入A
依次探索上面几种动作，比如A倒空，状态变成(A,0,B,n)。然后察看这个状态有没有被记录过，如果状态没有被记录过，就记录下这个状态，然后回到（1），如果记录过，就回到(A,m,B,n),探索第二种动作……直到成功或者退回初始状态（A,0,B,0），后者代表无解。 [/B]


典型的最短路径回朔法？
回复

使用道具 举报

focus
     
发表于 2003-10-16 22:18 | 显示全部楼层
一次回朔得不到最短路径，只能得到一种解法而已
最短路径和6种动作的排列顺序相关，要用其他算法
回复

使用道具 举报

Demitri
发表于 2003-10-16 22:21 | 显示全部楼层
应该和排列顺序无关吧 和动作的数量以及权值有关
回复

使用道具 举报

focus
     
发表于 2003-10-16 22:28 | 显示全部楼层
最初由 Demitri 发布
[B]应该和排列顺序无关吧 和动作的数量以及权值有关 [/B]


绝对是和排列顺序相关，你可以用简单的实例来验证
回复

使用道具 举报

永远的rookie
发表于 2003-10-17 03:23 | 显示全部楼层
A princess is as old as the prince will be when the princess is twice as old as the prince was when the princess\'s age was half the sum of their present age.

>how old are they now?

博得2里面的一个谜题。
回复

使用道具 举报

风の千秋 该用户已被删除
发表于 2003-10-17 08:32 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

堕落耶和华
发表于 2003-10-17 12:32 | 显示全部楼层
最初由 focus 发布
[B]简单，设A的容量为M，B的容量为N （MN都是已知的）
第5种情况：
假若m>(N-n)，结果是（A,m-(N-n),B,N）
假若m<=(N-n)，结果是（A,0,B,n+m） [/B]


女皇的(a,m,b,n)表示法是用来表示静止状态的的,
一个表达式代表一种状态
也就是说你分析的所谓第5种情况根本就该拆分为2个状态

如果要表示a倒入b这种情况,必须引入时间状态才能建立适当的表达式来描述状态随时间的变化.

根本来说,就是女皇把静态和动态的情况混淆了
回复

使用道具 举报

focus
     
发表于 2003-10-18 17:51 | 显示全部楼层
最初由 堕落耶和华 发布
[B]女皇的(a,m,b,n)表示法是用来表示静止状态的的,
一个表达式代表一种状态
也就是说你分析的所谓第5种情况根本就该拆分为2个状态

如果要表示a倒入b这种情况,必须引入时间状态才能建立适当的表达式来描述状态随时间的变化.

根本来说,就是女皇把静态和动态的情况混淆了 [/B]


唉我跟你讲不清楚，则么简单的问题下地怎么就想不明白涅？
6个动作根本是完全平等的，绝对不能再分割
回复

使用道具 举报

focus
     
发表于 2003-10-18 17:55 | 显示全部楼层
把具体算法给你看算了


  public void fillQuest(clsBottle bottleA,clsBottle bottleB,int target)
  {
    TraceElementType temp = new TraceElementType();
    //tag this spot
    this.TM.setTag(bottleA.getCurrent(),bottleB.getCurrent(),1);
    //print trace
    this.TraceStack.printTrace(bottleA.getVolume(),bottleB.getVolume());

    if(bottleA.getCurrent() == target) {
      this.TraceStack.printTrace(bottleA.getVolume(),bottleB.getVolume());
      System.out.println(\"finished\");
      System.exit(0);
      return;
    }

    if(bottleB.getCurrent() == target) {
      this.TraceStack.printTrace(bottleA.getVolume(),bottleB.getVolume());
      System.out.println(\"finished\");
      System.exit(0);
      return;
    }

    if((bottleA.getCurrent() - bottleB.getVolume() + bottleB.getCurrent()) == target) {
      bottleA.fill(bottleB);
      this.TraceStack.printTrace(bottleA.getVolume(),bottleB.getVolume());
      System.out.println(\"finished\");
      System.exit(0);
      return;
    }

    if((bottleB.getCurrent() - bottleA.getVolume() + bottleA.getCurrent()) == target) {
      bottleB.fill(bottleA);
      this.TraceStack.printTrace(bottleA.getVolume(),bottleB.getVolume());
      System.out.println(\"finished\");
      System.exit(0);
      return;
    }

    if((bottleB.getCurrent() + bottleA.getCurrent()) == target)
    {
      if(bottleA.getVolume() > bottleB.getVolume())
      {
        bottleB.fill(bottleA);
        this.TraceStack.printTrace(bottleA.getVolume(),bottleB.getVolume());
        System.out.println(\"finished\");
        System.exit(0);
        return;
      }
      else
      {
        bottleA.fill(bottleB);
        this.TraceStack.printTrace(bottleA.getVolume(),bottleB.getVolume());
        System.out.println(\"finished\");
        System.exit(0);
        return;
      }
    }


    //action
    temp.setApart(bottleA.getCurrent());
    temp.setBpart(bottleB.getCurrent());

    //1:splash A
    bottleA.splash();
    if(this.TM.getTag(bottleA.getCurrent(),bottleB.getCurrent()) == 1) {
      bottleA.setCurrent(temp.getApart());
      bottleB.setCurrent(temp.getBpart());
    }
    else {
      this.TE.setApart(bottleA.getCurrent());
      this.TE.setBpart(bottleB.getCurrent());
      this.TraceStack.push(this.TE);
      System.out.println(bottleA.getName() + \" splash\");
      this.fillQuest(bottleA,bottleB,this.target);
    }
    //2:splash B
    bottleB.splash();
    if(this.TM.getTag(bottleA.getCurrent(),bottleB.getCurrent()) == 1) {
      bottleA.setCurrent(temp.getApart());
      bottleB.setCurrent(temp.getBpart());
    }
    else {
      this.TE.setApart(bottleA.getCurrent());
      this.TE.setBpart(bottleB.getCurrent());
      this.TraceStack.push(this.TE);
      System.out.println(bottleB.getName() + \" splash\");
      this.fillQuest(bottleA,bottleB,this.target);
    }
    //3:reload A
    bottleA.reload();
    if(this.TM.getTag(bottleA.getCurrent(),bottleB.getCurrent()) == 1) {
      bottleA.setCurrent(temp.getApart());
      bottleB.setCurrent(temp.getBpart());
    }
    else {
      this.TE.setApart(bottleA.getCurrent());
      this.TE.setBpart(bottleB.getCurrent());
      this.TraceStack.push(this.TE);
      System.out.println(bottleA.getName() + \" load\");
      this.fillQuest(bottleA,bottleB,this.target);
    }
    //4:reload B
    bottleB.reload();
    if(this.TM.getTag(bottleA.getCurrent(),bottleB.getCurrent()) == 1) {
      bottleA.setCurrent(temp.getApart());
      bottleB.setCurrent(temp.getBpart());
    }
    else {
      this.TE.setApart(bottleA.getCurrent());
      this.TE.setBpart(bottleB.getCurrent());
      this.TraceStack.push(this.TE);
      System.out.println(bottleB.getName() + \" load\");
      this.fillQuest(bottleA,bottleB,this.target);
    }
    //5: A to B
    bottleA.fill(bottleB);
    if(this.TM.getTag(bottleA.getCurrent(),bottleB.getCurrent()) == 1) {
      bottleA.setCurrent(temp.getApart());
      bottleB.setCurrent(temp.getBpart());
    }
    else {
      this.TE.setApart(bottleA.getCurrent());
      this.TE.setBpart(bottleB.getCurrent());
      this.TraceStack.push(this.TE);
      System.out.println(bottleA.getName() + \" to \" + bottleB.getName());
      this.fillQuest(bottleA,bottleB,this.target);
    }
    //6:B to A
    bottleB.fill(bottleA);
    if(this.TM.getTag(bottleA.getCurrent(),bottleB.getCurrent()) == 1) {
      bottleA.setCurrent(temp.getApart());
      bottleB.setCurrent(temp.getBpart());
    }
    else {
      this.TE.setApart(bottleA.getCurrent());
      this.TE.setBpart(bottleB.getCurrent());
      this.TraceStack.push(this.TE);
      System.out.println(bottleB.getName() + \" to \" + bottleA.getName());
      this.fillQuest(bottleA,bottleB,this.target);
    }
    //7: back
    this.TE = this.TraceStack.pop();
    bottleA.setCurrent(this.TE.getApart());
    bottleB.setCurrent(this.TE.getBpart());
    this.fillQuest(bottleA,bottleB,this.target);

}
  public clsFillWater() {

    this.TE = new TraceElementType();
    this.TM = new TagMatrix(100,100);
    this.TraceStack = new Tstack(400);

    clsBottle bottleA = new clsBottle(\"A\");
    clsBottle bottleB = new clsBottle(\"B\");
    bottleA.setVolume(11);
    bottleB.setVolume(9);
    this.target = 4;

    System.out.println(\"[start: bottleA\'s volume = \" + bottleA.getVolume() +
                       \" , bottleB\'s volume = \" + bottleB.getVolume() +
                       \" , target = \" + this.target + \"]\");
    this.TraceStack.push(this.TE);
    this.fillQuest(bottleA,bottleB,this.target);
  }

  public static void main(String[] args) {
    clsFillWater clsFillWater1 = new clsFillWater();
  }
}


------------------------------------------------------------------
运行结果（A=5 B=3 要求=4）

[start: bottleA\'s volume = 5 , bottleB\'s volume = 3 , target = 4]
(0,0)
A load
(0,0) (5,0)
B load
(0,0) (5,0) (5,3)
A splash
(0,0) (5,0) (5,3) (0,3)
B to A
(0,0) (5,0) (5,3) (0,3) (3,0)
B load
(0,0) (5,0) (5,3) (0,3) (3,0) (3,3)
B to A
(0,0) (5,0) (5,3) (0,3) (3,0) (3,3) (5,1)
A splash
(0,0) (5,0) (5,3) (0,3) (3,0) (3,3) (5,1) (0,1)
B to A
(0,0) (5,0) (5,3) (0,3) (3,0) (3,3) (5,1) (0,1) (1,0)
B load
(0,0) (5,0) (5,3) (0,3) (3,0) (3,3) (5,1) (0,1) (1,0) (1,3)
B to A
(0,0) (5,0) (5,3) (0,3) (3,0) (3,3) (5,1) (0,1) (1,0) (1,3) (4,0)
finished

--------------------------------------------------------------------
（A=11 B=9 要求=4）
[start: bottleA\'s volume = 11 , bottleB\'s volume = 9 , target = 4]
(0,0)
A load
(0,0) (11,0)
B load
(0,0) (11,0) (11,9)
A splash
(0,0) (11,0) (11,9) (0,9)
B to A
(0,0) (11,0) (11,9) (0,9) (9,0)
B load
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9)
B to A
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7)
A splash
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7)
B to A
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0)
B load
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9)
B to A
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5)
A splash
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5)
B to A
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0)
B load
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0) (5,9)
B to A
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0) (5,9) (11,3)
A splash
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0) (5,9) (11,3) (0,3)
B to A
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0) (5,9) (11,3) (0,3) (3,0)
B load
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0) (5,9) (11,3) (0,3) (3,0) (3,9)
B to A
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0) (5,9) (11,3) (0,3) (3,0) (3,9) (11,1)
A splash
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0) (5,9) (11,3) (0,3) (3,0) (3,9) (11,1) (0,1)
B to A
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0) (5,9) (11,3) (0,3) (3,0) (3,9) (11,1) (0,1) (1,0)
B load
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0) (5,9) (11,3) (0,3) (3,0) (3,9) (11,1) (0,1) (1,0) (1,9)
B to A
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0) (5,9) (11,3) (0,3) (3,0) (3,9) (11,1) (0,1) (1,0) (1,9) (10,0)
B load
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0) (5,9) (11,3) (0,3) (3,0) (3,9) (11,1) (0,1) (1,0) (1,9) (10,0) (10,9)
B to A
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0) (5,9) (11,3) (0,3) (3,0) (3,9) (11,1) (0,1) (1,0) (1,9) (10,0) (10,9) (11,8)
A splash
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0) (5,9) (11,3) (0,3) (3,0) (3,9) (11,1) (0,1) (1,0) (1,9) (10,0) (10,9) (11,8) (0,8)
B to A
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0) (5,9) (11,3) (0,3) (3,0) (3,9) (11,1) (0,1) (1,0) (1,9) (10,0) (10,9) (11,8) (0,8) (8,0)
B load
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0) (5,9) (11,3) (0,3) (3,0) (3,9) (11,1) (0,1) (1,0) (1,9) (10,0) (10,9) (11,8) (0,8) (8,0) (8,9)
B to A
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0) (5,9) (11,3) (0,3) (3,0) (3,9) (11,1) (0,1) (1,0) (1,9) (10,0) (10,9) (11,8) (0,8) (8,0) (8,9) (11,6)
A splash
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0) (5,9) (11,3) (0,3) (3,0) (3,9) (11,1) (0,1) (1,0) (1,9) (10,0) (10,9) (11,8) (0,8) (8,0) (8,9) (11,6) (0,6)
B to A
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0) (5,9) (11,3) (0,3) (3,0) (3,9) (11,1) (0,1) (1,0) (1,9) (10,0) (10,9) (11,8) (0,8) (8,0) (8,9) (11,6) (0,6) (6,0)
B load
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0) (5,9) (11,3) (0,3) (3,0) (3,9) (11,1) (0,1) (1,0) (1,9) (10,0) (10,9) (11,8) (0,8) (8,0) (8,9) (11,6) (0,6) (6,0) (6,9)
B to A
(0,0) (11,0) (11,9) (0,9) (9,0) (9,9) (11,7) (0,7) (7,0) (7,9) (11,5) (0,5) (5,0) (5,9) (11,3) (0,3) (3,0) (3,9) (11,1) (0,1) (1,0) (1,9) (10,0) (10,9) (11,8) (0,8) (8,0) (8,9) (11,6) (0,6) (6,0) (6,9) (11,4)
finished
回复

使用道具 举报

saiya 该用户已被删除
发表于 2003-10-18 18:12 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

12
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|上海互联网违法和不良信息举报中心|网上有害信息举报专区|962110 反电信诈骗|举报电话 021-62035905|Stage1st ( 沪ICP备13020230号-1|沪公网安备 31010702007642号 )

GMT+8, 2024-11-5 04:58 , Processed in 0.112717 second(s), 6 queries , Gzip On, Redis On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表