首页 > ACM题库 > 九度OJ > 九度-1073-杨辉三角形[解题代码]
2013
12-12

九度-1073-杨辉三角形[解题代码]

题目来源:2002年清华大学计算机研究生机试真题(第I套)

题目描述:

输入n值,使用递归函数,求杨辉三角形中各个位置上的值。

输入:

一个大于等于2的整型数n

输出:

题目可能有多组不同的测试数据,对于每组输入数据,
按题目的要求输出相应输入n的杨辉三角形。

样例输入:
6
样例输出:
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

cpp 代码如下:
#include <stdio.h>
#include <stdlib.h>

void print_arr(int * arr,int len){
    for(int i=0; i<len-1; i++)
    	printf("%d ",arr[i]);
    printf("1\n");
}

//void swap(int **a,int **b){
//    int **temp = a;
//    *a = *b;
//    *b = *temp;
//}

int main() {
    int n;
    int * pre;
    int * current;
    while(scanf("%d",&n) != EOF){
        pre = (int *)malloc(sizeof(int) * n);
        current = (int *)malloc(sizeof(int) * n);
        int i,j;
        for(i=2; i<=n; i++){
            if(2 == i){
                pre[0] = pre[1] = 1;
                current[0] = current[1] = 1;
                printf("1 1\n");
                continue;
            }
//          2
            for(j=1; j<i-1; j++){
                current[j] = pre[j] + pre[j-1];
            }
            current[i-1] = 1;

            print_arr(current,i);
            int * temp = pre;
            pre = current;
            current = temp;
//            swap(&pre,&current);
        }
    }

    return 0;
}
/**************************************************************
	Problem: 1073
	User: coder
	Language: C
	Result: Accepted
	Time:10 ms
	Memory:912 kb
****************************************************************/


  1. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。