Задания с ответами. Занимательные задачи по информатике (Ответы и решения). Илья Муромец и Змей Горыныч
 Скачать 51.45 Kb.
|
|
Рисунок 1 Следовательно, в шоколадке 8 х 6 придется сделать 47 разломов, т.е., как бы не действовали участники игры, при 48 дольках шоколадки последний разлом всегда сделает тот, кто начал (поэтому задача и названа шуткой). Ответ на дополнительное задание к задаче 4 "Бедный торговец" Пусть груз, который надо взвесить, весит А кг. Это число можно представить в троичной системе: А = (аn аn-1...a1a0)3 т.е. А = аn 3n+an-1 3n-1+ ... +а13+а0, - где коэффициенты а0, a1, …, аnмогут принимать значения 0, 1 или 2 (как вы, очевидно, знаете, это так называемая "развернутая" запись числа А). Можно доказать, что 2 3m = 3m+1 – 3m. Введем "отрицательную цифру" 1 и обозначим ее 1. Тогда последнее равенство можно записать в виде: 2 3m = 3m+1 +1 – 3m . А это означает, что любое целое число А можно изобразить в троичной системе счисления с помощью цифр 0,1 и 1 (заменив в его развернутой записи цифры 2 на соответствующую разность): А = bm 3m+bm-1 3m-1+ ... +b13+b0, - где каждый из коэффициентовbm, bm-1, …, b0 может быть равным 0, 1 или 1 Например, число 100, которое обычным образом записывается в троичной системе как 10201, во втором варианте будет иметь вид 11101, поскольку 100 =34 + 33 -32+1. Следовательно, чтобы уравновесить груз в А граммов, нужно положить его на первую чашу весов, а гирю в 1 грамм поставить на вторую чашу, если b0 =1, и на первую чашу, если b0= 1 (если b0= 0, то гирю в 1 грамм мы вообще не используем); далее, гиря весом в 3 грамма ставится на вторую чашу, если b1 = 1, и на первую, если b1=1, и т.д. Легко понять, что, расставив гири по такому принципу, мы уравновесим груз А. Поясним сказанное на примере. Предположим, что у нас имеется груз в 200 граммов. Переводя 200 в троичную запись, мы получим: Следовательно, 20010= 211023, или в развернутой записи — 200 = 2 34+ + 1 33 + 1 32 + 0 3 + 2 1. Таким образом, чтобы уравновесить груз в 200 граммов, положенный на чашу весов, нужно на ту же чашу положить гири в 1 грамм и 81 грамм, а на противоположную — гири в 3, 9, 27 и 243 грамма. Антиквар и 99 монет Задача 2. Сначала положим на две чашки весов по 13 монет, затем (если весы находятся в равновесии) уберем их и положим по 11 из еще не бравшихся монет, затем по 9, 7, 5, 3 и 1 до тех пор, пока одна из чашек не перевесит. Если такого не произойдет, то после седьмого взвешивания (когда на чашках весов будет по одной монете) останется одна, 99-я по счету, монета, которая во взвешиваниях не участвовала. Она и является фальшивой. Сложнее, если при каком-то взвешивании какая-то чашка весов перевесила. Прежде всего ясно, что в этот момент фальшивая монета лежит в другой чашке. Составим табличку (см. табл. 9): Таблица 9
Итак, при каком-то, k-м, взвешивании мы можем выявить n монет, среди которых находится искомая фальшивая. Можно записать, что п =(7 - k)* 2 + 1. Получается, что мы пришли к задаче нахождения среди (7 - k)* 2 + 1 монет фальшивой монеты за (7 -k) взвешиваний (так как k взвешиваний уже проведено, причем каждая монета в рассматриваемой группе взвешивалась один раз). Введем новую величинуm = 7- k. Тогда только что сформулированная задача сводится к следующей: среди(2m + 1) монет найти фальшивую монету за m взвешиваний (среди трех монет за одно взвешивание, среди пяти монет — за два, … среди тринадцати — за 6). При этом никакую монету нельзя взвешивать более одного раза. Такую задачу мы уже решали (см. решение предыдущей задачи). Ее можно решить так. Надо все монеты, кроме одной; разбить наmпар и последовательно сравнивать веса монет каждой пары — для этого понадобится m взвешиваний. Если при каком-то взвешивании равновесие нарушится, то более легкая монета и является фальшивой. В противном случае фальшивая монета — оставшаяся "без пары". Умная обезьяна Может. Первый раз обезьяна должна уронить один из двух уцелевших орехов с 4-го "яруса". Если он разбился, она, используя оставшийся орех, проверит 2-й и, при необходимости, 3-й "ярусы". Если орех, брошенный с 4-го яруса, не разбился, то второй раз она уронит его с 7-го "яруса". Если он разбился, то проверит 5-й и 6-й "ярусы". Если орех не разбился, то третий раз уронит орех с 9-го "яруса". Если орех разбился, то проверит 8-й "ярус". Если орех не разбился, то проверит 10-й "ярус". Вся схема испытаний следующая: Первое испытание — бросить один из двух орехов с 4-г "яруса" если орех, разбился то Второе испытание - бросить оставшийся орех с 2-го "яруса" если орех разбился то ярус:=1 номер искомого "яруса" иначе Третье испытание – бросить орех с 3-го "яруса" если орех разбился то ярус:=2 иначе ярус:=3 все все иначе При первом испытании орех не разбился Второе испытание – бросить орех с 7-го "яруса" если орех разбился то Третье испытание – бросить оставшийся орех с 5-го "яруса" если орех разбился то ярус:=4 иначе Четвертое испытание – бросить орех с 6-го "яруса" если орех разбился то ярус:=5 иначе ярус:=6 все все иначе При втором испытании (с 7-го "яруса")орех не разбился Третье испытание – бросить орех с 9-го "яруса" если орех разбился то Четвертое испытание – бросить оставшийся орех с 8-го "яруса" если орех разбился то ярус:=4 иначе Четвертое испытание – бросить орех с 6-го "яруса" если орех разбился то ярус:=7 иначе ярус:=8 все иначеПри третьем испытании (с 9-го "яруса" орех не разбился Четвертое испытание – бросить орех с 10-го "яруса" если орех разбился то ярус:=9 иначе ярус:=10 все все все все Можно также первое испытание провести на 5-м "ярусе". Если орех разбился, обезьяна, используя оставшийся орех, проверит 2-й и, при необходимости, 3-й и 4-й "ярусы". В противном случае второй раз она уронит его с 7-го "яруса". Если он разбился, то проверит 6-й "ярус''. Если же при втором испытании (на 7-м "ярусе") орех не разбился, то дальнейшие действия умного животного должны быть аналогичными первому варианту решения задачи. Возможна также модификация только что рассмотренного варианту, в котором второе испытание проводится на 8-м "ярусе". Задание для самостоятельной работы 1. Составьте полную схему испытанийдля второго варианта решения, аналогичную приведенной чуть выше. - 2. Сравните рассмотренные варианты (см.табл. 10) Таблица 10
Литература Гарднер М. Математические головоломки и развлечения. М.: Мир, 1999. Заславская О.Ю. Логические парадоксы и софизмы // Информатика, № 8/2004. "Квант": научно-популярный физико-математический журнал, 1970-1995. Кордёмский Б. А. Математическая смекалка. М.: Юнисам, МДС, 1994. Перельман Я.И. Занимательная математика. М.: Издательство Русанова, 1994. | |||||||||||||||||||||||||||||||||||||||