请用pl/sql解欧拉计划594题:菱形划分法

newkid · 发表于 2017-4-9 07:19

我也是打算把单元格分成四小块，但我不管中心点，只需每块用二进制的一位来表示占用与否。每个子图占用哪些块都是可以实现算好的。做这个拼图不需要任何图形学方面的知识。

〇〇 · 发表于 2017-4-9 13:12

newkid 发表于 2017-4-9 07:19
我也是打算把单元格分成四小块，但我不管中心点，只需每块用二进制的一位来表示占用与否。每个子图占用哪些 ...

做出来了,O1,1用1秒，O2,1用几分钟。
http://www.ituring.com.cn/article/274780

〇〇 · 发表于 2017-4-9 13:15

newkid 发表于 2017-4-9 07:19
我也是打算把单元格分成四小块，但我不管中心点，只需每块用二进制的一位来表示占用与否。每个子图占用哪些 ...

什么叫不管中心点？
我的判断点在四边形完全是为了判断2个形状是否相容。
不用它，不知道怎么判断某个小三角形归属哪个形状

〇〇 · 发表于 2017-4-9 19:19

我感觉如果做出一个占八边形一半的图形,就可以利用对称找到其他的

newkid · 发表于 2017-4-9 22:24

在这种坐标体系中，子图和其占用区域存在着简单的对应关系，几个CASE就能搞定，用不着复杂的计算。你是不是在拼图过程中有很多实时计算，用的时间有点长。(3,2)能算出来吗？
把大图分成两半的思路是难以实现的，因为你得随时保证分界线（不一定是直线）也是对称的形状，还得论证所有分法都存在一条形状对称的中线。

〇〇 · 发表于 2017-4-10 05:42

我觉得22 31都要1小时，主要就是递归时选下一轮允许形状时有数组bitand

〇〇 · 发表于 2017-4-10 08:44

本帖最后由〇〇于 2017-4-10 08:47 编辑

〇〇发表于 2017-4-10 05:42
我觉得22 31都要1小时，主要就是递归时选下一轮允许形状时有数组bitand

N=6 几分钟了，还只输出前几个，据说总数是832
julia> include("d:\\testfun1.txt")
1 7 13 19 21 22 26 32 45 47 49 53 59 72 74 76 80 85 99 101 103 106
1 7 13 19 21 22 26 32 45 47 49 53 59 73 76 80 85 95 100 101 103 106
1 7 13 19 21 22 26 32 45 47 49 53 59 73 76 80 86 89 100 101 103 108
1 7 13 19 21 22 26 32 45 47 49 53 59 73 76 81 83 86 100 101 105 108
1 7 13 19 21 22 26 32 45 47 49 53 59 73 77 78 81 86 100 102 105 108

隔了一会
又输出
1 7 13 19 21 22 26 32 46 49 53 59 69 75 76 80 85 95 100 101 103 106
1 7 13 19 21 22 26 32 46 49 53 59 69 75 76 80 86 89 100 101 103 108
1 7 13 19 21 22 26 32 46 49 53 59 69 75 76 81 83 86 100 101 105 108
1 7 13 19 21 22 26 32 46 49 53 59 69 75 77 78 81 86 100 102 105 108
1 7 13 19 21 22 26 32 46 49 53 60 63 75 76 80 89 91 100 101 103 108
1 7 13 19 21 22 26 32 46 49 53 60 63 75 76 81 83 91 100 101 105 108
1 7 13 19 21 22 26 32 46 49 53 60 63 75 77 78 81 91 100 102 105 108
1 7 13 19 21 22 26 32 46 49 54 57 60 75 76 83 85 91 100 101 105 108
1 7 13 19 21 22 26 32 46 49 54 57 60 75 77 78 85 91 100 102 105 108
1 7 13 19 21 22 26 32 46 50 51 54 60 75 78 80 85 91 100 102 105 108

〇〇 · 发表于 2017-4-10 09:23

〇〇发表于 2017-4-10 08:44
N=6 几分钟了，还只输出前几个，据说总数是832
julia> include("d:\\testfun1.txt")
1 7 13 19 21 22 ...

修改了fun函数，把里面的map改为循环,减少了临时对象创建，就快了
N=6，输出832
6.728173 seconds (9.54 M allocations: 236.604 MiB, 0.81% gc time)

〇〇 · 发表于 2017-4-10 09:53

〇〇发表于 2017-4-10 09:23
修改了fun函数，把里面的map改为循环,减少了临时对象创建，就快了
N=6，输出832
6.728173 seconds (9. ...

N=7
julia> include("d:\\testfun2.txt")
91.759213 seconds (200.35 M allocations: 5.154 GiB, 1.21% gc time)
10036

〇〇 · 发表于 2017-4-10 10:36

〇〇发表于 2017-4-10 09:53
N=7
julia> include("d:\\testfun2.txt")
91.759213 seconds (200.35 M allocations: 5.154 GiB, 1.21 ...

O2,2
julia> include("d:\\testfun2.txt")
28.107125 seconds (56.34 M allocations: 1.436 GiB, 1.29% gc time)
5383