algorithm - 平铺三角形网格

Question

设计并解释了一种递归分治算法。有人有主意吗？
给定如图1（b）所示的k≥2的等腰直角三角形网格，这个问题要求您使用图1（a）中给出的瓷砖完全覆盖它。不得覆盖网格的左下角。两块瓷砖不能重叠，所有瓷砖必须完全位于给定的三角形网格内。您必须使用图1（a）中所示的所有四种类型的磁贴，并且任何磁贴类型都不能覆盖总网格面积的40%以上。您可以根据需要旋转瓷砖，然后再将其放置到网格上。

Answer 1

这确实是归纳法的概念，与著名的例子类似。
如你所说，你已经解决了k=2的问题，这是一个很好的正确的起点，首先解决小例子，但我认为这个问题对于k=2的情况有点棘手，主要是因为每种类型不能超过40%的约束。
然后对于k>2，在你的例子中，假设k=3，我们试图利用你已经解决的问题，即情况k=2
通过非常简单的观察，我们可能会注意到，对于k=n，它实际上可以由4个k=n-1的情况组成（见下图）
中间的阴影部分形成一个孔，可以用1个B型填充，所以我们可以先填充4个小N-1的情况，然后用B型填充。
但是这个建筑面临一个问题：B型建筑面积将超过40%！
考虑k=2，无论你如何填充区域，都必须使用2类型b，我没有有力的证据，但是通过一些暴力的跟踪和错误，你应该被说服。那么对于k=3，我们有4个小三角形，也就是说我们有2*4=8个类型b，再加上1个填充孔，我们就得到9个类型b，每个使用1.5平方单位，总共使用13.5平方单位。
当k=3时，总面积为（2^3）^2/2=32平方单位
13.5/32=0.42….这违反了约束！
那该怎么办？这就是为什么我们要用一个技巧来处理k=2的情况（我假设你已经完成了这部分，就像你说的，你知道如何处理k=2的情况）
首先，我们知道使用构造方法从4个较小的三角形构建一个大三角形，只有类型B会违反此约束（即40%的面积），您可以验证自己。所以我们想减少B型的总数，但是每个较小的三角形必须至少使用2个B型，所以我们唯一可以减少的地方是大三角形中间的空孔，我们可以用其他类型的代替B型吗？同时，我们希望小三角形的其他部分保持不变，以便我们可以使用相同的参数进行归纳（即，一般来说，使用相同的构造方法从42^（n-1）个三角形形成2^n个三角形）
如果我们特别设计k=2的情况，答案是肯定的
看下面我的建筑：（可能还有其他建筑工程，但我只需要知道一个）
诀窍是我故意将1个类型b移到空（灰色）三角形旁边
让我们在这里停一下，做些验证：
为了构造k=2的情况，我们使用
2 A型=2平方单位<40%
2类B=3平方单位<40%
1个C类=1.5平方单位<40%
1类D=1平方单位<40%
总使用面积7.5平方单位，良好
现在假设我们使用完全相同的方法来构造这4个三角形来形成一个大的三角形，中间的那个仍然是一个B型形状的空洞，但是现在不是用1个B型填充它，而是用A型和D型填充旁边的3个B型（回头看K=2的情况）
（我使用相同的颜色方案，以便于理解），我们这样做的所有3个小三角形组成的孔在中间。
最后一部分（我知道很长…）
我们已经减少了从较小三角形构造大三角形时使用的类型B的数量，但同时我们增加了使用的类型A和D的数量！那么这种新的施工方法有效吗？
首先注意，它不会改变除灰色三角形旁边的类型B以外的小三角形的任何部分，即如果满足40%的约束，则此方法是归纳和递归的，用于填充2^n边三角形
然后我们再数一次我们使用的每种类型的数量。
对于k=3，总单位为32，我们使用：
2*4+3=11 A型=11平方单位<40%
2*4-3=5 B类=7.5平方单位<40%
1*4=4 C类=6平方单位<40%
1*4+3=7 D型=7平方单位<40%
我们总共覆盖了31.5个单元，好，现在让我们证明，对于k=n>3，40%的约束是满足的
设fa（n-1）是用我们的新方法填充2^n-1三角形的a型总面积，同样，fb（n-1），fc（n-1），fd（n-1）具有相似的定义
假设f*（n-1）是真的，即不超过总面积的40%，我们证明f*（n）是真的。
我们有
FA(n) = FA(n-1)*4 + 3*1
FB(n) = FB(n-1)*4 - 3*1.5
FC(n) = FC(n-1)*4
FD(n) = FD(n-1)*4 + 3*1
我们只给出fd（n）的证明，其他三个证明应该用类似的方法（m.i.）
用代换法，FD(n) = 2*(4^(n-2)) - 1 for n>=3（你至少应该自己想出这个方程式）
我们要显示FD(n)/(2^2(n)/2) < 0.4
即2FD(n)/4^n < 0.4
考虑一下左手侧，
lhs=（4*（4^（n-2））-1）/4^n
<4^（n-1）/4^ n=1/4<0.4 q.e.d
也就是说，对于任何2^k边三角形，所有类型的a-d都不会超过总面积的40%，对于k>=3，最后我们归纳地证明，有一种方法满足所有约束来构造这样一个三角形。
TL；博士
最困难的部分是满足40%的面积限制
先在k=2的情况下使用一个特殊的构造，试着用它来构造k=3的情况（然后k=4，k=5…归纳法的思想！）
当使用k=n-1的情况来建立k=n的情况时，写下每种类型所消耗的总面积的公式，并表明它们不会超过总面积的40%
结合点2和3，这是一种归纳方法，表明对于任何k>=2，有一种方法（我们描述过）在不破坏任何约束的情况下填充2^k边三角形