BlackDante Temat założony przez niniejszego użytkownika |
[C++] Backtracking » 2011-02-24 19:39:20 Hej, mam do napisania program, który na standardowym wejściu przyjmuje najpierw listę argumentów a następnie w każdej następnej lini przyjmuje jakiś dodatni, całkowity argument. np. na wyjściu ma pogrupować dane wejściowe na dwie równe grupy (o ile jest to możliwe), np. mam przy tym zastosować algorytm przeszukiwania z nawrotami, i tutaj zaczynają się schody... ponieważ mam sobie o taką funkcję: void bactracking( int rozmiar, int poczatek, int suma, int polowa, bool & koniec, int * tablica, bool * tab ) { if( suma == polowa ) { koniec = true; } else if( poczatek != rozmiar && !koniec ) { for( int i = poczatek; i < rozmiar && !koniec; i++ ) { suma = suma + tablica[ i ]; if( suma <= polowa ) { suma = suma + tablica[ i ]; tab[ i ] = true; bactracking( rozmiar, i + 1, suma, polowa, koniec, tablica, tab ); } else { suma = suma - tablica[ i ]; tab[ i ] = false; } } } } wywołuję ją tak: bactracking( ilosc, 1, liczby[ 0 ], polowa, warunek, liczby, tab );
gdzie ilość to rozmiar tablicy, suma to pierwszy element tablicy, polowa to połowa sumy elementów tablicy, warunek to zmienna bool zainicjalizowana na false, liczby to tablica pobranych argumentów, tab to tablica do przechowywania wyników tzw. tablica wartości false, true. Mój problem polega na tym że ta funkcja gubi się przy ilości argumentów powyżej 10 i pokazuję zły wynik, jak by ktoś mógł by mi pomóc to byłbym niezmiernie wdzięczny :) |
|
DejaVu |
» 2011-02-24 20:29:02 Może tablicę źródłową masz za małą? |
|
BlackDante Temat założony przez niniejszego użytkownika |
» 2011-02-24 21:33:29 otóż tablicę tworzę dynamicznie: int ilosc; cin >> ilosc; int liczby[ ilosc ]; int i = 0; while( i < ilosc ) { cin >> liczby[ i ]; i++; }
i mieści wszystkie elementy, problem polega na tym że np. dla wejścia: 13 99 58 55 44 44 39 26 22 16 13 12 10 2
|
wyświetla mi: 99 58 2 55 44 44 39 26 22 16 13 12 10
|
zamiast: 99 58 39 22 2 55 44 44 26 16 13 12 10
|
a przykład z tamtego postu działa mi znakomicie i sam już nie mam żadnego pomysłu... ;F |
|
malan |
» 2011-02-24 21:42:55 Dlaczego rozpoczynasz przeszukiwanie tablic od ich drugiego elementu? Pierwszy nie ma znaczenia? |
|
BlackDante Temat założony przez niniejszego użytkownika |
» 2011-02-24 21:52:04 Rozwiązanie dzieli się na dwie grupy, które łącznie dają wszystkie argumenty podane przez użytkownika więc pierwszy element zawsze będzie w jakiejś grupie, nie ma innej możliwości :) w zasadzie to można powiedzieć o każdym elemencie od którego zaczynamy poszukiwanie rozwiązania. |
|
malan |
» 2011-02-24 21:59:01 (...)więc pierwszy element zawsze będzie w jakiejś grupie(...) |
A co mi tam- raz się żyje. Założysz się, że Twój kod nie przydziela go do żadnej z grup? ;) /edit: W sumie to skoro widzisz go na wyjściu to jakoś go przydzielił... Ale, hm... Nie dziwi Cie, że w tych dwóch przykładach jest na pierwszym miejscu? ;) |
|
BlackDante Temat założony przez niniejszego użytkownika |
» 2011-02-24 22:11:05 Pierwszy element przydzielam jeszcze w programie głównym, a kolejność elementów jest bez znaczenia bo są one przeze mnie sortowane w tablicy a następnie tablica jest odwracana tak aby największy element był na samym początku (za pomocą funkcji sort i reserve z biblioteki algorithm) |
|
malan |
» 2011-02-24 22:16:09 Aaa, czyli w wywołaniu bactracking( ilosc, 1, liczby[ 0 ], polowa, warunek, liczby, tab ); drugi argument (równy jeden) jest tutaj poprawny? Uczepiłem się tego, bo zobaczyłem, że po prostu rozpoczynasz przeszukiwanie od 1, a nie 0: void bactracking( int rozmiar, int poczatek, int suma, int polowa, bool & koniec, int * tablica, bool * tab ) { for( int i = poczatek; i < rozmiar && !koniec; i++ )
...i wydało mi się to dziwne ;p. |
|
« 1 » 2 |