26.10.2004 03:51 Mike | Уточнение Предполагается, что нитка достаточно короткая и "край стола" - "граница полуплоскости на ножках"...
|
26.10.2004 03:59 Mike | Источник Задача хорошая и известная. Была на Московской олимпиаде пару лет назад... Но в графе автор там указано "фольклор". Наверное, какой-нибудь программист придумал...
|
26.10.2004 23:25 Загрей | А вот вообще обалденная задача. Мне ее пару лет назад рассказал Basilisk. Мужик без денег приезжает в отель и хочет заселиться на неделю. Есть у него золотая цепь из семи звеньев. Большая такая цепь, на шею не повесишь. Он предложил отдать цепь перед отъездом. Администратор не согласен. Отдавать цепь вперед невыгодно постояльцу. Администратор потребовал, что бы в конце каждого прожитого дня постоялец отдавал ему одно звено, причем в цепи допускается сделать только один распил (распилить одно звено). Как это сделать?
|
27.10.2004 01:17 Дата регистрации:
12 лет назад Посты: 96 | И это давно известно... 1) Распилить третье звено и отдать его. 2) Забрать одно, отдать два. 3) Отдать одно. 4) Забрать одно и два, отдать четыре. И т.д.
|
27.10.2004 15:28 Дата регистрации:
12 лет назад Посты: 134 | какой-нибудь программист Цитата
Наверное, какой-нибудь программист придумал...
Мне задача немного напомнила вот такую "программистскую" задачу. Вася играет в такую игру. Зайдя на произвольный сайт в Интернет, он переходит дальше по первой попавшейся ссылке, затем дальше и т.п. Суть игры в том, чтобы зациклиться и понять это. Только вот браузер и Васи примитивный, может запоминать только один выбранный Васей адрес. Как он должен действовать?
|
27.10.2004 15:39 пианист | Вася должен записывать адреса на бумажке. :))
|
27.10.2004 16:28 Игорь Абрамов | у Кнута похожая задача про цикл в последовательности Ответ знаю, но не скажу :)
|
27.10.2004 19:50 Дата регистрации:
11 лет назад Посты: 183 | так цепь не замкнута? :) Я устроил себе пятиминутное зависание, безуспешно пытаясь решить задачу для замкнутой цепочки. Воистину: не можешь решить задачу - измени условие. :)
|
27.10.2004 20:00 Дата регистрации:
11 лет назад Посты: 183 | есть гипотеза Один способ сразу приходит в голову. Если действовать по этому способу и первый цикл возникает не сразу (например, 46-й элемент равен 47-му), то мы узнаем об этом нескоро (ходов через 8). Легко видоизменять этот способ, но при этом может увеличиться число лишних сравнений или увеличиться запаздывание (цикл обнаруживается не сразу). В любом случае, я не вижу способа, который работает без запаздывания (как и в задаче с заключенными и лампочкой).
|
27.10.2004 20:15 Игорь Абрамов | не очень понял, но ... Действительно, цикл обнаруживается отнюдь не сразу. (И можно показать, что сразу при такой дырявой памяти и не поймаешь.) Метод на самом деле используется Кнутом при определении циклов псевдослучайных последовательностей, и там это все равно. А еще он используется в некоторых файловых системах, где цикл является ошибкой, и если уж мы туда вляпялись, дело все равно плохо.
|
27.10.2004 20:19 Игорь Абрамов | мне вот запомнилась такая: Вроде как вступительный в вечернюю школу при экономфаке, была напачатана в Кванте: Беспризорник может из трех окурков сделать одну папиросу. У него 6 окурков, сколько папирос он может выкурить ? Решение, правда не совсем математическое, скорее, экономическое :)
|
27.10.2004 20:23 Игорь Абрамов | оценка там вроде получается 2(x+y) где x --- число шагов до входа в цикл и у --- число шагов в цикле.
|
31.10.2004 21:32 Игорь Абрамов | решение: Сначала, из 6 окурков сооружается две папиросы и они выкуриваются. Образуется два окурка. Затем, беспризорник одалживает один окурок у другого беаспризорника ! Сооружает еще одну папиросу, выкуривает, и отдает оставшийся окурок обратно. Итого: 3
|
31.10.2004 22:16 Дата регистрации:
11 лет назад Посты: 183 | великолепно :) Папиросы я представлял себе в виде беломорных, в которых содержимое можно выкурить полностью, так что мысль об остатках папирос в голову даже не приходила. :) Прием с "одалживанием" немножко напоминает знаменитую задачку (я прочитал ее в сборнике "Физики шутят") о рыбаках, которые по очереди делили улов на три равные части, каждый раз выбрасывая остаток 1 (сначала первый рыбак выбросил одну рыбу и взял третью часть того, что осталось; потом то же самое сделал второй и третий). Спрашивается наименьшее число рыб. Дирак дал такое решение: " рыб было -2".
|
