魔方吧·中文魔方俱乐部

标题: 两个立方体的边长问题 [打印本页]

作者: yang_bigarm 时间: 2009-3-27 00:00:58 标题: 两个立方体的边长问题

没想到第一次在这个版发帖，居然有那么多人回应，小弟受宠若惊啊，
于是再来一个大餐，满足这里高手们的胃口。

------------------------------------------------Problem---------------------------------------------------
矩阵博士是一个爱出难题的人，他在桌子上放了两个立方体，矩阵博士告诉我们，
这两个立方体的边长都是有理数，它们的体积之和为16，然后问我们立方体的边长。
很快我们就得出它们的边长皆为2；现在矩阵博士又拿出了两个立方体，“这回的问题
和前面的一样，不过唯一不同的是它们的体积之和为17。”

那么这两个立方体的边长到底是多少呢？
----------------------------------------------------------------------------------------------------------------

列方程很容易，但是如何求解呢？个人觉得用手算是不太可能的，借助计算器也许有希望。
但我觉得最有希望的就是借助计算机，编程来解决这个问题。不妨假定两个正方体的边长分别是 x/z, y/z
x,y,z 都是正整数，我自己编了一个程序，发现1000以内的 x,y,z 都不可能是解，（用时0.3秒）
如果在更大的范围内求解的话，每扩大一个数量级，花的时间至少要多100倍，因此是否有人能挖掘
出这个问题的更深的内涵，不使用暴力搜索的方法来求解。

作者: tonylmd 时间: 2009-3-27 00:09:11

可以发一下你的算法？什么语言？

作者: 123小毛虫 时间: 2009-3-27 06:57:18

学习之中

作者: Cielo 时间: 2009-3-27 08:55:04

占个座位想想！

P.S:是出自《矩阵博士的魔法数》一书吗？

作者: zhy3729 时间: 2009-3-27 09:02:39

想一下……………？…………

作者: kexin_xiao 时间: 2009-3-27 13:49:04

坐地上学习，期待详细的解答学习一下

作者: lulijie 时间: 2009-3-27 18:33:40

到底是立方体还是正方体？

作者: kaylmu 时间: 2009-3-27 19:28:44

是17/2的立方根吗?　
原来是有理数…看漏了…

[ 本帖最后由 kaylmu 于 2009-3-27 21:02 编辑 ]

作者: lulijie 时间: 2009-3-27 19:49:53

解 x^3+y^3=17*z^3 ，x、y、z为正整数。
我觉得很难。让电脑来找，主要是如何优化算法。
让x=17*k +p ,y=17*m-p 来寻找不知会不会快些。( p=0 to 16)

作者: lucki1987 时间: 2009-3-27 19:52:41

看了下，很难很难的问题啊。。

作者: 骰迷 时间: 2009-3-27 20:44:04

兩個分數，三次方後的數字加起來是整數，確實很少見

作者: 风花雪夜 时间: 2009-3-27 23:28:26

设两个正方体的边长分别是 x/z, y/z x,y,z 都是正整数 2000以内符合条件的如下：（果然很慢，电脑都累坏了！）

附件: QQ截图.jpg (2009-3-27 23:28:26, 11.83 KB) / 下载次数 37
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NDMyMzZ8Y2QxNjg2NTl8MTc0NjI1NjgxMHwwfDA%3D

作者: yang_bigarm 时间: 2009-3-27 23:52:55

原帖由 tonylmd 于 2009-3-27 00:09 发表
可以发一下你的算法？什么语言？

随便什么语言都行啊，搜索10000以内的所有可能的情况很快的。

原帖由 Cielo 于 2009-3-27 08:55 发表

P.S:是出自《矩阵博士的魔法数》一书吗？

不是出自这本书，只是觉得矩阵博士这个人物总会有层出不穷的问题，所以借用他的名字。

原帖由 lulijie 于 2009-3-27 19:49 发表
解 x^3+y^3=17*z^3 ，x、y、z为正整数。
我觉得很难。让电脑来找，主要是如何优化算法。
让x=17*k +p ,y=17*m-p 来寻找不知会不会快些。( p=0 to 16)

楼下抓到这个问题的实质了，如何优化算法才是解答这个问题的关键。

原帖由骰迷于 2009-3-27 20:44 发表
兩個分數，三次方後的數字加起來是整數，確實很少見

这样的数多得不可胜数，怎么会少见呢？

原帖由 风花雪夜 于 2009-3-27 23:28 发表
设两个正方体的边长分别是 x/z, y/z x,y,z 都是正整数 2000以内符合条件的如下：（果然很慢，电脑都累坏了！）

你贴出的解一个都不对，而且我一开始就都说了，我自己编程检验过10000以内的所有x,y,z没有一个符合条件的。

作者: 风花雪夜 时间: 2009-3-28 00:37:57

自己拿计算机把结果算了一下，果然不对！汗……

作者: 骰迷 时间: 2009-3-28 09:52:43

這題從哪來的？有答案沒？會不會是耍人的

作者: yang_bigarm 时间: 2009-3-28 10:23:41

原帖由骰迷于 2009-3-28 09:52 发表
這題從哪來的？有答案沒？會不會是耍人的

我可以很自信地告诉你，这个问题是有答案的，而且有无数组答案，
更进一步告诉你，(x/z)^3 + (x/z)^3 =N，N取100以内的自然数且N不取立方数
的情况，都是有解答的。

作者: 骰迷 时间: 2009-3-28 17:32:48

解一定有，不過可能是天文數字罷
但這題是從哪來的？如果答案非常大，必須以電腦暴力尋解，那便沒什麼意思了

作者: yang_bigarm 时间: 2009-3-28 23:53:02

解一定有，不過可能是天文數字罷
但這題是從哪來的？如果答案非常大，必須以電腦暴力尋解，那便沒什麼意思了

电脑搜索当然是必要的，但是怎样巧妙地去搜素呢？也就是如何优化算法，这才是问题的关键所在啊。就好像你要用电脑去解一个3阶魔方，魔方有4.3乘10的19次方种状态，世界上任何电脑也不能存储这么多种状态，于是照你的逻辑就不可能直接搜索出来啊，但是cube explorer采用two phase algorithm把问题分解了，于是就能在不到1s的时间内得到接近最优解的步骤，这就是巧妙的算法，巧妙的搜索啊。你怎么能说，单凭我对问题目前的理解，觉得这个是个暴力搜索的题目，就没有意思了呢？为什么不仔细分析问题，把问题分解，排除简单的情况，缩小搜索的范围，最终一步步逼进答案呢？

说实话，这个题目确实有相当的难度，绝对不是在纸上乱画几下就，或者用计算器算几个数就能搞定的，是要不断优化自己的算法，不断缩小自己的搜索范围，逼近答案的。

[ 本帖最后由 yang_bigarm 于 2009-3-28 23:54 编辑 ]

作者: lulijie 时间: 2009-3-29 00:32:38

解  x^3+y^3=17*z^3 ，x、y、z为正整数。

因为X除以17 的余数与Y除以17的余数的和必须等于17或0。
不妨设X除以17的余数为 0~8，Y除以17的余数为  9~16，0
让x=17*k +p  ,y=17*m-p 。( p=0 to 8) 来搜索比全暴力搜索可以节约17*2=34倍时间
按照这个算法，17*591=10047以内无解，费时4秒。

作者: 骰迷 时间: 2009-3-29 10:38:32

這可是電腦奧林匹克的範疇？

作者: lulijie 时间: 2009-3-29 13:50:07

X和Y 都在100317以内无解，费时6分7秒时间。

作者: 金眼睛 时间: 2009-3-29 21:57:23

虽然数不是很大，还是动用了我的大数计算程序，呵呵！

思路：让z从1至无穷。设x大于y，则x在[(17/2)^(1/3)*z]与[17^(1/3)*z]之间。
用x，z推算y，并使y圆整为整数，计算p=x^3+y^3-17*z^3，以p最小作为限定，可以保存最佳结果。

p=0，则满足题意。

给出其中一个结果，耗时2分钟左右：

x=104940;y=11663;z=40831。

比较有意思的是，这三个数都是合数，但两两互质。

作者: lulijie 时间: 2009-3-29 22:47:29

用X和Y求z，有个问题，就是每次都要规定一个范围，若寻找不到，把范围扩大后，又要从头算起。
而金眼睛的方法，从z来找x和y，最大的好处就是不需要规定z的范围，就算规定了范围，若寻找不到，下次还可以从这个范围开始寻找，不用重复工作。还有他规定X大于Y，来优化算法，比规定X小于Y，来优化算法速度快的多。
速度比等于2^（1/3）-1 =1：4。
很好，考虑的很全面。

作者: yang_bigarm 时间: 2009-3-29 23:35:01

原帖由 金眼睛 于 2009-3-29 21:57 发表
虽然数不是很大，还是动用了我的大数计算程序，呵呵！

思路：让z从1至无穷。设x大于y，则x在[(17/2)^(1/3)*z]与[17^(1/3)*z]之间。
用x，z推算y，并使y圆整为整数，计算p=x^3+y^3-17*z^3，以p最小作为限定，可以 ...

两分钟？那么快啊，牛

[ 本帖最后由 yang_bigarm 于 2009-3-29 23:37 编辑 ]

作者: tonylmd 时间: 2009-3-29 23:40:53

我也觉得这题的解决靠算法的优化…
各位能否都发布一下算法？学习学习…

作者: ggglgq 时间: 2009-3-30 02:59:02

　　
　　　　
　　
　　这个题目应该是比较难的数论问题！比如歌德巴赫猜想就是数论问题。
　　
　　　　
　　楼主的题目是数论问题中比较棘手的不定方程问题！比如费尔马大定理

就是很棘手的不定方程问题！


关于楼主的不定方程问题，大家可对照一下《三元三次不定方程》

http://www.docin.com/p-102258.html
　　
　　
　　
　　　　
　　

作者: lulijie 时间: 2009-3-30 20:15:55

用金眼睛的算法精神，我设计了一下，发现算出结果要20分钟。
而金眼睛只需要2分钟，不知如何实现的。
我估计一下时间。
金眼睛的算法，z没有优化，x优化后节约时间约4倍。
所以总共节约时间4倍。
我的算法，按理论讲，应该节约34倍时间，应该速度更快，但苦于事先需设定搜索范围，范围设小了，搜寻不到结果，范围设大了，又浪费时间。
我想了一个办法，改变循环进行的次序，既能理论上节约34倍时间，又不用事先设定范围。大家看看有没道理。
原先：
      X=17*i+p ，  Y=17*j-p       p=0 to 8
   两个嵌套for 循环
         for i=0 to  m             m为事先设定的范围。
               for j=1 to m
                     ......
               next j
         next  i
-------------------------------------------
修改为：
      X=17*i+p ，  Y=17*j+17-p       p=0 to 8

   m=0                                  ‘m为i和j之间的最大值
   do  while true
            i=m                         ’i先固定为m
            for j=0 to m
                     ......                ‘j 从小到大循环
            next j

               j=m                            ’j再固定为m
            for i=0 to m-1
                     ......                   ‘i从小到大循环
            next i

            m=m+1                      ’m逐渐增加
   loop
-------------------------------------------------------------------------
重新运行程序，  花费407秒得出结果，不到7分钟时间。

作者: 金眼睛 时间: 2009-3-30 21:15:11

呵呵，借工作之便用工作站算的，办公电脑5~6分钟也应该搞定了。

周日匆忙，没来得及说一个规律，这就是x，y，z对3求余结果互不相同。

原因如下：任何一个正整数的3次方对9求余的结果有三种：0，1，8。

考虑x^3+y^3=17*z^3的尾数情况，可以得到前面的结论。

当然，x，y，z也可以同时对3求余余零，但这样等式两边可以约掉27，也就是说解已经存在（正整数倍的都算一个解）。

再补充一个结果，z直到88000也还只有40831及其2倍81662两个解，有兴趣的朋友可以接着这个结果继续算。

作者: yang_bigarm 时间: 2009-3-30 22:12:36

原帖由 ggglgq 于 2009-3-30 02:59 发表
　　
　
　　这个题目应该是比较难的数论问题！

如果你把他看做是一个纯粹的数论问题，那么你可以考虑不用编程，直接用纸和笔再加上一个科学计算器
来解决这个问题，当然这样做会很难。因此我希望的是大家从算法的优化角度来攻克这个问题，我今天就
看到这个版上的几位朋友提出了很多优化的方法，很佩服你们的勤于思考的精神。

作者: 金眼睛 时间: 2009-3-31 22:09:53

lulijie的想法很好，可以跟我的想法结合一下么，这样就更好了，呵呵！每次来得匆忙，别人的观点都没仔细看。

lulijie注意到x，y的和为17的整数倍，这不难证明，很好，我想这样就可以把原方程转化一下了。

设x+y=A=17*m，x-y=B

原方程变为：(A+B)^3+(A-B)^3=8*17*z^3 -> A^3+3*A*B^2=4*17*z^3 -> 289*m^3+3*m*B^2=4*z^3

由于B<17m，得到m的范围为：ceil(17^(1/3)/17*z)<=m<=floor(68^(1/3)/17*z)，这样程序运行就快多了：）

作者: killtest_tw 时间: 2009-4-1 11:15:01

看看，能不能對我的孩子有用

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)