Comments 12
Эх, куры. Исходная задача может быть переформулирована в реальный мир так:
Есть рынок с конечным числом покупателей, есть некоторый товар, который покупатели случайным образом продают друг другу. Купивший сразу же убеждается, что товар ему не нужен (т.е. это ему «впарили» ненужный товар) и повторно ему уже продать этот товар не получится. Какое ожидаемое количество покупателей не купит в итоге товар?
И в такой формулировке легко понять, почему эта задачка так актуальна сегодня (см. качество ликвидности на финансовых рынках).
И вот ссылка на старинную статью Очкова про расчет финансовой пирамиды, один из графиков (тот, что с двумя пиками) удивительно похож на то, что в статье.
Есть рынок с конечным числом покупателей, есть некоторый товар, который покупатели случайным образом продают друг другу. Купивший сразу же убеждается, что товар ему не нужен (т.е. это ему «впарили» ненужный товар) и повторно ему уже продать этот товар не получится. Какое ожидаемое количество покупателей не купит в итоге товар?
И в такой формулировке легко понять, почему эта задачка так актуальна сегодня (см. качество ликвидности на финансовых рынках).
И вот ссылка на старинную статью Очкова про расчет финансовой пирамиды, один из графиков (тот, что с двумя пиками) удивительно похож на то, что в статье.
Когда летом читал оригинал, набросал симулякр на питоне, вдруг кому нужно поиграться пригодится…
Скрытый текст
REPEAT = 10000
DEBUG = False
CHICKS_CNT = 100
SIMULTANEOUS = True
ONCE = False
# --------------------------
import os
if DEBUG:
def debug(*args):
print(args[0] % args[1:])
else:
def debug(*args):
pass
try:
xrange
except NameError:
xrange = range
def get_rnd_01(length):
if isinstance(os.urandom(1)[0], int):
return (c & 1 for c in os.urandom(length))
return (ord(c) & 1 for c in os.urandom(length))
def it_peck(chicks, simultaneous=SIMULTANEOUS):
if simultaneous:
_pritbuf = list(chicks)
for i, p in enumerate(get_rnd_01(len(chicks))):
if simultaneous:
if _pritbuf[i] <= 0: continue
else:
if chicks[i] <= 0: continue
p = i + (1 if p else -1)
if p < 0: p = len(chicks) - 1
if p >= len(chicks): p = 0
debug(' %6r pecks %r', i, p)
chicks[p] -= 1
for i in xrange(len(chicks)):
if chicks[i] < 0: chicks[i] = 0
def stop_it(chicks):
for i in xrange(len(chicks)-1):
if chicks[i] and chicks[i+1]: return False
return False if chicks[len(chicks)-1] and chicks[0] else True
itn = 0
avg = 0
while itn < REPEAT:
chicks = [1]*CHICKS_CNT
debug('** %r) ...', itn)
while True:
debug(' ** %r) ** iter', itn)
it_peck(chicks)
if ONCE or stop_it(chicks): break
s = sum(chicks)
debug('** %r) = %r', itn, s)
avg += s
itn += 1
avg = float(avg) / REPEAT
print(avg)
У меня по другому получилось…
итерация 0) — 1. живых кур
итерация 1) — 1/4 живых кур, включительно: 1/16 живых кур парных
1/16 живых кур парных через N итераций останется половина = 1/32
итерация N) 1 = 3/4(одиночных кур)+1/4(парных кур)
N.1. 1/4*3/4 = 3/16, где 3/4 — одиночных кур
N.2. 1/4*1/4*1/2 =1/32, 1/4 — парных кур, 1/2 выживает в парном состязании
N.3. 3/16+1/32 = 7/32 итоговая выживаемость
сравнение итогов:
7/32 < 8/32(1/4 оригинальный ответ)
P.S.
предполагаю, что Люк Робитейл ни секунды не думал над ответом, а выбрал из один из предложенных.
конечно, я могу ошибаться в расчётах, но точно вижу, что оригинальные расчёты не учитывают возможность живых парных посте первой итерации
итерация 0) — 1. живых кур
итерация 1) — 1/4 живых кур, включительно: 1/16 живых кур парных
1/16 живых кур парных через N итераций останется половина = 1/32
итерация N) 1 = 3/4(одиночных кур)+1/4(парных кур)
N.1. 1/4*3/4 = 3/16, где 3/4 — одиночных кур
N.2. 1/4*1/4*1/2 =1/32, 1/4 — парных кур, 1/2 выживает в парном состязании
N.3. 3/16+1/32 = 7/32 итоговая выживаемость
сравнение итогов:
7/32 < 8/32(1/4 оригинальный ответ)
P.S.
предполагаю, что Люк Робитейл ни секунды не думал над ответом, а выбрал из один из предложенных.
конечно, я могу ошибаться в расчётах, но точно вижу, что оригинальные расчёты не учитывают возможность живых парных посте первой итерации
Мой вариант на Python 3:
import random
#chicken are represented as a [0, 1, 1, 0, ...] list
#0 for pecked, 1 for unpecked
#peck a random neighbor (if and where we can)
def peck(chicken, pecked_can_peck = True):
N = len(chicken)
ch = chicken[:]
for i in range(N):
if not pecked_can_peck and chicken[i] == 0: continue
left, right = i-1, (i+1)%N
who_to_peck = random.choice([left, right])
ch[who_to_peck] = 0
return ch
#check if there are still an opportunity to peck
def unpecked_adjacent_exist(chicken):
for i in range(len(chicken)):
if chicken[i-1] + chicken[i] == 2: return True
return False
#peck one time, return the number of survivors
def pecked_single(N):
chicken = [1]*N
chicken = peck(chicken)
return sum(chicken)
#peck iteratively while we can, then return the number of survivors
def pecked_iterative(N):
chicken = [1]*N
while unpecked_adjacent_exist(chicken):
chicken = peck(chicken, False)
return sum(chicken)
N_chicken = 100 #number of chicken
N_iter = 10000 #number of trials
survivors_single, survivors_iterative = 0, 0
for i in range(N_iter):
survivors_single += pecked_single(N_chicken)
survivors_iterative += pecked_iterative(N_chicken)
#averaged results
print(survivors_single/N_iter, survivors_iterative/N_iter)
Я так посчитал, незнаю правильно ли: минимальный процент выжившых = 0, максимальный = 1/3, оба варианта возможны но это крайтие точки, беру среднее = (0 + 1/3) / 2 = 1/6, т.е. результат = ~17
Function TaskOfHens(iHensCount)
numenator=0;
denominator=1;
N=iHensCount;
i=1;
prev=1;
while N>2 do
prev=prev*N/i;
numenator=numenator+i*prev;
N=N-3; i=i+1;
enddo;
N=iHensCount;
j=(numenator%4);
answer=numenator-j;
while N>2 do
answer=answer/4;
N=N-3;
enddo;
return answer+j/4;
EndFunction
iHensCount=99 Ответ -> 24,75
Я завидую упорству автора, а также владению им такого большого количества свободного времени)
Sign up to leave a comment.
Считаем кур, пока их не заклевали