Продолжаю рассказ о развивающих играх для детей, для которых можно использовать Киндер Сюрпризы. Первую часть можно увидеть
ТУТ, а игры с фигурками от шоколадных яиц можно посмотреть в статье “
Как делают игрушки для Киндер Сюрпризов?“. В постах по этим ссылкам вы найдете развивающие игры для дошкольников на логику, внимание и память. А в этом посте я хочу показать несколько более сложное занятие, которое подойдет для старших деток и даже подростков. Ведь сейчас мы будем изучать элементы программирования.
Используя контейнеры от киндеров и лоток для яиц очень легко дать ребенку представление о массивах данных и о том, что такое алгоритмы сортировки. Уж простите, что я пугаю вас этими сложными словами – во мне проснулся прикладной математик 🙂 Сейчас я объясню все это “человеческими” словами. Так, как я рассказывала Кате и Вите. Причем, передо мною стояла задача, с одной стороны, просто познакомить Катю с новыми терминами и понятиями из области программирования и научить выполнять определенные алгоритмы, а с Витей мне надо было написать программу и объяснить ему кое-какие вещи об устройстве компьютерной памяти и представления в ней данных. Это трудно сочетать для столь разновозрастных детей (ведь Кате 6, а Вите скоро 14), но, вроде, оба слушали, оба все поняли, ответили потом на мои вопросы, задавали свои и при этом не заскучали, что самое главное 🙂
|
Изучаем информатику на примере яичного лотка и контейнеров от Киндера с пуговицами |
Итак, в компьютере всякая информация (тексты, картинки, видео, любые другие данные) хранится в его памяти. Да не целиком, а разбитая на множество “единиц хранения”. Например, картинка в памяти разбивается на набор пикселов (точечек, которые как элементы мозаики потом и складываются в нужную картинку). У нас информацию будет олицетворять контейнер от киндера, в котором находится некоторое количество пуговиц. (В процессе объяснения лучше сразу все показывать на киндерах и проделывать с ними все названные манипуляции в реальности).
Для каждого элемента выделяется определенное место для его хранения (ячейка памяти) – у нас ее будет изображать ячейка яичного лотка. Набор таких ячеек, имеющий фиксированную длину (у нас это весь яичный лоток), в котором однородные элементы расположены друг за другом, называется массивом данных. Существует и другие способы хранить и упорядочивать информацию в памяти компьютера (например, динамический массив, список и т.д.), но мы о них в этот раз говорить не будем. Сегодня мы разбираемся только с простейшим видом массива.
Чтобы компьютер мог воспользоваться нужным элементом, ему нужно его как-то найти и к нему “обратиться“. Для этого в массиве каждому элементу присваивают номер – его индекс. По индексу будет легко найти адрес ячейки и взять оттуда нужный элемент.
Если у нас в лотке выложен только один ряд из киндеров (это называется одномерный массив), то мы можем обращаться к ним по их порядковому номеру в ряду. Например, киндер №1, киндер №2 и т.д.
Мы с Катей попрактиковались в нахождении нужного элемента массива – это просто надо доставать из яичного лотка киндер по тому номеру, который я давала.
Но если у нас заполнены все два ряда лотка – это уже двумерный массив (а может быть и трехмерный, если это ящик с яйцами, где есть еще и слои лотков). И тогда, чтобы пропасть к информации в нужной ячейке, номера в ряду недостаточно. Нужно добавить второй индекс, который будет нам говорить о том, в каком ряду надо искать информацию. Т.е. в индекс записывать еще и номер ряда. Значит, чтобы найти киндер с индексом 21, нам надо найти второй ряд и взять из этого ряда первый контейнер.
Катя быстро поняла, как это делать. А потом я ее спросила, где она еще видела в жизни подобные массивы? Оказывается, они нам хорошо знакомы! Это и зрительный зал, когда к каждому месту в нем доступ осуществляется по билету с двумерным индексом: номер ряда и номер места в нем. А еще это может быть шахматная доска. Там у каждой клетки тоже есть индекс: цифра, обозначающая ряд и латинская буква, обозначающая столбец. Например, Е4 или F8. То же самое в игре “Морской бой”: мы получаем доступ к каждому элементу массива (клеточкам игрового поля) по его индексу, состоящему из буквы и цифры.
А теперь, когда основные понятия мы усвоили, пора переходить к собственно самим алгоритмам сортировки данных. Ведь будет удобно, если наша информация в памяти будет лежать не как попало, а разложенная по какому-то признаку.
В нашем случае у Кати была задача разложить контейнеры из под киндера в порядке убывания веса. Еще одно условие – из лотка (массива) контейнеры выкладывать нельзя. Единственное, что можно делать, это сравнивать в руках два элемента и при необходимости менять их местами в лотке. Ведь никакого внешнего пространства у компьютера нет и ему свои данные переложить некуда. Хотя бывают алгоритмы, в которых заводится дополнительная память (например, берется еще один яичный лоток и там происходят временные перемещения), но мы сейчас рассматриваем самый простой случай.
Катя с энтузиазмом взялась за дело и быстро с ним справилась. Я попросила ее объяснить, как она это делала – т.е. рассказать алгоритм, по которому она действовала. В результате мы выяснили, что она интуитивно пользовалась алгоритмом сортировки, который называют “алгоритм поиска минимума/максимума“.
Вкратце, алгоритм работает так: по-очереди взвешиваем в руках все контейнеры и выбираем среди них самый тяжелый.
|
Так происходит сравнение веса 🙂 |
Он и должен стать первым. Но первое место может быть уже занято. Тогда мы просто меняем местами контейнеры – самый тяжелый идет на первое место, а тот, что раньше там был, идет на место самого тяжелого. Дальше мы находим самый тяжелый контейнер из еще не сортированных (то есть взвешиваем все, начиная со второго номера). И снова найденный ставим теперь уже на второе место, меняясь с тем что там был местами. И т.д., пока не дойдем до конца лотка. Катя, конечно, упрощала себе жизнь, просто запоминая, где лежит контейнер какого веса, и уже многие этапы сортировки проходя в уме. Но у компьютера-то нет ума, поэтому ему приходится делать все “по-честному”. В результате ему приходится много раз “пробегать” массив до конца, заново сравнивая его элементы.
Кроме Катиного есть и другие алгоритмы сортировки. Они могут отличаться от данного сложностью (количеством операций, которое надо проделать), количеством места, в котором хранятся промежуточные результаты, или временем, которое понадобится для работы этого алгоритма.
Например, пузырьковая сортировка.
Алгоритм действий тут такой (это я все объясняла, показывая, а потом Катя самостоятельно этим способом отсортировала контейнеры от киндера по возрастанию веса и по убыванию веса).
Берем первый киндер и сравниваем его с соседним. Если он легче, он перемещается на место соседа. Потом сравниваем его со следующим соседом, если он опять легче, он снова переходит на место соседа. И так до конца лотка. Если же он оказался тяжелее соседа, то мы его оставляем на том же месте, а дальнейшее сравнение таким же образом проводим со следующим за ним контейнером. В результате более легкие баночки как бы всплывают к концу лотка – отсюда и название “пузырьковая сортировка”.
|
Контейнеры от киндеров расставлены в нужном порядке |
А в конце я попросила уже не Катю, а Витю подумать, как бы выглядели эти алгоритмы, если писать программу для сортировки элементов массива на компьютере. Мы с ним пишем команды пока просто блок-схемами, потому что, несмотря на то, что он уже окончил 8 классов школы, предмета “информатика” у них еще нет, и языков программирования он не знает (хотя уже написал свою собственную программу –
компьютерную игру по мотивам “Стар Трек”).
|
Блок-схема алгоритма сортировки данных в массиве. Не очень аккуратно, зато работает! |