Задания с ответами. Занимательные задачи по информатике (Ответы и решения). Илья Муромец и Змей Горыныч
 Скачать 51.45 Kb.
|
|
Занимательные задачи по информатике (Ответы и решения). Илья Муромец и Змей Горыныч Ошибка1. После срубания у Змея Горыныча какого-то количества голов у него вырастало вдвое больше голов, поэтому если срубить 32 головы, то должно отрасти 64, а не 63. Ошибка 2. По той же причине, если срублено 63 головы, то должно отрасти 126, а не 128. Если же выросли 128 голов, то было срублено 64, а не 63. Ошибка 3. Восьмиразрядный Горыныч должен умереть после срубания 128 (а не 256) голов, потому что число 256 в двоичном виде уже не поместится в разрядную сетку, и все восемь младших разрядов будут нулевые. Если же Змей Горыныч все-таки умер после отрубания 256 голов, он был девятиразрядным, потому что в девяти разрядах число 256 в двоичном виде размещается, а 512 — нет. Слова после чисел «Вышел зайчик погулять» (в первой строке записаны числа от 1 до 5 в двоичной системе счисления). Градуировка весов Здесь рассуждения такие. Десятичное число 31 в двоичной системе счисления выглядит так: 11111, а все числа, меньшие 31, в этой системе состоят (естественно) из единиц и нулей. Любое двоичное число от 1 до 11111 можно получить, складывая двоичные числа 1,10,100,1000 и 10 000 (убедитесь в этом!). Эти числа есть двойка в степени 0, 1, 2, 3 и 4, т.е. десятичные цифры 1, 2, 4, 8 и 16. Значит, минимальный набор гирь-разновесов, который можно использовать для градуировки весов на интервал масс 1-31 кг, это гири массой 1, 2, 4, 8 и 16 кг. Например, чтобы отградуировать весы на 3 кг (310= 112), можно использовать гири массой 1 и 2 кг (этим значениям соответствуют двоичные числа 1 и 10), на 13 кг (1310= 11012) — гири массой 1,4 и 8 кг (12, 1002 и 10002). Бедный торговец (старинная задача) Прежде всего вспомним задачу 3. При ее решении использовалась запись чисел в двоичной системе счисления. На рычажных чашечных весах при взвешивании груза камни можно размещать на обеих чашках — и на свободной, и вместе с грузом. Следовательно, в нашей задаче надо найти такой набор чисел, которые можно не только складывать, но и вычитать. Если здесь также рассматривать представление десятичных чисел 1, 2, ..., 40 в двоичной системе счисления, то выяснится, что для взвешивания понадобится 6 разных камней — массой 1, 2, 4, 8, 16 и 32 кг (убедитесь, что с их помощью можно определить все нужные значения!). В условии же задачи говорится только о четырех камнях. Значит, надо попробовать использовать другие системы счисления. Чтобы найти, какую именно, рассмотрим более простую задачу: "С помощью какого минимального набора камней разной массы можно взвешивать предметы массой 1, 2, 3 и 4 кг?". Ответ здесь такой: с помощью двух камней—- массой 1 и 3 кг. Это должно навести на мысль о том, что нужно использовать троичную систему счисления. Действительно, любое троичное число от 1 до 1111 (4010= 11113) можно получить, складывая или вычитая числа 13, 103, 1003 и 10003 (убедитесь в этом!). Эти числа есть тройка в степени 0,1,2 и 3, т.е. десятичные числа 1, 3, 9 и 27, — именно такой массы и были камни в лавке бедного торговца. Задание для самостоятельной работы Подумайте, как определить, какие камни (или гири такого же веса) надо класть вместе с грузом, а какие — на свободную чашку, чтобы при грузе массой А кг весы были в равновесии. Как отгадать число? Одна из возможных серий вопросов, заведомо приводящая к успеху, такова. 1-й вопрос: "Разделите задуманное число на 2. Является ли единица остатком при таком делении?". Если ответ да, то запишем 1, если нет — 0 (иначе говоря, мы запишем остаток от деления задуманного числа на 2). 2-й вопрос: "Разделите на 2 то частное, которое получилось при первом делении. Является ли единица остатком при таком делении? Снова при ответе да запишем единицу, а при ответе нет — ноль". Каждый следующий вопрос будем составлять по тому же самому образцу, т.е. так: "Разделите на 2 то частное, которое получилось при предыдущем делении. Является ли единица остатком при таком делении?" Всякий раз мы пишем единицу при положительном ответе и ноль при отрицательном. Повторив эту процедуру 10 раз, мы получим 10 цифр, каждая из которых есть нуль или единица. После ответов на все вопросы записанные цифры надо расположить в обратном порядке — получится двоичное число, соответствующее задуманному десятичному (оно будет 10-значным), Действительно, система наших вопросов воспроизводит ту самую процедуру, с помощью которой делается перевод некоторого числа в двоичную систему. При этом десяти вопросов достаточно потому, что каждое число от 500 до 1000 записывается в двоичной системе с помощью не более чем десяти знаков. Переведя полученное число в десятичную систему счисления, получим задуманное число. Если считать, что задуманное число уже заранее переведено в двоичную систему, то система вопросов, с помощью которой его можно узнать, будет следующей. Нужно о каждой его цифре спросить, равна она нулю или нет. Для этого можно задать такие вопросы: "Является ли единица крайней справа цифрой двоичного числа, соответствующего задуманному десятичному числу?" "Является ли единица второй справа цифрой двоичного числа, соответствующего задуманному десятичному числу?" ... 10. "Является ли единица десятой справа цифрой двоичного числа, соответствующего задуманному десятичному числу?" , " Часы остановились "Изюминка" решения заключается в том, что, уходя из дома, надо пустить в ход свои стенные часы (которые остановились, но не сломались) и заметить по ним, в котором часу вы вышли, а затем — в котором часу вернулись. Так по своим часам можно определить, сколько времени вы отсутствовали. Придя к знакомому и уходя от него, вы узнаете показания его часов. Это даст вам возможность определить продолжительность пребывания у знакомого. Вычитая из продолжительности времени, которое вы отсутствовали дома, продолжительность пребывания у знакомого, вы получите количество времени, затраченного на дорогу туда и обратно. Прибавив половину этого количества времени к показанию часов товарища в момент, когда вы от него уходили, получите то показание, которое следует установить на остановившихся часах. В соответствии с этим алгоритм решения задачи следующий: Пустить в ход свои стенные часы. Отметить время ухода из дома по этим часам. Пойти к знакомому., Отметить время прихода к знакомому по его часам. Определить время ухода от знакомого (также по его часам). Рассчитать время пребывания у знакомого (разность значений времени по пунктам 5 и 4). Вернуться домой. Установить время возвращения домой по своим настенным часам. Рассчитать время, которое вы отсутствовали дома (разность значений времени по пунктам 8 и 2)., Вычесть из значения времени, рассчитанного в пункте 9, значение, вычисленное в пункте 6. Разделить полученное в предыдущем пункте значение на 2. Прибавить значение, рассчитанное в пункте 11, ко времени, установленному, в пункте 5. Поставить стрелки стенных часов на время, вычисленное в пункте 12 Ночной переход на мосту Оптимальное решение, согласно которому семья перейдет мост за минимально возможное время (17 минут), представлено в табл. 1. Таблица 1
Вкусные ломтики Если пронумеровать ломтики, то задача поджаривания четырех ломтиков за минимально возможное время решается за четыре шага (этапа), представленных в табл. 2, а пяти ломтиков – за пять шагов, показанных в табл. 3. Таблица 2
Таблица 3
Задача о лифте Решение представлено в табл.4 Таблица 4
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||