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

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

Cамурай
Аватара
Cамурай
Репутация: 32

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

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

Варианты решения пишем в теме и обсуждаем.

Pentium133
Аватара
Pentium133
Репутация: 12

#2 Pentium133 » 19.11.2013, 22:24

Варианты решения прячьте под спойлер! :?

Pentium133
Аватара
Pentium133
Репутация: 12

#3 Pentium133 » 19.11.2013, 23:07

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

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

Зная в какой тройке подозреваемый, взвешиваем два шара из трёх и находи его.

Cамурай
Аватара
Cамурай
Репутация: 32

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

Неясен частный случай, когда подозреваемый находится во второй шестёрке и вес второго взвешивания одинаков. Как найти среди оставшихся 3-х шаров нужный не зная тяжелее он или легче?

Cамурай
Аватара
Cамурай
Репутация: 32

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

Предлагаю такое решение:

Код: Выделить всё

Нумеруем шары от 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 тяжелее


Pentium133
Аватара
Pentium133
Репутация: 12

#6 Pentium133 » 20.11.2013, 09:41

Cамурай писал(а):Неясен частный случай, когда подозреваемый находится во второй шестёрке и вес второго взвешивания одинаков. Как найти среди оставшихся 3-х шаров нужный не зная тяжелее он или легче?
Ты прав. А твоё решение замудрёное. Как ты к нему пришёл?

Cамурай
Аватара
Cамурай
Репутация: 32

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

Pentium133 писал(а):Как ты к нему пришёл?
Взвешивал сначала по 3 шара, потом по 4, потом по 5 :) Я не проверял все 24 логических выражения. Но, думаю, что должно сработать.

Cамурай
Аватара
Cамурай
Репутация: 32

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

Следующая задача
Положим у парня есть 1000 бутылок вина. Выясняется, что одна из них отравлена. На счастье у него еще есть 10 мышей, которыми он готов пожертвовать для экспериментов. Опыты занимают сутки, то есть мышь хлебнувшая ядовитого вина подыхает только через 24 часа. Наш герой как раз планирует масштабную вечеринку на завтра. Сколько из 1000 бутылок может быть проверено на мышах и подано к столу окажись парень семи пядей во лбу? К примеру он может дать каждой мыши отведать из одной из бутылок и таким образом быть уверенным по меньшей мере в десяти бутылках, если ни одно животное не окочурится. При летальном исходе парень получает 999 надежных бутылок, но как уже указывалось, в задачах предполагается сценарий недружелюбный выбранной методике испытаний. Все мыши должны быть распределены по бутылкам немедленно потому что до вечеринки остается всего 24 часа.

RomanF
RomanF
Репутация: 14

#9 RomanF » 20.11.2013, 19:22

решение
Спойлер
1000 бутылок:
для простоты добавим еще 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ая бутылка отравлена.

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

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

#10 anton » 20.11.2013, 20:31

Есть и такой вариант:
Решение
Разделим 1000 бутылок на 10, затем пометим всех мышей.

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


RomanF
RomanF
Репутация: 14

#11 RomanF » 20.11.2013, 20:35

900 тоже неплохо :-) но 999 лучше :)

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

#12 anton » 20.11.2013, 20:41

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

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

Таким образом, на выходе в любом случае получим 910 бутылок.

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

#13 anton » 20.11.2013, 20:43

RomanF писал(а):900 тоже неплохо :-) но 999 лучше :)
Cамурай писал(а):в задачах предполагается сценарий недружелюбный выбранной методике испытаний.

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

RomanF
RomanF
Репутация: 14

#14 RomanF » 20.11.2013, 21:06

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

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

Cамурай
Аватара
Cамурай
Репутация: 32

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

Пусть x и y два целых числа 1 \< x \< y притом x + y \<= 100. Салли сказали только сумму x + y, а вот Полю произведение xy. Салли и Пол честнейшие ребята, это всем известно, они и друг другу отродясь не врали.
И вот такой вышел у них разговор:
Пол: «Не знаю я, что это за числа.»
Салли: «Тоже новость. Я знаю, что ты не знаешь.»
Пол: «Ну твоя то сумма мне теперь известна.»
Салли: «Да уж и мне теперь твое произведение.»
Каковы числа?

RomanF
RomanF
Репутация: 14

#16 RomanF » 21.11.2013, 20:14

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

Cамурай
Аватара
Cамурай
Репутация: 32

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

Изображение

Ipkis
Ipkis
Репутация: 0

#18 Ipkis » 29.09.2014, 12:32

[spoiler][/spoiler]
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й шар легче.

coler
coler
Репутация: 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, если ==<
Если не опечатался - то как-то так. Ну и шар легче, если везде < на > поменять.

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

#20 Olga » 01.10.2014, 22:34

:)


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

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

Сейчас этот раздел просматривают: 2 гостя