23 мая 2009 г.

Три программы

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

Вообще, на начальном этапе увлечь - это самое важное. Не столько стоит уделять внимание конкретным технологиям, которые осваивает чадо, сколько самому факту - если ребёнку интересна задача, то он осваивает что угодно в сотни раз быстрее и глубже.

Итак, задачи:

1. «Быки и коровы». Правила классические: один задумывает, например, четырёхзначное число, а другой пытается его угадать. Игра проходит так:
а) угадывающий называя свою версию (делает ход),
б) загадавший сообщает, сколько цифр из версии совпало с цифрами загаданного числа по позиции (это количество быков), а сколько совпало по значению, но не совпало по месту (количество коров).
в) если угадывающий назвал загаданное число (тест совпал с загадкой), то игра прекращается, иначе возвращаемся к пункту (а) - угадывающий пробует назвать другое число.

Поясню для тех, кто не знал этой игры. Пусть загадано число 9245, а угадывающий делает ход 1234. Тогда ему приходит следующий ответ от загадавшего: 1 бык (совпали вторые цифры по позиции) + 1 корова (так как в обоих числах есть четвёрки, но они на разных позициях). Это очень полезная информация для отгадывающего, теперь он знает, что среди цифр 1, 2, 3 и 4 ему интересны две, причём одна из них уже стоит на своём месте.

Обычно люди играют в «Быки и коровы» словами (например, пятибуквенными или шестибуквенными), но с компьютером это не так интересно (так как он может делать перебор по словарю), поэтому пусть он пока оперирует числами.

Цель в игре понятна: угадать число за минимальное количество ходов. Проверять программу тоже понятно как: попробовав загадать все возможные числа (их мало - всего 10000), набрать статистику: среднее и максимальное количество попыток на угадывание.

Хорошо, когда этой же задачкой увлекаются несколько школьников. Тогда у них развивается конкуренция: один пишет простейшего игрока, который гарантированно справляется с задачкой за 33 хода, а другой неожиданно приносит версию, которой хватает 27 ходов. Тогда первый отвечает очередным улучшением алгоритма - достигая ещё более радикального снижения среднего числа попыток и т. д. Игра интересная, в ней есть, где думать. Кстати, она приучает к тому, что полезно сначала человеческими мозгами сыграть несколько сотен партий, а уже потом садиться за клавиатуру реализовывать что-то :)

2. «Тетрис» и «Падликс» Сначала пишется обычный тетрис, который состоит из двух компонент:
а) Игровой сервер. Он хранит состояние стакана, положение текущей фигуры, набранные очки. Он же выбирает случайно следующую фигуру, когда текущая фигура коснулась дна или других элементов в стакане.
б) Игрок. На начальном этапе он просто принимает команды с клавиатуры (повернуть, сдвинуть или уронить текущую фигуру).

Когда это сделано, возникает естественный соблазн - сделать компьютерного игрока, чтобы машина играла в тетрис сама с собой. Сначала пишутся простейшие игроки, которые ставят фигуры «как попало», но постепенно удаётся создавать всё более смышлёные программы, которые уверенно разгребают последовательности из десятков тысяч фигур. Здесь, опять же, очень хорошо, когда есть единомышленники, создающие конкурирующих игроков. Можно скармливать одну последовательность фигур двум или более игрокам, наблюдая за качеством их работы (для этого обычно улучшают игровой сервер, чтобы он отображал одновременно два или три стакана, а фигуры в них отправлял одинаковые).

Уже на этом этапе есть масса интересной исследовательской деятельности, но можно пойти дальше. А что если следующая фигура в нашем тетрисе будет генерироваться не случайно, а специальным злым роботом «Падликс»? Человек, который наблюдал за работой играющего в тетрис робота, наверняка замечал, что есть последовательности фигур, с которыми тому трудно справиться. Зная это, можно делать свою программу, которая именно такие последовательности начнёт формировать (и вызывать её игровым сервером вместо генератора случайных чисел).

Здесь открываются новые просторы для улучшения основного игрока: хочется сделать так, чтобы свой игрок в тетрис, получая фигуры от своего «Падликса» набирал много очков, а вражеский игрок на этой же последовательности фигур быстро заваливал стакан. Новый виток конкуренции провоцирует разработку новых умных алгоритмов. Это весело и интересно, поэтому может длиться многими месяцами. Результат очевиден:
а) ребёнок осваивает язык программирования до такого уровня, что уже не замечает сложностей при реализации непростых алгоритмов;
б) большой опыт отладки относительно сложных приложений толкает школьника к более аккуратному программированию (чтобы быть уверенным почти во всех своих строчках, а не выискивать потом неделями ошибки);
в) десятипальцевый слепой метод осваивается сам собой (у меня примерно так было :)

Первые две программы были о математических алгоритмах, которые могут быть близки далеко не всем. А следующая подойдёт, например, филологам-полиглотам:

3. «Умный тренажёр». Классе в шестом-седьмом у меня была проблема с запоминанием неправильных английских глаголов, поэтому я написал тренажёр, который разными способами предлагал показать, какие глаголы я знаю, а какие ещё надо поучить. Важный момент - правильный подход к трате времени: если я недавно правильно отвечал на данный вопрос, то тренажёр его повторит не скоро, а если были ошибки, то вопрос по тому же глаголу будет скоро задан ещё несколько раз в различных вариациях. Здесь можно придумать много хитроумных способов проверять знания, поэтому простор для творчества огромен.

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

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

Хороших выходных!

8 комментариев:

  1. Был как-то даже международный конкурс по программированию компьютерных противников. Суть как и с тетрисом, но вместо тетриса старый добрый bomberman.

    Игрались когда-то :)

    ОтветитьУдалить
  2. Анонимный25.05.2009, 12:08

    Вам, возможно, будет интересен вот этот обзор: http://habrahabr.ru/blogs/programmers_games/59784/

    ОтветитьУдалить
  3. Arseni, да, я тоже видел несколько подобных конкурсов. Но интересен скорее сам перечень задачек, которые уже увлекали детей так, что их было не оторвать от изучения книжек об алгоритмах и языках программирования.

    Уважаемый аноним, Вам тоже спасибо за ссылку.

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

    ОтветитьУдалить
  4. Илья, а что развивающее можно найти для взрослого относительно развитого человека лет 25? А то читаю про тетрис и слюной исхожу - в детстве так и не "напрограммировался"

    ОтветитьУдалить
  5. Я вот очень хотел написать программку для решения японских кроссвордов. Простые решать не проблема, а вот со сложными не всё так просто и очевидно.

    ОтветитьУдалить
  6. Grad, кроме выше предложенного варианта http://habrahabr.ru/blogs/programmers_games/ (я надеюсь, он будет ещё развиваться), могу порекомендовать следующее:

    1) блог http://dfyz.livejournal.com/ - его автор (Иван) постоянно участвует в различных программерских интересных конкурсах, делая подробные отчёты. Там есть и одиночные, и командные варианты, с ограничением на язык программирования и почти без ограничений. Почитайте его записи за последний год - найдёте много интересного!

    2) Проект "Лаборатория интеллектуальных игр". Посмотрите на странице http://eq.ur.ru/main.pl?val=ShowGameList варианты, у которых есть пункт "Правила для программ заочных турниров" (это значит, что есть повод создавать своего игрока). Кстати, анонсы новых конкурсов по этому проекту выходят в блоге http://fdo-eq.livejournal.com/

    3) Ветка форума РСДН "Этюды для программистов" http://rsdn.ru/forum/etude/ - там порой попадаются интересные темы

    Пишите, пожалуйста, когда ещё найдёте путёвые ресурсы по этой теме!

    Arseni, спасибо за идею с решателем японских кроссвордов. Я в своё время делал решатель автобусных билетиков, но японские кроссворды должны быть сложнее.

    ОтветитьУдалить
  7. http://topice4.blogspot.com/2009/08/blog-post.html

    ОтветитьУдалить