藍橋杯 算法訓練 數字三角形（c語言版詳細注釋）

試題 算法訓練 數字三角形

                                                                                  藍橋杯試題解答彙總連結

資源限制

       時間限制：1.0s 記憶體限制：256.0MB

問題描述

       圖３.１－１）示出了一個數字三角形。 請編一個程式計算從頂至底的某處的一條路

　　徑，使該路徑所經過的數字的總和最大。

　　●每一步可沿左斜線向下或右斜線向下走；

　　●1＜三角形行數≤100；

　　●三角形中的數字為整數0，1，…99；

　　　

　　　（圖３.１－１）

輸入格式

       檔案中首先讀到的是三角形的行數。

　　接下來描述整個三角形

輸出格式

       最大總和（整數）

樣例輸入

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
           

樣例輸出

30
           

代碼

#include<stdio.h>
int max(int x,int y){//求兩個數較的數 
	if(x>y){
		return x;
	}
	else{
		return y;
	}
}
int main(){
	int i,j,n,v[100][100];//v用來存儲數字三角形
	scanf("%d",&n);
	for(i=0;i<n;i++){
		for(j=0;j<=i;j++){
			scanf("%d",&v[i][j]);//把三角形數字存儲到v數組 
		}
	}
	for(i=n-2;i>=0;i--){
		for(j=0;j<=i;j++){
			v[i][j]+=max(v[i+1][j],v[i+1][j+1]);//每行儲存下面一行通路中較數字和較大的 
		}
	}
	printf("%d",v[0][0]); 
	return 0;
}