关于求杨辉三角形mn值的算法

zqhxuyuan 发布于2019-06-27 16:20 / 2097人阅读

摘要：杨辉三角形，又称贾宪三角形帕斯卡三角形海亚姆三角形，是二项式系数在的一种写法，形似三角形，在中国首现于南宋杨辉的详解九章算术得名，书中杨辉说明是引自贾宪的释锁算术，故又名贾宪三角形。

杨辉三角形，又称贾宪三角形、帕斯卡三角形、海亚姆三角形，是二项式系数在的一种写法，形似三角形，在中国首现于南宋杨辉的《详解九章算术》得名，书中杨辉说明是引自贾宪的《释锁算术》，故又名贾宪三角形。

前9层写出来如下：
　　　　　　　　１
　　　　　　　１　１
　　　　　　１　２　１
　　　　　１　３　３　１
　　　　１　４　６　４　１
　　　１　５　10　10　５　１
　　１　６　15　20　15　６　１
　１　７　21　35　35　21　７　１
１　８　28　56　70　56　28　８　１

递归法

首先给大家介绍一种最简单的求杨辉三角mn值的方法（m为行，n为列，比如(5,3)即为第五行第三个，值为6）即为递归法：

function recursion($m, $n) {
    if ($n == 1 || $n == $m || $m == 1) {
        return 1;
    }

    $val = recursion($m-1, $n - 1) + recursion($m-1, $n);

    return $val;
}

这种方法实现最简单，但是如果mn的值特别大的话，性能会非常差，我试了个100，78，就把机器卡死了。。

迭代法

迭代法从第一层开始循环，只循环每行中必要的列，最后求出mn位置的值。代码如下：

function setNum($row, $list)
{
    $arr = array();
    for ($i = 0; $i < $row; $i++) {
        $start = ($list - ($row - $i)) < 0 ? 0 : ($list - ($row - $i));
        $end = ($list - 1) > $i ? $i : ($list - 1);
        for ($j = $start; $j <= $end; $j++) {
            if ($i == 0 || $i == 1 || $j == 0 || $i == $j) {
                $arr[$i][$j] = 1;
            } else {
                $arr[$i][$j] = $arr[$i - 1][$j] + $arr[$i - 1][$j - 1];
            }
        }
    }
    return $arr[--$row][--$list];
}

公式法

当然了，根据杨辉三角的性质:第n行的m个数可表示为 C(n-1，m-1),用排列组合的公式也可以获得mn的值，代码如下：

function express($m, $n) {
    $up = 1;
    for ($i = $m - 1; $i > ($m - $n); $i--) {
        $up *= $i;
    }


    $down = 1;
    for ($i = $n - 1; $i > 0; $i--) {
        $down *= $i;
    }

    return $up / $down;
}

云服务器 GPU云服务器数组杨辉三角形 java算法求素数 webrtc复数求模快速算法 webrtc agc算法三

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/22857.html

十道简单算法题

摘要：前言最近在回顾以前使用写过的数据结构和算法的东西，发现自己的算法和数据结构是真的薄弱，现在用改写一下，重温一下。前言最近在回顾以前使用C写过的数据结构和算法的东西，发现自己的算法和数据结构是真的薄弱，现在用Java改写一下，重温一下。只能说慢慢积累吧～下面的题目难度都是简单的，算法的大佬可直接忽略这篇文章了～入门或者算法薄弱的同学可参考一下～很多与排序相关的小算法(合并数组、获...

sunsmell 2019-08-16 11:11 评论0 收藏0
[Leetcode] Pascal's Triangle 杨辉三角形

摘要：迭代法复杂度时间空间思路简单的按照杨辉三角形的规则计算就行了。代码加入第一个加入中间的数加入最后一个逆序相加法复杂度时间空间思路同样用迭代的方法，根据上一层的值算下一层，不过这里每一层都在同一个上操作。 Pascals Triangle I Given numRows, generate the first numRows of Pascals triangle. For examp...

Berwin 2019-08-14 12:37 评论0 收藏0
使用python生成杨辉三角形

摘要：杨辉三角杨辉定义如下把每一行看做一个，试写一个，不断输出下一行的复制一个，这样才不会影响到原有的。不然里的每个列表的末尾会为杨辉三角杨辉定义如下： 1 / 1 1 / / 1 2 1 / / / 1 3 3 1 / / / / 1 4 6 ...

Zoom 2019-07-30 17:39 评论0 收藏0
杨辉三角形（开方做法本源）

摘要：简单做法打印空格请输入行数实现杨辉三角的算法效果杨辉三角形开方做法本源简单做法#includeusing namespace std;#include#includevoid kongge(int n)//打印空格{ for (int i = 0; i < n; i++) { cout

番茄西红柿 2021-11-29 10:50 评论0 收藏2637
程序员的算法趣题Q22: 不缠绕的纸杯电话

摘要：假设有几个小朋友以相同间隔围成圆周，要结对用纸杯电话相互通话。如果绳子交叉，很有可能会缠绕起来，所以结对的原则是不能让绳子交叉。如下所示运行结果上一篇异或杨辉三角形下一篇禁止右转本系列总目录参见程序员的算法趣题详细分析和全解目录 1. 问题描述 2. 解题分析 3. 代码及测试 1. 问...

MoAir 2021-09-09 09:33 评论0 收藏0