Szukanie "największej" drogi w tablicy dwuwymiarowej.
Ostatnio zmodyfikowano 2016-01-31 04:29
CzepiMM Temat założony przez niniejszego użytkownika |
Szukanie "największej" drogi w tablicy dwuwymiarowej. » 2016-01-30 00:06:25 Witam. Czy ktoś mógł by mi pomóc w napisaniu algorytmu, który szuka drogi po tablicy dwuwymiarowej. Zasady: -Do tablicy losuje się losowe liczny naturalne z przedziału od 1 do 9. -Można poruszać się po tablicy tylko w prawo lub w dół (załóżmy że zaczynamy od lewego górnego rogu tablicy) -Program ma znaleźć w tablicy drogę, po której przejściu suma komórek po których przeszedł będzie największa.
Np. Mamy wylosowaną przykładową tablicę: X 1 9 9 5 3 8 1 1 2 9 9 3 1 3 9
Chodzi o to żeby program zakomunikował nam w jakiś sposób że musiał przejść w prawa, w prawo, w dół, w dół, w prawo, w prawo :) Ale jeśli zakomunikuje tylko że suma takie wędrówki (1+9+8+9+9+9) wynosi 45 i jest to najlepsza droga, to i tak był bym zadowolony.
Czy ktoś mógł by podsunąć mi jakiś pomysł, albo podrzucić jakiś pomocny link :) ? |
|
mateczek |
» 2016-01-30 16:32:46 algorytm wyznaczenia największej sumy może być taki !!! mamy tablice i przeglądamy ją element po elemencie (0) 2 3 1 2 3 1 2 3 tworzymy pustą tablicę pomocniczą !!! w przypadku pierwszej iteracji obliczamy sąsiednie elementy 0+2 =2 oraz 0+1=1 tablica pomocnicza wyglądać będzie tak 0 (2) 0 1 0 0 0 0 0 2 iteracja wskatujemy w prawo i obliczamy znów sąsiednie elementy 2+2=4 i 2+3=5 tablica pomocnicza będzie wyglądać tak 0 2 (5) 1 4 0 0 0 0 3 iteracja mamy wskaźnik na piątce w prawo polecieć nie możemy więc lecimy tylko w dół 5+3=8 0 2 5 (1) 4 8 0 0 0 4 iteracja 1+1=2 oraz 1+2=3 ponieważ w tablicy pomocniczej mamy już w tym miejscu 4 to ta droga odpada(poprzednia droga dała większą sumę) !!! więc tablica pomocnicza będzie wyglądać tak: 0 2 5 1 (4) 8 2 0 0 przykładowy algorytm wydaje mi się że pokopałem x z y ale dla celów poglądowych powinien wystarczyć i dla danych daje prawidłowy wynik 45 #include <iostream> using namespace std; int main() { int tab[ 4 ][ 4 ] = { { 0, 1, 9, 9 }, { 5, 3, 8, 1 }, { 1, 2, 9, 9 }, { 3, 1, 3, 9 } }; int pom[ 4 ][ 4 ]; for( int y = 0; y < 4; y++ ) { for( int x = 0; x < 4; x++ ) { pom[ x ][ y ] = 0; } } for( int y = 0; y < 4; y++ ) { for( int x = 0; x < 4; x++ ) { if( x < 3 ) { int nowa = pom[ x ][ y ] + tab[ x + 1 ][ y ]; if( nowa > pom[ x + 1 ][ y ] ) pom[ x + 1 ][ y ] = nowa; } if( y < 3 ) { int nowa = pom[ x ][ y ] + tab[ x ][ y + 1 ]; if( nowa > pom[ x ][ y + 1 ] ) pom[ x ][ y + 1 ] = nowa; } } } cout << pom[ 3 ][ 3 ] << endl; } |
|
mateczek |
» 2016-01-31 04:29:31 poprawiony kod z uporządkowanymi osiami !!! + szukanie drogi #include <iostream> #include <string> #include <stack> using namespace std;
int main() { int tab[ 4 ][ 4 ] = { { 0, 1, 9, 9 }, { 5, 3, 8, 1 }, { 1, 2, 9, 9 }, { 3, 1, 3, 9 } }; int pom[ 4 ][ 4 ]; for( int y = 0; y < 4; y++ ) { for( int x = 0; x < 4; x++ ) { pom[ y ][ x ] = 0; } } for( int y = 0; y < 4; y++ ) { for( int x = 0; x < 4; x++ ) { if( x < 3 ) { int nowa = pom[ y ][ x ] + tab[ y ][ x + 1 ]; if( nowa > pom[ y ][ x + 1 ] ) pom[ y ][ x + 1 ] = nowa; } if( y < 3 ) { int nowa = pom[ y ][ x ] + tab[ y + 1 ][ x ]; if( nowa > pom[ y + 1 ][ x ] ) pom[ y + 1 ][ x ] = nowa; } } } cout << pom[ 3 ][ 3 ] << endl; for( int y = 0; y < 4; y++ ) { for( int x = 0; x < 4; x++ ) { cout << pom[ y ][ x ] << " "; } cout << endl; } stack < string > droga; int x = 3; int y = 3; while(( x > 0 ) &&( y > 0 ) ) { if( pom[ y ][ x - 1 ] > pom[ y - 1 ][ x ] ) { x--; droga.push( "right" ); } else { y--; droga.push( "down" ); } } while( x-- ) droga.push( "right" ); while( y-- ) droga.push( "down" ); while( !droga.empty() ) { cout << droga.top() << " "; droga.pop(); } cout << endl; } szukanie drogi rysunek http://zapodaj.net/images/de1d926c79e86.png |
|
« 1 » |