Rozwiązując arkusze maturalne z informatyki natknąłem się na te zadanie(matura 2002):
Danych jest n przedmiotów o niewielkich gabarytach i różnych wagach. Jest też do
dyspozycji waga z dwiema szalkami, ale nie ma odważników. Kładąc na wadze przedmioty
a i b, za pomocą jednego ważenia można ustalić, który przedmiot jest lżejszy.
Zapisz algorytm, który wykonuje możliwie najmniej ważeń i podaj liczbę ważeń w tym algorytmie.
najbardziej punktowana odpowiedź to 3n/2-2
Teraz w czym tkwi mój problem:
idąc na łatwiznę(znajdywanie najmniejszej i największej oddzielnie) liczba ważeń to 2n-2
Jedyny sensowny algorytm na jaki wpadłem wygląda tak, że wybieramy najlżejszy przedmiot i po kolei porównujemy, jeśli następuje zamiana, to wcześniejszy przedmiot nie jest dalej brana pod uwagę(pod warunkiem, że nie jest to pierwsze ważenie). Jeśli nastąpiło n-1 zamian, to od razu możemy wskazać najlżejszy i największy przedmiot(ustawione malejąco), więc w tym przypadku ważeń było n-1. Jeśli nie było żadnej zamiany( ustawione rosnąco), lub mniej niż n-1 to znajdujemy najcięższy przedmiot nie biorąc pod uwagę odrzucanych przedmiotów przy zamianie.
Więc w najbardziej sprzyjającym przypadku potrzebujemy n-1, a w najmniej 2n-3 ważeń. Ilość ważeń zależy od ustawienia liczb.
poza tym 3n/2-2 może być liczbą niecałkowitą(co jest przecież niemożliwe...)
Gdzie w moim rozumowaniu jest błąd?
Mam nadzieję, że w tym chaosie zrozumiecie sens 
.
