Re: И снова колпаки - Gnu , 30.11.2004 16:11 MSK
	: : Задачу с двумя цветами колпаков все с легкостью решили, очевидно, решат и когда колпаки трех цветов... (ну, кто решит?) : : : : А вот если цветов произвольное количество? Требуется выяснить при каком соотношении мудрецов/колпаков можно применить стратегию, спасающую всех кроме быть может одного. : : : : : : И ремэйк исходной задачи: : : заключенные стоят друг за другом, видят только тех, кто стоит впереди и не видят тех, кто сзади... поочереди, начиная с конца называют цвет колпака... требуется спасти максимальное количество зэков. : Оценка задачи сверху: максимум помрут N зэков - по количеству цветов. (каждый сигнализирует о четности определенного цвета) : решение лучше: M = log_n (2^N) : они записывают число содержащее четности в n ичной системе счисления. : я не знаю оптимальный ли это вариант. : K'eth Hennia the Elven Bard Не оптимальняй. (Под исходной задачей я понимал задачу с двумя цветами.)
И снова колпаки - Gnu , 30.11.2004 15:35 MSK