Информатика для детей: сортируем контейнеры от Киндер Сюрприза

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

Используя контейнеры от киндеров и лоток для яиц очень легко дать ребенку представление о массивах данных и о том, что такое алгоритмы сортировки. Уж простите, что я пугаю вас этими сложными словами – во мне проснулся прикладной математик ? Сейчас я объясню все это “человеческими” словами. Так, как я рассказывала Кате и Вите. Причем, передо мною стояла задача, с одной стороны, просто познакомить Катю с новыми терминами и понятиями из области программирования и научить выполнять определенные алгоритмы, а с Витей мне надо было написать программу и объяснить ему кое-какие вещи об устройстве компьютерной памяти и представления в ней данных. Это трудно сочетать для столь разновозрастных детей (ведь Кате 6, а Вите скоро 14), но, вроде, оба слушали, оба все поняли, ответили потом на мои вопросы, задавали свои и при этом не заскучали, что самое главное ?

Для каждого элемента выделяется определенное место для его хранения (ячейка памяти) – у нас ее будет изображать ячейка яичного лотка. Набор таких ячеек, имеющий фиксированную длину (у нас это весь яичный лоток), в котором однородные элементы расположены друг за другом, называется массивом данных. Существует и другие способы хранить и упорядочивать информацию в памяти компьютера (например, динамический массив, список и т.д.), но мы о них в этот раз говорить не будем. Сегодня мы разбираемся только с простейшим видом массива.

Чтобы компьютер мог воспользоваться нужным элементом, ему нужно его как-то найти и к нему “обратиться“. Для этого в массиве каждому элементу присваивают номер – его индекс. По индексу будет легко найти адрес ячейки и взять оттуда нужный элемент.

Если у нас в лотке выложен только один ряд из киндеров (это называется одномерный массив), то мы можем обращаться к ним по их порядковому номеру в ряду. Например, киндер №1, киндер №2 и т.д.

Мы с Катей попрактиковались в нахождении нужного элемента массива – это просто надо доставать из яичного лотка киндер по тому номеру, который я давала.

Но если у нас заполнены все два ряда лотка – это уже двумерный массив (а может быть и трехмерный, если это ящик с яйцами, где есть еще и слои лотков). И тогда, чтобы пропасть к информации в нужной ячейке, номера в ряду недостаточно. Нужно добавить второй индекс, который будет нам говорить о том, в каком ряду надо искать информацию. Т.е. в индекс записывать еще и номер ряда. Значит, чтобы найти киндер с индексом 21, нам надо найти второй ряд и взять из этого ряда первый контейнер. 

Катя быстро поняла, как это делать. А потом я ее спросила, где она еще видела в жизни подобные массивы? Оказывается, они нам хорошо знакомы! Это и зрительный зал, когда к каждому месту в нем доступ осуществляется по билету с двумерным индексом: номер ряда и номер места в нем. А еще  это может быть шахматная доска. Там у каждой клетки тоже есть индекс: цифра, обозначающая ряд и латинская буква, обозначающая столбец. Например, Е4 или F8. То же самое в игре “Морской бой”: мы получаем доступ к каждому элементу массива (клеточкам игрового поля) по его индексу, состоящему из буквы и цифры.

А теперь, когда основные понятия мы усвоили, пора переходить к собственно самим алгоритмам сортировки данных. Ведь будет удобно, если наша информация в памяти будет лежать не как попало, а разложенная по какому-то признаку. 

В нашем случае у Кати была задача разложить контейнеры из под киндера в порядке убывания веса. Еще одно условие – из лотка (массива) контейнеры выкладывать нельзя. Единственное, что можно делать, это сравнивать в руках два элемента и при необходимости менять их местами в лотке. Ведь никакого внешнего пространства у компьютера нет и ему свои данные переложить некуда. Хотя бывают алгоритмы, в которых заводится дополнительная память (например, берется еще один яичный лоток и там происходят временные перемещения), но мы сейчас рассматриваем самый простой случай. 

Катя с энтузиазмом взялась за дело и быстро с ним справилась. Я попросила ее объяснить, как она это делала – т.е. рассказать алгоритм, по которому она действовала. В результате мы выяснили, что она интуитивно пользовалась алгоритмом сортировки, который называют “алгоритм поиска минимума/максимума“.

Вкратце, алгоритм работает так: по-очереди взвешиваем в руках все контейнеры и выбираем среди них самый тяжелый. 

Он и должен стать первым. Но первое место может быть уже занято. Тогда мы просто меняем местами контейнеры – самый тяжелый идет на первое место, а тот, что раньше там был, идет на место самого тяжелого. Дальше мы находим самый тяжелый контейнер из еще не сортированных (то есть взвешиваем все, начиная со второго номера). И снова найденный ставим теперь уже на второе место, меняясь с тем что там был местами. И т.д., пока не дойдем до конца лотка. Катя, конечно, упрощала себе жизнь, просто запоминая, где лежит контейнер какого веса, и уже многие этапы сортировки проходя в уме. Но у компьютера-то нет ума, поэтому ему приходится делать все “по-честному”. В результате ему приходится много раз “пробегать” массив до конца, заново сравнивая его элементы.

Кроме Катиного есть и другие алгоритмы сортировки. Они могут отличаться от данного сложностью (количеством операций, которое надо проделать), количеством места, в котором хранятся промежуточные результаты,  или временем, которое понадобится для работы этого алгоритма.

Например, пузырьковая сортировка.

Алгоритм действий тут такой (это я все объясняла, показывая, а потом Катя самостоятельно этим способом отсортировала контейнеры от киндера по возрастанию веса и по убыванию веса).

Берем первый киндер и сравниваем его с соседним. Если он легче, он перемещается на место соседа. Потом сравниваем его со следующим соседом, если он опять легче, он снова переходит на место соседа. И так до конца лотка. Если же он оказался тяжелее соседа, то мы его оставляем на том же месте, а дальнейшее сравнение таким же образом проводим со следующим за ним контейнером. В результате более легкие баночки как бы всплывают к концу лотка  – отсюда и название “пузырьковая сортировка”.

А в конце я попросила уже не Катю, а Витю подумать, как бы выглядели эти алгоритмы, если писать программу для сортировки элементов массива на компьютере. Мы с ним пишем команды пока просто блок-схемами, потому что, несмотря на то, что он уже окончил 8 классов школы, предмета “информатика” у них еще нет, и языков программирования он не знает (хотя уже написал свою собственную программу – компьютерную игру по мотивам “Стар Трек”). 

Парадокс: Катя, которая идет в школу в этом году, информатику изучать начнет еще в начальной школе. Так что может оказаться, что они с Витей окажутся одного уровня знаний по этому предмету, несмотря на разницу в возрасте))) И тогда мне будет гораздо легче проводить занятия с ними обоими вместе)))

А вот тут можно посмотреть другие попытки моих детей освоить программирование: Компьютерная игра про собачку (на скретче), Компьютерная игра “Стар трек”.(на Game Maker), Интерактивная презентация о Ёлке на PowerPoint, Как делаются 3D мультфильмы