杨辉三角 算法

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

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

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

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

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 ( "M" , (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 ( "M" ,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 ( "= " ,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( "M" , 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 ( " " , $n *12, " " );      printf( "=" , $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 ( " " ,( $n +1- $i )*12, " " );          printf( "=" , $arr [ $i ][ $j ]= $arr [ $i -1][ $j -1]+ $arr [ $i -1][ $j ]);          echo  "  " ;        }        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）⁰ = 1a⁰b⁰  = 1

第二行，就是（a+b）¹ =1a¹b⁰ +1a⁰b¹

第三行，就是 (a+b)²  =1a²b⁰ + 2a¹b¹ +1a⁰b²

第四行，就是（a+b）³ = 1a³b⁰ +3a²b¹ + 3a¹b²+1a⁰b³

第五行，就是（a+b）⁴  =1a⁴b⁰ + 4a³b¹ +6a²b² + 4a³b¹ +1a⁴b⁰

(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