ПРОГРАММИРОВАНИЕ СУММ И ПРОИЗВЕДЕНИЙ
Ю.С. Антонов ipkro@sakha.ru
ТиМОИ ИМИ ЯГУ им. М.К. Аммосова РС(Я)
Programming of sums and sets
Y.S. Antonov ipkro@sakha.ru
TiMOI YSU after M.K. Ammosov. Yakutia
Методика преподавания программирования является частью методики преподавания информатики. Было время, когда программирование и информатика были синонимами. Затем программирование было полностью вытеснено информационными технологиями. В данное время программирование постепенно возвращается в школьный курс информатики. В самом деле, информационные технологии получили, в данный момент, такое развитие, что их более или менее детальное изучение без программирования практически невозможно. Visual Basic, Delphi, Power Point, SQL, HTML, PHP, PGP, Java, Perl – вот далеко не полный список программных продуктов, которые вошли, входят или будут входить в школьный курс информатики. Все перечисленные предметы являются или языками программирования или их изучение невозможно без навыков программирования.
Конечно, при изучении перечисленных программных продуктов могут возникнуть трудности в методике их освоения. Намного уверенней эти предметы можно изучать, если у учеников уже есть навыки программирования. Понятно, что обучение программированию надо начинать с более простых языков программирования, таких как Бейсик, Паскаль, Cи. Выбор конкретного языка для изучения программирования зависит от многих причин. В данной работе предпочтение отдано Паскалю.
Обучение программированию условно разделим на 4 части:
Методика обучения языку программирования.
Начальное обучение программированию.
Изучение приемов программирования и отдельных простых алгоритмов.
Изучение сравнительно сложных алгоритмов.
Как показывает практика, все эти части связаны и при изучении одной части невозможно обойтись без соседних частей. Однако, перепрыгивание через целый раздел нежелательно. Например, при изучении циклов возможно рассмотрение задач связанных с суммами и произведениями (2-я часть), в то же время, изучение олимпиадных задач хотя бы районного уровня (3-я часть), вряд ли будет уместно. Аналогично, при изучении сумм и произведений вполне возможно рассмотрение сравнительно несложного алгоритма Горнера, в то же время показ алгоритма Дейкстры при нахождении минимального пути в графе вряд ли целесообразно.
Очевидно, каждая из вышеприведенных частей изучения программирования должна иметь свою методику, которая в свою очередь должна варьироваться в зависимости от уровня преподавания.
Рассмотрим более подробно начальное обучение программированию. Этот этап изучения программирования можно разбить на следующие разделы: Разветвляющиеся программы, суммы и произведения, типичные задачи на одномерные массивы, типичные задачи на двумерные массивы, символьные переменные, графика и мультипликация, вычислительная геометрия, файлы, подпрограммы, рекурсия. На этом этапе вполне возможен возврат к изучению языка программирования. Например, показ преимущества применения оператора цикла while перед оператором цикла do в некоторых задачах перестановки элементов в массиве или преимущество множеств перед перечислением в некоторых задачах выбора. Но, все таки, этот этап ближе связан с третьим этапом. Он, как бы, является пропевдевтическим по отношению к некоторым темам третьего этапа (стеки, очереди, деки, списки, графы, метод Монте-Карло, переборные задачи, динамические переменные, динамическое программирование, жадные алгоритмы и т.д.).
Рассмотрим раздел программирование сумм и произведений. Эта тема тесно связана с динамическим программированием. В данном случае мы под динамическим программированием понимаем использование предыдущих вычислений. При этом предыдущие вычисления можно использовать разными способами. Рассмотрим вначале использование накопителей. Под накопителем мы будем понимать переменную, находящуюся по обе стороны от оператора присваивания, при этом, чтобы переменная стала накопителем данный оператор должен повторяться. Каждый накопитель обязательно должен иметь начальное значение. Накопители могут быть разными: накопители сумм, накопители произведений, накопители для схем Горнера, счетчики и т.д.
Рассмотрим программу, реализующую вычисление суммы  .
var a: integer; s: real;
begin
s:=0; for a:=1 to 5 do s:=s+a/(1+a); write(s:4:2); readln
end.
В этой программе s является накопителем суммы. Начальное значение s равно нулю. Данная программа осуществляет вычисления по следующему алгоритму s0:=0; sn+1:= sn+a/(1+a). Где n изменяется от 0 до 4. Отсюда видно, что на самом деле в этой программе осуществляется динамическое программирование.
Рассмотрим программу, реализующую вычисление  .
var a: integer; p: real;
begin
p:=1; for a:=1 to 5 do p:=p*a/(1+a); write(p:4:2); readln
end.
В этой программе p – накопитель произведения. Аналогично предыдущему, можно показать, что вычисление произведения осуществляется динамически.
Рассмотрим программу, реализующую вычисление  .
var a,f: integer; s: real;
begin
s:=0; f:=1; for a:=1 to 5 do
begin f:=f*a; s:=s+a/(1+f);
write(s:4:2); readln
end.
В этой программе f – накопитель произведения, s – накопитель суммы. Данная программа осуществляет вычисления по следующему алгоритму s0:=0; f0:=1; fn+1:= fn*a; sn+1:= sn+a/(1+ fn+1). Где n изменяется от 0 до 4. Организация вычислений усложнилась. Иначе можно сказать, что усилилась динамика.
Рассмотрим программу вычисления   .
var a,b: integer; s,p: real;
begin
s:=0; for a:=1 to 5 do s:=s+a/(1+a);
p:=1; for b:=1 to 5 do p:=p*b/(1+b);
s:=s+p;
write(s:4:2); readln
end.
В пятой строке s не является накопителем, так как оператор s:=s+p в программе не повторяется. В вычислениях можно увеличить динамику. Для этого нужно сначала вычислить произведение, а затем, используя то, что знак ‘+’ как бы является продолжением суммы, можно вычислить сумму с начальным значением в виде вычисленного произведения.
var a,b: integer; p: real;
begin
p:=1; for b:=1 to 5 do p:=p*b/(1+b);
for a:=1 to 5 do p:=p+a/(1+a);
write(p:4:2); readln
end.
Вторым способом реализации сумм и произведений является использование рекуррентных соотношений.
Рассмотрим следующее выражение  . Пусть  . Тогда  . Рассмотрим соотношение  . Приведем это соотношение к виду  . Мы получили рекуррентное соотношение. Начальным значением этого соотношения является p1= . Отсюда видно, что и в этом случае мы применяем динамическое программирование. Рассмотрим программу вычисления заданной суммы с использованием рекуррентных соотношений.
var a: integer; p,s: real;
begin
p:=1/2; for a:=1 to 4 do
begin p:=p*sqr(a+1)/(a+2); s:=s+p end;
write(s:4:2); readln
end.
Все вышесказанное показывает, что вычисления сумм и произведений можно считать динамическим программированием. При таком изложении материала ученики привыкают к слову динамическое программирование и не пугаются этого термина. Конечно, такое изложение материала ориентировано на школы с математическим или техническим уклоном. Для обычных школ вычисления сумм и произведений с использованием рекуррентных соотношений можно не изучать.
Литература:
Антонов Ю.С., Протодьяконова Т.Г. Программирование. (Задачи, алгоритмы, тесты). – Якутск, 2001. – 267 с.
|
