Menihi

Naloga

mamo n menihov, ki so cel dan vsak v svoji celici, le enkrat na dan se srečajo v jedilnici. Med menihi ni komunikacije. Nenadoma se v samostanu pojavi bolezen, ki se kaže kot pika na čelu. Zato se menihi odločijo: kdor ima piko, naj zapusti samostan. Za število obolelih c velja: 0 < c < n, kjer je n število vseh menihov v samostanu.

Rešitev

Pogoj: vsi menihi uporabijo ta algoritem. Velja: vsak, ki pride v jedilnico vidi k pik:

• k = c -> nimam pike
• k = c – 1 -> imam piko

Menihi štejejo dneve: vsak šteje toliko dni, kolikor je k. Če so po preštetju k dni še vedno vsi menihi v samostanu - imam piko in moram zapustiti samostan. Če pa po k dni v samostanu ni nikogar več s piko, potem nimam pike in lahko ostanem.