Witam forumowiczów. Na Waszym forum znalazłem wrzucony przez kolegę [alex]'a (klik ->) algorytm do “problemu podziału”.
Siedziałem nad tym dość długo, jednak nadal nie rozgryzłem sposobu, w jaki można to zaprogramować. Poprzez funkcję rekurencyjną? A może iteracyjnie? Nie proszę o kod, byłbym z góry wdzięczny za jakiekolwiek wskazówki.
Pozdrawiam!
Przecież matzu dał kod do c#, czego dokładnie nie rozumiesz ?
Przepisałem kod matzu na C++ i niestety nie działa tak, jak powinien:
bool bt(int n, int *tab, int *wynik, int k, int suma, int szukana)
{
bool goFurther = true;
suma += tab[k];
wynik[k] = true;
if(suma == szukana)
{
return true; //jezeli znalezlismy odpowiednia sume to konczymy rekurencje
} else if(suma > szukana)
{
goFurther = false;
}
if(goFurther)
{
for(int i=1; i< n; i++)
{
if(!wynik[i])
{
bt(n, tab, wynik, i, suma, szukana);
}
}
}
wynik[k] = false;
}
Nie rozumiem ostatniego if’a. Pętla przechodzi przez całą tablicę wyników, jeżeli trafi na fałsz to uruchamia rekurencję?
Niestety nie mam teraz dostępu do komputera, na którym jest ten program (i nie wiem kiedy będę miał), więc nie mogę uaktualnić linku, ale i tak w tym programie kluczowe były tylko te dwie metody. Wytłumaczę Ci po prostu o co chodzi, a Ty sobie to zaimplementuj w jakim języku chcesz 
Na początek jedna istotna uwaga … tablica przechowująca liczby otrzymane na wejściu musi zostać posortowana w porządku malejącym (od największej liczby do najmniejszej).
public void FindNumbers()
{
int searchedSum = NumbersSum / 2;
bool[] usedIndexes = new bool[Numbers.Length];
this.FindNumbers(0, 0, searchedSum, usedIndexes);
}
W metodzie void FindNumbers() inicjalizujesz sobie dwie zmienne lokalne: zmienna całkowita searchedSum -> przechowuje połowę sumy wszystkich liczb stanowiących wejście programu, czyli załóżmy na wejściu programu miałeś 12 liczb, ich suma to 240, czyli do tej zmiennej przypisujesz 120 tablica wartości logicznych usedIndexes -> przechowuje tyle elementów ile zostało podanych liczb na wejściu programu, czyli jeśli użytkownik podał 12 liczb, to tablica ma przechowywać 12 wartości logicznych. Tablica ta musi zostać zainicjalizowana wartościami false Następnie w tej metodzie wywołujesz metodę void FindNumbers(int currentIndex, int currentSum, int searchedSum, bool[] usedIndexes) i przekazujesz jako argumenty 0, 0, wartość zmiennej searchedSum oraz tablicę usedIndexes. Istotne jest to, że tablice w .NET przekazywane są przez referencję do metody i dlatego też w Swoim kodzie tablicę usedIndexes też musisz tak przekazywać.
private void FindNumbers(int currentIndex, int currentSum, int searchedSum, bool[] usedIndexes)
{
bool goFurther = true;
currentSum += Numbers[currentIndex];
usedIndexes[currentIndex] = true;
if (currentSum == searchedSum)
{
Results.Add(usedIndexes, Numbers);
goFurther = false;
}
else if (currentSum > searchedSum)
goFurther = false;
if (goFurther)
{
for (int i = 1; i < usedIndexes.Length; i++)
{
if (!usedIndexes[i])
this.FindNumbers(i, currentSum, searchedSum, usedIndexes);
}
}
usedIndexes[currentIndex] = false;
}
bool goFurther = true; Tworzysz lokalną zmienną logiczną goFurther i inicjalizujesz ją wartością true. 2. currentSum += Numbers[currentIndex]; Do zmiennej currentSum dodajesz liczbę umieszczoną pod indeksem currentIndex w tablicy przechowującej liczby, które program otrzymał na wejściu (może to być np. 12 liczb jak wspomniałem wyżej). currentSum oraz currentIndex to są zmienne przekazywane jako parametr metody. U mnie Numbers to było pole klasy, ale Ty możesz sobie po prostu dodać dodatkowy parametr do metody i tak przekazywać tą tablicę liczb. 3. usedIndexes[currentIndex] = true; Ustawiasz element o indeksie currentIndex w tablicy usedIndexes na true 4.
if (currentSum == searchedSum)
{
Results.Add(usedIndexes, Numbers);
goFurther = false;
}
else if (currentSum > searchedSum)
goFurther = false;
Tutaj wydaje mi się, że jedynie niejasna może być ta linijka: Results.Add(usedIndexes, Numbers); U mnie w kodzie Results to była klasa (kolekcja) przechowująca wyniki. Opiszę Ci co się dzieje w ramach metody void Add(bool[] usedIndexes, int[] numbers). Otóż jak już powiedziałem wielkość tablicy usedIndexes i tablicy numbers jest identyczna (przechowują tyle samo elementów). W ramach metody Add w pętli trzeba przejść po tablicy usedIndexes i jeśli dany element (o danym indeksie) ma wartość true to znaczy, że element z tablicy numbers znajdujący się pod tym samym indeksem musi zostać dodany do wynikowej tablicy. Rozmiar tej wynikowej tablicy jest nieznany, bowiem takich elementów o wartości true w tablicy usedIndexes może być różna ilość. Poza tym takich tablic wynikowych też może być dużo, jednak nie wiadomo ile dokładnie ich będzie (zależy to oczywiście od otrzymanych liczb na wejściu programu). Co więcej tablice wynikowe mogą się powtórzyć, dlatego musisz sprawdzać, czy dana tablica z wynikami już wystąpiła czy też nie (ale to możesz sobie zaimplementować na samym końcu, jak już wszystko pozostałe będziesz miał). 5.
if (goFurther)
{
for (int i = 1; i < usedIndexes.Length; i++)
{
if (!usedIndexes[i])
this.FindNumbers(i, currentSum, searchedSum, usedIndexes);
}
}
Tutaj wydaje mi się, że niejasne może być to:
!usedIndexes
Ten zapis oznacza, że jeśli element o indeksie i z tablicy usedIndexes jest równy false tzn, że całe wyrażenie umieszczone w if-ie ma być spełnione (prawdziwe)
this.FindNumbers(i, currentSum, searchedSum, usedIndexes);
To jest rekurencyjne wywołanie metody void FindNumbers(int currentIndex, int currentSum, int searchedSum, bool[] usedIndexes)
Jako parametry przekazujesz zmienną i, currentSum, searchedSum oraz tablicę usedIndexes.
6.
Ostatnim elementem kodu jest ustawienie flagi
usedIndexes[currentIndex] = false;
Czyli bierzesz element o indeksie currentIndex z tablicy usedIndexes i ustawiasz jego wartość na false.
To raczej tyle.
– Dodane 09.09.2011 (Pt) 15:12 –
Dodałem parę zmian w opisie Teraz jest już pełny.