Интересные задачи

Список форумов Общий раздел Программирование

Описание: Обучение программированию, интересные задачи, полезные ресурсы

#1 Cамурай » 19.11.2013, 21:33

Начнём :)
$this->bbcode_second_pass_quote('', '')ыдано 12 одинаковых на вид шаров из которых, как вам сказали, только один отличается по весу. Ваша задача заключается в том, чтобы определить какой именно и легче он или тяжелее. Единственный инструмент в вашем распоряжении это весы с двумя чашками. На чашки можно класть только шары. Весы можно использовать не более трех раз.

Варианты решения пишем в теме и обсуждаем.
Cамурай
Аватара
Откуда: Р/н/Д
Репутация: 32

#2 Pentium133 » 19.11.2013, 22:24

Варианты решения прячьте под спойлер! :?
Pentium133
Аватара
Репутация: 12

  • 1

#3 Pentium133 » 19.11.2013, 23:07

$this->bbcode_second_pass_spoiler('Решение', '
')Делим шары на две части по 6. Ищем 6-ку в которой подозреваемый. Взвешиваем 3 и 3 из первой шестёрки. Если вес одинаковый, то подозреваемый во второй. Иначе в первой.

Взвешиваем одну нормальную тройку и вторую из подозреваемой шестёрки. Зная где нормальная тройка определяем в какой тройке подозреваемый, а так же легче он или тяжелей. (если вес одинаковый, мы все равно знаем какая из подозреваемых троек отличается по весу)

Зная в какой тройке подозреваемый, взвешиваем два шара из трёх и находи его.
Pentium133
Аватара
Репутация: 12

#4 Cамурай » 19.11.2013, 23:13

Неясен частный случай, когда подозреваемый находится во второй шестёрке и вес второго взвешивания одинаков. Как найти среди оставшихся 3-х шаров нужный не зная тяжелее он или легче?
Cамурай
Аватара
Откуда: Р/н/Д
Репутация: 32

#5 Cамурай » 19.11.2013, 23:49

$this->bbcode_second_pass_spoiler('Предлагаю такое решение:', '$')this->bbcode_second_pass_code('', 'Нумеруем шары от 1 до 12:
1 2 3 4 5 6 7 8 9 10 11 12

Взвешиваем 1 2 3 4 5 и 6 7 8 9 10
Взвешиваем 1 3 5 7 9 и 4 6 8 10 12
Взвешиваем 1 2 4 6 8 и 3 5 7 9 11

На основании результатов взвешивания пишем логические выражения:
1 2 3 4 5 < 6 7 8 9 10 && 1 3 5 7 9 < 4 6 8 10 12 && 1 2 4 6 8 < 3 5 7 9 11 = шар 1 легче
1 2 3 4 5 > 6 7 8 9 10 && 1 3 5 7 9 > 4 6 8 10 12 && 1 2 4 6 8 > 3 5 7 9 11 = шар 1 тяжелее
и т.д. всего 24 комбинации до
1 2 3 4 5 == 6 7 8 9 10 && 1 3 5 7 9 > 4 6 8 10 12 && 1 2 4 6 8 == 3 5 7 9 11 = шар 12 легче
1 2 3 4 5 == 6 7 8 9 10 && 1 3 5 7 9 < 4 6 8 10 12 && 1 2 4 6 8 == 3 5 7 9 11 = шар 12 тяжелее')
Cамурай
Аватара
Откуда: Р/н/Д
Репутация: 32

#6 Pentium133 » 20.11.2013, 09:41

$this->bbcode_second_pass_quote('Cамурай', '')еясен частный случай, когда подозреваемый находится во второй шестёрке и вес второго взвешивания одинаков. Как найти среди оставшихся 3-х шаров нужный не зная тяжелее он или легче?
Ты прав. А твоё решение замудрёное. Как ты к нему пришёл?
Pentium133
Аватара
Репутация: 12

#7 Cамурай » 20.11.2013, 11:08

$this->bbcode_second_pass_quote('Pentium133', '')ак ты к нему пришёл?
Взвешивал сначала по 3 шара, потом по 4, потом по 5 :) Я не проверял все 24 логических выражения. Но, думаю, что должно сработать.
Cамурай
Аватара
Откуда: Р/н/Д
Репутация: 32

#8 Cамурай » 20.11.2013, 18:14

Следующая задача
$this->bbcode_second_pass_quote('', '')оложим у парня есть 1000 бутылок вина. Выясняется, что одна из них отравлена. На счастье у него еще есть 10 мышей, которыми он готов пожертвовать для экспериментов. Опыты занимают сутки, то есть мышь хлебнувшая ядовитого вина подыхает только через 24 часа. Наш герой как раз планирует масштабную вечеринку на завтра. Сколько из 1000 бутылок может быть проверено на мышах и подано к столу окажись парень семи пядей во лбу? К примеру он может дать каждой мыши отведать из одной из бутылок и таким образом быть уверенным по меньшей мере в десяти бутылках, если ни одно животное не окочурится. При летальном исходе парень получает 999 надежных бутылок, но как уже указывалось, в задачах предполагается сценарий недружелюбный выбранной методике испытаний. Все мыши должны быть распределены по бутылкам немедленно потому что до вечеринки остается всего 24 часа.
Cамурай
Аватара
Откуда: Р/н/Д
Репутация: 32

#9 RomanF » 20.11.2013, 19:22

решение
$this->bbcode_second_pass_spoiler('', '1')000 бутылок:
для простоты добавим еще 24 вымышленные бутылки, они точно не отравленные :)
1. делим бутылки на две части.
первую мышь поим из второй части (512 бутылок)
2. делим бутылки на 4 части,
вторая пьет 2 и 4ую части
3. делим бутылки на 8 частей (по 128)
третья пьет 2,4,6,8 части (все четные)
4. тоже самое с 4 мышью:
делим каждую 125 пополам: 64.
И так далее до 10 мыши включительно.
В итоге по номерам отконюченных мышей можно составить число из бит, прибавить 1 - это число и есть номер отравленной бутылки. Например, если ни одна мышь коньки не сбросила, то это 0000 0000 00 - нулевая бутылка отравлена (её ни одна мышь не выпьет)
Если сдохла последняя мышь - то это 0000 0000 01 = 1 или вторая бутылка отравлена, и т.д.
если сконючилась первая мышь, к примеру и больше никто, то это 1000 0000 00 - или 256 - значит 257ая бутылка отравлена.

Для простоты понимания можно еще так: если первая мышь сконючилась - значит отравленная бутылка во второй половине, нет - в первой. Дальше каждая половина каждой мышью делится пополам, почти как с весами. Таким образом по отконюченным мышам мы сможем построить бинарное дерево и вывести плохую бутылку на чистую воду.
RomanF
Репутация: 14

#10 anton » 20.11.2013, 20:31

Есть и такой вариант:
$this->bbcode_second_pass_spoiler('Решение', '
')Разделим 1000 бутылок на 10, затем пометим всех мышей.

Каждую мышь напоим 100 бутылками. Когда какая-то из мышей сдохнет, просто бракуем сотню, которую эта мышь употребила. Итого остается 900 чистых бутылок.

anton
Администратор
Аватара
Откуда: Россия, Ростов-на-Дону
Репутация: 33

#11 RomanF » 20.11.2013, 20:35

900 тоже неплохо :-) но 999 лучше :)
RomanF
Репутация: 14

#12 anton » 20.11.2013, 20:41

Можно максимизировать количество бутылок на выходе:

$this->bbcode_second_pass_spoiler('Решение', '
')Для этого делим 1000 не на 10, а на 11. Если все мыши выжили, то отравленная бутылка находится в 11-й части.

Таким образом, на выходе в любом случае получим 910 бутылок.
anton
Администратор
Аватара
Откуда: Россия, Ростов-на-Дону
Репутация: 33

#13 anton » 20.11.2013, 20:43

$this->bbcode_second_pass_quote('RomanF', '9')00 тоже неплохо :-) но 999 лучше :)
$this->bbcode_second_pass_quote('Cамурай', '') задачах предполагается сценарий недружелюбный выбранной методике испытаний.

Судя по условию задачи, нужно рассматривать неблагоприятные условия.
anton
Администратор
Аватара
Откуда: Россия, Ростов-на-Дону
Репутация: 33

#14 RomanF » 20.11.2013, 21:06

Да, у моего решения 999 - при любом раскладе, в т.ч. неблагоприятном.

Хотя что считать неблагоприятным? :D Может хозяин специально решил отравить гостей :twisted:
RomanF
Репутация: 14

#15 Cамурай » 21.11.2013, 13:02

$this->bbcode_second_pass_quote('', '')усть x и y два целых числа 1 \< x \< y притом x + y \<= 100. Салли сказали только сумму x + y, а вот Полю произведение xy. Салли и Пол честнейшие ребята, это всем известно, они и друг другу отродясь не врали.
И вот такой вышел у них разговор:
Пол: «Не знаю я, что это за числа.»
Салли: «Тоже новость. Я знаю, что ты не знаешь.»
Пол: «Ну твоя то сумма мне теперь известна.»
Салли: «Да уж и мне теперь твое произведение.»
Каковы числа?
Cамурай
Аватара
Откуда: Р/н/Д
Репутация: 32

#16 RomanF » 21.11.2013, 20:14

решается методом перебора :-) Завтра попробую программу написать
RomanF
Репутация: 14

#17 Cамурай » 24.12.2013, 13:25

Изображение
Cамурай
Аватара
Откуда: Р/н/Д
Репутация: 32

#18 Ipkis » 29.09.2014, 12:32

[spoiler][/spoiler]$this->bbcode_second_pass_quote('Cамурай', '')умеруем шары от 1 до 12:
1 2 3 4 5 6 7 8 9 10 11 12

Взвешиваем 1 2 3 4 5 и 6 7 8 9 10
Взвешиваем 1 3 5 7 9 и 4 6 8 10 12
Взвешиваем 1 2 4 6 8 и 3 5 7 9 11

На основании результатов взвешивания пишем логические выражения:
1 2 3 4 5 < 6 7 8 9 10 && 1 3 5 7 9 < 4 6 8 10 12 && 1 2 4 6 8 < 3 5 7 9 11 = шар 1 легче
1 2 3 4 5 > 6 7 8 9 10 && 1 3 5 7 9 > 4 6 8 10 12 && 1 2 4 6 8 > 3 5 7 9 11 = шар 1 тяжелее
и т.д. всего 24 комбинации до
1 2 3 4 5 == 6 7 8 9 10 && 1 3 5 7 9 > 4 6 8 10 12 && 1 2 4 6 8 == 3 5 7 9 11 = шар 12 легче
1 2 3 4 5 == 6 7 8 9 10 && 1 3 5 7 9 < 4 6 8 10 12 && 1 2 4 6 8 == 3 5 7 9 11 = шар 12 тяжелее
поправьте меня, если я не прав, но шары 3 и 5 находятся всегда в одном взвешивании, так же они учавствуют в каждом взвешивании. В итоге, если один из них и есть легкий/тяжелый шар, то нельзя различить какой конкретно из них легкий/тяжелый

Пример
1 2 3 4 5 < 6 7 8 9 10
1 3 5 7 9 < 4 6 8 10 12
1 2 4 6 8 > 3 5 7 9 11

в этом случае нельзя понять это 3й или 5й шар легче.
Ipkis
Репутация: 0

#19 coler » 29.09.2014, 19:50

Надо взвешивать
1 3 5 7 и 2 4 6 8
1 6 8 10 и 2 7 9 11
2 3 8 11 и 5 6 9 12
Ну и по ответам, тяжелее...
1, если >>=
2, если <<>
3, если >=>
4, если <==
5, если >=<
6, если <=<
7, если ><=
8, если <==
9, если =<<
10, если =>=
11, если =<>
12, если ==<
Если не опечатался - то как-то так. Ну и шар легче, если везде < на > поменять.
coler
Репутация: 0

#20 Olga » 01.10.2014, 22:34

:)
Olga
Репутация: 0

След.

Вернуться в Программирование

Кто сейчас на сайте (по активности за 60 минут)

Сейчас этот форум просматривают: 1 гость

cron