Презентация по информатике "Занимательные задачи по информатике 5-9 класс"

Занимательные задачи по информатике
Автор презентации:
Учитель информатики
ГБОУ Лицей №597
Курносова М.А.

Содержание (часть 1)
Илья Муромец и Змей Горыныч
Слова после чисел
Градуировка весов
Бедный торговец (старинная задача)
Как отгадать число?
Часы остановились
Ночной переход на мосту
Вкусные ломтики
Задача о лифте
Умная обезьяна

Содержание (часть 2)
Мешок с фальшивыми монетами
Еще один мешок с фальшивыми монетами
Почему трижды?
Шутники и серьезные
Приятели и их шапки
Те же приятели и те же шапки
10 единиц и 10 двоек
"Шоколадка" (задача-шутка)
Антиквар и 99 монет

Илья Муромец и Змей Горыныч
Перед вами фрагмент сказки:
«Срубил Илья Муромец Змею Горынычу голову, а взамен две выросли. Срубил 2 — выросли 4, срубил 4 — выросли 8, срубил 8— выросли 16, сру­бил 16 — выросли 32, срубил 32 — выросли 63, срубил 63 — выросли 128, срубил 128—выросли 256. А как срубил Илья 256 голов, тут и настал Змею Горынычу конец, потому что был Горыныч восьмиразрядный!"
Какие три ошибки имеются в приведенном фрагменте?

Проверь себя

Слова после чисел
Определите, какие слова должны быть записаны во второй строке:
1, 10, 11, 110, 111

Проверь себя

Градуировка весов
Есть пружинные весы, которые нужно отградуировать. Каким должен быть набор гирь-разновесов, который можно использовать для градуировки весов на интервал масс 1, 2, …, 31 кг, чтобы число гирь в наборе было минимальным?

Проверь себя

Бедный торговец (старинная задача)
В лавке бедного торговца вместо гирь было всего 4 камня. Однако с помо­щью этих камней он на рычажных чашечных весах совершенно правильно взвешивал предметы массой 1,2,..., 40 кг. Какого веса были камни?

Проверь себя

Как отгадать число?
Пусть кто-то загадал некоторое целое число из интервала от 500 до 1000 включительно. Беретесь ли вы узнать загаданное число, задав этому человеку не более 10 вопросов, на каждый из которых он будет отвечать только "да" или "нет"? Вопросы типа "Задуманное число больше 800?", в которых фигурируют слова "больше", "больше либо равно", "меньше", "не меньше", "превышает" и т.п., а также вопросы типа "Задуманное число находится в интервале от ... до ... ?" задавать нельзя. Беритесь, задача эта вполне разрешима.

Проверь себя

Часы остановились
Представьте себе, что у вас дома единственные часы остановились. Каким должен быть алгоритм ваших действий, чтобы правильно установить стрелки остановившихся часов, если вы можете пойти к знакомому, часы которого идут безукоризненно, и узнать точное время? Сколько времени занимает дорога, заранее неизвестно.
Проверь себя

Ночной переход на мосту
Ночью к мосту подошла семья (папа, мама, малыш, и бабушка). Папа может перейти мост за 1 минуту, мама — за 2, малыш — за 5, бабушка—за 10 минут. Мост выдерживает только двоих.
Какое минимальное время требуется этой семье для перехода через мост? (Есть один фонарик. Двигаться по мосту без фонарика нельзя. Светить издали нельзя. Носить друг друга на руках нельзя. Бросать фонарик друг другу нельзя. Если мост переходят двое, то они идут с меньшей из их скоростей.)

Проверь себя

Вкусные ломтики
Мама очень вкусно поджаривает ломтики хлеба, пользуясь специальной маленькой сковородкой. Для готовности каждый ломтик должен быть поджарен с двух сторон. Поджаривание каждой стороны ломтика длится 30 секунд, причем на сковороде умещается рядом только два ломтика.
За какое минимальное время при этих условиях мама может приго­товить:
а)четыре ломтика хлеба?
б)пять ломтиков?

Проверь себя

Задача о лифте
В кабине лифта 20-этажного дома есть две кнопки. При нажатии на одну, из них лифт поднимается на 13 этажей, при нажатии на другую—опускается на 8 этажей. Как попасть с 13-го этажа на 8-й?

Проверь себя

Умная обезьяна
Когда обезьяна несла три кокосовых ореха на вершину "многоярусного" дерева, один орех упал с 11-го "яруса" и разбился. Обезьяна хочет определять самый высокий "ярус", при падении с которого кокосовые орехи не разбиваются. Она может уронить орех с любого "яруса" и подобрать его, если он цел. При падении с первого "яруса" орехи не разбиваются.,
Может ли она, используя два уцелевших ореха, решить задачу за четыре испытания (во время которых орехи могут быть разбиты)?

Проверь себя

Илья Муромец и Змей Горыныч
(ответ)
Ошибка 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, а пяти ломтиков – за пять шагов, показанных в таблице 2

Вкусные ломтики
(ответ)

Задача о лифте
(ответ)
Решение представлено в таблице










Примечание. Кнопки с условными обозначениями «-8» и «+13» - те кнопки, при нажатии на которые лифт опускается на 8 этажей и понимается на 13 этажей соответственно.

Умная обезьяна
(ответ)
Может. Первый раз обезьяна должна уронить один из двух уцелев­ших орехов с 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
все все все все

Мешок с фальшивыми монетами


Имеются 10 мешков, набитых монетами. Известно, что все монеты в девяти мешках не фальшивые. Относительно же одного мешка известно, что в нем либо все монеты фальшивые, либо все настоящие. Фальшивая монета весит 11 г, а настоящая — 10 г. Как с помощью одного взвешива­ния на точных (до 1 г) весах выяснить, есть ли среди 10 мешков мешок с фальшивыми монетами, если есть — указать какой.

Проверь себя

Еще один мешок с фальшивыми монетами

Имеются 11 мешков, набитых монетами. В десяти мешках монеты настоящие, а в каком-то одиннадцатом — все монеты фальшивые. Все настоящие монеты одинаковы по весу. Все фальшивые монеты тоже оди­наковы, но несколько отличаются по весу от настоящих монет, причем заранее неизвестно, легче они или тяжелее настоящих. Как с помощью двух взвешиваний на точных весах определить, в каком мешке фальшивые монеты, и указать, легче они или тяжелее настоящих.

Проверь себя

Почему трижды?

Когда один компьютер посылает сообщения другому, используя условные единицы и нули, мы должны быть уверены в правильности полученной информации. Значит, для выявления редких, но возможных ошибок нам требуются какие-то методы. Один из таких методов — передача каждой цифры трижды, т.е. три раза подряд. Например, вместо 1100111 нужно передать 111 111 000 000 111 111 111. Почему именно так?

Проверь себя

Шутники и серьезные

Школьники для игры разбились на две "партии": на "серьезных", отве­чающих правильно на любой вопрос, и на "шутников", дающих па любой вопрос только неправильные ответы.
Учитель, узнав об этом, спросил у Иванова, серьезный ли он человек или шутник. Не расслышав ответа Иванова, он спросил у Петрова и Сидорова (сидевших рядом с Ивановым и все слышавших): "Что ответил мне Иванов?". Петров сказал: "Иванов ответил, что он серьезный человек". Сидоров же ска­зал: "Иванов ответил, что он шутник". Кем были Петров и Сидоров?

Проверь себя

Приятели и их шапки


Три приятеля: Андрей, Борис и Вадим сидели друг, за другом без головных уборов (см. рис. 1), причем Борису и Вадиму было запрещено оглядываться назад, Борис же видел голову сидящего внизу Вадима, а Андрей головы обоих своих приятелей. Из мешка, содержащего две белые и три черные шапки (об этом все трое были осведомлены), каждому была надета шапка неизвестного (для него) цвета, а еще две шапки неизвестных (для всех) цветов остались в мешке.
Андрей заявил, что он не может определить цвет своей шапки. Борис слышал ответ Андрея и сказал, что и у него не хватает данных для опре­деления цвета шапки, находящейся у него на голове.
Мог ли Вадим на основании ответов своих приятелей определить цвет своей шапки?

Проверь себя

Те же приятели и те же шапки

А теперь решите задачу о приятелях и их шапках, так сказать, в общем виде.
Каждого из юношей спросили, может ли он определить цвет своей шапки. Сможет ли Борис на основе ответа Андрея определить цвет своей шапки? Сможет ли Вадим на основе ответов Андрея и Бориса определить цвет своей шапки? Рассмотрите все возможные варианты.

Проверь себя

10 единиц и 10 двоек

На доске написаны 10 единиц и 10 двоек. За ход разрешается стереть две любые цифры и, если они были одинаковыми, написать двойку, а если разными — единицу. Если оставшаяся на доске цифра — единица, то вы­играл первый игрок, если двойка — второй. Кто выиграет в этой игре?

Проверь себя

"Шоколадка" (задача-шутка)

Двое ребят по очереди ломают шоколадку размером 6x8 долек. За ход разрешается сделать прямолинейный разлом любого из кусков вдоль углубления в шоколадке. Проигрывает тот, кто не сможет сделать ход. Как должны играть участники, чтобы выиграть?
Почему задача с этой игрой названа задачей-шуткой?

Проверь себя

Антиквар и 99 монет
Антиквар приобрел 99 одинаковых по виду старинных монет. Ему сообщили, что одна из монет фальшивая и что она легче настоящих (все настоящие весят одинаково).
Как, используя чашечные весы без гирь, не более чем за 5 взвешива­ний выявить фальшивую монету?
Как выявить фальшивую монету за 7 взвешиваний при условии, вы­двинутом антикваром, — не взвешивая никакую монету более двух раз?

Проверь себя

Мешок с фальшивыми монетами
(ответ)
Выяснить требуемое можно, пользуясь такой системой указаний:
Пронумеровать мешки числами от 1 до 10.
Из каждого мешка извлечь столько монет, каков его номер.
Определить на весах суммарную массу М всех извлеченных монет.
Проверить условие М = 550. Если да, то перейти к указанию 7, иначе — к следующему указанию.
Определить разность R, равную М - 550.
Объявить, что в мешке с номером R монеты фальшивые. Перейти к указанию 8.
Объявить, что мешка с фальшивыми монетами нет.
Конец.

Еще один мешок с монетами
(ответ)
1-евзвешивание. Взять по одной монете из каждого мешка и определить их общий вес V1. В результате можно определить:
вес настоящих монет т: он равен округленному до целого частному отделения V1, на 11;
на сколько вес фальшивых монет отличается от веса настоящих, эта величина равна V1-11 т и позволяет сказать, легче или тяжелее настоящих фальшивые монеты.
2-евзвешивание. Взять, как в предыдущей задаче, из каждого мешка столько монет, каков его номер (общее число взятых монет—66). Если их общий вес V2,то номер с фальшивыми монетами равен | V2 - V1,|/ |V1-11т|, где символы || означают абсолютную величину числа, представленного между ними.

Почему трижды?
(ответ)
Трехкратное повторение каждой двоичной цифры позволяет в случае ошибки выявить ее. Так, для примера, приведенного в статье, если будет при­нято число 111 101 000 000 111 111 111,то это означает, что при передаче второй цифры была допущена ошибка, и принявший ее (человек или компьютер по специальной программе проверки) сможет прочесть правильный вариант. Если передавать каждую цифру только два раза, то этого достаточно, чтобы выявить, была допущена ошибка при передаче или нет. Но для того, чтобы определить, какова ошибка, двойного повторения мало.

Шутники и серьезные
(ответ)
Прежде всего можно установить, что так как Петров и Сидоров на заданный вопрос ответили по-разному, то они относятся к разным "пар­тиям" (один — "шутников", другой — "серьезных").
Рассмотрим возможные ответы Иванова. Если он —- серьезный, то на вопрос учителя он так и ответит (что он серьезный). Если же он шутник — то тогда он ответит, что он якобы серьезный. Получается, что в любом случае Иванов должен ответить: "Я — серьезный человек".
Так как Петров сказал учителю то же, что ответил Иванов, то он отно­сится к "партии серьезных". Тогда Сидоров— шутник.
Можно также решить задачу методом допущений. Если допустить, что Петров — шутник, а Сидоров — серьезный человек, то из ответа первого следует, что Иванов на самом деле — шутник, а из ответов второго — что серьезный человек, чего быть не может.
Если же, наоборот, предположить, что Петров — серьезный человек, а Сидоров — шутник, то из ответа каждого из них следует одно и то же (что Иванов — серьезный).
Следовательно, Петров относится к "партии серьезных", а Сидоров — шутник.

Приятели и их шапки
(ответ)
На основании ответов своих приятелей Вадим может определить цвет своей шапки. Действительно, из ответа Андрея его друзьям должно быть ясно, что на них не может быть двух белых шапок (иначе Андрей определил бы, что на нем— черная шапка). Значит, на них либо одна белая и одна черная шапка, либо обе черных.
Если бы на Вадиме была белая шапка, то Борис легко определил бы цвет своей шапки (черный), а так как он этого сделать не смог, то Вадим должен понять, что его шапка черная.

Те же приятели и их шапки
(ответ)
Ответы на все вопросы, заданные в задаче, для всех возможных вариантов реплик Андрея, Бориса и Вадима приведены в таблице

10 единиц и 10 двоек
(ответ)
Для каждого из двух участников игры возможны три варианта хода:
зачеркнуть две единицы;
зачеркнуть две двойки;
зачеркнуть одну единицу и одну двойку.
Ситуация на доске после каждого из этих вариантов приведена в таблице
Из таблицы 8 видно, что при любой последовательности ходов количество единиц как было четным, так им и останется (или когда-то станет равно 0). Это означает, что на доске никогда не может остаться единица, т.е. в любом случае выиграет второй участник.

Шоколадка
(ответ)
Если проанализировать зависимость числа разломов R от количества долек шоколадки D (см. рис. 1), то можно установить, что R= D-1







Следовательно, в шоколадке 8 х 6 придется сделать 47 разломов, т.е., как бы не действовали участники игры, при 48 дольках шоколадки последний разлом всегда сделает тот, кто начал (поэтому задача и названа шуткой).

Антиквар и 99 монет
(ответ)
Задача 2. Сначала положим на две чашки весов по 13 монет, затем (если весы находятся в равновесии) уберем их и положим по 11 из еще не брав­шихся монет, затем по 9, 7, 5, 3 и 1 до тех пор, пока одна из чашек не пере­весит. Если такого не произойдет, то после седьмого взвешивания (когда на чашках весов будет по одной монете) останется одна, 99-я по счету, моне­та, которая во взвешиваниях не участвовала. Она и является фальшивой.
Сложнее, если при каком-то взвешивании какая-то чашка весов пере­весила. Прежде всего ясно, что в этот момент фальшивая монета лежит в другой чашке. Составим табличку

Антиквар и 99 монет
(ответ)
Итак, при каком-то, k-м, взвешивании мы можем выявить n монет, среди ко­торых находится искомая фальшивая. Можно записать, что п =(7 - k)* 2 + 1. Получается, что мы пришли к задаче нахождения среди (7 - k)* 2 + 1 монет фальшивой монеты за (7 - k) взвешиваний (так как k взвешиваний уже проведе­но, причем каждая монета в рассматриваемой группе взвешивалась один раз).
Введем новую величину m = 7- k. Тогда только что сформулированная задача сводится к следующей: среди (2m + 1) монет найти фальшивую монету за m взвешиваний (среди трех монет за одно взвешивание, среди пяти монет — за два, … среди тринадцати — за 6). При этом никакую мо­нету нельзя взвешивать более одного раза. Такую задачу мы уже решали (см. решение предыдущей задачи).
Ее можно решить так. Надо все монеты, кроме одной; разбить на m пар и последовательно сравнивать веса монет каждой пары — для этого пона­добится m взвешиваний. Если при каком-то взвешивании равновесие нарушится, то более легкая монета и является фальшивой. В противном случае фальшивая монета — оставшаяся "без пары".

На этом всё! Спасибо за внимание!