Na poniższym rysunku przedstawiono piramidę, która ma 4 poziomy. Pola piramidy są wypełnione
liczbami. Ciemniejsze pola na rysunku oznaczają drogę w takiej piramidzie – droga zaczyna się w
polu na najwyższym poziomie piramidy i biegnie do jej podstawy po polach na kolejnych poziomach,
które stykają się swoimi podstawami. Długością takiej drogi jest suma liczb znajdujących się w polach
drogi. Droga zaciemniona na rysunku ma długość: 7 + 6 + 3 + 5 = 21.
http://prntscr.com/5gj6loProblem: oblicz długość najdłuższej drogi w piramidzie.
Przykładowa piramida pokazana powyżej ma więc następującą reprezentację w tablicy:
http://prntscr.com/5gj7xcSPECYFIKACJA
Dane: Liczba naturalna n i tablica Pir[1..n;1..n], w której elementy Pir[i,j] dla i = 1, 2,…, n oraz j = 1,
2,…, i są dodatnimi liczbami całkowitymi.
Wynik: Ciąg n liczb j1, j2,…, jn, gdzie j1 = 1 oraz jk = jk-1 lub jk = jk-1 + 1 dla k = 2, 3,…, n taki, że suma
Pir[1,1] + Pir[2,j2] + Pir[3,j3] + … + Pir[n,jn] jest możliwie największa.
Czyli w programie ma obliczyć długość, jak i zapamiętać i wypisać jaką drogą doszedł do tego wyniku.
#include <iostream>
#define n 3
using namespace std;
int P[ n ][ n ];
int program( int P[] )
{
int smax = 0;
int s1 = 0;
int s2 = 0;
int i = 0;
while( i <= n )
{
s1 = s1 + P[ i, i ];
s2 = s2 + P[ i, i + 1 ];
if( s1 > smax ) { smax = s1; }
if( s2 > smax ) { smax = s2; }
i++;
}
return smax;
}
int main()
{
P[ 0 ][ 0 ] = 7;
P[ 1 ][ 0 ] = 5;
P[ 1 ][ 1 ] = 6;
P[ 2 ][ 0 ] = 6;
P[ 2 ][ 1 ] = 4;
P[ 2 ][ 2 ] = 3;
P[ 3 ][ 0 ] = 4;
P[ 3 ][ 1 ] = 6;
P[ 3 ][ 2 ] = 5;
P[ 3 ][ 3 ] = 6;
cout << program( P[ 3, 3 ] );
return 0;
}
Jedynie co mam dobrze w tym programie to wypisanie danych...
Czy ktoś mógłby nakierować mnie na sposób jak to zrobić/napisać dla mnie schemat jak mogłoby to wyglądać/napisać chociaż pętlę która obliczy długość najdłuższej drogi?
Pozdrawiam i z góry dziękuję.