找回密码
 注册
搜索
热搜: 超星 读书 找书
查看: 8932|回复: 39

[【主题讨论】] (理工类)寒武能够到找到艾莉吗?

[复制链接]
发表于 2007-12-22 02:38:03 | 显示全部楼层 |阅读模式
原题来自:http://cnc.readfree.net/bbs/read.php?tid=4555735



用高速计算机计算的,
游客,本帖隐藏的内容需要积分高于 1000 才可浏览,您当前积分为 0

e, w, n, s, t, b 分别表示红心朝东西北南上下。

第二种能走到终点的走法是,

tV  s>  s>  sV  s>  s>  s>  sV
sV  bA  w<  bV  bA  eV  b<  bV
bV  b>  wA  n>  nA  eV  nA  n<
n>  nA  eV  b<  w<  e>  b>  wV
eV  b<  e>  bV  wA  eV  b<  w<
eV  nA  n<  n<  wA  eV  s>  sV
e>  b>  wV  b>  wA  e>  bA  bV
e0  b<  w<  nA  n<  n<  n<  n<

但红心向东。

没有别的走法。

先前的编程错误是,当到达终点时,红心不能向上的限制没有去掉。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?注册

×
回复

使用道具 举报

 楼主| 发表于 2007-12-22 02:41:30 | 显示全部楼层


#include <math.h>
#include <stdio.h>
#include <stdlib.h>

// free=0, e=1, w=2, n=3, s=4, t=5, b=6
// move e(right)=1, w(left)=2, n(up)=3, s(down)=4

int position(int mp, int direction)
{
  short int n[ 6][ 4] = {6, 5, 1, 1, 5, 6, 2, 2, 3, 3, 6, 5, 4, 4, 5, 6, 1, 2, 3, 4, 2, 1, 4, 3};
  return n[ mp - 1][ direction - 1];
}

#define MM 1000
short int t[ MM][ 8][ 8], u[ MM][ 8][ 8], v[ 8][ 8], ti[ MM], tj[ MM];

int main (void)
{
  int i, j, k, n, n_new, mp, mp_new;

  n = 0;
  ti[ n] = tj[ n] = 0;
  for (i = 0; i < 8; i++) for (j = 0; j < 8; j++) t[ n][ i][ j] = u[ n][ i][ j] = 0;
  t[ 0][ 0][ 0] = 5;

L_0:
  n_new = n;
  mp = t[ n][ ti[ n]][ tj[ n]];

  // right
  mp_new = position(mp, 1);
  if (tj[ n] < 7) if (!t[ n][ ti[ n]][ tj[ n] + 1]) if (mp_new != 5)
  {
    n_new++;
    for (i = 0; i < 8; i++) for (j = 0; j < 8; j++)
    {
      t[ n_new][ i][ j] = t[ n][ i][ j];
      u[ n_new][ i][ j] = u[ n][ i][ j];
    }
    ti[ n_new] = ti[ n];
    tj[ n_new] = tj[ n] + 1;
    t[ n_new][ ti[ n_new]][ tj[ n_new]] = mp_new;
    u[ n_new][ ti[ n_new]][ tj[ n_new]] = 1;
  }

  // left
  mp_new = position(mp, 2);
  if (tj[ n]) if (!t[ n][ ti[ n]][ tj[ n] - 1]) if (mp_new != 5 || (ti[ n] == 7 && tj[ n] == 1))
  {
    n_new++;
    for (i = 0; i < 8; i++) for (j = 0; j < 8; j++)
    {
      t[ n_new][ i][ j] = t[ n][ i][ j];
      u[ n_new][ i][ j] = u[ n][ i][ j];
    }
    ti[ n_new] = ti[ n];
    tj[ n_new] = tj[ n] - 1;
    t[ n_new][ ti[ n_new]][ tj[ n_new]] = mp_new;
    u[ n_new][ ti[ n_new]][ tj[ n_new]] = 2;
  }

  // upword
  mp_new = position(mp, 3);  
  if (ti[ n]) if (!t[ n][ ti[ n] - 1][ tj[ n]]) if (mp_new != 5)
  {
    n_new++;
    for (i = 0; i < 8; i++) for (j = 0; j < 8; j++)
    {
      t[ n_new][ i][ j] = t[ n][ i][ j];
      u[ n_new][ i][ j] = u[ n][ i][ j];
    }
    ti[ n_new] = ti[ n] - 1;
    tj[ n_new] = tj[ n];
    t[ n_new][ ti[ n_new]][ tj[ n_new]] = mp_new;
    u[ n_new][ ti[ n_new]][ tj[ n_new]] = 3;
  }

  // downword
  mp_new = position(mp, 4);
  if (ti[ n] < 7) if (!t[ n][ ti[ n] + 1][ tj[ n]]) if (mp_new != 5 || (ti[ n] == 6 && tj[ n] == 0))
  {
    n_new++;
    for (i = 0; i < 8; i++) for (j = 0; j < 8; j++)
    {
      t[ n_new][ i][ j] = t[ n][ i][ j];
      u[ n_new][ i][ j] = u[ n][ i][ j];
    }
    ti[ n_new] = ti[ n] + 1;
    tj[ n_new] = tj[ n];
    t[ n_new][ ti[ n_new]][ tj[ n_new]] = mp_new;
    u[ n_new][ ti[ n_new]][ tj[ n_new]] = 4;
  }

  if (n_new > n)
  {
    for (k = n; k < n_new; k++) for (i = 0; i < 8; i++) for (j = 0; j < 8; j++)
    {
      t[ k][ i][ j] = t[ k + 1][ i][ j];
      u[ k][ i][ j] = u[ k + 1][ i][ j];
      ti[ k] = ti[ k + 1];
      tj[ k] = tj[ k + 1];
    }
    n = n_new - 1;
    if (n > MM - 4)
    {
      printf("not finifshed\n");
      return 0;
    }
    goto L_0;
  }

  for (i = 0; i < 8; i++) for (j = 0; j < 8; j++) if (!t[ n][ i][ j])
  {
    n--;
    if (n >= 0) goto L_0;
    else return 0;
  }
  if (ti[ n] == 7 && tj[ n] == 0) // && t[ n][ i][ j] == 5)
  {
    for (i = 0; i < 8; i++) for (j = 0; j < 8; j++)
    {
      if (u[ n][ i][ j] == 1) v[ i][ j - 1] = 1;
      else if (u[ n][ i][ j] == 2) v[ i][ j + 1] = 2;
      else if (u[ n][ i][ j] == 3) v[ i + 1][ j] = 3;
      else if (u[ n][ i][ j] == 4) v[ i - 1][ j] = 4;
    }
    v[ ti[ n]][ tj[ n]] = 0;

    for (i = 0; i < 8; i++)
    {
      for (j = 0; j < 8; j++) printf("%d-%d ", t[ n][ i][ j], v[ i][ j]);
      printf("\n");
    }
    printf("\n");
  }
  n--;
  if (n >= 0) goto L_0;
  return 0;
}

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?注册

×
回复

使用道具 举报

发表于 2007-12-22 08:10:56 | 显示全部楼层
book 老师就是强,:)
此帖从一开始就注定必将成为经典,
回复

使用道具 举报

发表于 2007-12-22 10:33:18 | 显示全部楼层
引用第37楼ly188于2007-12-21 23:32发表的 :
好不容易通关了~累死我了,最后关到比前面简单多了
寒武太了 6面都涂上心就好了么


知不知道 苯 有强致癌作用哇
回复

使用道具 举报

发表于 2007-12-22 11:14:50 | 显示全部楼层
哈哈,bookish的第一个图完全正确。此题目只有唯一解,开始我也晕了
如果换成从对角走到对角,则本题无解。此题目前身源自一个普通理发师发明的游戏,欢迎大家继续解答,原创有想法有内容的文章将被推荐给学术妙笔版块,有机会获得威望
回复

使用道具 举报

发表于 2007-12-22 11:43:57 | 显示全部楼层
此题目只有唯一解!!!!!

我的神啊~~~~
做对的又都是世上只有4个人能做对了~~~~
回复

使用道具 举报

发表于 2007-12-22 11:47:01 | 显示全部楼层
看来我是没有希望作对了,怎么这么难,竟然用了编程,不得不服
回复

使用道具 举报

发表于 2007-12-22 12:11:16 | 显示全部楼层
似乎只能用算法解决
我的思路 下面分别代表朝某方向转的两张表
右左 0 1 * 2 3 * (1)
下上 0 * 1 2 * 3 (2)
每次向右或者向左(1)值递加或递减,如果(1)遇到*则(1)(2)不变
每次向下或者向上(2)值递加或递减,如果(2)遇到*则(1)(2)不变
0 0 即是红心向上,不晓得对不
回复

使用道具 举报

发表于 2007-12-22 12:38:05 | 显示全部楼层
引用第48楼ly188于2007-12-22 12:11发表的 :
似乎只能用算法解决
我的思路 下面分别代表朝某方向转的两张表
右左 0 1 * 2 3 * (1)
下上 0 * 1 2 * 3 (2)
每次向右或者向左(1)值递加或递减,如果(1)遇到*则(1)(2)不变
.......
这个算下来应该比book老师的算的快一点,那for嵌套的计算量太大了~~~
回复

使用道具 举报

发表于 2007-12-22 12:58:18 | 显示全部楼层
游客,本帖隐藏的内容需要积分高于 1000 才可浏览,您当前积分为 0
回复

使用道具 举报

发表于 2007-12-22 13:23:46 | 显示全部楼层
谁会编这样的程序:
ly188兄是两个表,谁能编出三个表的。
记有红心的是1,对应红心的面是-1,
然后红心的南北面为1和-1,东西面也是1和-1,这样的好处就是直接可以按加和算~~
初始条件是(1,0,0)经过几次循环后,最后又变回了(1,0,0)
~~~~
来了着才发现自己是菜鸟~~

看大侠们编~~~
看了book老师编的穷举情况的方法,虽然感觉好像简化了不少,但总感到什么地方不对劲~~好像又没有简化~~~只是直觉~~
回复

使用道具 举报

发表于 2007-12-22 14:44:14 | 显示全部楼层
发现错误一堆,我再仔细看看
回复

使用道具 举报

发表于 2007-12-22 15:19:18 | 显示全部楼层
不好意思,我本来以为这个问题已经解决了,所以写了个续集。

昨天用主ID进来(看得见各位的加密),才发现原来还没有解决,所以得赶紧帮寒武一个忙,简单写了一个程序,完全是穷举,因为我那时正在大型并行高速计算机上,所以根本不考虑速度。

第一次算出的结果是我给出的第二个,唯一的结果,但是还不符合条件。

检查程序后发现,我忘了把到达终点时红心不能向上的限制去掉,把这个结果去掉之后,就得到了那个唯一正确的结果了。

计算时间大约十几秒钟!所以,我的程序在PC机上是不能运行的。

在PC机上编程,还需要简化问题和减少计算量。请画出平面图仔细考虑。
回复

使用道具 举报

发表于 2007-12-22 15:54:17 | 显示全部楼层
引用第49楼yzh_nj_china于2007-12-22 12:38发表的 :
这个算下来应该比book老师的算的快一点,那for嵌套的计算量太大了~~~

我的那个算法,for嵌套的计算量不大,要命的是 goto L_0,这个问题可能的走法太多,我没有统计这个数字,goto L_0 至少是千万次。

我在编程前先按编程思路手算了二十几步(这是我的编程习惯,用来了解问题的性质),手算是从目的地倒算的(本想用动态规划法,所以倒过来做),编程时是从起点出发,因为正走倒走一样。

还可以增加很多走法失败的判别条件,比如,当达到右边界时,就只能向下走,到达上边界就只能向右走,到达下边界就只能向左走,到达左边界就只能向下走,等等,我手算时用这些条件,编程就不考虑了。

但如果用PC机,这些限制条件考虑的越多,需要试探的可能的走法就越少,计算速度就越快。
回复

使用道具 举报

发表于 2007-12-22 16:16:49 | 显示全部楼层
引用第44楼磁铁于2007-12-22 11:14发表的 :
........此题目只有唯一解

一个极为重要的提示。

根据这个提示,晚上我要试试看能否用PC机解决这个问题。

呵呵,又是一个挑战!
回复

使用道具 举报

发表于 2007-12-22 16:38:26 | 显示全部楼层
游客,本帖隐藏的内容需要积分高于 1000 才可浏览,您当前积分为 0
回复

使用道具 举报

发表于 2007-12-22 16:40:37 | 显示全部楼层
算错了~
回复

使用道具 举报

发表于 2007-12-22 16:48:56 | 显示全部楼层
好的,画好我先把两位的妙笔乾坤大挪移到学术区
回复

使用道具 举报

发表于 2007-12-22 16:50:58 | 显示全部楼层
算法在很多地方还能改进
回复

使用道具 举报

发表于 2007-12-22 16:52:02 | 显示全部楼层
辛苦费,晕倒,ly这个图和正确答案不一样,这样到最后那里小红心不是向上的。
A点小红心向上,最后城堡小红心向上,其它时候小红心不能向上

谁能帮我演绎一下ly花心大萝卜的程序?谢谢!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|网上读书园地

GMT+8, 2024-5-18 07:46 , Processed in 0.410170 second(s), 5 queries , Redis On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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