[第24期]蛇棋（已总结）

agstick

[此贴子已经被作者于2007-6-26 21:25:35编辑过]

chylhr

已发至指定邮箱,请版主审核.

已发至指定邮箱,请版主审核.

投机取巧了，当蛇或梯子的数量大于3时不适用。求解时只考虑梯子，没有考虑蛇的影响，

蛇头所占的位置应该排除，如：1蛇1梯时，蛇：94－>33,梯子：2－>88，正确最小次数为4次（例：

1－2（88）－93－99－100），94是不可达的，按你的解法将为3次。ps：初始化是求解结果没有清除。

[此贴子已经被agstick于2007-6-23 17:28:57编辑过]

willin2000

答案已发送至：agstick@126.com，跟贴占位先。

第一次答VBA题，不知是否正确，请版主和大家指正。

此时次数为5次：

1－7－62（13）－47（68）－95（53）－100

[此贴子已经被agstick于2007-6-27 21:53:47编辑过]

fjlhgs

答题已发送至版主信箱agstick@126.com，请评阅。

结果正确，谢谢参与。

[此贴子已经被agstick于2007-6-23 17:43:09编辑过]

leeyong

这道题整了我一个白天还加一个通霄,终于干出来了,还不晓得对不对,真是的,整点简单的嘛,

图形操作起来太困难了

我自己先传上来,我的答案

抱歉，没看仔细，你的求解算法有误，如1蛇1梯，梯子：2－>98,求解出来为1次，正确应为2次，最小次数不能低于2次。by agstick

WHY?如果我第一次掷出4是不是可以一次就从从路径1->2->98->99->100到达终点?

终于明白你的意思了,看了W某的解答.原来是只能在一次掷SHAI子时的起点时才能爬梯子啊,

原先以为你说我做错了,我还以为是因为爬梯子只能一层层的爬,原来楼主意思却象是只能在一次掷SHAI子的起点处才能爬梯子,我原先的理解是:只要有梯子就可以爬,而不管是不是在一次的起点处,而且爬完整个梯子应该算作一步且仅算作一步。

不知道是我误解了,还是版主没有表述清楚???????

这本来是很直观得，小时候得飞行期，大家都玩过，扔一次色子就走一次，就是一步了，扔了几就走几格，只有到达得那格有梯子才能爬。－by agstick

[此贴子已经被agstick于2007-6-25 23:59:16编辑过]

f_qc

仅做了第一部分，求解没有想到好的方法，这几天再想想，先把第一部分发上来吧！！

只做了第一步，画线的方法不好，坐标可以直接借用单元格的Left、Width等属性，不用自己计算。

[此贴子已经被agstick于2007-6-23 17:55:24编辑过]

Luckyguy2008

VBA新人，绞尽脑汁才做出来，已经发到您的邮箱，请多多指教。

===================================================

蛇并不是完全没用的，比如下面这个例子，最短步数应该是4。
蛇：（63，43）；梯子：（2，62），（44，97）

结果正确，只是求解算法较慢。

[此贴子已经被agstick于2007-6-24 21:33:08编辑过]

leeyong

因为版主扣了我到手的一分,我开始查找自己的错误,经过我的测试,willin2000兄答案似乎有误。

权当我是一个报复欲强烈的人吧，楼主的还没有出来，就找楼主格外称赞的答案的茬了。

例：梯子（7->58)、(69->95)蛇(63->2)：经willin2000的代码找出的最少次数为4次。

但实际情形却是：假若每次掷6的情形，

第一次：1->7

第二次：07-58-59-60-61-62-63(因为63为蛇头，故第二次只能掷5，到达62处，7-58为一次爬梯子）

第三次：62-63-64-65-66-67-68

第四次：68-69-95-96-97-98-99（情形1：如果在中途可以爬梯子的话应该可以用该路径；情形2：若不能在中途爬梯子，只能在一次的起点处爬梯子，则为了爬梯子，则本次路径调整为68-69）

第五次：99-100（情形1时的情况，若为情形2则应调整为：69经梯子到95-96-97-98-99-100）

我建议：为了维护本论坛竞赛的严肃性、公正性，减少可能因出题者疏漏而导致的错评分，崇尚真理、维护真理的最大权威，是不是可以“不以版主之言为真言”，充分发挥群众的力量，让广大会员参与纠错评分，并给予纠错者适当的分值奖励。如以误加（误扣）分值加给纠错群众。

willin2000的没错，到了58在扔6就是64（58+6）了，您的建议很好，出题者难免会有疏忽的时候，而且很多代码书写不够规范又没有注释，看起来很费时，你的那个错误就是Luckyguy2008发现的，我开始只是验证几次没问题，大概看了一下算法，后来仔细看了一下，发现问题不小。以后一定仔细，避免错误，－By agstick

现在终于看明白了，原来爬梯子不算作一步，并且一次扔色子后，没有路径的问题，只是在原来的位置上加上色子点数为新位置，不是一步一步的走，并在每走一步时如有梯子都可以攀爬．都怪小时没有玩过爬行棋了，没有理解题意．意思

[此贴子已经被作者于2007-6-26 18:23:37编辑过]

agstick

总结

本期竞赛题主要有以下几个考点：

1． S形填数
这个很简单，方法很多，主要就是分一下奇偶就可以了。

2． 生成随机不重复数
这个其实也容易，最直观的算法，先生成一个随机数，再生成一个随机数，与前面生成的比较如果重复就不要，接着继续生成。（大家好像都是用的这种方法）。把它优化一下就是这样：
Public Sub rand1()
    Dim n(1 To 100), i, j, q
    
     For i = 1 To 100
        n(i) = 0
     Next
     j = 0
     Randomize
     While j < 10
        q = Int(Rnd * 99 + 1)
        If n(q) = 0 Then
            Debug.Print q
            n(q) = 1
            j = j + 1
        End If
     Wend
End Sub
此算法生成1－100间的10个不重复随机数。
解析：定义一个标记数组n(1 To 100)，将数组的每个值都设成0。生成1－100间的一个随机数q，将下标为q 的数组元素n（q）的值变为1，接着在生成下一个随机数s（其实还是q），此时只有判断n（s）是否为0，就可以知道有没有生成过此随机数，而不用在与前面生成的所有随机数做比较。
但是上面的算法仍然不是最优的，因为仍会产生重复的多余的数据。
看下面的算法，可以避免产生不必要的多余数据。
Public Sub rand2()
upperbound = 100 '设定初始值上界
Lowerbound = 1 '设定初始值下界
Dim RndNum(1 To 10) '设定动态数组,如果事先知道数组大小可直接设定大小值
Dim MyArray(upperbound) '定义动态数组的大小
For i = Lowerbound To upperbound '将Lowerbound与Upperbound之间的数顺序写入数组中
   MyArray(i) = i
Next
For i = 1 To 10 '随机取数
   Randomize
   Tmp = Int((upperbound - Lowerbound - i + 2) * Rnd + Lowerbound)
   RndNum(i) = MyArray(Tmp) '取得当前已经获取的值
   MyArray(Tmp) = MyArray(upperbound - i + 1) '将数组的最后一个值填入已取的位置
Next
End Sub

解析：先将1－100放入一个数组MyArray中，生成一个1-100的随机数Tmp，将下标为Tmp的数组元素MyArray(Tmp)的值作为生成的第一个随机数，然后将MyArray的最后一个值填入MyArray(Tmp)，接着生成第二个随机数应为1－99之间，此时取出MyArray中对应下标的元素值，就不会有重复了，因为重复的值已经被最后的值替换了。

3．操作直线对象
用VBA来操作直线对象，只要录制一个宏，所有的属性都清楚了。要获取下拉框的值要用到ControlFormat对象，用链接单元格的值有时候是不行的，除非下拉项的值为1、2、3。。。
（如本题是凑巧），否则应该用Shapes("snakenumber").ControlFormat.Value。
本题第二部分的求解需要获取箭头的起始位置，直接从图形来获取也是可以的，就是通过判断直线是否经过了水平和垂直翻转，然后通过TopLeftCell和BottomRightCell属性来获取其实单元格，具体方法见willin2000和leeyong的代码。其实这里是可以偷一下懒的，直接用第一步中生成的不重复随机数。
4．求解算法
这题的算法其实并不难，就是一个一维搜索的问题，大家把问题想复杂了，很多答案都用了递归来求解，其实没有必要。其实，此题是改编自一道ACM的试题，应该是最简单的了。
具体的算法及答案见附件里。

附件上传错了，现在更正

我的答案的验证方法：

在求解的过程代码前加入初始值，然后直接按求解，不用按开始。

如：

Sub 求解()
Dim Step As Integer
Dim grid(1 To 100) As Integer
Dim gridbak(1 To 100) As Integer
'
ReDim SnakeLadder(1 To 3)   '设定蛇和梯子的数量
n = 6                 '端点个数
SnakeLadder(1).L_Fr = 2           '起始点设置
SnakeLadder(1).L_To = 62
SnakeLadder(2).L_Fr = 44
SnakeLadder(2).L_To = 97
SnakeLadder(3).L_Fr = 63
SnakeLadder(3).L_To = 43
Step = 0
grid(1) = 1
。。。。。

[此贴子已经被作者于2007-6-28 9:58:33编辑过]

Luckyguy2008

版主给出的求解算法好像都是在处理梯子，并没有考虑蛇，其实蛇也是有用的。

比如我上面列举的例子：蛇：（63，43）；梯子：（2，62），（44，97）

如果不考虑蛇，应该需要8步。

最佳走法应该是4步：
第一步投1：1 -〉 2跳至62
第二步头1：62-〉63跳至43
第三步投1：43-〉44跳至97
第四步投3：97-〉100

===============================================

版主更新的这个算法很巧妙，正在努力学习中，收回上面说的话。
谢谢版主。

[此贴子已经被作者于2007-6-28 9:48:01编辑过]