基于递归算法对等边三角形i等分点三角形个数的求解思路

好久不见，再见已是决战中考100天倒计时了，常为鸽子的我连上篇过年时刚开的新坑都没填（刚删了，嘻嘻）

为何突然心血来潮来写一篇博客呢，还得感谢我班的王某某同学，就在昨天周五在学校百日誓师活动的下午，他来找我一同探讨以下问题：

虽然他是道算法题，要求是不能硬解，但实际上是道数学问题，于是我开始一个个画图，寻找规律

从i=1,2,3开始,我觉得这也不咋滴嘛，不就是一个普普通通的规律题吗，有啥难的，和编程有啥关系？？

但就当我从i=4开始画图，我人傻了。

很显然，在i=1,2,3时，还没有边长为2的倒三角形（简称倒2），如图

而到了i=4时，突然蹦出来倒2，麻了，一想到接下来更多的倒三角，顿时冒汗
然而我们可以继续深究，数出目前已知的三角形的构成，我们易得：
当i=1时，只有一个正1，总数=1
当i=2时，有3=1+2个正1，一个倒1，和一个正2，总数=5
当i=3时，有6=1+2+3个正1，3=1+2个倒1，3=1+2个正2，一个正3，总数为13
当i=4时，有10=1+2+3+4个正1，6=1+2+3个倒1，6=1+2+3个正2，3=1+2个正3，一个倒2，一个正4，总数为27

但由此，我产生了个新思路，通过分别算正立三角和倒立三角个数，相加即可。并且得通过i大小，判断其是否含有对应大小的三角形，然后一个把含有的三角用求和求出来，再递归一下算下一个，完美

既然已经有了基本思路那就得一步步实现，先找找正的规律

正三角算法

1
2
3
4
5
6
7
8

def count(m):
    return sum([i for i in range(1, m)])

def up(i, m):
    if 0 < m < i + 1:
        m += 1
        return count(i + 3 - m) + up(i, m)
    return 0

这个很好解决，找找规律就结束了，难的在倒三角

倒三角算法

当你开始找倒三角规律时，你会发现一个很烦人的问题——

一开始我有一个错误的思路，就是i=4时正2很巧的等于倒1，但稍加验证就可排除掉
那么该如何计算呢？

1
2
3
4
5
6
7
8
9
10
11

def down(i, n):
    if n == 0:
        return 0
    a = i % n
    b = i // n
    if n > 0:
        if b + n == i:
            n -= 1
            return count(b) + down(i, n)
    n -= 1
    return count(b + (i - b) // 2) + down(i, n)

可以肯定的是，你一定对这个a和b，以及(i-b)//2的用处和来源有疑问，不懂是吧？我也不懂哈哈
很显然这是我瞎凑的数，因为我当时实在是头大，找不着规律
但恰恰巧的是，他真的能跑（
只能说屎山代码太神奇了，将就着用吧

总代码

当时在学校看电影时手写的代码逻辑语法错误不少，在家稍加修改后，如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

def count(m):
    return sum([i for i in range(1, m)])


def up(i, m):
    if 0 < m < i + 1:
        m += 1
        return count(i + 3 - m) + up(i, m)
    return 0


def down(i, n):
    if n == 0:
        return 0
    a = i % n
    b = i // n
    if n > 0:
        if b + n == i:
            n -= 1
            return count(b) + down(i, n)
    n -= 1
    return count(b + (i - b) // 2) + down(i, n)


def func():
    i = int(input())
    n = i // 2  # 最大倒三角边长
    m = 1  # 小三角边长
    return up(i,m)+down(i,n)


func()

令人感动，他真的能跑

总结与反思

周六在家，我又一次用deepseek思考了这个问题，一开始他很蠢——

他得出的规律是i^2，很明显是错的，没算大三角，于是我提醒他

令我吃惊，第一次看到deepseek也烧脑了5分钟，不断地试错，不断地更改，最终终于得出了数学规律——

并且通过他修改并优化代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def count_triangles(i):
    # 计算正向三角形数量
    def count_up(i):
        if i < 1:
            return 0
        return (i**2) + count_up(i - 1)

    # 计算倒置三角形数量
    def count_down(i, k):
        if i - 2 * k < 1:
            return 0
        return (i - 2 * k)**2 + count_down(i, k + 1)

    # 总三角形数量 = 正向三角形 + 倒置三角形
    return count_up(i) + count_down(i, 1)

# 测试代码
if __name__ == "__main__":
    i = int(input("请输入等分点数 i: "))
    if i < 1:
        print("等分点数 i 必须大于 0")
    else:
        result = count_triangles(i)
        print(f"等分点数 i = {i} 时，三角形数量 = {result}")

碎碎念

很久没有碰编程了，同样也很久没有碰博客了，每年只有在域名续费时才想起他，开的坑也没填，只有像现在这样激动才能有动力写博客吧

下一次见面，大概绝对在那100天后，在这有欢乐，有不舍，有激情的中学时代，我也要好好画个句号。