Интересные задачи по программированию и логике 

bouchon писал(а) :Самое интересное, что некоторые могут решить эту задачу в голове, я не могу

Брось, Бушик. Это дело тренировки - десяток-другой-третий задач и будешь сноровисто в уме матричный перенос делать на ура

PS А если 14 умножить на 3, то получится.... Ответ На Главный Вопрос Жизни, Вселенной и Всего Такого

bouchon писал(а) :Самое интересное, что некоторые могут решить эту задачу в голове, я не могу
Ее как раз дают на интервью на работу с зарплатой $400к

ну обычно по зарплате и требования к соискателю.

Эрхафан писал :
Брось, Бушик. Это дело тренировки - десяток-другой-третий задач и будешь сноровисто в уме матричный перенос делать на ура

PS А если 14 умножить на 3, то получится.... 42

Тут хуже, я читал решение и не понял. Там какие то рассуждения с этими мартингейлами, никаких формул, потом бац, поэтому ответ 14. У нас на тервере не было мартингейлов, я тут на пару лекций сходил, ничего не понял кроме того что можно круто угадывать ответы в таких статистических задачах.

[внешняя ссылка]


Оoo, в русском это так [внешняя ссылка]

Эрхафан писал : Предлагаю усложнить задачку с шарами до поисков алгоритма для числа шаров b (варьирующегося между 1 и числом этажей )

А затем решить задачу: сколько шаров таки необходимо и достаточно. Очевидно ж, что существует такое количество шаров, которое уже избыточно для решения данной задачи, но ещё помещается в интервале до N (N - число этажей).

/Мечтательно ковыряюсь в носу: от это таки задача!/
==========

Предлагаю наиболее ясномыслящему (тут придётся уже голосовать) из нашего дружного коллектива оформить культурно эту задачку и кинуть её на [внешняя ссылка] (или как её там на сам деле) - нехай решат или подавятся. А затем воспользуемся (если решат) результатом. Это тоже алгоритм решения задачи, если что!
Рябина права!

Лохмастерье писал :
А затем решить задачу: сколько шаров таки необходимо и достаточно. Очевидно ж, что существует такое количество шаров, которое уже избыточно для решения данной задачи, но ещё помещается в интервале до N (N - число этажей).

Найти минимум от функции количества измерений b*(N^(1/b)) по b, это в точке b = ln(N)

GENA_DJ писал :Найти минимум от функции количества измерений b*(N^(1/b)) по b, это в точке b = ln(N)

Т.е. для 100 этажей это 5 шаров?

/Хотел уже послать Леди Юлию на [внешняя ссылка] - и чтобы по дороге спаржи занесла/

quote="bouchon" quote="Эрхафан"
Бушик, ну сколько раз повторять - N орлов подряд, N. Мы пишем универсальные "цЫклЫ" /quote

А ты в уме реши, это задача для телефонного интервью)



Я не смог ее в уме решить, более того я видел решение на полстраницы одного текста с рассуждениями, но не понял, так как не очень владею мартингейлами. Я решил ее своим способом через transfer matrix method, хотя это громоздко, зато дает точную функцию распределения и все моменты, а не просто среднее. /quote

Насколько я помню, правда очень смутно, никаких матриц для этого не требовалось. bouchon, Вас, чую, хотели развести.

Неконструктивно. Твой ответ?

GENA_DJ писал : Неконструктивно. Твой ответ?

По поводу необходимого и достаточного количества шаров?
Не знаю, не ковырялся, но вполне похоже на правду (+/- две трамвайные остановки). Всё ждал, когда же логарифмы всплывут.

Лохмастерье писал :
Насколько я помню, правда очень смутно, никаких матриц для этого не требовалось. bouchon, Вас, чую, хотели развести.

Для начала попробуй решить эту задачу аналитически ) Мартингейл это не матрица, а стохастический процесс. Суть в том что нужно придумать некий стохастический процесс связанный с исходной проблемой, который будет мартингейлом и тогда ответ сразу выписывается влет. Но я не владею этой техникой. То решение которое я привел полностью мое, я ничего другого не смог придумать кроме как адаптироватъ трансфер матрикс метод, который не является хорошо знакомым большинству математиков, но очень популярен среди физиков, в том числе и тех кто занимается компьютерными симуляциями.

другими словами использовать матрицы придумал я, там про них и слова не было, но если ты сможешь решить без матриц, я буду рад ознакомиться.

bouchon писал(а) :Для начала попробуй решить эту задачу аналитически )

2+4+8, чо там

Эрхафан писал :
2+4+8, чо там

Ок, сколько в среднем нужно кинуть монетку для того чтобы получить не 3, а 4 орла подряд?


О мне повезло, я нашел решение без матриц и мартингейлов для любого n )

bouchon писал(а) :

Эрхафан писал ... :
2+4+8, чо там

Ок, сколько в среднем нужно кинуть монетку для того чтобы получить не 3, а 4 орла подряд?


О мне повезло, я нашел решение без матриц и мартингейлов для любого n )

2**(n+1)-2?

Я так думаю, что для получения из 111 последовательности 1111 нужно иметь в среднем две попытки. То бишь 14+14+1+1=30 бросков

bouchon писал(а):

Лохмастерье писал ... :
Насколько я помню, правда очень смутно, никаких матриц для этого не требовалось. bouchon, Вас, чую, хотели развести.

<skipped>
другими словами использовать матрицы придумал я, там про них и слова не было, но если ты сможешь решить без матриц, я буду рад ознакомиться.

Не, какникулы закончились - ухожу в серые будни. Учебник по теор.вер. сам шукай