資訊專欄INFORMATION COLUMN
摘要：楊輝三角形，又稱賈憲三角形帕斯卡三角形海亞姆三角形，是二項式系數(shù)在的一種寫法，形似三角形，在中國首現(xiàn)于南宋楊輝的詳解九章算術(shù)得名，書中楊輝說明是引自賈憲的釋鎖算術(shù)，故又名賈憲三角形。
楊輝三角形，又稱賈憲三角形、帕斯卡三角形、海亞姆三角形，是二項式系數(shù)在的一種寫法，形似三角形，在中國首現(xiàn)于南宋楊輝的《詳解九章算術(shù)》得名，書中楊輝說明是引自賈憲的《釋鎖算術(shù)》，故又名賈憲三角形。
前9層寫出來如下：
?。?br> １?。?br> １?。病。?br> ?。薄。场。场。?br> ?。薄。础。丁。础。?br> ?。薄。怠?0 10?。怠。?br> ?。薄。丁?5 20 15?。丁。?br>?。薄。贰?1 35 35 21?。贰。?br>１?。浮?8 56 70 56 28 ８?。?/p>
首先給大家介紹一種最簡單的求楊輝三角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;
}
這種方法實現(xiàn)最簡單，但是如果mn的值特別大的話，性能會非常差，我試了個100，78，就把機器卡死了。。
迭代法迭代法從第一層開始循環(huán)，只循環(huán)每行中必要的列，最后求出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];
}
公式法
當然了，根據(jù)楊輝三角的性質(zhì):第n行的m個數(shù)可表示為 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;
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/22857.html
摘要：前言最近在回顧以前使用寫過的數(shù)據(jù)結(jié)構(gòu)和算法的東西，發(fā)現(xiàn)自己的算法和數(shù)據(jù)結(jié)構(gòu)是真的薄弱，現(xiàn)在用改寫一下，重溫一下。 前言 最近在回顧以前使用C寫過的數(shù)據(jù)結(jié)構(gòu)和算法的東西，發(fā)現(xiàn)自己的算法和數(shù)據(jù)結(jié)構(gòu)是真的薄弱，現(xiàn)在用Java改寫一下，重溫一下。 只能說慢慢積累吧～下面的題目難度都是簡單的，算法的大佬可直接忽略這篇文章了～入門或者算法薄弱的同學(xué)可參考一下～ 很多與排序相關(guān)的小算法(合并數(shù)組、獲...
摘要：迭代法復(fù)雜度時間空間思路簡單的按照楊輝三角形的規(guī)則計算就行了。代碼加入第一個加入中間的數(shù)加入最后一個逆序相加法復(fù)雜度時間空間思路同樣用迭代的方法，根據(jù)上一層的值算下一層，不過這里每一層都在同一個上操作。 Pascals Triangle I Given numRows, generate the first numRows of Pascals triangle. For examp...
摘要：楊輝三角楊輝定義如下把每一行看做一個，試寫一個，不斷輸出下一行的復(fù)制一個，這樣才不會影響到原有的。不然里的每個列表的末尾會為 楊輝三角楊輝 定義如下： 1 / 1 1 / / 1 2 1 / / / 1 3 3 1 / / / / 1 4 6 ...
摘要：簡單做法打印空格請輸入行數(shù)實現(xiàn)楊輝三角的算法效果楊輝三角形開方做法本源 簡單做法#includeusing namespace std;#include#includevoid kongge(int n)//打印空格{ for (int i = 0; i < n; i++) { cout
摘要：假設(shè)有幾個小朋友以相同間隔圍成圓周，要結(jié)對用紙杯電話相互通話。如果繩子交叉，很有可能會纏繞起來，所以結(jié)對的原則是不能讓繩子交叉。如下所示運行結(jié)果上一篇異或楊輝三角形下一篇禁止右轉(zhuǎn)本系列總目錄參見程序員的算法趣題詳細分析和全解 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 1. 問...
閱讀 786·2021-09-30 09:46
閱讀 3804·2021-09-03 10:45
閱讀 3620·2019-08-30 14:11
閱讀 2555·2019-08-30 13:54
閱讀 2266·2019-08-30 11:00
閱讀 2364·2019-08-29 13:03
閱讀 1571·2019-08-29 11:16
閱讀 3593·2019-08-26 13:52
