|
Тема |
Re: Затворниците... [re: rovado] |
|
Автор | pe (Нерегистриран) | |
Публикувано | 13.10.05 16:33 |
|
|
баси това е гаден проблем. само да кажа че си изгубих времето. :) имам 2 малки оптимизации на решението на поназнайващ. първо лидерът да процедира и като специалист - така се спестява междинното предаване на известна информация. второ, в самото начало, да речем първите 20 дни, да се създаде една поредица от неповтарящи се затворници (в началото вероятността за повторение е малка), и първият повтарящ се да стане лидер (средната дължина ми излиза някъде 11 души).
ако никой не се е повторил, човекът на 20-ия ден става лидер. лампата е светната докато се стигне до повторение, а след това е загасена до 20-ия ден.
(има един детайл: ако някой човек предназначен за чист специалист се появи в поредицата, то този специалист после трябва да чака един сигнал в повече, защото лидерът ще е намалил намали своят брояч с колкото души той е отчел в поредицата. тези от поредицата няма да пращат сигнали, това е ясно. ако лидерът се окаже някой от предназначените за чисти специалисти, той трябва да брои и за двамата, и да очаква един сигнал от специалист по-малко.)
след 20-ия ден се процедира по другия алгоритъм.
тези две неща към решението на поназнайващ ми дадоха решение средно за 3500 дена.
друга забележка: намерете оптимална система за 3-ма затворника сред 97 ретранслатора. (слагам ги така за да не може да се използва знание за дните). излиза ми 283 дена средно. същото за 4,5,6 затворника...?
|
| |
|
|
|