?

Log in

No account? Create an account

Задачка - Общество дровосеков Бердичева по изучению Мишны

Aug. 4th, 2009

05:01 pm - Задачка

Previous Entry Share Next Entry



Абстрагируясь от предметной области:

Даны N > 0, K > 0. Массив чисел размером 2N первоначально содержит нули. Далее, пока в массиве осталось не менее 2 элементов, меньших K, из них выбираются 2 случайных (или, если осталось ровно 2, то не очень случайных), и к обоим прибавляется 1.

Найти ожидаемое количество итераций цикла.

Бонус: восстановить формулировку в терминах исходной предметной области.

Tags:

Comments:

[User Picture]
From:juan_gandhi
Date:August 5th, 2009 01:19 am (UTC)
(Link)
Кроме обычной комбинаторики из Кнута я как-то не заметил ничего выдающегося.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 5th, 2009 01:36 am (UTC)
(Link)
В задаче как таковой, пожалуй, ничего выдающегося нет, но результат оказался для меня несколько неожиданным.
(Reply) (Parent) (Thread)
[User Picture]
From:raindog_2
Date:August 5th, 2009 07:43 am (UTC)
(Link)
Наверное, не понял условия. Получится же что каждое число дойдет до К и "остановится", поэтому число итераций всегда равно K*N. В чем подвох?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 5th, 2009 07:51 am (UTC)
(Link)
В любом случае, отличном от тривиального, это не так:
N = 2, K = 2
0 0 0 0
1 1 0 0
2 1 1 0
2 2 2 0
Приехали.
(Reply) (Parent) (Thread)
[User Picture]
From:stas
Date:August 5th, 2009 06:15 pm (UTC)
(Link)
может быть от К*N до [K*(2N-1)/2] в зависимости от значения "последнего могиканина".
(Reply) (Parent) (Thread)
[User Picture]
From:syarzhuk
Date:August 27th, 2009 08:41 pm (UTC)
(Link)
восстановить формулировку в терминах исходной предметной области
А вот это как раз интересно
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 27th, 2009 08:48 pm (UTC)
(Link)
Хинт: носки.
(Reply) (Parent) (Thread)
[User Picture]
From:syarzhuk
Date:August 28th, 2009 01:44 pm (UTC)
(Link)
Типа - на сколько дней хватит N пар носков, если каждый день брать два более-менее подходящих (разница в цвете не больше K по какой-то шкале)?
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:August 28th, 2009 02:05 pm (UTC)
(Link)
Почти. За сколько дней они износятся.
(Reply) (Parent) (Thread)