【杭电】[2032]杨辉三角

问题描述

问题分析

啊
杨辉三角
感觉这一题值得说说

杨辉三角是我进入ACM协会时上机做的一题
据当时学长学姐说是当时在所有题里最难的一题
(所以进协会其实还是挺简单的)
做了这一题其它题就不用做了……‘

不过这一种写法是在进协会之前想的一种公式法
也就是根据
第n行的m个数可表示为 C(n-1,m-1)
即为从n-1个不同元素中取m-1个元素的组合数
根据这个公式用变量和循环来做

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include <stdio.h>
int main() {
    int s = 1, n;
    int i, j;
    while(scanf("%d", &n)!=EOF) {
        printf("1\n");
        for (i = 2; i <= n; s = 1, i++) {
            printf("1 ");
            for (j = 1; j <= i - 2; j++)
                printf("%d ", (s = (i - j) * s / j));
            printf("1\n");
        }
        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
#include <stdio.h>
int main() {
    int a[100][100] ;
    int i,j,n;
    while(scanf("%d",&n)!=EOF) {
        for(i=1 ; i<=n; i++) {
            for(j=1; j<=i; j++) {
                if(j==1)
                    a[i][j]=1;
                else
                    a[i][j]=a[i-1][j-1]+a[i-1][j];
            }
        }
        for(i=1; i<=n; i++) {
            for(j=1; j<=i; j++) {
                printf("%d",a[i][j]);
                if(j!=i)
                    printf(" ");
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}

也是有纪念意义的一题啊~