Статья «Метод половинного деления для начальной и средней школы»
«Метод половинного деления для начальной и средней школы».
Т. Г. Родина,
учитель информатики
МБОУ « Школа №54» г. Рязань
На уроках информатики и математики, олимпиадах и конкурсах встречаются задачи, в которых нужно использовать метод половинного деления. Этот метод проще всего изучить на примере игры «Угадай число».
Цель работы:
изучить метод половинного деления, анализирую игру «Угадай число»
привести примеры практического решения задач данным способом.
научить детей анализировать с помощью этого метода любые задачи на угадывание и решать такие задачи.
Задачи работы:
1. развить творческие и исследовательские способности;
2. раскрыть суть метода половинного деления;
3.использовать метод для решения задач;
4.узнать, как определить наименьшее число вопросов в игре.
Основные формы работы : индивидуальная, парная, фронтальная.
Учитель предлагает детям решить следующую задачу:
Вы идете в гости к другу, который живет в 16-этажном доме. Но не знаете, где именно: ни этаж, ни квартиру. Можно позвонить другу и задавать вопросы, на которые он будет отвечать да или нет. Ваши действия?
Учащиеся помладше, обычно задают такие вопросы:
- Ты живешь на 4-м этаже? Ты живешь на 10-м этаже? Поэтому угадывание происходит долго.
Дети постарше, понимают, что надо ехать на 8-й этаж и там уже спрашивать-вниз ехать или вверх и т.д. В этот момент у некоторых учеников в головах начинает рождаться представление о половинном делении. Именно поэтому, эту тему нужно разобрать подробнее и возможно не один урок. Так как этот вопрос не рассматривается в рабочей программе по информатике, то ее изучение можно вынести на внеурочную деятельность.
Итак, учитель приглашает учащихся сыграть в игру «Угадай число». Сначала учитель загадывает число от 1 до 10. Ученик отгадывает. Кто-то считает за сколько вопросов угадано число. Потом ученик загадывает, учитель угадывает и опять считаются кол-во вопросов.
Пояснение: В игре «Угадай число» участвуют двое игроков: Водящий и Угадывающий. Водящий загадывает любое число, обычно от 1 и до заранее определённого числа (например, до 10 или до 500). Угадывающий должен отгадать это число, задавая Водящему вопросы, на которые можно ответить только «Да» или «Нет».
После нескольких таких игр, учащиеся должны понять, что учитель всегда угадывает быстрее и почти всегда за определенное кол-во вопросов, и тогда учитель говорит, что сегодня на уроке они узнают секрет таких игр.
Чтобы понять метод учителя сначала нужно поговорить о сортировках.
Пусть дано множество А чисел от 1 до 10.
А (1,2,3,4,5,6,7,8,9,10)
Нужно его рассортировать.
На каждом этапе сортировки разделяем каждое множество на две части, то есть сначала разделяем исходное множество на две части, потом разделяем каждую из двух полученных частей ещё на две и т. д., пока в каждой части не останется только один элемент.
Рассмотрим два примера такой сортировки.
1 способ.
2 способ)
Учащиеся могут предложить свой способ сортировки.
- Сколько уровней в каждом примере?
- В первой сортировке -5 уровней, во второй сортировке - 9.
То есть, сортировка одного и того же множества может быть разной.
- Нас интересует способ, при котором сортировка будет произведена за наименьшее число уровней.
Попробуем разделить множество, всегда деля его примерно пополам: если в исходном множестве было чётное число элементов, то в множествах, полученных после разделения, элементов будет поровну, а если в исходном множестве было нечётное число элементов, то в полученных множествах число элементов будет различаться на 1.
Ученик выходит к доске и выполняет задание, учащиеся выполняют его в тетради самостоятельно.
Вот пример такой сортировки.
-Сколько у вас получилось уровней?
При любой сортировке данным методом у учащихся должно получиться одно и тоже число уровней. В данном случае - 4.
Работа в парах: Возьмем множество цифр от 1 до 8. Нужно рассортировать это множество любым способом сортировки
После опроса учеников какой метод они использовали и сколько уровней получилось, выясняется, что самый лучший и быстрый способ сортировки множеств-это метод половинного деления! Минимальное число уровней-3.
Обязательно делаем запись в тетрадь: метод деления пополам самый быстрый и эффективный!
Следующее задание.
1. Рассортируй множество всех гласных букв русского алфавита с помощью половинной сортировки. Сколько уровней в сортировке?
Ответ. 4 уровня.
А теперь вернемся к нашей игре. Условие те же, только задавать вопросы будем так, чтобы делить множество примерно пополам.
Игра «Угадай число»
Один из учащихся задумал натуральное число от 1 до 16 (написал его на бумаге), учитель, задавая не более 4 вопросов, отгадывает задуманное число. При этом на вопросы учителя учащиеся отвечают только “да” или “нет”. Например, задумано число 15.
Происходит диалог следующего вида:
Учитель спрашивает: 1. Задуманное число больше 8? Ответ: Да.
Учитель спрашивает: 2. Задуманное число больше 12? Ответ: Да.
Учитель спрашивает: 3. Задуманное число больше 14? Ответ: Да.
Учитель спрашивает: 4. Задуманное число больше 15? Ответ : Нет.
Учитель отвечает: Это число 15.
Такую игру проигрывают 2-3 раза, тем самым убеждаясь, что совпадений нет, а есть точный алгоритм угадывания. Предлагается проанализировать следующие вопросы:
1. Как учитель угадывает задуманное число?
2. Почему гарантировано угадывание числа за 4 вопроса?
Ответ:
1. Тот промежуток чисел, в котором находится задуманное число, следует разделить пополам и выяснить в какой половине находится это число. С уменьшенным вдвое промежутком опять поступить так же.
Так как нам надо угадать число, то нам придётся придумать всевозможные вопросы, в зависимости от ответов. Сложность в том, что заранее составить список вопросов здесь невозможно ведь каждый следующий вопрос зависит от того, как нам ответили. Поэтому придётся строить дерево вопросов. После каждого вопроса должны следовать два новых: один вопрос задается в случае ответа «Да», другой - в случае ответа «Нет».
Рассмотрим пример такого дерева вопросов для игры «Угадай число» от 1 до 8:
Вот дерево сортировки множества чисел от 1 до 8, построенное по дереву вопросов:
Итак, вопросы должны быть такими, чтобы ответы на них разделяли каждое множество примерно пополам. Используя такие вопросы, вы всегда отгадаете загаданное число, задав наименьшее количество вопросов.
Напоминаю, что такой метод поиска элемента в заданном множестве называется методом половинного деления.
I Используя метод половинного деления, построй дерево вопросов в игре «Угадай число от 1 до 16». Сколько уровней в сортировке? За сколько вопросов можно наверняка отгадать число от 1 до 16?
За 4 вопроса можно угадать цифру(16-8-4-2-1)
Заметьте, знак можно использовать строгий или нестрогий (когда само число тоже рассматривается в данном промежутке). Обычно, дети путаются именно в этом вопросе, поэтому стоит уделить внимание и разобрать на примере эту математическую тему.
За какое наименьшее число вопросов можно наверняка угадать число от 1 до 40?
Чтобы ответить на этот вопрос, строить дерево не обязательно. Достаточно построить самый длинный путь такого (последовательность множеств), ведь именно его длина равна высоте дерева. На самом деле, работу можно упростить больше: можно не выписывать все элементы каждого множества, а только сосчитать, сколько в нём элементов.
Ответ: за 6 вопросов (40-20-10-5-3-2-1)
Правила игры «Угадай букву» очень похожи на правила игры «Угадай число». В игре «Угадай букву» Водящий загадывает букву русского алфавита. Определи, за сколько вопросов можно отгадать наверняка букву в игре.
Ответ: за 6 вопросов (33-17-9-5-3-2-1)
За какое наименьшее число вопросов можно наверняка дать число от 1 до 512?
Ответ: за 9 вопросов (512-256-128-64-32-16-8-4-2-1)
Бабушка приезжает на поезде в гости, Поезд состоит из 20 вагонов. Вы не знаете, в каком вагоне бабушка. Задавая вопросы, на которые можно ответить да, нет - отгадать номер вагона. За сколько вопросов вы это сделаете?
Ответ за 5 вопросов (20-10-5-3-2-1)
Чтобы у ребят не сложилось впечатление, что метод половинного деления используется только для игр (ведь он универсальный и позволяет решать самые разные задачи), можно на завершающем этапе проекта предложить несколько математических задач, где используется так же идея. Ниже мы приводим несколько примеров таких задач.
Задача 1. Имеется стопка из 8 монет, одна из которых фальшивая (она отличается по весу от всех остальных). Как, имея чашечные весы, найти фальшивую монету за 3 взвешивания?
Решение: Делим монеты на две равные кучки. Из каждой кучки берем по 3 монеты, кладем на весы и взвешиваем. Если вес одинаковый то взвешиваем оставшиеся 1и 1 монеты и выявляем фальшивую (более легкую). Если же одна группа из трех монет легче другой, значит там есть фальшивая монета. Оставляем более легкую группу из трех монет и кладем на весы 1и 1 и действуем по предыдущему алгоритму: если вес одинаков, значит фальшива третья, а если нет, то та которая легче.
Задача 2. Имеется полоска бумаги длиной 64 см с точкой, отмеченной на ней. Как, имея только ножницы, отрезать от этой полоски кусочек длиной 1 см так, чтобы на нем находилась отмеченная точка? Какое наименьшее число разрезов для этого необходимо сделать?
Задача 3. Имеется стопка из 27 монет, одна из которых фальшивая (она легче настоящих). Как за 3 взвешивания на чашечных весах найти фальшивую монету?
В задаче 3 используется не совсем метод половинного деления, а скорее, его обобщение – деление предметов на равные кучки и выяснение, в какой кучке находится искомый предмет. Действительно, результаты взвешиваний дают нам информацию, аналогичную ответам Водящего в игре Угадай число, но одно взвешивание дает больше информации, чем ответ по типу «да – нет». Так, играя с Водящим, мы могли бы угадать фальшивую монету из трех монет наверняка за 2 вопроса. Имея вместо Водящего чашечные весы, мы можем найти из трех монет фальшивую за одно взвешивание. Возьмем 2 любые монеты из трех и положим на чаши весов. Если чаши не пришли в равновесие, то более легкая монета – фальшивая. Если чаши пришли в равновесие, то фальшивая монета – третья, которую мы не взвешивали. Именно поэтому в данной задаче удобно делить на каждом этапе все монеты не на 2, а на 3 стопки. Только в этом случае можно будет найти фальшивую монету за 3 взвешивания.
Информатике трудно существовать в школе как отдельной науке, она должна помогать другим учебным предметам в развитии познавательного интереса к предмету, в решении логических задач, в обработке результатов лабораторных работ и индивидуальных практических заданий. Школьники начинают испытывать удовлетворение, замечая, что элементы математики и информатики имеют реальное воплощение.
В ходе серии уроков на эту тему мы научились использовать метод половинного деления для угадывания. Общий алгоритм любой такой игры довольно прост – после каждого вопроса мешок, в котором содержится данный объект, должен уменьшаться в 2 раза (или почти в 2 раза, если число объектов на предыдущем этапе было нечетным). В процессе проведения эксперимента выяснили, что при такой стратегии игры мы наверняка угадаем объект за наименьшее число вопросов.
Мы узнали, как определить наименьшее число вопросов, имея число объектов в начальной позиции, но не строя дерева игры (ведь это же долго, да и объектов в начальной позиции может быть много, тогда дерево получится очень громоздким). Для ответа на данный вопрос достаточно просто смоделировать ситуацию половинного деления в игре на каждом шаге.
Графически результат можно представить в виде цепочки, каждое следующее число которой в два раза меньше предыдущей. Если число на два нацело не делится, то берем большее число. Например, для угадывания числа из интервала от 1 до 100 цепочка, содержащая число объектов, после каждого шага будет выглядеть так:
100 – 50 – 25 – 13 – 7 – 4 – 2 – 1
Таким образом, наименьшее необходимое число вопросов в данной игре – 7( исходное число не считаем)
Попробуйте и вы взять любую игру на угадывание, заранее выяснить наименьшее число вопросов и сыграть парами, пытаясь угадать объект за такое число вопросов.
Список используемой литературы.
А. Л. Семёнов, Т. А. Рудченко. Тетрадь проектов. Информатика 5 , - М. «Просвещение» Институт новых технологий, 2006.
https://www.bibliofond.ru/view.aspx?id=66337 ( Библиофонд)
http://old.prosv.ru/ebooks/Binder3.pdf
http://xn--i1abbnckbmcl9fb.xn--p1ai/%D1%81%D1%82%D0%B0%D1%82%D1%8C%D0%B8/100219/
http://files.school-collection.edu.ru/dlrstore/38e8fa00-ed84-c4ed-b8ac-b4d5ad8e1572/lesson_37-38.htm
