ChenGen

一切归零，重新开始
随笔 - 13, 文章 - 10, 评论 - 21, 引用 - 0
数据加载中……

杨辉三角

   前段时间复习了01背包问题的算法，受它的启发，我采用同样的数据结构来解决杨辉三角的问题。

   下面是这种数据结构的图示：
Yanghui.JPG
   数组 r 用来存储杨辉三角每一行的数据，那么 r 的大小就是 (n+1)n/2 ，其中 n 是杨辉三角的行数。数组 f 用来存储每一行开始位置的下标，如第一行从位置1开始，所以 f[1]=1；第四行从位置7开始，所以 f[4]=7。

   完整的程序如下(环境turbo c 2.0)：
#include "stdio.h"
#include "stdlib.h"

void Yanghui(int n);

void main(void)
{
    int n;
    printf("intput n: ");
    scanf("%d",&n);
    Yanghui(n);
}

void Yanghui(int n)
{
    int *r,*f;
    int i,j,k,next;
    r=(int *)malloc(sizeof(int)*( n*(n+1)/2+1 ));
    f=(int *)malloc(sizeof(int)*( n+2 ));
    r[1]=1;
    f[1]=1;
    f[2]=2;
    next=2;
    i=2;
    while(i<=n){
        r[next++]=1;//每行第一个位置是1
        for(j=f[i-1];j<f[i]-1;j++){
            r[next++]=r[j]+r[j+1];
        }
        r[next++]=1;//每行最后一个位置是1
        f[i+1]=next;//下一行的开始位置
        i++;
    }
    //输出
    for(i=1;i<=n;i++){
        for(j=1;j<=n-i;j++)
            printf("   ");
        for(j=f[i];j<f[i+1];j++){
            printf("%2d   ",r[j]);
        }
        printf("\n");
    }

}

posted on 2006-10-05 00:58 ChenGen 阅读(1841) 评论(0)  编辑  收藏 所属分类: 数据结构复习


只有注册用户登录后才能发表评论。
网站导航: