fork download
copy 
  1. /*
  2.    Program računa maksimalnu sumu u zapisu brojeva u obliku trokuta. Problem se može riješiti
  3.    na nekoliko načina (npr. dinamičko programiranje), ovdje ćemo predstaviti rekurzivno rješenje.
  4.    
  5.    Označimo s f(i,j) maksimalnu sumu koja završava na nekom putu odozdo prema gore na i-tom retku
  6.    i j-tom stupcu i neka je T 2D polje koje sprema unesene podatke i visine je h. || je mjera za duljinu.
  7.    Tada f(i,j) možemo rekonstruirati preko prijašnjih riješenja 
  8.    
  9.    					  T(i,j), i = h-1
  10.    			f(i,j) ={ 
  11.    					  max{f(i+1,j), f(i+1,j+1) : j = 0,1, ..., |T(i+1)|-1}+T(i,j), 0<= i< h-1.
  12.    			
  13.   Kako svi putovi završavaju u početnom vrhu trokuta (0,0), onda i maksimalni put završava u (0,0)
  14.   
  15.   *** komentar: koristimo memoizaciju kako bi spremeli vrijednosti prevog rekurzivnog računanja funkcije f
  16. */
  17.  
  18.  
  19.  
  20. #include <iostream>
  21. using namespace std;
  22.  
  23. // C support
  24. #include <cstdlib>
  25. #include <cstring>  // memset
  26.  
  27. // input from file
  28. #include <fstream>
  29.  
  30. #define MEMO
  31. #define NONE     -1
  32.  
  33. #define MAX(a,b) ((a) > (b) ? (a) : (b))
  34.  
  35.  
  36.  
  37. int max_sum_trian(short T[100][100], int MaxSums[100][100], int row, int col, int height)
  38. {
  39.   // varijable 
  40.   int max_value;
  41.   // rekruzija
  42.   if (row == height-1) return T[row][col];
  43.  
  44.   // rekurzivni poziv
  45.  
  46.   #ifdef NO_MEMO
  47.   return (MAX(max_sum_trian(T,MaxSums, row+1, col,height), max_sum_trian(T,MaxSums, row+1, col+1,height))+T[row][col]);
  48.   #endif
  49.  
  50.   // s memoizacijom
  51.   #ifdef MEMO 
  52.   if (MaxSums[row+1][col] == NONE)   MaxSums[row+1][col] = max_sum_trian(T,MaxSums, row+1, col,height);
  53.   if (MaxSums[row+1][col+1] == NONE) MaxSums[row+1][col+1] = max_sum_trian(T,MaxSums, row+1, col+1,height);
  54.  
  55.   MaxSums[row][col] = MAX(MaxSums[row+1][col], MaxSums[row+1][col+1])+T[row][col];
  56.   return MaxSums[row][col];
  57.   #endif
  58.  
  59.  
  60. }
  61.  
  62.  
  63. int main()
  64. {
  65.   // postavljanje podataka
  66.    // 2D apolje za spremanje podataka
  67.  
  68.  
  69.   short T[100][100];
  70.   int   max_sums[100][100];
  71.  
  72.   int   n; // broj testnih primjera
  73.   int   max_value; // rjesenje
  74.   int   height;    // visina trokuta
  75.  
  76.   int      num_of_Tests = 0;
  77.  
  78.   cin >> n; 
  79.  
  80.   while(++num_of_Tests<=n)
  81.   {
  82.  
  83.     // incijaliziraj polja T, max_sums
  84.     memset(T, 0, sizeof(T[0][0]) * 100 * 100);
  85.     memset(max_sums, NONE, sizeof(max_sums[0][0]) * 100 * 100);
  86.  
  87.  
  88.     // ucitavanje podataka trokuta
  89.     cin >> height;
  90.  
  91.     int row = 0;
  92.     while(row < height)
  93.     {
  94.       for(int col = 0; col <= row; col++) cin >> T[row][col];
  95.       row++;
  96.     }
  97.  
  98.     // rjesavanje problema
  99.     max_value = max_sum_trian(T,max_sums, 0,0, height);
  100.     // ispis outputa
  101.     cout <<  max_value << endl;
  102.  
  103.   } // end of num_of_tests<n
  104.  
  105. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
2
3
1
2 1
1 2 3
4 
1 
1 2 
4 1 2
2 3 1 1
stdout
copy 
5
9
https://ideone.com/joh91U
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!