数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 算法交流 › 埃及分数问题
123456789下一页
返回列表 发新帖
楼主: 无心人

[讨论] 埃及分数问题

[复制链接]
无心人
 楼主| 发表于 2008-3-10 19:44:34 | 显示全部楼层
我暂时只能实现穷举

分类要考虑模式叠加
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2008-3-11 09:33:28 | 显示全部楼层
现在我实现了计数的程序了，运行结果如下:
Total 0 solution for 1 numbers
Total 0 solution for 2 numbers
Total 1 solution for 3 numbers
Total 6 solution for 4 numbers
Total 61 solution for 5 numbers
Total 635 solution for 6 numbers
Total 5562 solution for 7 numbers
Total 46530 solution for 8 numbers
Total 363835 solution for 9 numbers
Total 2677596 solution for 10 numbers
Total 18599967 solution for 11 numbers
Total 122231891 solution for 12 numbers
Total 761885131 solution for 13 numbers
Total 4519425241 solution for 14 numbers
Total 25587199368 solution for 15 numbers
Total 138556840936 solution for 16 numbers

real    2m36.923s
user    2m36.700s
sys     0m0.250s
也就是16个不同的埃及分数和为1的数目为138G.这个部分花费了157秒。
这个计算结果同liangbc的结果不同，我估计他的计算包含了相同的埃及分数的结果了。
不然两个不同埃及分数的和为1显然不可能，数目应该为0。
liangbc可以把你的代码修改一下，比较一下结果看看是否匹配。
不过这个程序运行速度看来没有想象的快。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2008-3-11 09:36:01 | 显示全部楼层
Show下
看还有改进么
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 2008-3-11 09:53:18 | 显示全部楼层
原帖由 mathe 于 2008-3-11 09:33 发表
现在我实现了计数的程序了，运行结果如下:
Total 0 solution for 1 numbers
Total 0 solution for 2 numbers
Total 1 solution for 3 numbers
Total 6 solution for 4 numbers
Total 61 solution for 5 numbers ...
感觉上面的结果有遗漏，我用2001年VB编的程序运行的结果如下：
Total 0 solution for 1 numbers
Total 0 solution for 2 numbers
Total 1 solution for 3 numbers
Total 6 solution for 4 numbers
Total 62 solution for 5 numbers
Total 640 solution for 6 numbers


其中5个数的情形如下：
  1. No.1    1 = 1/2 + 1/3 + 1/7 + 1/51 + 1/238
  2. No.2    1 = 1/2 + 1/3 + 1/7 + 1/54 + 1/189
  3. No.3    1 = 1/2 + 1/3 + 1/7 + 1/56 + 1/168
  4. No.4    1 = 1/2 + 1/3 + 1/7 + 1/60 + 1/140
  5. No.5    1 = 1/2 + 1/3 + 1/7 + 1/63 + 1/126
  6. No.6    1 = 1/2 + 1/3 + 1/7 + 1/70 + 1/105
  7. No.7    1 = 1/2 + 1/3 + 1/7 + 1/78 + 1/91
  8. No.8    1 = 1/2 + 1/3 + 1/8 + 1/27 + 1/216
  9. No.9    1 = 1/2 + 1/3 + 1/8 + 1/28 + 1/168
  10. No.10   1 = 1/2 + 1/3 + 1/8 + 1/30 + 1/120
  11. No.11   1 = 1/2 + 1/3 + 1/8 + 1/32 + 1/96
  12. No.12   1 = 1/2 + 1/3 + 1/8 + 1/33 + 1/88
  13. No.13   1 = 1/2 + 1/3 + 1/8 + 1/36 + 1/72
  14. No.14   1 = 1/2 + 1/3 + 1/8 + 1/40 + 1/60
  15. No.15   1 = 1/2 + 1/3 + 1/8 + 1/42 + 1/56
  16. No.16   1 = 1/2 + 1/3 + 1/9 + 1/20 + 1/180
  17. No.17   1 = 1/2 + 1/3 + 1/9 + 1/21 + 1/126
  18. No.18   1 = 1/2 + 1/3 + 1/9 + 1/22 + 1/99
  19. No.19   1 = 1/2 + 1/3 + 1/9 + 1/24 + 1/72
  20. No.20   1 = 1/2 + 1/3 + 1/9 + 1/27 + 1/54
  21. No.21   1 = 1/2 + 1/3 + 1/9 + 1/30 + 1/45
  22. No.22   1 = 1/2 + 1/3 + 1/10 + 1/16 + 1/240
  23. No.23   1 = 1/2 + 1/3 + 1/10 + 1/18 + 1/90
  24. No.24   1 = 1/2 + 1/3 + 1/10 + 1/20 + 1/60
  25. No.25   1 = 1/2 + 1/3 + 1/10 + 1/24 + 1/40
  26. No.26   1 = 1/2 + 1/3 + 1/11 + 1/14 + 1/231
  27. No.27   1 = 1/2 + 1/3 + 1/11 + 1/15 + 1/110
  28. No.28   1 = 1/2 + 1/3 + 1/11 + 1/22 + 1/33
  29. No.29   1 = 1/2 + 1/3 + 1/12 + 1/13 + 1/156
  30. No.30   1 = 1/2 + 1/3 + 1/12 + 1/14 + 1/84
  31. No.31   1 = 1/2 + 1/3 + 1/12 + 1/15 + 1/60
  32. No.32   1 = 1/2 + 1/3 + 1/12 + 1/16 + 1/48
  33. No.33   1 = 1/2 + 1/3 + 1/12 + 1/18 + 1/36
  34. No.34   1 = 1/2 + 1/3 + 1/12 + 1/20 + 1/30
  35. No.35   1 = 1/2 + 1/3 + 1/12 + 1/21 + 1/28
  36. No.36   1 = 1/2 + 1/3 + 1/14 + 1/15 + 1/35
  37. No.37   1 = 1/2 + 1/4 + 1/5 + 1/22 + 1/220
  38. No.38   1 = 1/2 + 1/4 + 1/5 + 1/24 + 1/120
  39. No.39   1 = 1/2 + 1/4 + 1/5 + 1/25 + 1/100
  40. No.40   1 = 1/2 + 1/4 + 1/5 + 1/28 + 1/70
  41. No.41   1 = 1/2 + 1/4 + 1/5 + 1/30 + 1/60
  42. No.42   1 = 1/2 + 1/4 + 1/5 + 1/36 + 1/45
  43. No.43   1 = 1/2 + 1/4 + 1/6 + 1/13 + 1/156
  44. No.44   1 = 1/2 + 1/4 + 1/6 + 1/14 + 1/84
  45. No.45   1 = 1/2 + 1/4 + 1/6 + 1/15 + 1/60
  46. No.46   1 = 1/2 + 1/4 + 1/6 + 1/16 + 1/48
  47. No.47   1 = 1/2 + 1/4 + 1/6 + 1/18 + 1/36
  48. No.48   1 = 1/2 + 1/4 + 1/6 + 1/20 + 1/30
  49. No.49   1 = 1/2 + 1/4 + 1/6 + 1/21 + 1/28
  50. No.50   1 = 1/2 + 1/4 + 1/7 + 1/10 + 1/140
  51. No.51   1 = 1/2 + 1/4 + 1/7 + 1/12 + 1/42
  52. No.52   1 = 1/2 + 1/4 + 1/7 + 1/14 + 1/28
  53. No.53   1 = 1/2 + 1/4 + 1/8 + 1/9 + 1/72
  54. No.54   1 = 1/2 + 1/4 + 1/8 + 1/10 + 1/40
  55. No.55   1 = 1/2 + 1/4 + 1/8 + 1/12 + 1/24
  56. No.56   1 = 1/2 + 1/4 + 1/9 + 1/12 + 1/18
  57. No.57   1 = 1/2 + 1/4 + 1/10 + 1/12 + 1/15
  58. No.58   1 = 1/2 + 1/5 + 1/6 + 1/8 + 1/120
  59. No.59   1 = 1/2 + 1/5 + 1/6 + 1/9 + 1/45
  60. No.60   1 = 1/2 + 1/5 + 1/6 + 1/10 + 1/30
  61. No.61   1 = 1/2 + 1/5 + 1/6 + 1/12 + 1/20
  62. No.62   1 = 1/3 + 1/4 + 1/5 + 1/6 + 1/20
复制代码
请查看是漏了哪组？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 2008-3-11 10:09:44 | 显示全部楼层

我上面的结果可能也有遗漏

因为程序设计中用的是全整型变量，当可能超出范围时，程序会给出“超标”指示，
而实际上在运行过程中确实有该警示，
但比较肯定的是：搜索的结果应只多不少。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 2008-3-11 10:17:52 | 显示全部楼层

这是我的程序运行的结果，FYI

  1. 埃及分数分解：1（禁止重复 | 全奇数）
  2. No.1    1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/21 + 1/135 + 1/10395
  3. No.2    1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/21 + 1/165 + 1/693
  4. No.3    1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/21 + 1/231 + 1/315
  5. No.4    1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/33 + 1/45 + 1/385
  6. No.5    1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/35 + 1/45 + 1/231
复制代码
设定分解项数≤10，但输出结果的项数却均=9
问题：将“1”分解成不重复的、且全奇数的埃及分数，是否有且仅有上述5组？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2008-3-11 11:25:19 | 显示全部楼层
终于找到BUG了，筛选27对应的模板时弄错了，使用的倍数280被误写成140了，结果错误了。
现在修改过来，附件里面有两个c文件，flter.c用于计数,fltere.c用于输出所有结果
比如现在flter.c在我的Linux上面运行243秒算出20以内的计数为:

Total 0 solution for 1 numbers
Total 0 solution for 2 numbers
Total 1 solution for 3 numbers
Total 6 solution for 4 numbers
Total 62 solution for 5 numbers
Total 642 solution for 6 numbers
Total 5623 solution for 7 numbers
Total 47126 solution for 8 numbers
Total 368680 solution for 9 numbers
Total 2715613 solution for 10 numbers
Total 18876751 solution for 11 numbers
Total 124137535 solution for 12 numbers
Total 774232619 solution for 13 numbers
Total 4595291801 solution for 14 numbers
Total 26030660449 solution for 15 numbers
Total 141031079451 solution for 16 numbers
Total 731862267491 solution for 17 numbers
Total 3641135367129 solution for 18 numbers
Total 17379359388167 solution for 19 numbers
Total 79633646141291 solution for 20 numbers

real    4m3.688s
user    4m3.330s
sys     0m0.310s

newtest.zip (3.74 KB, 下载次数: 13)
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2008-3-11 11:47:24 | 显示全部楼层
试着运行了fltere.c程序，输出所有10个数的情况
花费了10分半钟，产生一个136M的文本文件
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2008-3-11 11:50:11 | 显示全部楼层
Level 5我计算出来结果也是62，gxqcn上面那个结果是正确的
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2008-3-11 12:06:01 | 显示全部楼层
呵呵，现在提一个问题，不限制埃及分数的数目，那么使用分母在2到256之间的不同埃及分数构成1，总共有多少种方案。
估计一下计算机大概要花多长时间可以解出。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

123456789下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-5-3 15:30 , Processed in 0.046067 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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