Обеспечение всеобщей компьютерной грамотности (стр. 4 из 6)

Темы работ по программированию разбиваются на три группы:

системные задачи; задачи вычислительной математики; информационные, или нечисленные, задачи (разумеется, некоторые задачи находятся «на стыке»).

Системные задачи, требующие глубокого знания работы ЭВМ, обычно привлекают немногих сильных учеников. Желательно предоставлять им возможность индивидуальной работы

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

Численный метод представляет собой полностью описанный алгоритм, и изучение его сопровождается составлением и подробным разбором схемы алгоритма и программы, а часто и отладкой этой программы в качестве практического задания. Поэтому задание типа «Составьте программу решения данного уравнения методом хорд» ко времени прохождения практики является слишком простым и, главное, не требует самостоятельной творческой работы учащегося. Кроме того, курс вычислительной математики в школе в силу нехватки учебного времени и отсутствия развитого математического аппарата носит неполный характер и, как правило, оставляет в стороне вопросы сходимости, точности и т. п. Это может привести к неожиданным сложностям при решении практических задач. Отметим также, что если в курсе вычислительной математики изучается большое количество приближенных методов, то в школьной практике в отличие от научной применяются в основном точные аналитические методы, что достигается искусственным сужением класса рассматриваемых функций и подбором коэффициентов. Практически все сводится к приближенному подсчету значения выражений в задачах по физике и химии.

Чтобы избежать этих трудностей, целесообразно предлагать учащимся исследовать реальные физические, химические и другие подобные ситуации, самостоятельно продумать математическую модель явления, приводящую к уравнению или системе уравнений. Эти уравнения решаются в дальнейшем путем применения численного метода с использованием стандартной подпрограммы, составленной на соответствующем уроке вычислительной математики. Желательно, чтобы уравнения, описывающие рассматриваемые явления, не решались аналитически или их решение было чересчур сложным — этим наглядно демонстрируется эффективность применения приближенных методов.

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

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

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

Мы остановимся на следующих темах, отражающих межпредметные связи между курсом ОИВТ и математическими курсами:

1. Целые и рациональные алгебраические выражения.

2. Делимость чисел.

3. Разложение на множители многочленов с рациональными коэффициентами.

4. Комбинаторика.

5. Выпуклые фигуры.

Целые и рациональные алгебраические выражения.

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

Многочлены степени N естественно представлять в виде одномерных массивов размерности (0:N), т. е. нумеруя их коэффициенты:

а(0), а(1), ..., а (N). Условимся, что нулевой элемент массива содержит старший коэффициент многочлена, например, многочлен x3+3x+2 представляется массивом (1, 0, 3, 2).

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

Программа умножения работает методом накопления значений коэффициентов. На этом простом примере мы поясним способ записи алгоритма, который будет использован ниже. Каждый алгоритм имеет название («Произведение»), его шаги обозначаются первыми буквами названия и пронумерованы (Пр1 —Пр4). Шаги содержат сравнительно крупные действия, соответствующие одному-двум операторам развитого языка уровня Алгола-68 или ПЛ/1. В других языках программирование одного шага может потребовать группы операторов. Комментарии к алгоритму заключены в круглые скобки.

ПРОИЗВЕДЕНИЕ.

Пр1. ПРОИЗВ ¬0 (присвоить элементам ПРОИЗВ значение 0)

Пр2. для всех i от 0 до М выполнить Пр3 — Пр4.

Пр3. для всех j от 0 до N выполнить Пр4.

Пр4. ПРОИЗВ (M+N-i-j) ¬ПРОИЗВ (M+N-i-j)+A (i)´B (j). Здесь A(0:M) и B(0:N)—перемножаемые многочлены, ПРОИЗВ (0:M+N)—их произведение.

Более сложной является программа деления многочленов с остатком «уголком». В ней используются четыре массива: ДЕЛМ (О :М)— делимое, ДЕЛТ (0: N) — делитель, ЧАСТН (0: M)—частное и ОСТ (O:M) — остаток. Поскольку любая программа не должна менять входную информацию, массивы ДЕЛМ и ДЕЛТ должны оставаться неизменными, а для промежуточных вычислений используется массив OCT. Поэтому его размерность определена (0:M), хотя окончательно размерность остатка меньше размерности делителя. Если первые элементы массива — нули, то степень соответствующего многочлена меньше размерности массива. Определим функцию СТЕПЕНЬ (A), аргументом которой является массив, а значением — истинная степень многочлена, определяемого этим массивом. Она равна разности между числом элементов в массиве и номером первого ненулевого элемента. Алгоритм подсчета значения СТЕПЕНЬ тривиален.

ДЕЛЕНИЕ.

Д1. СТЕПМ ¬СТЕПЕНЬ (ДЕЛМ), СТЕПN ¬СТЕПЕНЬ (ДЕЛТ), ОСТ ¬ДЕЛМ

Д2. для всех i от 0 до СТЕПM — СТЕПN выполнить Д3 — Д4

ДЗ. ЧАСТН (i) ¬ДЕЛМ (СТЕПМ-i) /ДЕЛТ (N — СТЕПN)

(вычисляется коэффициент частного при члене степени СТЕПM — CTEПN - i)

Д4. для всех i от 0 до СТЕПN выполнить ОСТ (i+j)-OCT(i+/)- ЧАСТН (i) Х ДЕЛТ (/)

Д5. СТЕПОСТ ¬СТЕПЕНЬ (ОСТ), СТЕПЧАСТН ¬СТЕПЕНЬ (ЧАСТН) (СТЕПОСТ содержит степень остатка, ОСТ — остаток, СТЕПЧАСТН — степень частного, ЧАСТН — частное)

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

ПРИВЕДЕНИЕ.

П1. QR¬P, RR¬Q (Q и Р—исходные массивы, RR, QR и PR—рабочие массивы, используемые при вычислениях).

П2. пока RR отлично от 0 (т. е. хотя бы один элемент не равен 0) выполнять ПЗ — П4, иначе перейти к П5 (при этом PR содержит НОД Р и Q).

ПЗ. PR¬QR, QR¬RR.

П4. Разделить с остатком (применить ДЕЛЕНИЕ) PR на QR. Остаток поместить в RR.

П5 (разделить числитель на НОД). Разделить Р на PR, частное поместить в RR (остаток равен 0).

П6 (разделить знаменатель на НОД). Разделить Q на PR, частное поместить в QR (остаток равен 0).

П7. Разделить поэлементно RR и QR на первый ненулевой элемент QR (для его определения можно воспользоваться функцией СТЕПЕНЬ) и закончить (RR и QR содержат числитель и знаменатель дроби).

Отметим, что время работы можно сократить, убрав пересылки в П3. Правда, при этом увеличивается число шагов

2. Делимость чисел. Приведем пример межпредметных связей, когда математические формулы и теоремы используются для оценки алгоритма. Мы разберем задачу, связанную с теоремой Лагранжа. Алгоритм ее решения несложен, но дает возможность познакомить школьников с проблемами анализа алгоритмов. Эти проблемы наряду с тестированием незаслуженно обходятся не только в школьных, но и в вузовских курсах программирования.

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

Доказательство опирается на понятие вычетов по простому модулю и может быть изучено сильным учеником на факультативных занятиях или по книге. Будем рассматривать только упорядоченные по убыванию разложения, тогда при N =i2 + j2 + k2 + l2 выполняется i³j³k³l. Тогда верно i2£N и i2 ³ N/4, т. е. i принадлежит отрезку [

/2, ] . Поскольку j, k и l не превышает i, общее число комбинаций можно оценить сверху Точную оценку дает формула