Pascal三角形

作者:bakari   时间:2012.8.4

Pascal三角形又称杨辉三角形,是多项式系数的一种规律展示,最早是由我国数学家杨辉发现,比Pascal早200多年。

下面简单地总结一些其算法。

一、数组计算法:

1、公式推导:

这个很简单,看图就知道

由图可得公式:a[ i ][ j ] = a[i - 1] [j - 1] + a[i - 1][ j ] 

2、代码展示:

 1 void YangHuiTriangleArray(int Row)                           
 2 {
 3     for (int i = 0;i < Row; i++)
 4     {
 5         for (int j = 0;j <= i; j++)
 6         {
 7             if (j == 0 || j == i)  //置1条件
 8                 a[i][j] = 1;
 9             else 
10                 a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
11             cout<<a[i][j]<<" ";
12         }
13         cout<<endl;
14     }
15 }

二、递归法

这个是最好想到的,这一步的实现需要上一步作为铺垫。

废话不多说,直接来看代码

 1 long GetElement(int Row,int Col)
 2 {
 3     if (0 == Col || Row == Col)   //递归出口
 4         return 1;
 5     else 
 6         return GetElement(Row - 1,Col - 1) + GetElement(Row - 1,Col);
 7 }
 8 
 9 void YangHuiTriangleRecur(const long n)
10 {
11     for(int i = 0;i < n; i++)
12     {
13         for(int j = 0; j <= i; j++)
14             cout<<GetElement(i,j)<<" ";
15         cout<<endl;
16     }
17 }

三、数学推导法

本方法主要借助数学推导,比起前两种性能要好很多

令X10= 1 ;则

X20 = 1 , X21 = X20 * (2 - 1 + 1)/1 = 2 , X22 = X21 * (2 - 2 + 1)/2 = 1;

X30 = 1 , X31 = X30 * (3 - 1 + 1)/1 = 3 , X32 = X31 * (3 - 2 + 1)/2 = 3 , X33 = X32 * (3 - 3 + 1)/3 = 1;

.........

Xij = 1, Xij+1 = Xij * (i - j + 1)/j , ...... , Xii = 1;

大体就是这么个推导法,下面看代码:

 1 void YangHuiTriangle(int RowN)
 2 {
 3     for (int i = 0;i < RowN;i++)
 4     {
 5         for (int j = 0;j <= i;j++)
 6         {
 7             if (j == 0)        //第一个数前面要输出相应的空格
 8             {
 9                 for (int k = 1;k < RowN - i; k++)
10                     cout<<"  ";
11             }
12             else 
13                 cout<<" ";                          //数与数之间输出相应空格  
14             printf("%3d",ComputeNextInteger(i,j));  //输出下一个数
15         }
16         cout<<endl;
17     }
18 }
19 
20 int ComputeNextInteger(int iRow ,int iRowIndex)
21 {
22     long p = 1;
23     for (int i = 1;i <= iRowIndex; i++)    
24         p = p * (iRow - i + 1)/i;            //根据公式计算每一个数;
25     return p;
26 }

见图:

OK!希望多多烧香!  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法导论2-9章补充几道题

    本篇博文意在对前几章中遗漏的,本人觉得有意思的习题当独拿出来练练手。 1、习题2-4,求逆序对,时间复杂度要求Θ(nlgn) 定义:对于一个有n个不同的数组A,...

    CloudDeveloper
  • 算法导论第二章小试牛刀

    Author: bakari   Date: 2015.9.11 《算法导论》真是一本让人又爱又恨的书,爱自然是因为它精简凝练的算法呈现,读来让人欲罢不能;至于...

    CloudDeveloper
  • 腾讯2016春招之算法编程解析

    第一道题:求有删除情况的最长回文子串 题目: ? 解题思路: 这个题严格意义上来说,删除了字符就谈不上回文串了,既然有删除,那估计考察的不是回文串,而是其他的...

    CloudDeveloper
  • 蛇形填数

    在n*n方陈里填入1,2,...,n*n,要求填成蛇形。例如n=4时方陈为: 10 11 12 1 9 16 13 2 8 15 14 3 7 6 5 4

    书童小二
  • P3389 【模板】高斯消元法

    题目背景 Gauss消元 题目描述 给定一个线性方程组,对其求解 输入输出格式 输入格式: 第一行,一个正整数 nn 第二至 n+1n+1行,每行 n+1n+1...

    attack
  • 1036 跟奥巴马一起编程 (15 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • hdu1094

    @坤的
  • Minesweeper(蓝桥杯)

    然后就想着更好的方法嘛,就是给雷区标记,然后每个区的贡献值都是周围八个区的贡献值叠加。边输入边更新就能得到答案!

    用户7727433
  • P1719 最大加权矩形

    为了更好的备战NOIP2013,电脑组的几个女孩子LYQ,ZSC,ZHQ认为,我们不光需要机房,我们还需要运动,于是就决定找校长申请一块电脑组的课余运动场地,听...

    attack
  • P3717 [AHOI2017初中组]cover

    题目背景 以下为不影响题意的简化版题目。 题目描述 一个n*n的网格图上有m个探测器,每个探测器有个探测半径r,问这n*n个点中有多少个点能被探测到。 输入输出...

    attack

扫码关注云+社区

领取腾讯云代金券