Тема: Логические загадки - 5

[Арвинд›]

Цитата из: Erlom-Tiu on 13-11-2003, 17:14:15
целая часть(N/(k-1))+1.

Не совсем - эта формула при делении нацело не туда округляет.

Короче, на все вопросы по людоедам правильно и первым ответил azyam, давайте дружно требовать от него задачу.

               

               

[Erlom-Tiu›]

это я уточнил решение azyam-a
(округление первоначально было, а потом потерялось)

ждём задачу!

               

               

[azyam›]

Есть 100-этажный дом и 2 стеклянных шарика (одинаковой прочности). Начиная с некоторого этажа шарики разбиваются. Надо за наименьшее число попыток определить этот самый этаж (или последний, с которого шарики еще не бьются). Оба шарика можно разбить, новых не выдают.

               

               

[Vantela›]

если я правильно понял залачу.......
то 14.......


ЗЫ если вдруг правильно
то я задачу не задаю..... их интереснее решать

ЗЫЫ с другой стороны решения я не приложил так что можно задаться  вопросом как это сделать за 14.....
впрочим так гораздо прощее....

               

               

[azyam›]

2Vantela
правильно
пусть другие пока подумают, как это можно сделать за 14, обычно говорят, что 20


а пока еще одна задача
Написать следующий ряд логической последовательности.
1
11
21
1211
111221
312211
13112221
1113213211


               

               

[Erlom-Tiu›]

Цитата из: azyam on 14-11-2003, 11:55:56
пусть другие пока подумают, как это можно сделать за 14, обычно говорят, что 20


я бы сказал 50, так что не знаю, что и думать
(одно утешает - это необычно)

в любом случае, меньше ~25 пока не видно

               

               

[Арвинд›]

Цитата из: azyam on 14-11-2003, 11:55:56
пусть другие пока подумают, как это можно сделать за 14

Буду думать вслух. Если идти самым очевидным путем, то надо минимизировать функцию (x-1) + 100/x, её минимальное значение при натуральных x <= 100 будет оценкой сверху.
Как вконец обленившийся человек, беру Excel. Получаю 19. Это больше 14. Значит, думаю дальше...

               

               

[Erlom-Tiu›]

14 так 14.
А теперь вопрос (с подвохом!):
как добиться меньшего числа сбрасываний

               

               

[azyam›]

2Арвинд думать лучше над алгоритмом

2Erlom-Tiu меньше чем 14?

оффтоп
а что такое рейтинг в колонке справа?

               

               

[Erlom-Tiu›]

да, меньше 14

[offtop - будет удалён]
Слева?
Рейтинг - неформальная мера уважения.
Ведутся споры, а также см. Служебное помещение.
Вожможность влиять на рейтинг даётся после N постов
(что на руку флудерам).
[/offtop]


               

               

[qui›]

Цитата из: Erlom-Tiu on 15-11-2003, 12:57:35
да, меньше 14



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

               

               

[Erlom-Tiu›]

Цитата:
За 13 бросаний этого сделать нельзя

Уточню:
можно за 12 бросаний, и, вероятно, даже меньше!
(подвох заключается в доп. физических предположениях и определённом прочтении условий задачи :-)

               

               

[Maeglor›]

Кажется я понял что ты имеешь в виду.
Но если предположить что шарик равновероятно разбивается на любом этаже и кроме разбивания/не разбивания никакой информации нет то меньше чем за 14 не удастся.
Я как ленивый человек решая эту задачу поосто накатал модель на с++ и прогнал ее по алгоритму поиска (не скажу какому). Логического решения я не нашел и признатся не искал, но подозреваю что это таже оптимизация процесса только вручную.
Кстати на Exele ее тоже можно смело решать.

               

               

[qui›]

Еще обобщение: та же задача (100 этажей), но количество доступных шариков неограничено (т.е., новые выдают).

За какое минимальное количество ходов можно решить задачу?

При условии, что количество ходов минимально, какое минимальное количество шариков понадобится?


               

               

[Erlom-Tiu›]

Цитата из: Maeglor on 16-11-2003, 00:51:19
... если предположить что шарик равновероятно разбивается на любом этаже и кроме разбивания/не разбивания никакой информации нет то меньше чем за 14 не удастся.

да...
действительно, меньше, чем за 14 падений/ударов не удастся.
А за 12 бросков (отпусканий шарика) - вполне.
Теперь очевидно? Тогда назовите этаж первого броска сброса.
(подсказка: дом-то ни много, ни мало, а сто-этажный)

Для бесконечного числа шариков:
задача сводится к классической игре.

               

               

[qui›]

Цитата из: Erlom-Tiu on 16-11-2003, 16:12:09
Для бесконечного числа шариков:
задача сводится к классической игре.



Не совсем.


               

               

[Maeglor›]

Для бесконечного количества, очевидно, золотым сечением 6 бросков.
Также как и при игре в угадывании числа.

               

               

[Арвинд›]

Ага. 14 несложно, действительно.

И если исходить из того, что единственно возможным действием является "скинуть шарик, проверить, разбился ли", то меньше нельзя.
В этих же предпосылках в задаче про бесконечное число шариков "6" - неправильный ответ.

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

Еще: мне не нравится последняя мода, когда решения к задачам не пишутся. Конечно, стоит погодить с решением, когда кто-то еще думает. Но подумайте, как наш диалог будет выглядеть для новичка: задается вопрос, кто-то отвечает "14", потом еще несколько человек соглашается "угу, 14", потом обсуждают другую задачу. Междусобойчик-с...
Давайте решать, как лучше.

               

               

[qui›]

Похоже, интерес к задаче иссяк.

6 бросаний даже с бесконечным числом шариков не хватит.
В задаче с неограниченным числом шариков более интересен второй вопрос:

При условии, что делается минимально возможное число бросаний, каким минимальным количеством шариков можно обойтись?

Есть общий метод, который позволяет быстро решить все приведенные задачи с шариками.


               

               

[qui›]

Цитата из: Maeglor on 17-11-2003, 01:15:35
Для бесконечного количества, очевидно, золотым сечением 6 бросков.
Также как и при игре в угадывании числа.



Почему золотым сечением? Ты, наверное, с чем-то другим путаешь. Золотое сечение это 1 : 1,618...