Witam. Muszę napisać algorytm, który w std wejściu dostaje z liczb, i musi na std wyjściu wyświetlić te liczby podzielone na dwie równe połowy, np. dostaję liczby:
13
99
58
55
44
44
39
26
22
16
13
12
10
2, a na wyjściu:
99 58 39 22 2 oraz
55 44 44 26 16 13 12 10
Jeśli masz jakiś problem to może pokażesz kod, który już napisałeś? Opiszesz z czym masz problem, a nie tylko co chcesz osiągnąć.
Napisz co masz zrobić w sytuacji, gdy suma tych liczb wejściowych nie jest liczbą parzystą (a więc nie jest podzielna przez 2). Z tego co widzę w tym przykładzie zignorowałeś jedno 13, ale dlaczego akurat 13?
Załóżmy, że suma liczb wejściowych jest parzysta, ale z żadnej kombinacji tych liczb nie da się uzyskać takiej sumy, która będzie równa połowie sumy całkowitej. Co w takiej sytuacji należy zrobić?
Czy masz wyświetlić wszystkie możliwe kombinacje liczb, czy też wystarczy tylko jedna? Tzn. w tym przykładzie poprawnym wynikiem jest też np.
26, 12, 10, 2, 13, 99, 58
oraz
55, 44, 44, 39, 22, 16
Przynajmniej tak mi zwrócił program. Chyba, że czegoś nie rozumiem i chodzi tu o coś zupełnie innego.
Jeżeli suma nieparzysta lub największy element większy niż polowa sumy to już nić się nie zrobi.
Sortujesz listę nierosnąco tb[].
Obliczasz połowę sumy P.
Ustawiasz aktualną sumę S na 0.
Ustawiasz aktualny indeks I na 0.
Jeżeli S+tb[I]==P to zaznaczamy tb[I] i mamy rozwiązanie gotowe, koniec
Jeżeli S+tb[I]
Jeżeli I poza zakresem to rozwiązanie nie istnieje i koniec, jeżeli nie jest poza zakresem to przejdź do 6
Znajdź zaznaczone tb[K] o największym K, odznacz go ustaw I na wartość K+1, przejdź do 6.
Mógłbyś ALEX albo Matzu zrzucić kod do tego algorytmu bo nie bardzo rozumiem przykład?
Dzięki za odp.
To te zaznaczanie wpisać do tablicy bool’owskiej i później w pętli sobie sprawdzań od ostatniego elementu który (pierwszy)element ma 1 odznaczam go i aktualny indeks zwiększam o ta liczbe+1 ?!
I wynik sobie odczytuje z tej tablicy bool ?!
Można to zrobić na wiele sposobów.
Osobna tablica bool
Zaznaczone liczby zrobić ujemnymi.
Wszystkie liczby pomnożyć przez dwa (liczba<<=1) w młodszym bicie trzymać zaznaczenie.
I tp.
W ramach treningu napisałem sobie ten programik w C#. Poniżej zamieszczam exe (do jego uruchomienia konieczne jest zainstalowanie .NET Framework 4 na komputerze). W programie można wybierać, czy chce się szukać tylko jedno rozwiązanie, czy też wszystkie możliwe. Wyszukiwanie jednego rozwiązania jest w miarę szybkie. Natomiast wyszukiwanie wszystkich możliwych rozwiązań w sytuacji, gdy jest więcej niż 12 liczb wejściowych trwa już zdecydowanie za długo. Próbowałem poprawić ten kod, aby przyspieszyć cały proces, ale na razie bezskutecznie. Jakbyś ktoś miał jakiś pomysł, co można zmienić to chętnie posłucham. Poniżej zamieszczam kod kluczowej funkcji.
http://rapidshare.com/files/450333807/Calculator.zip
public List Numbers
{
get { return numbers; }
}
...
public void FindNumbers(bool findOneSolution)
{
this.ResetVariables();
if (NumbersSum % 2 != 0)
throw new Exception("Suma podanych liczb wynosi " + NumbersSum.ToString() + ", a więc nie jest liczbą parzystą.");
startTime = DateTime.Now;
this.FindNumbers(new HashSet(), 0, 0, NumbersSum / 2, findOneSolution);
stopTime = DateTime.Now;
}
private void FindNumbers(HashSet numbersKeys, int numbersAdded, int sum, int numbersHalfOfTheSum, bool findOneSolution)
{
if (numbersAdded == Numbers.Count || (findOneSolution && Results.Count > 0))
return;
for (int i = 0; i < Numbers.Count; i++)
{
if (!numbersKeys.Contains(i))
{
int sumCopy = sum + Numbers[i];
HashSet numbersKeysCopy = numbersKeys.Clone();
numbersKeysCopy.Add(i);
if (sumCopy == numbersHalfOfTheSum && !(findOneSolution && Results.Count > 0))
{
int index = Results.AddResultItem(numbersKeysCopy, Numbers);
if (index != -1)
{
this.OnResultFound(this, new EventArgs());
return;
}
}
else if (sumCopy < numbersHalfOfTheSum)
this.FindNumbers(numbersKeysCopy, numbersAdded + 1, sumCopy, numbersHalfOfTheSum, findOneSolution);
}
}
}
PS 1) Jak ktoś bardzo będzie chciał to wrzucę cały kod.
PS 2) Dla liczb podanych w przykładzie (99 58 55 44 44 39 26 22 16 13 12 10 2) wynik otrzymałem w czasie 00:03:38.3784906 na laptopie sprzed dwóch lat. Otrzymałem takie wyniki:
2 10 12 13 16 26 39 44 58 ; 22 44 55 99
2 10 12 13 26 44 55 58 ; 16 22 39 44 99
2 10 12 13 26 58 99 ; 16 22 39 44 44 55
2 10 12 16 26 55 99 ; 13 22 39 44 44 58
2 10 12 39 44 55 58 ; 13 16 22 26 44 99
2 10 12 39 58 99 ; 13 16 22 26 44 44 55
2 10 13 16 22 44 55 58 ; 12 26 39 44 99
2 10 13 16 22 58 99 ; 12 26 39 44 44 55
2 10 26 39 44 44 55 ; 12 13 16 22 58 99
2 10 26 39 44 99 ; 12 13 16 22 44 55 58
2 12 13 39 55 99 ; 10 16 22 26 44 44 58
2 13 16 22 26 39 44 58 ; 10 12 44 55 99
2 13 22 26 44 55 58 ; 10 12 16 39 44 99
2 13 22 26 58 99 ; 10 12 16 39 44 44 55
2 16 22 26 55 99 ; 10 12 13 39 44 44 58
2 22 39 44 55 58 ; 10 12 13 16 26 44 99
2 22 39 58 99 ; 10 12 13 16 26 44 44 55
matzu , gdyby przeczytałeś ten mój algorytm i na jego podstawie zrealizowałeś kod to wynik dla 13 liczb obliczał by wszystkie warianty w niecałą milisekundę.
@ [alex]
Próbowałem sam z tym powalczyć 
Może ostatecznie użyję tego Twojego rozwiązania, ale na razie po kolei sprawdzam swoje pomysły i patrzę co jest nie tak. Udało mi się poprawić trochę ten mój kod i teraz na tym moim laptopie wynik dla wszystkich tych liczb podanych przez autora tematu dostaję w niecałe 13 sekund. Nie jest to wprawdzie jedna milisekunda, ale progress jest. Poprawiłem też trochę GUI programu.
http://rapidshare.com/files/450623136/Calculator.zip
public void FindNumbers()
{
startTime = DateTime.Now;
this.ResetVariables();
int searchedSum = NumbersSum / 2;
bool[] usedIndexes = new bool[Numbers.Length];
int percentComplete = 0;
for (int i = 0; i < Numbers.Length; i++)
{
FindNumbers(i, 0, searchedSum, usedIndexes);
percentComplete = (int)(((float)((i + 1) * 2) / (float)(Numbers.Length * 2)) * 100);
this.OnProgressChanged(this, new ProgressChangedEventArgs(percentComplete));
}
stopTime = DateTime.Now;
}
public void FindNumbers(int currentIndex, int currentSum, int searchedSum, bool[] usedIndexes)
{
bool goFurther = true;
currentSum += Numbers[currentIndex];
usedIndexes[currentIndex] = true;
if (currentSum == searchedSum)
{
Results.AddResultItem(usedIndexes, Numbers);
goFurther = false;
}
else if (currentSum > searchedSum)
goFurther = false;
if (goFurther)
{
for (int i = 0; i < usedIndexes.Length; i++)
{
if (!usedIndexes[i])
this.FindNumbers(i, currentSum, searchedSum, usedIndexes);
}
}
usedIndexes[currentIndex] = false;
}
Problem polega na tym, że nie wiem jeszcze jak zabezpieczyć się przed sprawdzaniem tego samego rozwiązania. Załóżmy, że jest tablica trzech liczb, co daje 3! wszystkich możliwych kombinacji. Przy czym tylko 3 z nich powinny być sprawdzane, tj.
012
021
102
bo pozostałe trzy tj.
120
201
210
to są już niejako kopie trzech poprzednich. W tym momencie sprawdza mi wszystkie możliwe kombinacje, tzn. wszystkie gałęzie drzewa i dopiero w odpowiedniej metodzie (AddResultItem) sprawdzam, czy takie rozwiązanie już zostało znalezione, czy też nie. Gdybym nie musiał wykonywać tego sprawdzania oraz nie musiał przeszukiwać niepotrzebnych gałęzi to powinienem zyskać kolejne kilka sekund. Tak, czy siak zamieściłem kod i program może się komuś przyda.
Powinieneś sprawdzić nie te kombinacje co wypisałeś, zaś 3 następujące kombinacji:
0
0+1
0+2
jeżeli żadna z nich nie daje dokładnie polowy to niema rozwiązania.
Dla 4ch liczb będzie to od 3ch do 4ch następujące kombinacji, ty zaś sprawdzasz 24 kombinacji:
0
0+1
0+1+2 (tą kombinacje nawet nie należy sprawdzać jeżeli 0+1 jest większa niż polowa)
0+2
Dla 5ciu liczb będzie to od 4ch do 7iu następujących kombinacji, ty zaś sprawdzasz 120 kombinacji:
0
0+1
0+1+2 (pomijamy jeżeli 0+1 przekracza połowę)
0+1+2+3 (pomijamy jeżeli 0+1 lub 0+1+2 przekracza połowę)
0+2
0+2+3 (pomijamy jeżeli 0+2 przekracza połowę)
0+3
A w przypadku 13 liczb wejściowych, czyli tylu ile jest w przykładzie, to jakie będą kombinacje?
0
0+1+2+3+…+12 (po drodze jest sprawdzane 0+1, 0+1+2, 0+1+2+3, itd.)
0+2+…+12 (po drodze jest sprawdzane 0+2, 0+2+3, 0+2+3+4, itd.)
0+3+…+12
0+4+…+12
0+5+…+12
…
0+12
czy jeszcze jakieś? Bo jeśli tylko te to jak posortujemy te przykładowe 13 liczb malejąco to nie znajdzie żadnego rozwiązania.
Właśnie mają być posortowane nierosnąco.
Oczywiście opuściłeś kilka sprawdzeń:
np międzygminnymi będzie sprawdzenie:
0+1+3+4+…+12
czyli z pomięciem dwójki, a jest takich wele.
No faktycznie nieprecyzyjnie się wyraziłem. Liczby posortowałem nierosnąco, bo faktycznie 44 się powtarza. Zresztą czy bym posortował nierosnąco, czy niemalejąco to rozwiązanie bym nie dostał. A dlatego pominąłem część kombinacji, bo zasugerowałem się tym co napisałeś tutaj (wypisałem je sobie analogicznie):
np. tutaj nie sprawdzasz w ogóle 0+1+3. Teraz zresztą zauważyłem, że w ogóle tutaj nie uwzględniasz liczby o indeksie 4.
Masz racje coś mi się niepoprawnie wypisało dla 4’ch oraz 5’ciu liczb.
Właściwie to jak odpalisz ten algorytm co napisałem nieco wyżej to on wiele kombinacji pomija grupowo.
Powiedzmy jeżeli dodałeś elementy 0+1 i jest to więcej niż polowa to automatycznie wszystkie pozostałe kombinacji zawierające jedynkę już są pomijane, przechodzi od razu do kombinacji 0+2, no i następne.
OK, rozumiem. To by pasowało. W ten sposób rzeczywiście można znacznie zredukować ilość kombinacji do sprawdzenia. Niby takie oczywiste, a o tym nie pomyślałem /facepalm.
EDIT: Zmodyfikowałem trochę ten swój poprzedni kod uwzględniając częściowo to o czym mówiliśmy. Czas znalezienia wszystkich rozwiązań dla liczb z przykładu spadł do poniżej 90ms (na tym moim laptopie).
http://rapidshare.com/files/451295910/Calculator.zip
public void FindNumbers()
{
this.ResetVariables();
int searchedSum = NumbersSum / 2;
bool[] usedIndexes = new bool[Numbers.Length];
this.FindNumbers(0, 0, searchedSum, usedIndexes);
stopTime = DateTime.Now;
}
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);
if (currentIndex == 0)
{
int percentComplete = (int)(((float)(i * 2) / (float)((Numbers.Length - 1) * 2)) * 100);
this.OnProgressChanged(this, new ProgressChangedEventArgs(percentComplete));
}
}
}
}
usedIndexes[currentIndex] = false;
}
– Dodane 19.09.2011 (Pn) 18:40 – Z racji tego, że ostatnio na forum często pojawiały się tematy odnośnie tego problemu, dorzucam objaśnienie kodu oraz przykładową implementację w C.http://forum.dobreprogramy.pl/algorytm-problem-podzialu-t460903.html#p2915711
http://forum.dobreprogramy.pl/backtracking-t462021.html#p2921965
#include
#include
#include
int compareDescendingOrder(const void *x, const void *y)
{
return (*(int*)y - *(int*)x);
}
int calculateNumbersSum(int *numbers, int numbersCount)
{
int sum=0;
int i;
for(i=0; i
sum+=numbers[i];
return sum;
}
bool checkIfNumbersSolutionExists(int numbersCount, int *numbers, int *resultsCount, bool **results, bool** resultsTemporary, int **resultsNumbersTemporary)
{
bool numbersSolutionExists = false;
int i;
int j;
int k;
for (i=1; i<=*resultsCount; i++)
{
int offset = (i-1) * numbersCount;
numbersSolutionExists = true;
k = 0;
for(j=0; j
{
if((*resultsTemporary)[j])
{
if (numbers[j] != (*resultsNumbersTemporary)[offset + k])
{
numbersSolutionExists = false;
break;
}
else
k++;
}
}
if(numbersSolutionExists)
break;
}
return numbersSolutionExists;
}
void addNumbersSolution(int numbersCount, int *numbers, int *resultsCount, bool **results, bool** resultsTemporary, int **resultsNumbersTemporary)
{
*resultsCount += 1;
*results =(bool *) realloc(*results, *resultsCount * numbersCount * sizeof(bool));
*resultsNumbersTemporary =(int *) realloc(*resultsNumbersTemporary, *resultsCount * numbersCount * sizeof(int));
int i;
int k;
int offset = (*resultsCount-1) * numbersCount;
for(i=0, k=0; i
{
(*resultsNumbersTemporary)[offset + i] = 0;
(*results)[offset + i]=(*resultsTemporary)[i];
if((*resultsTemporary)[i])
{
(*resultsNumbersTemporary)[offset + k] = numbers[i];
k++;
}
}
}
void findAllNumbersSolutionHelper(int currentIndex, int currentSum, int searchedSum, int numbersCount, int *numbers, int *resultsCount, bool **results, bool** resultsTemporary, int **resultsNumbersTemporary)
{
bool goFurther = false;
currentSum += numbers[currentIndex];
(*resultsTemporary)[currentIndex] = true;
if (currentSum == searchedSum && !checkIfNumbersSolutionExists(numbersCount, numbers, resultsCount, results, resultsTemporary, resultsNumbersTemporary))
addNumbersSolution(numbersCount, numbers, resultsCount, results, resultsTemporary, resultsNumbersTemporary);
else if (currentSum < searchedSum)
goFurther = true;
if (goFurther)
{
int i;
for (i = 1; i < numbersCount; i++)
if (!(*resultsTemporary)[i])
findAllNumbersSolutionHelper(i, currentSum, searchedSum, numbersCount, numbers, resultsCount, results, resultsTemporary, resultsNumbersTemporary);
}
(*resultsTemporary)[currentIndex] = false;
}
void findAllNumbersSolution(int searchedSum, int numbersCount, int *numbers, int *resultsCount, bool **results)
{
bool *resultsTemporary;
resultsTemporary = (bool *) malloc(numbersCount*sizeof(bool));
int *resultsNumbersTemporary;
resultsNumbersTemporary = (int *) malloc(numbersCount*sizeof(int));
int i;
for(i=0; i
resultsTemporary[i] = false;
findAllNumbersSolutionHelper(0, 0, searchedSum, numbersCount, numbers, resultsCount, results, &resultsTemporary, &resultsNumbersTemporary);
free(resultsTemporary);
free(resultsNumbersTemporary);
}
int main()
{
int numbersCount;
// Get numbers count
scanf("%d",&numbersCount);
int *numbers;
numbers=(int *) malloc(numbersCount*sizeof(int));
// Get numbers
int i;
for(i=0; i
scanf("%d",&numbers[i]);
int numbersSum=calculateNumbersSum(numbers,numbersCount);
if( numbersSum%2 != 0 )
{
printf("Suma podanych liczb jest nieparzysta. Zadanie nie ma rozwiazania.");
free(numbers);
return 0;
}
qsort(numbers, numbersCount, sizeof(int), compareDescendingOrder);
if( numbers[0] > numbersSum/2)
{
printf("Najwieksza z liczb jest wieksza niz polowa sumy wszystkich podanych liczb. Zadanie nie ma rozwiazania.");
free(numbers);
return 0;
}
int resultsCount = 0;
bool *results;
results = (bool *) malloc(numbersCount*sizeof(bool));
findAllNumbersSolution(numbersSum / 2, numbersCount, numbers, &resultsCount, &results);
if (resultsCount > 0)
{
printf("Ilosc rozwiazan: %d \n",resultsCount);
for (i=1; i<=resultsCount; i++)
{
printf("---------------------------------------------------------\n");
int offset = (i-1) * numbersCount;
int j;
for(j=0; j
if (results[offset + j])
printf("%d ",numbers[j]);
printf("\n");
for(j=0; j
if (!results[offset + j])
printf("%d ",numbers[j]);
printf("\n");
}
}
else printf("Nie istnieje taka kombinacja liczb, ktorych suma jest rowna polowie sumy wszystkich podanych liczb. Zadanie nie ma rozwiazania.");
free(numbers);
free(results);
return 0;
}