ChenGen

一切歸零，重新開始

隨筆 - 13, 文章 - 10, 評論 - 21, 引用 - 0

數(shù)據(jù)加載中……

楊輝三角

???前段時(shí)間復(fù)習(xí)了01背包問題的算法，受它的啟發(fā)，我采用同樣的數(shù)據(jù)結(jié)構(gòu)來解決楊輝三角的問題。

???下面是這種數(shù)據(jù)結(jié)構(gòu)的圖示：

???數(shù)組 r 用來存儲楊輝三角每一行的數(shù)據(jù)，那么 r 的大小就是 (n+1)n/2?，其中 n 是楊輝三角的行數(shù)。數(shù)組 f 用來存儲每一行開始位置的下標(biāo)，如第一行從位置1開始，所以 f[1]=1；第四行從位置7開始，所以 f[4]=7。

???完整的程序如下(環(huán)境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;//每行第一個(gè)位置是1

????????for(j=f[i-1];j<f[i]-1;j++){

????????????r[next++]=r[j]+r[j+1];

????????}

????????r[next++]=1;//每行最后一個(gè)位置是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 閱讀(1855) 評論(0) 編輯收藏所屬分類: 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發(fā)表評論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關(guān)文章: 楊輝三角復(fù)習(xí)動態(tài)規(guī)劃算法——01背包問題復(fù)習(xí)回溯算法——N皇后問題復(fù)習(xí)二叉排序樹復(fù)習(xí)排序算法2 復(fù)習(xí)排序算法

ChenGen

楊輝三角

導(dǎo)航

常用鏈接

留言簿(5)

隨筆分類

隨筆檔案

文章分類

文章檔案

收藏夾

Good BLogs

搜索

最新評論

閱讀排行榜

評論排行榜