關于求楊輝三角形mn值的算法

zqhxuyuan 發布于2019-06-27 16:20 / 2092人閱讀

摘要：楊輝三角形，又稱賈憲三角形帕斯卡三角形海亞姆三角形，是二項式系數在的一種寫法，形似三角形，在中國首現于南宋楊輝的詳解九章算術得名，書中楊輝說明是引自賈憲的釋鎖算術，故又名賈憲三角形。

楊輝三角形，又稱賈憲三角形、帕斯卡三角形、海亞姆三角形，是二項式系數在的一種寫法，形似三角形，在中國首現于南宋楊輝的《詳解九章算術》得名，書中楊輝說明是引自賈憲的《釋鎖算術》，故又名賈憲三角形。

前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算法三

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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