Drzewo decyzyjne dla szukania fałszywej monety

[Zelman]

Witam!

Mam takie zadanko:

Narysuj minimalne drzewo decyzyjne dla szukania 1 fałszywej monety spośród 5. Do dyspozycji waga szalkowa bez odważników

I nie wiem za bardzo jak to zrobić. Udało mi się znaleźć wersję dla 3 monet:


Z góry dzięki za pomoc

[Crizz]

Zakładam, że nie wiemy, czy moneta fałszywa jest lżejsza, czy cięższa.

Strategia jest następująca:

*oznaczasz monety przez \(\displaystyle{ 1,2,3,4,5}\)
*dzielisz monety na trzy grupy \(\displaystyle{ (1,2),(3,4),5}\)

Kod: Zaznacz cały

(1,2)?(3,4)
       -jeśli =, to 5
       -jeśli <, to 1?2
               -jeśli <, to 1
               -jeśli >, to 2
               -jeśli =, to 3?4
                          -jeśli <, to 4
                          -jeśli >, to 3
       -jeśli >, to 1?2
               -jeśli <, to 2
               -jeśli >, to 1
               -jeśli =, to 3?4
                          -jeśli <, to 3
                          -jeśli >, to 4

W ten sposób wykonujemy najwyżej trzy porównania, mniej raczej się nie da. Myślę, że z drzewem sobie poradzisz.