7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Questo è un triangolo!
Scrivete un programma che calcoli la più grande somma di numeri ottenibile seguendo un percorso che parta dalla cima del triangolo e termini da qualche parte sulla sua base. Ad ogni passo si può procedere diagonalmente in basso o a destra o a sinistra.
Input
Il programma deve leggere da un file di nome ‘input.txt’. La prima riga del file contiene un’unico intero N, il numero di righe del triangolo. Le successive N righe contengono un numero crescente di interi 2′, la n-esima riga contiene n interi separati da uno spazio.
Output
Il programma deve scrivere in un file di nome ‘output.txt’ la somma massima ottenibile dal triangolo.
Assunzioni
1 < N ≤ 100
0 < i < 100
input.txt output.txt
5 30
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Partendo dal basso salviamo il punteggio maggiore fra i figli nel padre, il nonno di tutti (il vertice) avrà la risposta:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include<cassert> #include<fstream> #include<iostream> using namespace std; #define UNKNOWN -1 #define N 100 int t[N][N],n,memoRisp[N+1][N+1]; int main() { ifstream fin("input.txt"); assert( fin ); fin >> n; for(int i = 0; i < n; i++) for(int j = 0; j <= i; j++) fin >> t[i][j]; fin.close(); for(int i = 0; i < n; i++) for(int j = 0; j <= i; j++) memoRisp[i][j] = UNKNOWN; for(int j = 0; j <= n; j++) memoRisp[n][j] = 0; for(int i = n-1; i >= 0; i--) for(int j = 0; j <= i; j++) memoRisp[i][j] = t[i][j] + max( memoRisp[i+1][j], memoRisp[i+1][j+1] ); ofstream fout("output.txt"); assert( fout ); fout << memoRisp[0][0] << endl; fout.close(); return 0; } |
