乐趣区

关于算法:杨辉三角的5个特性一个比一个牛皮

作者:小傅哥
博客:https://bugstack.cn

积淀、分享、成长,让本人和别人都能有所播种!😄

一、前言

杨辉三角的历史

杨辉三角依照杨辉于 1261 年所编写的《详解九章算法》一书,外面有一张图片,介绍此种算法来自于另外一个数学家贾宪所编写的《释锁算书》一书,但这本书早已失传无从考据。但能够必定的是这一图形的发现我国不迟于 1200 年左右。在欧洲,这图形称为 ” 巴斯加 (Pascal) 三角 ”。因为个别都认为这是巴斯加在 1654 年创造的。其实在巴斯加之前曾经有许多人遍及过,最早是德国人阿匹纳斯(Pertrus APianus),他已经把这个图形刻在 1527 年著的一本算术书封面上。但无论如何,杨辉三角的发现,在我国比在欧洲至多要早 300 年光景。

此外杨辉三角原来的名字也不是三角,而是叫做 开方作法根源 ,起初也有人称为 乘法求廉图。因为这些名称切实太古奥了些,所以起初简称为“三角”。

在小傅哥学习杨辉三角的过程中,找到了一本大数学家华罗庚的 PDF[《从杨辉三角谈起 – 华罗庚》]()。—— 这些数学真的十分重要,每每映射到程序中都是一段把 for 循环优化成算法的体现,进步执行效率。

二、杨辉三角结构

在开始分享杨辉三角的个性和代码实现前,咱们先来理解下杨辉三角的构造结构。

杨辉三角的构造和法则非常简单,除去每次两边的 1,两头的数字都是下面两个数字的和。如图示意的三角区域。但也就是如此简略的构造,却有着诸多的数学逻辑体现。包含咱们计算的二项式、N 选 X 的种数还有斐波那契数列等,都能够在杨辉三角中体现进去。接下来咱们就来看看这些个性。

三、杨辉三角个性

为了不便学习杨辉三角的数学逻辑个性,咱们把它按左对齐形式进行排列。

[1]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]
[1,5,10,10,5,1]
[1,6,15,20,15,6,1]
[1,7,21,35,35,21,7,1]
[1,8,28,56,70,56,28,8,1]

接下来咱们就以这组杨辉三角数列,来展现它的数学逻辑个性。对于杨辉三角的 Java 代码放已到下文中,读者能够查阅。

1. 二项式开展

大家在上学阶段肯定学习过二项式开展,例如:(x+y)^2 = x^2 + 2xy + y^2 其实这个开展的数学逻辑在杨辉三角中能够十分好的展现进去。

  • 任意一个二项式开展后的数字乘积,都能够映射到杨辉三角对应的中的数字。
  • 二项式开展公式是用来计算给定二项式的指数幂的展开式的公式。对于给定的二项式 (x + y)n,二项式开展公式为:(x + y)^n = x^n + nx^{n-1}y + n(n-1)x^{n-2}y^2 + ... + y^n 这个公式也正好合乎杨辉三角的数字值。

2. 组合数

组合数是数学中定义的一种数学概念,用于计算有多少种抉择能够从一组物品中抉择出若干的物品。比方你早上有 5 种水果能够吃,但你吃不了那么多,让你 5 种水果当选 2 个,看看有多少种抉择。通过应用公式 c(n,k) = n!/k!(n-k)! 能够计算出,5 选 2 有 10 种抉择。

那么这样一个计算也是能够体现在杨辉三角中的。

  • 5 选 2,在杨辉三角中能够找到第 5 行的第 2 列,后果是 10。依照这个法则,5 选 3 =10、5 选 4 =5

3. 斐波那契数列

斐波那契数列呈现在印度数学中,与梵文韵律无关。在梵语诗歌传统中,人们对列举所有持续时间为 2 单位的长 (L) 音节与 1 单位持续时间的短 (S) 音节并列的模式很感兴趣。对于更多斐波那契更多常识能够浏览小傅哥的:《程序员数学:斐波那契》—— 为什么不能用斐波那契散列,做数据库路由算法?

斐波那契数列能够由递归关系定义:F0 = 0,F1 = 1,Fn = Fn-1 + Fn-2

F0 F1 F2 F3 F4 F5 F6 F7 F8 F9
0 1 1 2 3 5 8 13 21 34

而这样一个有法则的斐波那契数列在杨辉三角中也是有所体现的。

  • 把斜对角的数字做加和,会失去一组斐波那契数列;1、1、2、3、5、8、13、15、33

4. 次方数

在杨辉三角中还有一个十分有意思的个性,就是有 2 的次方和 11 次方数。

2 次方

– 杨辉三角每一行的数字加和,正好的 2 的 0 次方、1 次方..n 次方

11 次方

  • 另外一个是 11 的次幂,例如 11 的 2 次幂的后果正好是 121 这一排数字的组合。如果是 11 的 5 次幂,两头有间断的 10,则是把后一位向前一位进位一下。

5. 平方数

  • 在杨辉三角中还有一个平方数的法则体现。比方 3 的平方正好是右侧 3 + 6 的后果。4 的平方是右侧 6 +10 的后果。

四、杨辉三角实现

接下来咱们实现下杨辉三角;

public HashMap<Integer, Integer> pascalTriangle(int lineNumber) {HashMap<Integer, Integer> currentLine = new HashMap<>();
    currentLine.put(0, 1);
    int currentLineSize = lineNumber + 1;
    for (int numberIdx = 1; numberIdx < currentLineSize; numberIdx += 1) {
        /*
         * https://github.com/trekhleb/javascript-algorithms/blob/master/src/algorithms/math/pascal-triangle/pascalTriangle.js
         * 第 i 行号中的第 -th 个条目 lineNumber 是 Binomial CoefficientC(lineNumber, i)并且所有行都以 value 结尾 1。这个思路是 C(lineNumber, i)应用 C(lineNumber, i-1). 它能够 O(1)应用以下办法及时计算:* C(lineNumber, i)   = lineNumber! / ((lineNumber - i)! * i!)
         * C(lineNumber, i - 1) = lineNumber! / ((lineNumber - i + 1)! * (i - 1)!)
         *
         * 从以上两个表达式咱们能够推导出上面的表达式:C(lineNumber, i) = C(lineNumber, i - 1) * (lineNumber - i + 1) / i
         * 所以 C(lineNumber, i)能够从 C(lineNumber, i - 1)工夫上算进去 O(1)
         */
        currentLine.put(numberIdx, ((null == currentLine.get(numberIdx - 1) ? 0 : currentLine.get(numberIdx - 1)) * (lineNumber - numberIdx + 1)) / numberIdx);
    }
    return currentLine;
}

单元测试

@Test
public void test_PascalTriangle() {PascalTriangle pascalTriangle = new PascalTriangle();
    for (int i = 0; i <= 10; i++) {HashMap<Integer, Integer> currentLineMap = pascalTriangle.pascalTriangle(i);
        System.out.println(JSON.toJSONString(currentLineMap.values()));
    }
}

[1]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]
[1,5,10,10,5,1]
[1,6,15,20,15,6,1]
[1,7,21,35,35,21,7,1]
[1,8,28,56,70,56,28,8,1]
[1,9,36,84,126,126,84,36,9,1]
[1,10,45,120,210,252,210,120,45,10,1]
  • 这样咱们能够失去一组杨辉三角数列了。

五、常见面试题

  • 杨辉三角有哪些用处?
  • 用代码实现下杨辉三角。—— 在 LeetCode 中也有这样的题目
退出移动版