Znajdowanie lidera w przedziale!
Ostatnio zmodyfikowano 2014-06-08 21:21
Gahaalt Temat założony przez niniejszego użytkownika |
Znajdowanie lidera w przedziale! » 2014-06-08 20:41:52 Próbuję napisać prosty kodzik znajdowania lidera w wybranym przez użytkownika przedziale danej tablicy. Wygląda to tak: int lider( int tab[], int beg, int end )
{
int l, c = 1, licznik;
for( licznik = beg; licznik < end; licznik++ )
{
if( c == 0 ) { tab[ licznik ] = l; c++; }
else
if( tab[ licznik ] == l ) c++;
else c--;
licznik++;
}
if( c == 0 ) return 0;
else
{
c = 0;
for( licznik = beg - 1; licznik < end; licznik++ ) if( tab[ licznik ] == l ) c++;
if( c > end - beg + 1 ) return l;
}
}
int main()
{
int tab[] = { 3, 3, 4, 3, 1, 3 };
int beg, end;
cin >> beg >> end;
cout << lider( tab, beg, end );
}
Niestety program zwraca złą wartość. Działa na podstawie standardowego algorytmu wyszukiwania lidera w zbiorze. Ktoś wie w czym tkwi problem? Edit: Inkrementowałem wartość licznika, którą inkrementowała dodatkowo pętla for. Niezły błąd ;) Ale program wciąż nie działa.. Edit2: Tyle błędów to ja jeszcze nigdy nie natworzyłem. Wszystko już działa, wątpię żeby kogoś to interesowało. Błędy pewnie sami zauważycie, jakby ktoś chciał to mogę je wypisać. |
|
pekfos |
» 2014-06-08 20:58:22 | jakby ktoś chciał to mogę je wypisać. |
Jest coś mocniejszego, niż te nieszczęsne l? |
|
Gahaalt Temat założony przez niniejszego użytkownika |
» 2014-06-08 21:17:38 Błędy typowo składniowe. Nie nadałem początkowej wartości l. Przy końcowym sprawdzaniu czy liczba jest liderem, sprawdzałem czy licznik jest większy od (end-beg+1), kiedy powinno to być (end-beg+1)/2. Użyłem pętli for, która wykona powtórzenie nawet jeśli przedział będzie, np. od 2 do 2. Pętla while nadaje się w tym przypadku lepiej. W każdym razie po skorygowaniu problemu i małym rozszerzeniu programu pojawił się kolejny problem. Wprowadzam do programu tablicę (w moim przypadku 1 1 3 2 3 4 3), a program widzi ją dokładnie jako (1 1 3 2 1 4 1). Nie mam zielonego pojęcia dlaczego! kod: int lider( int tab[], int beg, int end )
{
int l = tab[ beg - 1 ], c = 1, licznik = beg;
while( licznik < end )
{
if( c == 0 ) { tab[ licznik ] = l; c++; }
else
if( tab[ licznik ] == l ) c++;
else c--;
licznik++;
}
if( c == 0 ) return 0;
else
{
c = 0;
licznik = beg - 1;
while( licznik < end ) { if( tab[ licznik ] == l ) c++; licznik++; }
if( c >( end - beg + 1 ) / 2 ) return l;
else return 0;
}
}
int main()
{
int n, m;
cin >> n;
cin >> m;
int tab[ n ];
for( int licz = 0; licz < n; licz++ ) { cin >> tab[ licz ]; }
int beg, end;
for( int licz = 0; licz < m; licz++ )
{
cin >> beg >> end;
cout << lider( tab, beg, end ) << "\n";
}
}
Problem był tylko chwilowy xD Nagle ustąpiło, a nic nie zmieniałem. Dlaczego dzieją się takie dziwactwa? |
|
pekfos |
» 2014-06-08 21:19:41 |
|
Gahaalt Temat założony przez niniejszego użytkownika |
» 2014-06-08 21:21:03 Oczywiście, powinno być odwrotnie!
Dziękuję :) |
|
| « 1 » |