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

〇〇

--从任意一个点出发，能够连接的点
with a as(
select sqrt(2)/2 a , 1 b from dual),
t as(select level-1 l from dual connect by level<=3),
x as(select a*p.l+b*p2.l p from a,t p,t p2
where a*p.l+b*p2.l <=sqrt(2)+1),
p as(select x.p x,y.p y from x,x y),
b as(select rownum rn,x,y from p
where
power(x-(sqrt(2)+1)/2,2)+power(y-(sqrt(2)+1)/2,2)
<=
power(sqrt(2)/2-(sqrt(2)+1)/2,2)+power(0-(sqrt(2)+1)/2,2)
),
c(x0,y0,n,pa,lv)
as(select x,y,rn,power(2,rn),1 from b --where x=sqrt(2)/2 and y=0
union all
select x,y,rn,pa+power(2,rn),lv+1 from b,c where
power(x-x0,2)+power(y-y0,2)=1 and lv<=1)
select distinct pa from c where lv=2
;
           PA
-------------
      1048592
   2148532224
     12582912
  17184063488
1099545182208
279172874240
      4194308
206158430208
           66
         3072
        12288
       393216
  17180000256
  68720525312
     50331648
          260
           96
         8320
   1073742336
       786432
  12884901888
566935683072
       131076
275146342400
   6442450944
2267742732288
         1040
        16640
    268437504
1133871366144
          520
          192
         4160
        33280
        66560
   1610612736
    100663296

已选择37行。

〇〇

找到一点思路
八边形的外圈点都是固定的,内部点随着菱形而不同,以O1,1为例。
外圈
i=sqrt(1/2)
p=[
[i,0],[1+i,0],
[0,i],[1+2i,i],
[0,1+i],[1+2i,1+i],
[i,1+2i],[1+i,1+2i]
]
每点可以找到邻居（距离为1）
for a in 1:8-1
for b in a+1:8
if abs((p[a][1]-p[b][1])^2+(p[a][2]-p[b][2])^2 -1)<10.0^6
println(a,",",b)
end #if
end end

1,2
1,3
2,4
3,5
4,6
5,7
6,8
7,8
已知4边形的3点，可以用对角2点之和减去中点，得到第4点
julia> p[1]-p[2]+p[4]
2-element Array{Float64,1}:
1.41421
0.707107
随着4边形的加入，内圈点不断增加，直到4边形个数满足面积。
八边形中已经属于某个4边形的边，不能再用于另一个4边形

内圈的点和内外圈的点构成的边，恰好每个边都用了2次，分别属于2个四边形

用回溯法可以解，解的个数就是内圈点的不同坐标数

〇〇

〇〇 发表于 2017-4-4 11:07
找到一点思路
八边形的外圈点都是固定的,内部点随着菱形而不同,以O1,1为例。
外圈

每次选的相邻3点，不能是连成一线的

〇〇

〇〇 发表于 2017-4-4 11:07
找到一点思路
八边形的外圈点都是固定的,内部点随着菱形而不同,以O1,1为例。
外圈

从1点出发，两边夹角有4种情况
1.45度，只能放1个菱形
2.90度，放2个菱形或1个正方形
2.135度，放3个菱形或1个正方形+1个菱形
2.180度，放4个菱形或2个正方形或1个正方形+2个菱形

newkid

提供一个思路：
首先对图形进行等价的拉伸变型：所有的斜边长度单位都不再是1, 而是以根号2为单位。
所有子小图形变成了这几种：边长为1的正方形；边长分别为1和根号2的平行四边形（原来的菱形）,以及边长为根号2的正方形（倾斜45度的）
这样做的好处，是把所有图形的顶点变成了整数的格子点。比如O(2,1)，全部可以在4X4的格子中画出来。
从边缘的任意一条边开始画小图。如果是中间的边，最多可以画六个：四个方向的平行四边形，两个方向的正方形。
画小图的时候不能超出边缘，不能和已经画好的有交叉。
如果全部画满或者无法继续就回溯。

我最近忙，没有时间实现，你自己接着玩。

〇〇

我消化一下

newkid

你先把4X4的格子画出来，然后用笔在上面做几个例子就理解了。
所有可能的小图、线段、覆盖格子都可以事先编号，拼图就是找共同的边而已，从任何一边出发最后肯定可以盖满。

〇〇

newkid 发表于 2017-4-6 05:00
你先把4X4的格子画出来，然后用笔在上面做几个例子就理解了。
所有可能的小图、线段、覆盖格子都可以事先 ...

照你的描述画了O1,1,感觉变形后不太像了

〇〇

O2,1

〇〇

newkid 发表于 2017-4-6 05:00
你先把4X4的格子画出来，然后用笔在上面做几个例子就理解了。
所有可能的小图、线段、覆盖格子都可以事先 ...

你说的小图是半个格子的直角三角形？