帕斯卡三角形||杨辉三角

问题陈述:

       杨辉三角如图所示:要求编程输出。


问题解法:

      常规思路每个数字等于其"肩膀"上两数字之和,即a[i][j] = a[i-1][j-1] + a[i-1][j],代码稍有繁琐。

      从代数的角度来考虑这个问题,可以得到一个通式:a[i][j] = a[i][0] * (i/1) * ((i-1)/2)) * ((i-2)/3) * ... * (1/i)。

      公式可能比较抽象,举个例子说明 :(行列下标均从0开始)

             第7行第1列 a[6][0] = 1;

             第7行第2列 a[6][1] = 1 * 6/1;

             第7行第3列 a[6][2] = 1 * 6/1 * 5/2;

             第7行第4列 a[6][3] = 1 * 6/1 * 5/2 * 4/3;

             第7行第5列 a[6][4] = 1 * 6/1 * 5/2 * 4/3 * 3/4;

             第7行第6列 a[6][5] = 1 * 6/1 * 5/2 * 4/3 * 3/4 * 2/5;

             第7行第7列 a[6][6] = 1 * 6/1 * 5/2 * 4/3 * 3/4 * 2/5 * 1/6;


代码详解:

 1 /*
 2 N:杨辉三角行数减一
 3 combine(int n, int c) 计算第n行第c列的值 下标从0开始
 4 */
 5 #include <stdio.h>
 6 #include <stdlib.h>
 7 #define N 12
 8 long combine(int n, int c);
 9 
10 int main()
11 {
12     int i, j, k;
13     for(i=0; i<=N; i++) {
14          for(j=0; j<=i; j++) {
15             if(j == 0) {
16                 for(k=0; k<N-i; k++){
17                     printf("   ");
18                 }
19             }else {
20                 printf("   ");
21             }
22             printf("%3d", combine(i, j));
23          }
24          printf("
");
25     }
26     return 0;
27 }
28 
29 long combine(int n, int c) {
30     int i;
31     long p = 1;
32     for(i=1; i<=c; i++) {
33         p = p*(n-i+1) / i;
34     }
35     return p;
36 }

转载请注明出处:http://www.cnblogs.com/michaelwong/p/4114940.html

原文地址:https://www.cnblogs.com/michaelwong/p/4114940.html