Вижте пък аз какво измислих. Накратко идеята е следната:
Броят всички затворници. При първото си влизане в стаята всеки брои себе си за 1 човек. При следващите влизания затворниците си прехвърлят бройки. Някой затворник дава от своите бройки и сигнализира с лампата. Друг, влязъл след него, взема бройките му и ги добавя към своите, така че сумата на бройките на всички затворници остава равна на броя на влезлите. Който пръв събере 100, вика уво.
Сега подробностите:
Календарът се разделя на 7 фази: Ф0,Ф1,...,Ф6, които са с предварително зададени продължителности и в предварително определен ред. Всеки затворник поддържа личен брояч, като в началото броячите на всички са 0 с изключение на един (няма значение кой), който е 28 (за да се брои не до 100, а до 2^7=128). Затворниците записват броячите си в двоична бройна система. В която и фаза да влезе даден затворник за първи път в стаята, той увеличава брояча си с 1. Освен това всеки път, когато затворникът е в стаята, той се старае да се отърве от някоя по-младша единица в брояча си. Разрядът се избира според фазата: Ф0 съответства на бит 0 в брояча, Ф1 - на бит 1 и т.н. Ако например затворникът влезе в стаята през Ф3, той гледа, дали броячът му съдържа 1 в бит 3 (разрядът на осмиците).
Ако съответният бит е 0, затворникът не прави нищо.
Ако съответният бит е 1 и лампата не свети, затворникът я запалва и намалява брояча си (с 8 в случая), така че съответстващия на фазата бит да се нулира.
Ако съответният бит е 1 и лампата свети, затворникът я гаси и увеличава брояча си (с 8 в случая), при което въпросния бит пак се нулира.
Ако затворникът влезе в първия ден от някоя фаза и лампата свети, той безусловно увеличава брояча си с числото, съответстващо на предходната фаза.
Който пръв получи 128, обявява освобождаването.
Хубавото на алгоритъма е, че изисква всички да влязат по не повече от 7 пъти последователно (при йерархията на преброители числото е около 20). Лошото е, че трябва да се влиза в определена фаза.
Много е трудно да се направи оптимизация на разделянето по фази. Поиграх си малко на ръка, но тази работа явно изисква нещо повече. Най-добрият ми резултат е за следния график: Ф0=420,Ф1=270,Ф2=150,
Ф0=420,Ф1=470,Ф2=500,Ф3=560,Ф4=520,Ф5=510,Ф6=510,
Ф0=300,Ф1=350,Ф2=400,Ф3=510,Ф4=510,Ф5=510,Ф6=510,
и оттук нататък се редуват от Ф0 до Ф6, всички по 510 дни. Получават се средно 4680 дни до освобождаването - повече от решението на Поназнайващ, но предполагам, че една добра оптимизация би могла да намали съществено това време. Най-голяма е вероятността да излязат на 4330-я ден.
|