Question

求一个matlab程序，运行时间越短越好

题目17：考察立方体两个角落间的最短距离。
一只蜘蛛S坐在一个6×5×3的立方体屋子的一个角落里，一个苍蝇F坐在与之相对的角落里。如果只允许在屋子的表面行走的话，从S到F的最短“直线”距离是10，路线在图中标出。

但是，每个立方体都有三条可能的最短路径，而且最终的最短路径并不一定是整数。
考虑所有整数边长的立方体屋子，最大不超过M×M×M，当M=100时一共有2060个立方体的最短路径是整数，而且这也是解超过2000的最小的M；M=99时又1975个立方体的最短路径是整数。
找出解超过一百万的最小的M。

Answer 1

楼主确定M=100的时候，有2060个立方体（确切一点说，应该是长方体吧？）的最短路径是整数吗？我算出来的是4430个，而M=99时对应的是4289个。

 

我不敢肯定自己是对的，所以，建议从比较小的M入手，我们对比一下结果，先确定方法是正确的，再考虑进一步优化程序，以提高效率（对于比较大的M，涉及到内存和运行时间两方面问题，需要进一步研究）。

 

以下是我取M=3~10的时候，对应的最短路径是整数的立方体个数：

     3     2
     4     3
     5     3
     6     7
     7     9
     8    14
     9    20
    10    23

请楼主核实一下自己的答案，如果有异议，我们再来进一步对比分析。

追问

我写出来一个程序，但是运行时间特别长，当M=100时，确实是2060个。做的时候需要排除掉重复的情况。比如a=1,b=2,c=3,与a=2,b=1,c=3是同一种情况，这两个长方体的长宽高是一样的。现在明白这个题目的意思了吗？要排除重复的情况.

追答

这个我明白，我说的就是剔除重复项之后的数。

 

但对于M比较大（比如100）的情况，要罗列出所有的组合太麻烦，所以我上面建议用小一些的M来比较我们的结果是否一致，如果不一致，再进一步分析哪个是对的。根据我的计算，刚好M=70的时候，最短路径是整数的立方体个数是2000。

 

我写的程序尽量使用向量化运算，效率还可以，G630的CPU，4G内存，XP系统，对于M=100，运行一次只需要0.1秒左右的时间。但如果M超过200，会遇到内存不足的问题，为了克服该问题，程序会复杂不少，效率也会受影响。

 

不妨再多贴一些M值的结果：

     3     2
     4     3
     5     3
     6     7
     7     9
     8    14
     9    20
    10    23
    11    26
    12    40
    13    44
    14    48
    15    61
    16    72
    17    76
    18    89
    19    96
    20   120

对于比较小的M，相信应该不会有太多出入，例如M=3的abc组合只有两种：

     3     1     3
     2     2     3

M=7的组合有9种：

     2     1     4
     3     1     3
     7     1     6
     2     2     3
     6     2     6
     5     3     6
     4     4     6
     7     5     5
     6     6     5

 

楼主可以看看是从哪个M开始，我们的结果不同的，并贴出相应的abc组合，然后我再拿我的结果和你对照。

追问

  

上面就是M从3到50的结果。昨天晚上停电了，所以没有及时回复。你比较一下。

我把我的程序贴出来吧。还有7 1 6你的这三个出了问题，最短路径不是整数。

这个就是我计算M从3到50的程序。你看一下就会知道我的思路，这个程序中的combntns语句耗时太长。我没有考虑用循环。你试试换一个思路来解决。

追答

你的程序我稍后再看，但你所说“7 1 6最短路径不是整数”恐怕不对吧？其最短路径是10，另外两组的最短路径是13，你不妨检验一下。

 

我觉得你的程序最大问题可能在“==0”上，因为经过浮点数开方运算，很容易造成误差，不一定能满足严格等于0的条件。你不妨改成abs(·)<=eps试试。

 

另，程序最好贴出文字版，我总不成再重新录入一次吧。即使贴图片版，至少应该考虑程序的缩进，以及使用等宽字体，否则很难读。

仔细想了一下，的确是我的算法有误。稍后修改一下。

追问

我写的程序不好，只是给你看看，贴图片是因为字数限制。最短路径应该是两条短边和的平方再加上另一条长边的平方再开方。就是sqrt(（a+b）^2+c^2),其中a<=b<=c。你再试试是不是。

追答

嗯，我原来算法的错误就在于任意取了前两个边求和。在你上一次追问之前，我补充了一句“仔细想了一下，的确是我的算法有误。稍后修改一下”，就是因为发现了这个问题。

 

对程序做了一些改进，目前的结果如下（第1列为M，第2列为长方体数量，第3列为计算耗时）：

    10       14       0.00
    70      943       0.03
    99     1975       0.11
   100     2060       0.11
   150     4918       0.36
   200     9034       0.84

楼主可以试试和自己程序的运行时间相比，是否能快一些。如果尚且比不上楼主的程序，那我也就没必要继续改进了。如果效率还可以，我再进一步研究如何解决内存不足的问题（M超过200就容易导致内存不足，目前的解决手段还比较简单），以及如何尽快找到长方体超过一百万的最小M（肯定不能简单地用循环方式增大M，需要采取一些策略）。

Answer 2

可以说一下思想吗？

Answer 3

Answer 4

呵呵。。。。。