Теория и методика преподавания раздела "Алгоритмизация и программирование" в школьном курсе информатики
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?;
) определить необходимый набор исходных данных для решения задачи.
В качестве примера задачи первого типа можно использовать алгоритм игры Баше, рассматриваемый в учебниках [6, 8, 15]. В книгах [8, 15] правила игры определены так: в игре используются 7, 11, 15, 19 предметов. За один ход можно брать 1, 2 или 3 предмета. Проигрывает тот игрок, который берет последний предмет. Предлагается алгоритм выигрыша для первого игрока. В книге [6] правила несколько другие. В игре используются 11, 16, 21, 26,... предметов. За один ход можно брать от 1 до 4 предметов. Рассматривается алгоритм, благодаря которому всегда выигрывает игрок, берущий вторым.
После того как ученики поиграли в эту игру по тем правилам, что описаны в учебнике, можно предложить им несколько заданий аналитического характера на тему игры Баше. Задания могут быть предложены в качестве домашней работы.
Задача 1. Разгадать загадку алгоритма, т. е. объяснить, почему второй игрок всегда выигрывает (для варианта [6])?
Решение. По данным правилам второй игрок будет всегда выигрывать, если общее число камней определяется формулой:
N= 5k + 1
Здесь k - любое натуральное число.
Задача 2. Составить алгоритм, по которому игрок, делающий первый ход, может выиграть в том случае, если соперник не знает выигрышной тактики.
Решение. Необходимо перехватить инициативу, т.е. оказаться в положении второго игрока, который дополняет предыдущий ход соперника до 5 камней. Это возможно лишь в случае ошибки соперника. Начать игру можно так:
. Взять 1 камень.
. Предоставить ход сопернику; соперник взял n камней.
. Если n + 1 < 5, то взять 5 - (n + 1) камней.
. Предоставить ход сопернику.
И далее играть по выигрышному алгоритму для второго игрока.
Следующая задача требует от учеников незаурядных математических навыков.
Задача 3. Попробуйте провести математический анализ игры Баше в общем случае для N камней. Определите правила игры (т. е. сколько камней можно брать за один ход), при котором имеется выигрышный алгоритм. Опишите этот алгоритм в виде последовательности команд.
Решение. Выигрышный алгоритм для второго игрока можно построить только в тех случаях, когда исходное число камней (N) представимо в виде
= X * K+ 1
где Х и К - натуральные числа. По правилам игры за один ход можно брать от 1 до X - 1 камней. Второй игрок будет всегда выигрывать, если своим ходом он будет дополнять число камней, взятых соперником, до X. Например, пусть N = 25. Это значение можно представить: 25 = 4 * 6 + 1.
Следовательно, правило игры должно быть таким: за один ход можно брать 1 - 2 - 3 камня. А для того, чтобы второй игрок всегда выигрывал, в свой ход он должен дополнять ход соперника до 4 камней.
Следующая задача относится ко второму типу из приведенной выше классификации.
Задача 4. Назвать исполнителя следующего вида работы - выдача заработной платы; определить СКИ исполнителя,
Решение. Очевидно, исполнителя можно назвать Кассир. Система команд, которые он должен уметь выполнять, следующая:
найти в ведомости получателя;
посчитать деньги;
выдать деньги.
В задачах такого типа нужно учить учеников разбивать работу исполнителя на сравнительно простые действия, которые требуют формального исполнения. Команда выдать зарплату не удовлетворяет таким требованиям.
При построении СКИ решаются две проблемы: проблема элементарности команд и проблема полноты системы команд. Система команд исполнителя называется полной, если она содержит весь минимально-необходимый набор команд, позволяющий построить любой алгоритм в том классе задач, на который ориентирован исполнитель.
Рассмотрим еще один пример задания второго типа.
Задача 5. Описать систему команд исполнителя Геометр, который мог бы выполнять геометрические построения с помощью циркуля и линейки.
Решение. Ученикам знаком класс задач, которые в геометрии называются задачами на построение с помощью линейки, циркуля и карандаша. Полной системой команд для исполнителя Геометр является следующий список:
. Провести отрезок прямой между двумя данными точками.
. Установить раствор циркуля, равный длине данного отрезка.
. Установить ножку циркуля в данную точку.
. Провести окружность.
. Выделить общие точки двух линий (пересечения или касания). Обратите внимание на элементарность каждой команды. Делить их на более простые не имеет смысла.
Следующая задача относится к третьему типу.
Задача 6. Записать для Геометра алгоритм решения следующей задачи: дан отрезок АВ; построить окружность, для которой отрезок АВ является диаметром.
Решение.
Алгоритм ОКРУЖНОСТЬ ДАННОГО ДИАМЕТРА
начало
установить ножку циркуля в т. А
установить раствор циркуля, равный АВ
провести окружность
установить ножку циркуля в т. В
провести окружность
выделить точки пересечения окружностей: т. С и т. D
провести отрезок CD
выделить точку пересечения АВ и CD: т. О
установить ножку циркуля в т. О
установить раствор циркуля, равный 0В
провести окружность
конец
Анализируя этот пример, следует подчеркнуть то, что данный алгоритм удовлетворяет всем основным свойствам: понятности, точности, конечности; благодаря чему может исполняться формально.
Урок 2
Тема: Использование языка Паскаль в программировании
Изучение языка программирования происходит в контексте решаемых задач, т.е. новые средства языка вводятся по мере необх