 |
|
dla nominalow 1 10 11 wydanie kwoty 20 przez algorytm zachllanny daje falszywe rozwiazanie mimo, ze "każda możliwa do zadania kwota dzieli się przez któryś z dostępnych nominałów"
ps co to jest "możliwa do zadania kwota"?
Kbsc 16:43, 24 cze 2007 (CEST)
-
- Co rozumiesz przez fałszywe rozwiązanie...? Algorytm zachłanny, jak to się często bywa, daje wynik nieoptymalny (tu: wyznacza rozwiązanie z dziesięciu monet zamiast z dwu – 11 plus dziewięć razy 1 zamiast dwa razy 10), jednak wyda poprawną resztę. Gorzej, że przy pewnych układach danych może w ogóle nie znaleźć rozwiązania (przykład poniżej).
-
-
-
-
-
- zadanie brzmi: "wydać żądaną kwotę przy użyciu minimalnej liczby monet" wiec algorytm zachłanny nie daje rozwiązania.Kbsc
-
-
-
-
- Podejrzewam, że "możliwa do zadania kwota" to jest niezręcznie napisane "kwota wymaganej reszty, jaka może pojawić się na wejściu algorytmu wskutek zewnętrznych uwarunkowań". Np. jeśli automat przyjmuje tylko monety 2 i 10, sprzedaje "cos", i wszystkie "cosie" mają ceny parzyste, to reszta musi też być parzysta. Jeśli ceny są całkowite i przyjmowane monety takoż, to i reszta musi być całkowita. I autor twierdzi, że wystarczającym warunkiem rozwiązalności zadania jest, by każda taka kwota dzieliła się przez co najmniej jeden z dostępnych nominałów.
Ale w tym się myli. Nie wystarczy nawet podzielność przez najmniejszy dostępny nominał! Kontrprzykładem jest kwota 6 przy nominałach 2 i 5. Algorytm zachłanny wyda najpierw 5, po czym nie będzie w stanie wydać pozostałej jedności.
Najprostszym warunkiem, gwarantującym wykonalność zadania, jest by najmniejszy dostępny nominał był wspólnym dzielnikiem wszystkich możliwych kwot oraz dostępnych nominałów.
- CiaPan (Odp.) 20:27, 11 lip 2007 (CEST)
-
- ponadto sformulowanie problemu jest zle.
Kbsc 09:10, 12 lip 2007 (CEST)
-
-
-
- Dziękuję za wskazanie błędów i poprawki. Co rozumiesz jako "błędne sformułowanie problemu"? Chętnie poprawię. bryn (dyskusja) 14:13, 18 lip 2007 (CEST)
-
-
w standardowym problemie mamy zadane zbior nominalów .Monet kazdego nominalu jest dosc. a nie zbior monet.
Kbsc 18:25, 26 lip 2007 (CEST)
edytuj Dowód
Sugerowałbym też zamieszczenie szkicowych dowodów poprawności dla tych algorytmów... de2k 10:23, 8 kwi 2008 (CEST)
- Sugerowałbym powstrzymanie się przed umieszczaniem dowodów, a nawet ich szkiców. Nawet szczegółowe opisy algorytmów są moim zdaniem przesadą. No, chyba że w postaci osobnej strony, dopiętej *pod* zasadniczym artykułem – ale nie w artykule. Encyklopedia to nie podręcznik! --CiaPan (Odp.) 10:45, 9 kwi 2008 (CEST)