Задачник по программированию для школы

Листая старую тетрадь...

Да, нравится мне эта песня, но сейчас, не об этом...

Итак, просматривая свои архивы, нашел свой задачник по программированию — ну, почему бы ни поделиться.

На момент написания, для решения задач планировалось использовать Turbo Pascal, время прошло, и эта программа значительно устарела, предлагаю заменить ее на PascalABC.NET – отличная штука, специально создана для обучения программированию, сочетает возможности старого Turbo Pascal и Delphi и много других вкусностей.

Вступление. (которое, можно пропустить)

Задачи здесь, разной сложности, ну, например, такая шутка:

«Все, внимание!!! Всякий кто решит данную задачу за 45 минут, получит годовую 5 не только по информатике, но и по математике. Записываем:

Доказать, что для любых не нулевых значений переменных a, b, c : integer не существует решения следующего уравнения, при n > 2.

aⁿ + bⁿ = cⁿ

- Что ты хочешь сказать, Вова?

… ... ...

- Хорошо, Вова, - молодец! За знание классики + 5.

- А почему не годовая?

- Но, ты же не привел доказательства...»

Часто у «продвинутых» учеников возникает вопрос:

- А чё мы должны учить этот древний, никому не нужный Pascal?

Ну, давайте, сравним простейший код:

C++

Pascal

#include <iostream>

#include <cstdlib>

using namespace std;

int main()

{

cout << <Hello, world!< << endl;

system(pause);

return 0;

}

begin

Writeln('Hello, World!');

end.

И дело не в том, что текст на C длиннее.

Учащийся должен понимать, что и как, делает программа.

Если объяснение программы на Паскале займет 2 минуты и можно идти дальше, то в случае С, вы убьете 45 минут на объяснение совершенно не нужной начинающему информации, и совершенно запутаете школьников, т.е - если вам надобно вызвать у учащихся отвращение к программированию то начинайте учить их с С++ или C#.

А после Паскаля, любой си образный язык пойдет «влегкую».

Объясните любопытному, что все процедурные языки, близнецы братья (но Паскаль проще!!!). Для профессионального программиста не составляет большой проблемы перейти с PHP на Java.

Но, как-то, расскажите, что есть не только процедурные языки. Например, о языке Prolog, или такие вкусности как Форт (англ. Forth) или Эйфория.

Но вернемся к нашим баранам (я не имел ввиду учащихся), как уже сказано, задачи разного уровня. Я сознательно не размечаю сложность, во-первых, это очень субъективно, во-вторых ученик должен учиться соизмерять свои возможности, и не отчаиваться если сейчас задача не по силам. Многие задачи не уложатся в один урок, а некоторые, могут развиваться от "простого к сложному".

Например:

(1)

Двоичный тренажер

а) Программа задумывает случайное число от 0 до 15 и выдает его в двоичном виде, пользователь должен ввести десятичный(или шестнадцатеричный) аналог.

Полезно решить эту задачу, сюда входят несколько подзадач:

' преобразование числа в двоичный вид

'' контроль введенных пользователем символов

''' разработка интерфейса программы (внешний вид, реакции на ошибки, поощрительные сообщения и т.п.)

Кроме того, такая программка полезна для игрового запоминания двоично-шестнадцатеричных чисел.

б) Программа должна анализировать время ожидания ответа пользователя, и выдавать оценку за выполнение, допустим, 20 заданий, учитывая число ошибок и суммарное время затраченного на ответы.

в) «Случайное число» человек и машина понимают по-разному, например:

2 2 2 2 2 2 2

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

Давайте, я расскажу, как решил эту задачу, во времена оны.

Задаем байтовый массив[размером в заданных диапазон]

начинается цикл 1.

заполняем массив нулями;

цикл 2. задумывание числа

программа задумывает число из заданного диапазона

если в соответствующей ячейке массива 0, то записываем туда 1 и завершаем цикл 2 задумывания числа, в ином случае повторяем цикл 2.

Если написать только вышесказанное, то получим бесконечный цикл!!! (что очень полезно для начинающего программиста) Посему введем переменную «счетчик успешных попыток задумывания числа» и при достижении максимального числа возможных вариантов переходим к началу цикла 1 (т. е. заполнение массива нулями)

Ну, а дальше, как и раньше вывод на экран... ожидание ответа...

Еще один нюанс, со «случайным числом». Если вы запустите программу несколько раз, то увидите, что задумываются одни и те же числа!!! Как с этим бороться? Программист, должен знать эту мелочь.

г) Байт изображается двумя шестнадцатеричными числами. Пусть и программа задумывает по два таких числа (в этом случае рекомендации пункта в, надо основательно пересмотреть [ну например, задать два байтовых массива... не-ет не верное решение..., массив будет один но от 2 до 255...])

Ну, вот так, примерно, решаются задачи, чем дальше в лес....

Не люблю олимпиадные задачи, как правило, они слишком «академичны», но это естественно, у олимпиады совершенно иные задачи (т. е. не обучение)

Задачи для школьника должны быть веселы! На экране должно что-то прыгать, бегать, хихикать...

В каждом маленьком ребенкеИ мальчишке и девчонкеЕсть по двести грамм взрывчаткиИли даже полкило!Должен он бежать и прыгатьВсе хватать, ногами дрыгатьА иначе он взорвется, трах-бабах !И нет его!

Веселые задачи

Игры со строками.

Все нижеследующие программы, должны начитаться и продолжаться объяснениями пользователю, что ему следует сделать для продолжения работы программы.

(2)

Написать программу со следующим сценарием:

пользователь вводит строку, нажимает Enter и далее варианты:

а) Буквы падают в низ экрана с начала строки, одна за другой;

б) Буквы падают с конца строки;

в) Буквы падают случайным образом;

г) Буквы падают наискосок;

д) После какого либо вида падения буквы взлетают на свои места.

(3)

Написать программу, печатающую бегущую строку

варианты:

а) бегущая строка с зацикленным текстом;

б) предложение бегает от начала в конец строки и обратно;

в) бегущая строка информация в которую берется из файла.

(4)

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

(5)

Написать программу, которая напечатает строку по следующему сценарию:

а) в середине экрана появляются 2 крайние буквы строки (первая и последняя)

Затем они раздвигаются и в середину записываются две следующие (вторая и предпоследняя) и т.д. в результате строка печатается разъезжаясь из центра.

б) печатаются сначала средние буквы строки (одна или две – в зависимости четное число символов в строке или нет) затем парами печатаются остальные символы.

(6)

Написать программу, в которой строка будет печататься:

а) сверху вниз

б) снизу вверх

в) наискосок

(7)

Написать программу, в которой в середине экрана выводится строка, а затем:

а) буквы по очереди подпрыгивают на 1 или 2 позиции.

б) подпрыгивание с конца строки

г) подпрыгивание случайным образом.

(8)

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

(9)

Написать программу, объединяющую максимальное число вышеперечисленных сценариев.

(10)

Играем в шпионов.

Первый пользователь вводит строку

на следующей строке выводится ее зашифрованный вариант

зашифрованная строка сообщается другому пользователю

и он на другом компьютере ее расшифровывает.

Методы шифровки:

1 - в строке меняется четные и нечетные символы (если длина строки нечетная, она дополняется точкой).

2 - в начале печатается последний символ потом первый затем предпоследний, а потом второй и т.д.

3 - строку делим пополам (если надо дополняем точкой), а потом печатается символ из одной строки затем из другой и т.д.

Дополнительный материал:

Квадрат Полибия, Шифр Цезаря, Решето Кардано, Тарабарская грамота, Диск Энея

(11)

Римские цифры

Программа выводит число в римском стиле, пользователь вводит десятичный аналог. Для оживления программа будет выводить реакции «Долго думал», «Go to the first class», ну, на сколько хватит цензурного юмора.

(12)

Mad string

Пользователь вводит строку. При нажатии, каждой клавиши, буквы возникают в произвольных местах экрана. По нажатии Enter экран стирается(это, чисто технологический момент и стирание не должно быть заметно), затем буквы опять появляются в случайных местах экрана, а затем они начинают весело прыгать, бегать, перемешиваться но через минуту должны собраться в исходную строку. [это типичный случай, когда задачу надо решать сзади наперед]

Кстати, забавный способ, проверить правильность набора текста, методом слепой печати.

Игры с числамиПятница 13

(13)

Программа должна выдать список из 13 ближайших тринадцатых пятниц, отсчитывая от текущей даты

(14)

Угадай число

Примерный сценарий:

(компьютер) Загадано двух [трех, четырех, пяти] значное число, сколько попыток вам надо для отгадывания?

(пользователь) 8

Попытка №1

Больше

Попытка №2

Меньше

Попытка №3

Поздравляю, вы угадали, затратив 3 попытки!!

Сыграем еще (Да, Нет)?

Да

Целей, при написании такой программы, несколько:

1. сама по себе интересная работа с интерфесом программы;

2. выработка алгоритма угадывания.

3. Как итог - разработка программы с обратной задачей, пользователь задумывает число, а программа отгадывает!!!

"Натуральная" случайность

В задаче №1, я упоминал два вида случайностей «машинную» и «человеческую», давайте вспомним еще одну, пожалуй, главную, - «природную».

Найдите информацию о «нормальном распределении», не хочу пересказывать, то, что вы найдете, но там очень много вкусненького.

Задача – написать программу, которая будет генерировать случайные числа по закону нормального распределения.

Для того, чтобы убедиться в правильности работы, постройте графики используя «машинную» и «природную» случайности. Так, сказано невнятно.

Попробую подробнее...

Вот такая программа:

uses GraphABC;

const

Max = 600;

var

Mas : array[0..max] of integer;

n : integer;

begin

for var i:=1 to 200000 do

begin

n := Random(Max+1);

inc(Mas[n]);

SetPixel(25+n,Window.Height - Mas[n],clRandom);

end;

end.

Нарисует график:

Как видите, "машинная" случайность имеет "плоское" распределение. Ваша задача - сделать программу выдающую "нормальное" распределение случайности, это может выглядеть, примерно так:

Как сказал бы Кролик Винни-Пуху "Случайности могут быть разные".

Такие не простые, "простые" числа

1. Выяснить: для чего нужны простые числа, методы их определения. (Уверяю вас, они очень и очень ценны...)

(15)

2. Написать программу для нахождения простых чисел

Счастливый билет

Объясните учащимся, что в древности в автобусах покупали билеты, и на каждом билете был шестизначный номер. И в течении скучной поездки школьники искали счастливые билеты, т. е. сумма первых трех чисел в номере должна быть равна сумме оставшихся (некоторые чудаки съедали их перед экзаменом :).

(16)

Задача: подсчитать число счастливых билетов, в дальнейшем можно выяснить вероятность приобретения «счастья».

Как-то эту задачу на уроке решали двое учеников, и результат получился существенно разный, но был конец урока, и проверять алгоритмы было лень.. А ученики... сейчас, оба, и он и она, профессиональные программисты, и надеюсь, счастливы в браке.

Лирическое отступление

Большинство задач в данном сборнике рассчитано на работу в текстовом режиме. У «знатоков» закономерно возникнет вопрос:

- Зачем нам учиться программировать в устаревшем текстовом режиме.

- Ну, во-первых, мы движемся от простого… далее… сейчас наверно кто-то пишет ПО для утюга или фена, а скоро надо будет писать для зубочистки, это конечно хорошо, программистам есть работа, но учтите, аппаратные возможности таких устройств очень ограничены. Т.е. винды в кастрюлю никто засовывать не станет, и программировать на низком уровне надо будет еще много лет. Освойтесь с основами программирования в Паскале, а дальше Ассемлбер, Java, Си - да мало ли, что еще возникнет.

А, чтобы напомнить возможности текстового режима, смотрите:

Игры с графикой.

Один «информатик» способен поставить столько задач, что не справятся 10 мудрецов из 10а.

The Adventure of the Dancing Men

(17)

В начале, все просто,… а потом ООП.

Рисуем человечка.

Человечек должен иметь двигающиеся конечности. Для начала перемещаем конечности мышкой:

Перемещение мышки в направлении r - конечность сгибается в локте (колене), перемещение в направлении φ – вращение конечности вокруг точки О.

Теперь начинаем наращивать зрелищность.

а) человечек хаотично размахивает конечностями

б) на экране 10 человечков, синхронно размахивающих ручками и ножками

в) на экране толпа, каждый человечек движется независимо

(18)

А теперь вернемся к первоисточнику.

Пользователь набирает строку – на экране появляется строка пляшущих человечков.

На старт

(19)

Написать программу, которая будет имитировать счет до старта (от 9 до 0)

В качестве основы использовать такую матрицу:

В этой матрице (семи-сегментном индикаторе) будут изменяться закрашенные сегменты.

Например: цифры 6 и 2:

Теннис

(20)

Не мною придумано, но зрелищная и полезная игрушка:

Два игрока управляют двумя ракетками, по экрану бегает шарик, отражаясь от стенок и от ракеток, ведется счет

Смайлик

(21)

Написать программу, которая нарисует такое личико.

Имеется в виду, что выражение лица меняется:

а) меняется автоматически по кругу (анимация)

б) меняется в зависимости от нажатой кнопки

С новым годом

(22)

На экране рисуется зеленая елка, с игрушками свечами и т. п.

Не обязательно точно такую.

Как, слишком статично. Ничего, добавим ужастика! Пусть, вначале осыпятся игрушки, а затем и иголки — останется только елочный «скелет».

Калейдоскоп

(23)

В ведущем треугольнике появляются и начинают перемещаться, объекты случайной формы и цвета. Каждый шаг изменения (с задержкой в 1-2 секунды) отображается симметрично в остальных треугольниках.

Орнамент

(24)

В каком-то сериале, в титрах, на экране росли и развивались завитки орнамента.

В кино, художники научились делать это еще сто лет назад.

А программисту, слабо?

Совершенно не обязательно повторить именно этот орнамент, главное, чтобы на экране что-то росло, зеленело.

Игры с файлами

Пока не наступает проза жизни, все мы немножко поэты.

Колбазов "Колония. Дубликат"

(25)

Написать программу, которая при включении спрашивает имя, фамилию.

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

Если же пользователь уже работал с программой, то имитируется разговор:

'Ты что заболел, уже 3 дня мы не виделись!!!'

(или наоборот 'Слишком много сидишь за компьютером')

'Поздравляю, тебе сегодня 14 лет, 3 месяца и 5 дней'

'Как здоровье Мурки?'

или 'Передай привет Шарику'

. . .

Если программу запускает другой пользователь, то используются его данные (как видите, ничего нового — пытаемся пройти тест Тьюринга ).

Анти поле чудес

(26)

Все время толкую, что для игры в стране дураков, надо знать волшебное заклинание ОЕАНТИСРВ.

Программа читает файл, с текстом русской книги (ну например, "Война и мир"), и определяет:

* встречаемость букв в файле (в результате, должно получиться - то самое заклинание).

* встречаемость букв в начале слова

* встречаемость букв в конце слова

(27)

Заодно, написать и свое «Поле чудес» (слова для заданий, из того же файла).

(28)

Вспомним шпионские игры (10). Один учащийся пишет программу, которая зашифровывает текст простейшим цифровым кодом, для простоты пробелы и знаки препинания остаются без изменений, а символы разделяются… ну, например “/” т.е. получается что-то вроде:

23/54/27/2, 5/6 55/76/7.

Результат сохраняется в файле, и файл передается другому ученику(или ученикам).

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

HTML

(29)

Заданный текст превращается в HTML файл. Придумать методы для задания форматирования текста (ну допустим, если строка начинается с # то это заголовок, и т. д. Пусть ребята помучаются, но зато поймут смысл форматирования)

Ну, вот и все.

А что дальше? Ну, конечно же, в Интернет - там есть масса задачников, НО задачи там посерьезнее, так вот, последнее задание:

(30)

1. Научиться находить удовольствие при решении самой скучной задачи!

2. Научиться изобретать новые задачи!

Включайте вашу фантазию, и у вас возникнет множество своих красивых задач. Потому, что не затронуто еще множество тем: работа с окнами в текстовом и графическом режимах, музыкальные шкатулки, создание шуточных тестов, игр…………

End.

Печальные задачи

(печаль заключается в том, что это, не мои задачи)

Задачи взяты из различных источников.

(стр 122[1]) Какое число обозначает число КОТ

КТО

КОТ

----------

ТОК

(стр 121) Какие числа зашифрованы:

OXOXO

AXAXA

-----------

AXAXAX

Калькулятор.

Пользователь вводит два числа по 50 – 70 цифр, программа должна сложить их и вывеси результат.

(стр 17) Вирус уничтожил исключительно знаки арифметических действий ( +, -, *, / ). Можно ли узнать, что печатала программа?

repeat

x := x ?1;

y := y ? x;

z := z ? y;

writeln(x*x, y*y, z*z );

until x * x < 100;

----------------------------------

Надеюсь, все это безобразие, разбудило вашу фантазию.

Успехов.

W Cat