[开_72]一道益智题，试试大家的编程技巧 [已总结]

asdf1001 · 发表于 2005-12-9 13:37

不同的算法，不同速度

0y6vz8yB.rar (13.29 KB, 下载次数: 155)

等有空了再把注释补上。

山菊花 · 发表于 2005-12-9 22:48

还可以提速，其实找出一条路线后，沿终点逆过来就是另一条路线。如：

0_0 1_2 2_0 0_1 1_3 3_2 1_1 3_0 2_2 1_0 3_1 2_3 0_2 2_1

0_0 2_1 0_2 2_3 3_1 1_0 2_2 3_0 1_1 3_2 1_3 0_1 2_0 1_2

hy8888 · 发表于 2005-12-10 08:33

如果没理解错,11楼的代码利用了对称点来提速了,检查条件的算法比较独特,学习了

12楼的思路只能说是有想法,如果用在代码中,要提速未必很容易,起码要判断逆转后的路线是否有重复,如果有,还得排除,在数组中倒未必比不逆转的代码快上多少[em08]

shuyee · 发表于 2005-12-16 14:27

这题可以使用自调函数.我以为每个落脚点只要找出一解法呢,所以原来利用单元格的代码就不传了.说真的,由于我没怎么用过C(更没学过),自调处理起来比较困难.大伙有兴趣可以试试.

hcf568 · 发表于 2005-12-22 14:58

呵呵，真是高手呀！

hcf568 · 发表于 2005-12-26 10:52

呵呵，我没有时间编写了，但我提出了几点提高速度的思路！可能会提高10倍！

1、既然每个点都能踏到而必须踏到，且必须能回到原出发点，则每一条线路则是一条可以形成闭环的路线，选择其中任何一点开始就是一种新的走法，共有14个点，因此第一条基本循环路线都有14种走法，计算出一个循环后，把14个点的排序信息做成一个有14个数据的数组，依次以排序的点开始，并让数组首尾相连，这样就可以轻松输出14种走法了！

2、日字角的走法规则是对称的，也就是可逆的，因此把第1条的基本循环路线按逆序输出又衍生出另一条准基本的路线，根据1的思想又产生14条线路。由此可见，正确答案必定是14＊2＝28的倍数！由此推广，以此为规则的所有不同的图案的正确路线必定是2＊点数的倍数，包括没有正确答案时的0,呵呵，0是任何数的倍数！

3、根据1、2的思想，只要测出任何一个开始点的正确答案就能计算出所有的路线来，因此我们应当选择一个只有2种第2点的点开始计算，并且只计算其中的一个第2步的走法就行了，这样可以减少以后计算错误路线的过程。根据规则，不难看出任何一个内角只有90度的点都只有两个第二步点，因此均可成为理想的开始点，但是0,0点开始设计比较直观，计算比较方便，因此还是0,0开始，第二步为2，1或1,2的任何一条比较好！

经过以上3点的分析，我认为以全部都采用暴力全方位的计算方案做对比，速度至少提高10倍！

不知老管是否认同本人观点，并且加分－－呵呵，我没有时间做程序了！

hcf568 · 发表于 2005-12-26 10:55

我的思路希望能得到大家的认同！谢谢啦！！！嘿嘿

hcf568 · 发表于 2005-12-26 11:04

笔者认为，要设置一个后台程序不变，但又能适应前面的图案任意变化且不能在图案表增加任何辅助单元的程序，难度才能算比较难！

UNARTHUR · 发表于 2005-12-26 11:07

此题原来是一个flash益智游戏，公司里当时很多同事在玩，兴趣之余我用vba写了它的代码贴到程序版，后来由taller版主建议才修改成VBA测试题放到了竞赛区。编写这道题代码的时候注意以下几点可以帮助理解思路。

1，因为经过路径为14个不同的点，所以只要找到1组解救相当于找到了28组相似的解（14个不同的起始点+移动方向颠倒）。实际结果为共有4个不同的回路。当然想利用这一点来简化代码看似并不容易。

2，如果是编写常规思路的代码，难点在于处理好回退的过程，需要保证位置回退后不再重复走错误的路线。

3，本题计算量并不是很大，因此代码的速度并不是关键。在编程前经过仔细分析，找出题目中的一些tricks,对简化代码会很有帮助。

截至目前为止，给出本题答案的朋友一共有3位，boszzy:虽然是常规思路，但速度不错，注释详细，代码可读性强。

山菊花:代码最简单，循环镶套很漂亮。asdf1001:代码思路新颖，运行速度很快。

至于本人的代码，采用了最常规的编程思路，论简洁论速度都不及以上各位，但是作为始作俑者，也只能献丑了。

urQC3qm5.rar (10.86 KB, 下载次数: 144)

本想仔细研读几位的代码以后在作详细的总结，只可惜本人水平实在有限，加上恰逢年总结算，公司事情太多，只能总结到此地步了，如有不周，向大家致歉了。

hcf568 · 发表于 2005-12-26 12:14

笔者不赞同楼主的第1点意见，其实根本就没有难处，只是把输出结果的起点和方向改变一下很简单的呀，根本不去计算，只是输出的时候动点手脚而已，方法的数目只需＊28直接得出！

如果有1000多个点的时候，这种思路绝对重要！

		自动登录	找回密码
密码			免费注册

[Excel 程序开发] [开_72]一道益智题，试试大家的编程技巧 [已总结]

[总结]