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

newkid · 发表于 2017-4-6 08:30

因为正方形有两种了。但是分法是等价的，你不就想知道有多少种分法？我说的小图是指构成单位，就是两种正方形和一种平行四边形，在所有可能的位置。

newkid · 发表于 2017-4-6 08:52

超过(2,1)之后，可能得限定大方块的个数，要不确实有问题。

〇〇 · 发表于 2017-4-6 21:08

newkid 发表于 2017-4-6 08:52
超过(2,1)之后，可能得限定大方块的个数，要不确实有问题。

面积不同了.还有什么原因

newkid · 发表于 2017-4-6 21:21

〇〇发表于 2017-4-6 21:08
面积不同了.还有什么原因

其实我的担心是多余的，新旧图形完全可以一一对应，大小方块不会互相干扰。
现在的问题是怎么能避开对称，如果每个拼法都试一遍也可以，但数量太大。

〇〇 · 发表于 2017-4-6 21:40

每个单元格用上面的形状命名，就能构造对称了，原题不要求排除对称

newkid · 发表于 2017-4-6 21:49

〇〇发表于 2017-4-6 21:40
每个单元格用上面的形状命名，就能构造对称了，原题不要求排除对称

我知道题目不排除对称。但是遍历过程中如果能避开对称，然后直接把结果做乘法，不是更高效？
我的思路是选一条边做出发点，而且只需一个出发点，就能把所有图形衍生出来。如果能够选到中点，即奇数边的中点，那还可以控制只往左边，或者只往右边，如果边都是偶数的就不好办。T(4,2)的答案是什么数量级的？

〇〇 · 发表于 2017-4-7 05:44

几亿的数量级

〇〇 · 发表于 2017-4-7 09:09

newkid 发表于 2017-4-6 21:49
我知道题目不排除对称。但是遍历过程中如果能避开对称，然后直接把结果做乘法，不是更高效？
我的思路是 ...

已知3点求第4点的算法 p4=p1+p3-P2仍然可用

〇〇 · 发表于 2017-4-7 09:30

本帖最后由〇〇于 2017-4-7 09:36 编辑

内部的4点，只能出现3点，之间的连线
有8种
214
314
324
123
234
132
241
143

〇〇 · 发表于 2017-4-7 10:34

〇〇发表于 2017-4-7 09:30
内部的4点，只能出现3点，之间的连线
有8种
214

with t as(select level n,ceil(level/2)r,mod(level,2)+1 c from dual connect by level<=4)
,line as(
select rownum rn,t.n p1,t1.n p2 from t,t t1
where
t.n<t1.n and abs(t.r-t1.r)<=1 and abs(t.c-t1.c)<=1)
select * from line,line line2
where line.rn<line2.rn and
line.p1 in( line2.p1 ,line2.p1 )
or  line.p2 in( line2.p1 ,line2.p1 )
;

RN       P1       P2       RN       P1       P2
----- ---------- ---------- ---------- ---------- ----------
1       1       2       2       1       3
1       1       2       3       1       4
1       1       2       4       2       3
1       1       2       5       2       4
2       1       3       3       1       4
2       1       3       6       3       4
4       2       3       5       2       4
4       2       3       6       3       4