Sortowanie przez scalanie - Problem ze zrozumieniem.
Ostatnio zmodyfikowano 2013-12-29 20:28
masa... Temat założony przez niniejszego użytkownika |
Sortowanie przez scalanie - Problem ze zrozumieniem. » 2013-12-29 11:33:30 Witam. Zdaje w tym roku maturę z infy(ROZ). I przerabiam sobię o ten algorytm: #include <iostream>
#include <cstdlib>
using namespace std;
const int N = 5;
int d[ N ] = { 5, 4, 2, 9, 1 };
int p[ N ];
void MergeSort( int i_p, int i_k )
{
int i_s, i1, i2, i;
i_s =( i_p + i_k + 1 ) / 2;
if( i_s - i_p > 1 ) MergeSort( i_p, i_s - 1 );
if( i_k - i_s > 0 ) MergeSort( i_s, i_k );
i1 = i_p; i2 = i_s;
for( i = i_p; i <= i_k; i++ )
p[ i ] =(( i1 == i_s ) ||(( i2 <= i_k ) &&( d[ i1 ] > d[ i2 ] ) ) ) ? d[ i2++ ]
: d[ i1++ ];
for( i = i_p; i <= i_k; i++ ) d[ i ] = p[ i ];
}
int main( int argc, char ** argv ) {
MergeSort( 0, N - 1 );
for( int k = 0; k < N; k++ )
cout << d[ k ] << " ";
return 0;
}
Nie rozumiem dokładnie tej części : if( i_s - i_p > 1 ) MergeSort( i_p, i_s - 1 );
if( i_k - i_s > 0 ) MergeSort( i_s, i_k );
W debugerze na drugim przejściu funkcji i_p=0,i_k=4,p[]={4,5,0,0,0},d[] = {4,5,2,9,1}. W tym wypadku i_s-i_p jest wieksze od jeden. W jaki sposób przechodzi mi tak funckja do ifa niżej.Nie rozumiem tego. Jeżeli ktoś by mi to prostu wytłumaczyć (Jeżeli się da) bd wdzieczny. Ogólnie wiem o co chodzi w rekurencji. Ale tu jest dla mnie troche nie zrozumiała. [/i] Edit: Nadmienie, że ogólnie nadtym już z 3h siedzę. [/i] |
|
pekfos |
» 2013-12-29 15:44:27 | W jaki sposób przechodzi mi tak funckja do ifa niżej.Nie rozumiem tego. |
Tak samo, jakby zamiast wywołania było tam cokolwiek innego. | Nadmienie, że ogólnie nadtym już z 3h siedzę. |
Co to ma na celu? I tak, na 90%, nie siedzisz nad tym więcej niż pół godziny. |
|
masa... Temat założony przez niniejszego użytkownika |
» 2013-12-29 20:28:46 Ja siędze na tym ogólnie rzecz biorąc to pół dnia. Na zrozumienie tego nakierował mnie temat z wieżami Hanoi http://cpp0x.pl/forum/temat/?id=13131&p=2\Nie rozumiałem rekurencji do końca. Bardzo mi pomógł post autora pekfos. #include <iostream>
void f( int a )
{
if( a > 0 )
{
std::cout << a << std::endl;
f( a - 1 );
std::cout << a << std::endl;
}
}
int main()
{
f( 5 );
}
oraz przykład z symfonii (rozdział 5.12). Na zrozumieniu tego. |
|
| « 1 » |