Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

[C++] Backtracking

Ostatnio zmodyfikowano 2011-02-24 22:24
Autor Wiadomość
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.
Wejście:
6
13
1
3
5
4
8
 na wyjściu ma pogrupować dane wejściowe na dwie równe grupy (o ile jest to możliwe), np.
Wyjście:
13 4
8 5 3 1
mam przy tym zastosować algorytm przeszukiwania z nawrotami, i tutaj zaczynają się schody... ponieważ mam sobie o taką funkcję:
C/C++
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:

C/C++
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 :)
P-28566
DejaVu
» 2011-02-24 20:29:02
Może tablicę źródłową masz za małą?
P-28574
BlackDante
Temat założony przez niniejszego użytkownika
» 2011-02-24 21:33:29
otóż tablicę tworzę dynamicznie:
C/C++
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
P-28575
malan
» 2011-02-24 21:42:55
Dlaczego rozpoczynasz przeszukiwanie tablic od ich drugiego elementu? Pierwszy nie ma znaczenia?
P-28576
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.  
P-28577
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? ;)
P-28579
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)
P-28585
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:
C/C++
void bactracking( int rozmiar, int poczatek, int suma, int polowa, bool & koniec, int * tablica, bool * tab )
{
    // Przy pierwszym wywołaniu @poczatek jest równy 1 (jeden)...
    for( int i = poczatek; i < rozmiar && !koniec; i++ )
    //...
...i wydało mi się to dziwne ;p.
P-28586
« 1 » 2
  Strona 1 z 2 Następna strona