ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
HR薪酬管理数字化实战 Excel 2021函数公式学习大典 Excel数据透视表实战秘技 打造核心竞争力的职场宝典
300集Office 2010微视频教程 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
用ChatGPT与VBA一键搞定Excel WPS表格从入门到精通 Excel VBA经典代码实践指南
查看: 6847|回复: 11

[Excel 程序开发] [第24期]蛇棋(已总结)

[复制链接]

TA的精华主题

TA的得分主题

发表于 2007-5-28 23:20 | 显示全部楼层 |阅读模式
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册


[此贴子已经被作者于2007-6-26 21:25:35编辑过]
单选投票, 共有 12 人参与投票

距结束还有: 3849 天8 小时55 分钟

您所在的用户组没有投票权限

本帖子中包含更多资源

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

x

TA的精华主题

TA的得分主题

发表于 2007-5-30 11:20 | 显示全部楼层

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

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


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

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

1-2(88)-93-99-100),94是不可达的,按你的解法将为3次。ps:初始化是求解结果没有清除。

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

本帖子中包含更多资源

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

x

TA的精华主题

TA的得分主题

发表于 2007-6-3 23:46 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助

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

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


此时次数为5次:

1-7-62(13)-47(68)-95(53)-100


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

本帖子中包含更多资源

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

x

TA的精华主题

TA的得分主题

发表于 2007-6-4 15:58 | 显示全部楼层

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


结果正确,谢谢参与。

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

本帖子中包含更多资源

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

x

TA的精华主题

TA的得分主题

发表于 2007-6-10 16:19 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助

回复

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

图形操作起来太困难了

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


抱歉,没看仔细,你的求解算法有误,如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编辑过]

本帖子中包含更多资源

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

x

TA的精华主题

TA的得分主题

发表于 2007-6-13 19:14 | 显示全部楼层

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


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

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

本帖子中包含更多资源

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

x

TA的精华主题

TA的得分主题

发表于 2007-6-18 13:04 | 显示全部楼层

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

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

蛇并不是完全没用的,比如下面这个例子,最短步数应该是4。
蛇:(63,43);梯子:(2,62),(44,97)


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

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

本帖子中包含更多资源

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

x

TA的精华主题

TA的得分主题

发表于 2007-6-25 22:37 | 显示全部楼层

因为版主扣了我到手的一分,我开始查找自己的错误,经过我的测试,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编辑过]

TA的精华主题

TA的得分主题

 楼主| 发表于 2007-6-26 00:22 | 显示全部楼层

总结

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

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编辑过]

本帖子中包含更多资源

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

x

TA的精华主题

TA的得分主题

发表于 2007-6-26 09:58 | 显示全部楼层
版主给出的求解算法好像都是在处理梯子,并没有考虑蛇,其实蛇也是有用的。

比如我上面列举的例子:蛇:(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编辑过]
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2024-3-29 14:25 , Processed in 0.057070 second(s), 16 queries , Gzip On, Redis On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

沪公网安备 31011702000001号 沪ICP备11019229号-2

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:李志群律师

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