Re: продвинуться до K+1


Автор сообщения: Roger
Дата и время сообщения: 24 October 2004 at 11:18:15:

В ответ на сообщение: Re: продвинуться дальше в передаче полномочий

Буду осуществлять информационную поддержку проекта Jailhouse :)

Вот, опять же, сравнительная таблица. Первое число - размер шайки (N), второе - время отсидки с выбранным водилой, третье - модифицированный алгоритм, где водила определяется в третий день, четвёртое число - последний предложенный алгоритм (в скобках оптимальное К для данного N). Как и прежде, всё получено аналитически, К определяется перебором. Вообще-то я и для К нашел аналитическое условие, но для него всё-равно перебирать нужно. Надеюсь, я нигде не ошибся (немного смущает, что новый алгоритм работает хуже при N=4,5). Если кто желает, могу поделиться вычислениями и программой.

4 19.3 15.1 15.7(3)
5 30.4 24.2 24.3(3)
6 43.7 35.5 34.8(4)
7 59.1 49.0 46.9(4)
8 76.7 64.6 61.0(5)
9 96.5 82.3 76.7(5)
10 118.3 102.2 94.4(5)
11 142.2 124.1 113.8(6)
12 168.2 148.2 135.0(6)
13 196.3 174.3 158.0(7)
14 226.5 202.5 182.8(7)
15 258.8 232.7 209.5(7)
16 293.1 265.0 238.0(8)
17 329.5 299.4 268.3(8)
18 367.9 335.9 300.5(8)
19 408.4 374.4 334.4(9)
20 451.0 414.9 370.2(9)
21 495.6 457.5 407.9(9)
22 542.2 502.2 447.3(10)
23 590.9 548.8 488.6(10)
24 641.6 597.6 531.8(10)
25 694.4 648.4 576.8(11)
26 749.2 701.2 623.6(11)
27 806.1 756.0 672.4(11)
28 865.0 812.9 722.9(12)
29 925.9 871.9 775.3(12)
30 988.8 932.8 829.6(12)

Я считал, что если все K дней в карцере сидели разные разбойники, то водилой становится тот, кто попадает туда на K+1 день.

Неплохо бы ещё просчитать алгоритм, описанный в 38653.html, хотя бы монте-карло раскинуть.


1811. Mihael'ю еще одна задачка! - Заметил-Просто 11:14 21.10.04 (61)
К списку тем на странице