ChenGen
          

          一切歸零，重新開始
          

          

          

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

          


          		
	
          

          

          
	
          
		
			
          

					

          導航
          


					
          
	
          
		
          <2006年10月>
          
	
          日一二三四五六
          24252627282930
          1234567
          891011121314
          15161718192021
          22232425262728
          2930311234
          

          

					
					

          常用鏈接
          


          留言簿(5)
          


		
          隨筆分類
          
		
				
			
	
		
          隨筆檔案
          
		
				
			
	
		
          文章分類
          
		
				
			
	
		
          文章檔案
          
		
				
			
	
		
          收藏夾
          
		
				
			
	
		
          Good BLogs
          
		
				
			
	



          搜索
          

            
	
          • 
		
          •  
	
            • 

          


          最新評論
	
          

          
	
			
		

          


          閱讀排行榜
          



          評論排行榜
          




          
		          		
		
			
          
				
					
	
          
		
          
			楊輝三角
		
          
		
          
		???前段時間復習了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 閱讀(1855) 評論(0)  編輯  收藏  所屬分類: 數據結構復習 
		
          
	
          
	
	


	


          
	    
    




          








          

				
			
          
		          		
	
          
	
          
		
			

		
	
          

          


    







          
        
	




主站蜘蛛池模板：
高唐县|
灵丘县|
徐水县|
缙云县|
平罗县|
亚东县|
历史|
颍上县|
手游|
金阳县|
荔浦县|
和静县|
新巴尔虎右旗|
崇义县|
丰顺县|
云浮市|
灵山县|
开远市|
仁怀市|
金坛市|
河间市|
呼伦贝尔市|
红河县|
临澧县|
白山市|
锦屏县|
怀化市|
曲阳县|
佛冈县|
嘉义县|
汕头市|
康保县|
横峰县|
资阳市|
杭州市|
合肥市|
金乡县|
阳东县|
富川|
桦甸市|
永新县|