找回密码
 注册
搜索
热搜: 超星 读书 找书
楼主: 磁铁

[探索发现♡] 探索  (棋牌益智类)《寒武能够到找到艾莉吗?》(已有答案,请等待续集)

[复制链接]
发表于 2007-12-22 22:46:34 | 显示全部楼层
原来已经解了啊。
回复

使用道具 举报

 楼主| 发表于 2007-12-22 22:53:58 | 显示全部楼层
引用第79楼fferror于2007-12-22 22:45发表的 :
建议先不要解密。
继续诱惑各路高人。

你快些数学妙笔吧!跑来遛达啥
回复

使用道具 举报

发表于 2007-12-23 01:06:42 | 显示全部楼层
原来我的PC机也不慢啊。

在修改了程序错误之后,我把昨天的程序在我的PC机上运行了一下,完成全部搜索,该算法总共走了141,390,059步(包括试探),用时332秒。

修改后的新算法(老程序改了几个数字,加了几个限制),完成全部搜索,总共走了12864步,用时0.013秒。

以下内容需要积分高于 0 才可浏览

我先是手算,确定了计算方法,发现可能的解很多,便开了一个数组t(k,i,j),i是行号,j是列号,存放的数据是红心的朝向,

未走过=0,朝东=1,朝西=2,朝北=3,朝南=4,朝上=5,朝下=6。

这个数组其实是个堆栈,因为在手算的时候我就注意到,每走出一步,就会多出几个可能性,每一种还未验证过的可能性都被压入堆栈,堆栈指针为n。

24-27行描述了一个开始,堆栈指针n=0,红心朝上。

这里出现了一个数组u,它是用来记录这一步是从哪个方向走来的,从东面=1,从西面=2,从北面=3,从南面=4。

由于这个题目是上下对称的,若它有一个非对称解,那么必然就有一个镜像,即必有偶数个解。因为磁铁版主说了,解唯一,所以解必然不是非对称的。于是,我们就只要考虑上面一半区域里的走法。

接下去就是从寒武此刻所在位置向东南西北4个方向试探。

32行的mp是此刻红心的朝向。试探时调用了一个子程序position(mp, dir),用来得到翻动之后红心的朝向,其实就是一张表,

mp=1 6, 5, 1, 1, 原红心向东,向东、西、北、南翻动后的朝向分别为 下、上、东、东
mp=2 5, 6, 2, 2, 原红心向西,向东、西、北、南翻动后的朝向分别为 上、下、西、西
mp=3 3, 3, 6, 5, 原红心向北,向东、西、北、南翻动后的朝向分别为 北、北、下、上
mp=4 4, 4, 5, 6, 原红心向南,向东、西、北、南翻动后的朝向分别为 南、南、上、下
mp=5 1, 2, 3, 4, 原红心向上,向东、西、北、南翻动后的朝向分别为 东、西、北、南
mp=6 2, 1, 4, 3, 原红心向下,向东、西、北、南翻动后的朝向分别为 西、东、南、北

先设定试探行动的指针,n_new=n

向东试探,36行计算的mp_new就是向东翻动后红心的朝向,试探成功的条件是:

37行:
if (tj[ n] < 7) 不在右边界上;
if (!t[ n][ ti[ n]][ tj[ n] + 1]) 右边的格子没走过;
if (mp_new != 5) 红心不朝上

如果成功,39-48行就把堆栈指针n_new增加,把它送入第n_new层堆栈保存起来,寒武在这次试探中此时所处的位置则记录在ti[n_new]和tj[n_new]中。如果不成功则什么也不做。

然后向西试探,试探成功的条件是53行:

if (tj[ n]) 不在左边界上;
if (ti[ n]) 不在第1行(如果在第1行,向西走是进入死区);
if (!t[ n][ ti[ n]][ tj[ n] - 1]) 左边的格子没走过;
if (mp_new != 5) 红心不朝上

然后向北试探,试探成功的条件是69行:

if (ti[ n]) 不在上边界上;
if (tj[ n] < 7) 不在最右边一列(如果在最右边,向上走是进入死区);
if (tj[ n]) 不在最左边一列(如果在最左边,向上走是进入死区);
if (!t[ n][ ti[ n] - 1][ tj[ n]]) 上边的格子没走过;
if (mp_new != 5) 红心不朝上

然后向南试探,试探成功的条件是85行:

if (ti[ n] < 3) 不在下边界上;
if (!t[ n][ ti[ n] + 1][ tj[ n]]) 下边的格子没走过;
if (mp_new != 5) 红心不朝上

现在,四个方向都试探过了。如果有路可走,就有 n_new>n,那几条路也已送入堆栈,寒武不必留在原地,所以,102-109行把原来在堆栈n中的内容去除,寒武则到堆栈最上层的那个位置,开始新的探索(109、115行)。

如果四个方向的试探都失败了(n_new=n),先检查,是不是每个空格都走过了(118行),如果还有空格,说明刚才寒武所在位置n是条死胡同,放弃它,把指针往下移一下(120行),站到下面一层所记录的位置上(121行)。如果n=0,说明所有可能性都已试过了,结束计算(122行)。

如果四个方向的试探都失败了,并且每个空格都走过了,那么,这条路就走到头了,我们只要看看这条路的尽头是不是寒武要去的地方就可以了。

124行: if (ti[ n] == 3) 在下边界上

既然路的尽头在下边界上,那么,只要寒武按照刚才的路径向下镜像复制下去,就可以找到公主了。

126-133行只是把记录每一步是从哪个方向来的,改为要向哪个方向走,便于根据输出结果绘图。

以下是新算法的完整的程序。

1    #include <ansi_c.h>
2    #include <math.h>
3    #include <stdio.h>
4    #include <stdlib.h>
5   
6    // free=0, e=1, w=2, n=3, s=4, t=5, b=6
7    // move e(right)=1, w(left)=2, n(up)=3, s(down)=4
8   
9    int position(int mp, int direction)
10   {
11     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};
12     return n[ mp - 1][ direction - 1];
13   }
14   
15   #define MM 1000
16   short int t[ MM][ 4][ 8], u[ MM][ 4][ 8], v[ 4][ 8], ti[ MM], tj[ MM];
17   
18   int main (void)
19   {
20     int i, j, k, n, nn, ss, n_new, mp, mp_new;
21   
22     ss = time(0);
23     nn = 0;
24     n = 0;
25     ti[ n] = tj[ n] = 0;
26     for (i = 0; i < 4; i++) for (j = 0; j < 8; j++) t[ 0][ i][ j] = u[ 0][ i][ j] = 0;
27     t[ 0][ 0][ 0] = 5;
28   
29   L_0:
30     nn++;
31     n_new = n;
32     mp = t[ n][ ti[ n]][ tj[ n]];
33     // printf("%d\n", mp);
34   
35     // right
36     mp_new = position(mp, 1);
37     if (tj[ n] < 7) if (!t[ n][ ti[ n]][ tj[ n] + 1]) if (mp_new != 5)
38     {
39       n_new++;
40       for (i = 0; i < 4; i++) for (j = 0; j < 8; j++)
41       {
42         t[ n_new][ i][ j] = t[ n][ i][ j];
43         u[ n_new][ i][ j] = u[ n][ i][ j];
44       }
45       ti[ n_new] = ti[ n];
46       tj[ n_new] = tj[ n] + 1;
47       t[ n_new][ ti[ n_new]][ tj[ n_new]] = mp_new;
48       u[ n_new][ ti[ n_new]][ tj[ n_new]] = 1;
49     }
50   
51     // left
52     mp_new = position(mp, 2);
53     if (tj[ n]) if (ti[ n]) if (!t[ n][ ti[ n]][ tj[ n] - 1]) if (mp_new != 5)
54     {
55       n_new++;
56       for (i = 0; i < 4; i++) for (j = 0; j < 8; j++)
57       {
58         t[ n_new][ i][ j] = t[ n][ i][ j];
59         u[ n_new][ i][ j] = u[ n][ i][ j];
60       }
61       ti[ n_new] = ti[ n];
62       tj[ n_new] = tj[ n] - 1;
63       t[ n_new][ ti[ n_new]][ tj[ n_new]] = mp_new;
64       u[ n_new][ ti[ n_new]][ tj[ n_new]] = 2;
65     }
66   
67     // upword
68     mp_new = position(mp, 3);  
69     if (ti[ n]) if (tj[ n] < 7) if (tj[ n]) if (!t[ n][ ti[ n] - 1][ tj[ n]]) if (mp_new != 5)
70     {
71       n_new++;
72       for (i = 0; i < 4; i++) for (j = 0; j < 8; j++)
73       {
74         t[ n_new][ i][ j] = t[ n][ i][ j];
75         u[ n_new][ i][ j] = u[ n][ i][ j];
76       }
77       ti[ n_new] = ti[ n] - 1;
78       tj[ n_new] = tj[ n];
79       t[ n_new][ ti[ n_new]][ tj[ n_new]] = mp_new;
80       u[ n_new][ ti[ n_new]][ tj[ n_new]] = 3;
81     }
82   
83     // downword
84     mp_new = position(mp, 4);
85     if (ti[ n] < 3) if (!t[ n][ ti[ n] + 1][ tj[ n]]) if (mp_new != 5)
86     {
87       n_new++;
88       for (i = 0; i < 4; i++) for (j = 0; j < 8; j++)
89       {
90         t[ n_new][ i][ j] = t[ n][ i][ j];
91         u[ n_new][ i][ j] = u[ n][ i][ j];
92       }
93       ti[ n_new] = ti[ n] + 1;
94       tj[ n_new] = tj[ n];
95       t[ n_new][ ti[ n_new]][ tj[ n_new]] = mp_new;
96       u[ n_new][ ti[ n_new]][ tj[ n_new]] = 4;
97     }
98     // printf("nn=%d, n=%d\n", nn, n);
99     
100     if (n_new > n)
101     {
102       for (k = n; k < n_new; k++) for (i = 0; i < 4; i++) for (j = 0; j < 8; j++)
103       {
104         t[ k][ i][ j] = t[ k + 1][ i][ j];
105         u[ k][ i][ j] = u[ k + 1][ i][ j];
106         ti[ k] = ti[ k + 1];
107         tj[ k] = tj[ k + 1];
108       }
109       n = n_new - 1;
110       if (n > MM - 4)
111       {
112         printf("not finifshed\n");
113         goto L_end;
114       }
115       goto L_0;
116     }
117   
118     for (i = 0; i < 4; i++) for (j = 0; j < 8; j++) if (!t[ n][ i][ j])
119     {
120       n--;
121       if (n >= 0) goto L_0; // if (n) goto L_0;
122       else goto L_end;
123     }
124     if (ti[ n] == 3)
125     {
126       for (i = 0; i < 4; i++) for (j = 0; j < 8; j++)
127       {
128         if (u[ n][ i][ j] == 1) v[ i][ j - 1] = 1;
129         else if (u[ n][ i][ j] == 2) v[ i][ j + 1] = 2;
130         else if (u[ n][ i][ j] == 3) v[ i + 1][ j] = 3;
131         else if (u[ n][ i][ j] == 4) v[ i - 1][ j] = 4;
132       }
133       v[ ti[ n]][ tj[ n]] = 0;
134   
135       for (i = 0; i < 4; i++)
136       {
137         for (j = 0; j < 8; j++) printf("%d-%d ", t[ n][ i][ j], v[ i][ j]);
138         printf("\n");
139       }
140       printf("\n");
141     }
142     n--;
143     if (n >= 0) goto L_0; // if (n) goto L_0;
144   L_end:
145     printf("nn=%d, time=%ds\n", nn, time(0)-ss);
146     scanf("%d", &i);
147     return 0;
148   }


回复

使用道具 举报

发表于 2007-12-23 12:30:38 | 显示全部楼层
这种题目可能用PROLOG写比较简单
回复

使用道具 举报

发表于 2007-12-23 19:10:55 | 显示全部楼层
刚才又算了一下,发现了又一个秘密。

原来,艾莉不仅是个美丽的公主,而且无比聪明。

按照艾莉的要求,寒武只能到达艾莉公主的城堡,即, “终点红心向上,途中红心不能向上”,只有一个解,那就是,到艾莉那里去。

那要用我第一个程序计算,并将到达终点时的判断由原来的

if (ti[n] == 7 && tj[n] == 0 && t[n][ti[n]][tj[n]] == 5) // 到达城堡且红心向上

  if (ti[n] == 7 && tj[n] == 0) // 到达城堡,红心不必向上

改为,
  if (t[n][ti[n]][tj[n]] == 5) // // 不管到哪里,只要在终点红心向上

寒武根本不可能走到别的姑娘那里去!这就是艾莉的聪明所在。
回复

使用道具 举报

发表于 2007-12-23 19:17:12 | 显示全部楼层
不对,至少有一个错误。请先取消评分
回复

使用道具 举报

 楼主| 发表于 2007-12-23 19:17:55 | 显示全部楼层
知道为什么ly188走不出去了,因为他太花心了
回复

使用道具 举报

发表于 2007-12-23 19:42:13 | 显示全部楼层
按照对称性,至少应该可以走到右上角的。怎么就搜索不到呢?
回复

使用道具 举报

发表于 2007-12-23 19:46:22 | 显示全部楼层
能走左下 应该能走右上的
右和下换 左和上换

棋盘问题 以前见过八皇后和马遍历
找公主到是头遭
回复

使用道具 举报

 楼主| 发表于 2007-12-23 20:07:45 | 显示全部楼层
评分是下次发现的定金,哈哈,我突然想起来原题就是右上,我为画图方便改成了左下 ,这几天忙晕了
回复

使用道具 举报

 楼主| 发表于 2007-12-23 20:09:50 | 显示全部楼层
引用第88楼ly188于2007-12-23 19:46发表的 :
找公主到是头遭

看寒武中奖消息一激动,就给他配了个公主
回复

使用道具 举报

发表于 2007-12-23 20:19:38 | 显示全部楼层
引用第86楼磁铁于2007-12-23 19:17发表的 :
知道为什么ly188走不出去了,因为他太花心了

他花心?我报告天使心去,明天见头条新闻
回复

使用道具 举报

发表于 2007-12-23 20:55:24 | 显示全部楼层
引用第84楼bookish 于2007-12-23 19:10发表的 :
刚才又算了一下,发现了又一个秘密。

原来,艾莉不仅是个美丽的公主,而且无比聪明。

按照艾莉的要求,寒武只能到达艾莉公主的城堡,即, “终点红心向上,途中红心不能向上”,只有一个解,那就是,到艾莉那里去。.......

艾莉真的想这么聪明一下,哎,只能自己困在城堡里了,寒武--------------------
回复

使用道具 举报

发表于 2007-12-23 21:06:00 | 显示全部楼层
我在,找不到不要紧,能看到就成了,可苦了你了,要呆在小城堡里面度日了
回复

使用道具 举报

发表于 2007-12-23 21:10:38 | 显示全部楼层
留着丝丝长发,好把你栓回来。
回复

使用道具 举报

 楼主| 发表于 2007-12-23 21:16:03 | 显示全部楼层
哈哈,艾莉还是幽默大师父
回复

使用道具 举报

发表于 2007-12-23 21:46:20 | 显示全部楼层
三千青丝真能把我栓住
回复

使用道具 举报

发表于 2007-12-23 21:46:23 | 显示全部楼层
程序的错误找到了,

121    if (n) goto L_0;

143    if (n) goto L_0;

都应该是

      if (n >= 0) goto L_0;

结果已经出来了,总共有4座城堡,左下角、右上角、图示位置以及对角线对称映射过去的位置。



走了141,390,059步,332秒。

算法已经写出来了,在加密部分,等版主在适当的时候解密。

本帖子中包含更多资源

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

×
回复

使用道具 举报

发表于 2007-12-23 21:51:59 | 显示全部楼层
bookish 老师~
开始讲解吧7375怎么来的额
回复

使用道具 举报

 楼主| 发表于 2007-12-23 21:58:29 | 显示全部楼层
请bookish骑士快来帮助帮助我们这些小骑士吧
回复

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-7-17 03:54 , Processed in 0.987363 second(s), 4 queries , Redis On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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