天哥学编程

V1

2022/01/18阅读:56主题:自定义主题1

谢尔宾斯基三角形--数学与编程

这道题来源于初一期末数学考试的填空题。

原题:

如图1,按照这样的规律,第六个这样的图形中有___个三角形? 图1(图1)

显然,这一道题要我们找规律。通过前三个图形的规律,得出第六个图形中的三角形个数。

思路一:

图形一有5个三角形(1大4小);

图形二有3个相同的图形一(上面,左下,右下),另外有中间一个+外围一个=两个三角形;

图形三有3个相同的图形二(上面,左下,右下),另外有中间一个+外围一个=两个三角形;

此时,若记图形 中的三角形数量为 ,则有递推公式:

(边界:

根据这一公式,可求出第六个图形的三角形个数:

把上面这道题改换成算法竞赛题会是怎样呢?


变式1:

题目描述:

一天,小A在一本书中看到了这样一段文字:

定义谢尔宾斯基三角形如下:

1.取一个等边三角形。

2.沿三边中点的连线,将它分成四个小三角形。

3.去掉中间的那一个小三角形。

4.对其余三个小三角形重复1。

如图(同上文图1) 从左往右分别为第1,2,3个谢尔宾斯基三角形。

看完书后小A想知道,第 个谢尔宾斯基三角形里面一共有多少个三角形(不限大小)。

输入格式:

共一行,第一行一个数字,表示

输出格式:

共一行,第一行一个数字,表示第 个谢尔宾斯基三角形的三角形总数

样例数据:

样例1:

输入:

3

输出:

53

数据限制:

代码:

(我们的思路1时间复杂度是 ,在本题可以轻松通过)

记住,十年OI一场空,不开long long见祖宗!

#include <stdio.h>

int n;
long long a[35];

int main() {
    scanf("%d", &n);
    a[1] = 5;
    for (int i = 2; i <= n; i++) {
        a[i] = 3 * a[i-1] + 2;
    }
    printf("%d", a[n]);
    return 0;
}

变式2:

将变式1中 的大小改为 ,并将最终结果对 (即 )取模。

此时,我们原来 的思路一已不满足于 的数据大小,必须寻求效率更高的算法。

算法二: 时间复杂度

回到最开始分形三角形的图片,我们还可以发现另一个规律:

图形一有1个最大的三角形,4个第二大的三角形;

图形二有1个最大的三角形,4个第二大的三角形,4 * 3个第三大的三角形;

图形三有1个最大的三角形,4个第二大的三角形,4 * 3个第三大的三角形,4 * 3 * 3个第四大的三角形。

同样记图形 中的三角形数量为 ,则有:

除第一项外提取公因数4,得:

根据等比数列求和公式转化为 ,代入式中为:

化简得:

然后,我们可以非常愉快地用快速幂计算 啦!

#include <stdio.h>
int Pow(int a, long long b, int k) {
    int ans = 1 % k;
    while (b) {
        if (b & 1) ans = (long long)ans * a % k;
        a = (long long)a * a % k;
        b = b >> 1;
    }
    return ans;
}
int main() {
    long long n;
    scanf("%lld", &n);
    int ans = (long long)(2 * Pow(3, n, 1000000009) - 1) % 1000000009;
    printf("%d", ans);
    return 0;
}

总结:

其实,编程竞赛中,往往需要用到一些数学知识作为其理论铺垫,而数学思维往往会对编程竞赛有所帮助,因而学习信息学竞赛的同学更不能将数学落下。同时,我们也可以举一反三,将平时所做的一些数学题目用信息学竞赛的角度进行思考,并将平常的积累转化为自己在赛场上得分的基础。

分类:

数学

标签:

数学

作者介绍

天哥学编程
V1