您的位置: 首页  >  文章  >  杨辉三角 算法

杨辉三角 算法

分类: 文章 • 2024-06-14 16:04:52

最近，看一些东西突然碰到了杨辉三角，有点懵，故查了点资料，

首先看一下杨辉三角形式：

杨辉三角 算法


首先，要想编程解决杨辉三角，必先了解其性质：

杨辉三角 算法



上述那么多，我们真正需要的也就是第一个，每个数等于它上方两数之和。



C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<cstdio>
#include<iostream>
using namespace std;
long long int Triangle[1000][1000];
int main()
{
    Triangle[1][1]=1;//初始化 
    Triangle[2][1]=1;Triangle[2][2]=1;
    for(int i=3;i<=50;i++)//制作三角。 
    {
        for(int j=1;j<=i;j++)
        {
            Triangle[i][j]=Triangle[i-1][j-1]+Triangle[i-1][j];
        }
    }
    for(int i=1;i<=50;i++)//输出 
    {
        for(int j=1;j<=i;j++)
        {
            cout<<Triangle[i][j]<<"  ";
        }
        cout<<endl;
    }
    return 0;
}


C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Program
{
  public int yanghui(int value)
  {
  if(value<3) return 1;
  int[,]arry=new int[value,value];
  Console.WriteLine("数组为：");
  for(int i=0;i<value;i++)
  {
    string str="";
    str=str.PadLeft(value-i);
    Console.Write(str);
    for(int j=0;j<=i;j++)
    {
      if(i==j||j==0)
        arry[i,j]=1;
      else
        arry[i,j]=arry[i-1,j-1]+arry[i-1,j];
      Console.Write(arry[i,j]+"");
    }
    Console.WriteLine();
  }
}
  
static void Main(string[]args)
{
  Program p=new Program();
  Console.WriteLine("请输入数组值：");
  if (p.yanghui(Convert.ToInt16(Console.ReadLine())))
    Console.WriteLine("输入数值必须大于3");
  Console.Readkey();
}
  
}



C
以下的代码均用标准 C 语言写成，可以被包括 MSVC（含 VC6）、GCC 的多种 C 编译器编译。
这个算法使用只行列位置和左侧的数值算出数值：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* yh-rt1.c - 时间和空间最优算法 */
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int s = 1, h;                    // 数值和高度
    int i, j;                        // 循环计数
    scanf("%d", &h);                 // 输入层数
    printf("1\n");                   // 输出第一个 1
    for (i = 2; i <= h; s = 1, i++)         // 行数 i 从 2 到层高
    {
        printf("1 ");                // 第一个 1
        for (j = 1; j <= i - 2; j++) // 列位置 j 绕过第一个直接开始循环
            //printf("%d ", (s = (i - j) / j * s));
            printf("%d ", (s = (i - j) * s / j));
        printf("1\n");               // 最后一个 1，换行
    }
    getchar();                       // 暂停等待
    return 0;
}
杨辉三角 算法默认状态下不启用金字塔和菱形的输出
默认求直角三角形，可通过注释的开关或使用编译器的 -D 定义开关调节等腰三角形和菱形输出。如果觉得复杂，可按照 define 使用的情况剔除因不符合 ifdef 条件从而未启用的代码之后阅读。
这个算法创建了一个二维数组，并且通过上一行的数值求当前行。在反过来再次打印时，这个程序会使用以前算好的值，从而节省了重复迭代的时间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/* yh-2d.c - 二维数组迭代 */
#include<stdio.h>
#define M 10       // 行数
// #define PYRAMID // 金字塔，会额外填充空格
// #define REVERSE // 反向再来一次，得到菱形
int main(void)
{
  int a [M][M], i, j;   // 二维数组和循环变量，a[行][列]
  for (i = 0; i<M; i++) // 每一行
  {
#ifdef PYRAMID
    for (j = 0;j <= M-i; j++) printf ("  ");
#endif // 填充结束
    for (j = 0; j <= i; j++) // 赋值打印
      printf("%4d", (a[i][j] = (i == j || j == 0) ? 1 : // 首尾置 1
        a[i - 1][j] + a[i - 1][j - 1] )); // 使用上一行计算
    printf("\n");
  }
#ifdef REVERSE
  for(i = M-2; i >= 0; i--)
  {
#ifdef PYRAMID
    for (j = 0;j <= M - i; j++) printf("  ");
#endif // 填充结束
    for (j = 0;j <= i; j++) printf("%4d",a[i][j]); // 直接使用以前求得的值
    printf("\n");
  }
#endif // 菱形结束
  getchar(); // 暂停等待
}
这一个使用大数组写成，风格更接近教科书上的 VC6 代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* yh-rt3.c - 较为暴力的大数组 */
#include <stdio.h>
#include "string.h"
int main()
{
    int a[10000];        //容器，由n*(n+1)/2<=10000可知，n<=141
    int b,CR,i;        //b为当前行数，CR为要求显示的行数，i为循环数
    printf("请输入要显示的行数（3~141）：");
    scanf("%d",&CR);
    YHSJ(CR);
    a[1]=a[2]=1;        //前两行数值少且全为1，故直接输出
    printf("%d\n",a[1]);
    printf("%d %d\n",a[1],a[2]);
    for(b=3;b<=CR;b++)        //从第三行开始判断
    {
        for(i=b;i>=2;i--)        //从倒数第一个数开始加
          a[i]=a[i]+a[i-1];        //杨辉三角的规律，没有值的数组默认为0
        for(i=1;i<=b;i++)        //显示循环
          printf("%d ",a[i]);
        printf("\n");        // 换行
    }
    return 0;
}
这个版本使用队列的方式输出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
#define EMPTY 1
#define OFLOW 2
#define INVAL 3
#define MAX_Q 100
typedef int DataType; // 数据类型选择
typedef struct{ DataType elem[MAX_Q]; int front, rear; } LinkQ;
// 队列及检查宏
#define InitQ(Q) LinkQ Q; Q.front=Q.rear=-1;
#define _EQ(Q,e) Q.elem[(Q.rear=(Q.rear+1)%MAX_Q)]=e
#define EnQ(Q,e) if((Q.rear+1)%MAX_Q==Q.front) Exit(OFLOW,"Overflow"); _EQ(Q,e)
#define DeQ(Q,e) e=Q.elem[(Q.front=(Q.front+1)%MAX_Q)]
#define Front(Q) Q.elem[(Q.front+1)%MAX_Q]
// 退出
int Exit(int err, char msg[]) { puts(msg); exit(err); return err; }
int main(void){
    int n=1,i,j,k,t;
    InitQ(Q);
    printf("please enter a number:");
    scanf("%d",&n);
    if (n<=0) {
        printf("ERROR!\n");
        exit(INVAL);
    }
    for(i=0;i<n;i++) printf(" ");
    puts("1"); EnQ(Q,1); EnQ(Q,1);
    for(i=1;i<n;i++) {
        for(k=0;k<n-i;k++) printf(" ");
        EnQ(Q,1);
        for(j=0;j<i;j++){
            DeQ(Q,t);
            printf("%3d ",t);
            EnQ(Q,t+Front(Q));
        }
        EnQ(Q,1);
        DeQ(Q,t);
        printf("%d\n",t);
    }
    return 0;
}

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class TriangleArray
{
   public static void main(String[] args)
   {
      final int NMAX = 10; 
 
      // allocate triangular array
      int[][] odds = new int[NMAX + 1][];
      for (int n = 0; n <= NMAX; n++)
         odds[n] = new int[n + 1];  
 
      // fill triangular array
      for (int n = 0; n < odds.length; n++)
         for (int k = 0; k < odds[n].length; k++)
         {
            /*
             * compute binomial coefficient n*(n-1)*(n-2)*...*(n-k+1)/(1*2*3*...*k)
             */
            int lotteryOdds = 1;
            for (int i = 1; i <= k; i++)
               lotteryOdds = lotteryOdds * (n - i + 1) / i;
 
            odds[n][k] = lotteryOdds;
         }
 
      // print triangular array
      for (int[] row : odds)
      {
         for (int odd : row)
            System.out.printf("%4d", odd);
         System.out.println();
      }
   }
}

PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
<?php
/* 默认输出十行，用T(值)的形式可改变输出行数 */
class T{
  private $num;
  public function __construct($var=10) {
    if ($var<3) die("值太小啦！");
    $this->num=$var;
  }
  public function display(){
    $n=$this->num;
    $arr=array();
  //$arr=array_fill(0,$n+1,array_fill(0,$n+1,0));
    $arr[1]=array_fill(0,3,0);
    $arr[1][1]=1;
    echo str_pad("&nbsp;",$n*12,"&nbsp;");
    printf("%3d",$arr[1][1]);
    echo "<br/>";
    for($i=2;$i<=$n;$i++){
      $arr[$i]=array_fill(0,($i+2),0);
      for($j=1;$j<=$i;$j++){
        if($j==1)
          echo str_pad("&nbsp;",($n+1-$i)*12,"&nbsp;");
        printf("%3d",$arr[$i][$j]=$arr[$i-1][$j-1]+$arr[$i-1][$j]);
        echo "&nbsp;&nbsp;";
      }
      echo"<br/>";
    }
  }
}
$yh=new T(); //$yh=new T(数量);
$yh->display();
?>
只输出数组的方式如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
<?php
$max = 10;
$L = [1];
var_dump($L);
$L = [1,1];
var_dump($L);
$n = 2;
while ($n <= $max - 1){
    $oldL = $L;
    $L[$n] = 1;
    $n++;
    for ($i = 1;$i <count($oldL);$i++){
        $L[$i] = $oldL[$i-1] + $oldL[$i];
    }
    var_dump($L);
}
?>

Python
较为便捷，代码量较少的实现方式如下：
1
2
3
4
5
6
7
8
# -*- coding: utf-8 -*-
#!/usr/bin/env python
def triangles():
    L = [1]
    while True:
        yield L
        L.append(0)
        L = [L[i - 1] + L[i] for i in range(len(L))]
该方式用到了列表生成式，理解起来较困难，下面是另一种方式：
1
2
3
4
5
6
7
8
def triangles():
    ret = [1]
    while True:
        yield ret
        for i in range(1, len(ret)):
            ret[i] = pre[i] + pre[i - 1]
        ret.append(1)
        pre = ret[:]


杨辉三角还有可以通过以下方式完成

 第一行，就是（a+b）0 = 1a0b0  = 1

第二行，就是（a+b）1 =1a1b0 +1a0b1

杨辉三角 算法

第三行，就是 (a+b)2  =1a2b0 + 2a1b1 +1a0b2

第四行，就是（a+b）3 = 1a3b0 +3a2b1 + 3a1b2+1a0b3

第五行，就是（a+b）4  =1a4b0 + 4a3b1 +6a2b2 + 4a3b1 +1a4b0杨辉三角 算法

(a+b)^n=C(n,0)a^n+C(n,1)a^(n-1)*b+C(n,2)a^(n-2)*b^2+...+C(n,n)b^n

相关推荐