МЕДВЕНСКИЙ РАЙОННЫЙ МЕТОДИЧЕСКИЙ КАБИНЕТ
ДОПОЛНИТЕЛЬНОГО ОБРАЗОВАНИЯ
МО учителей информатики
Медвенского района
Мастер-класс
Технология решения задач части С
единого государственного экзамена
Обработка целочисленных массивов
Автор: учитель информатики
.
МОкУ «Нижне-реутчанская средняя общеобразовательная школа»
МОБУ «Высоконодворская средняя общеобразовательная школа»
МОбУ «СПАССКАЯ средняя общеобразовательная школа»
МОкУ «любачанская средняя общеобразовательная школа»
Курская область Медвенский район 2013 г
Содержание
Массивы как инструмент программирования. | Стр.3 |
Технология решения задач, связанных с обработкой массивов данных. | Стр.6 |
Планирование курса информатики в основной и средней школе с учетом возможной сдачи экзамена. | Стр.11 |
Обработка целочисленных массивов. | Стр.18 |
1.1 Массивы как инструмент программирования
Программирование на любом языке основывается на следующих инструментах:
Текстовый редактор, трансляторы. Переменные и постоянные величины. Алгоритмические структуры. Массивы. Записи (сложные структуры данных). Подпрограммы. Операторы.Рассмотрим такой важный элемент программирования как массивы. Массивы это наборы данных одного типа. Массивы могут быть одномерными, двухмерными, многомерными, статическими и динамическими.
Простая таблица, в которой имеются только заголовки столбцов или только заголовки строк – это пример одномерного массива. Таблица, у которой есть заголовки столбцов и строк – это двухмерный массив (матрица). Ячейка таблицы – это наглядный пример элемента массива.
Массивы описываются операторами dim и redim:
Dim – команда (оператор) описания статических массивов.
Например, dim a(1 to 5) as integer. Описан одномерный статический массив с именем a, состоящий из 5 элементов. Наглядно этот массив можно представить в виде таблицы:
1 | 2 | 3 | 4 | 5 |
Описанный вышеприведенной командой массив пустой, но в каждый элемент массива (ячейку таблицы) может быть записано целое число (integer).
Если, например, a(1)=25, a(4)=3, то:
1 | 2 | 3 | 4 | 5 |
25 | 3 |
Для работы с массивами целесообразно использовать алгоритмическую структуру «Цикл», например, для считывания и ввода данных в массив, а также для его обработки.
Следующий фрагмент программы осуществляет ввод данных в массив, который описан выше:
For i=1 to 5
Input “Ввведите данные в массив”; a(i)
Next i
Приведем пример описания двухмерного целочисленного массива из 10 элементов и осуществим ввод данных в него через «Цикл».
Dim m(1 to 5, 1 to 2) as integer
Наглядно такой массив можно представить в виде таблицы.
m | 1 | 2 | 3 | 4 | 5 |
1 | |||||
2 |
Ввести данные в двухмерный массив можно двумя вложенными друг в друга циклами:
for j=1 to 2
for i=1 to 5
input “Введите данные в массив”; m(i, j)
next i
next j
Redim - команда (оператор) описания динамических массивов. Массивы, описанные данной командой, являются динамическими и отличаются от статических тем, что количество элементов массива может меняться в процессе работы программы.
Массивы являются важнейшими объектами программирования, так как без них не может обойтись ни одна более или менее сложная программа. Например, строки в текстовом редакторе Word, в сущности, являются элементами массива.
1.2 Технология решения задач,
связанных с обработкой массивов данных
Экзаменационная работа по информатике и ИКТ состоит из 3 частей, содержащих 32 задания. На выполнение частей 1 и 2 работы рекомендуется отводить 1,5 часа (90 минут). На выполнение заданий части 3 – 2,5 часа (150 минут).
Часть 1 содержит 13 заданий с выбором ответа. К каждому заданию даётся 4 варианта ответа, из которых только один правильный.
Часть 2 состоит из 15 заданий с кратким ответом.
Часть 3 состоит из 4 заданий. Для выполнения заданий этой части необходимо написать развёрнутый ответ в произвольной форме.
Рассмотрим задачи части С, связанные с обработкой массивов данных.
Опишите на русском языке или одном из языков программирования алгоритм подсчета числа элементов равных максимальному в числовом массиве из 30 элементов. (2005 г.) Опишите на русском языке или на одном из языков программирования алгоритм поиска второго по величине (т. е. следующего по величине за максимальным) элемента в числовом массиве из 30 различных элементов. (2006 г.) Опишите на русском языке или одном из языков программирования алгоритм поиска номера первого из двух последовательных элементов в целочисленном массиве из 30 элементов, сумма которых максимальна (если таких пар несколько, то можно выбрать любую из них). (2007 г.) Опишите на русском языке или одном из языков программирования алгоритм подсчета максимального количества подряд идущих совпадающих элементов в целочисленном массиве длины 30. (2008 г.) Опишите на русском языке или одном из языков программирования алгоритм получения из заданного целочисленного массива размером 30 элементов другого массива, который будет содержать модули значений элементов первого массива (не используя специальной функции, вычисляющей модуль числа). (2009 г.) Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 100 – баллы учащихся выпускного класса за итоговый тест по информатике. Для получения положительной оценки за тест требовалось набрать не менее 20 баллов. Опишите на русском языке или на одном из языков программирования алгоритм, который находит и выводит минимальный балл среди учащихся, получивших за тест положительную оценку. Известно, что в классе хотя бы один учащийся получил за тест положительную оценку. (2010 г.)
Технология решения вышеприведенных задач является универсальной и заключается в применении алгоритмических структур «Циклы» и «Ветвление», а также логических операторов и операторов сравнения.
Рассмотрим, например, решение первой задачи:
Необходимо найти максимальный элемент. Подсчитать количество элементов, равных максимальному.Решение задачи приведено в листинге 1.
Листинг 1
'c2_2005
CLS
DIM a(1 TO 10) AS INTEGER
DIM i, n, max AS INTEGER
n = 0
FOR i = 1 TO 10
INPUT a(i)
NEXT i
max = a(1)
FOR i = 1 TO 10
IF a(i) > max THEN
n = 1
max = a(i)
ELSE
IF a(i) = max THEN n = n + 1
END IF
NEXT i
PRINT n
PRINT max
END
Изменим программу таким образом, чтобы данные в массив не вводились в процессе выполнения программы, а считывались из текстового файла.
Листинг 2
'c2_2005
CLS
DIM i, n, k, max AS INTEGER
DIM st AS STRING
n = 1
OPEN "L:\Basic\c2_2005.txt" FOR INPUT AS #1
LINE INPUT #1, st
k = VAL(st)
DIM a(1 TO k) AS INTEGER
LINE INPUT #1, st
a(1) = VAL(st)
max = a(1)
FOR i = 2 TO k
LINE INPUT #1, st
a(i) = VAL(st)
IF a(i) > max THEN
n = 1
max = a(i)
ELSE
IF a(i) = max THEN n = n + 1
END IF
NEXT i
PRINT n
PRINT max
CLOSE
END
В задаче №2 необходимо найти второй по величине элемент целочисленного массива. В листинге 3 приведено решение данной задачи.
Листинг 3
'c2_20061
CLS
DIM i, n, k, max1, max2 AS INTEGER
DIM st AS STRING
OPEN "L:\Basic\c2_2006.txt" FOR INPUT AS #1
LINE INPUT #1, st
k = VAL(st)
DIM a(1 TO k) AS INTEGER
LINE INPUT #1, st
a(1) = VAL(st)
max1 = a(1)
max2 = a(1)
FOR i = 2 TO k
LINE INPUT #1, st
a(i) = VAL(st)
IF a(i) > max1 THEN
max2 = max1
max1 = a(i)
ELSE
IF a(i) > max2 AND a(i) < max1 THEN max2 = a(i)
END IF
NEXT i
PRINT max1
PRINT max2
CLOSE
END
Приведем программу для решения задачи №3.
В данной программе предусмотрен вывод результата не только на экран, но и в текстовый файл.
Листинг 4
'c2_20071
CLS
DIM i, n, k, max, j AS INTEGER
DIM st AS STRING
n = 1
OPEN "L:\Basic\c2_2005.txt" FOR INPUT AS #1
LINE INPUT #1, st
k = VAL(st)
DIM a(1 TO k) AS INTEGER
LINE INPUT #1, st
a(1) = VAL(st)
LINE INPUT #1, st
a(2) = VAL(st)
max = a(1) + a(2)
FOR i = 3 TO k
LINE INPUT #1, st
a(i) = VAL(st)
IF a(i) + a(i - 1) > max THEN
n = 1
max = a(i) + a(i - 1)
j = i - 1
ELSE
IF a(i) + a(i - 1) = max THEN n = n + 1
END IF
NEXT i
PRINT n
PRINT max
PRINT j
CLOSE
OPEN "L:\Basic\resultat. txt" FOR OUTPUT AS #1
WRITE #1, n, "-kolichestvo"
WRITE #1, max, "-summa"
WRITE #1, j, "-nomer 1 elementa"
CLOSE
END
Анализируя решение вышеприведенных задач, можно сделать следующий вывод:
«Перебор» элементов массива осуществляется с помощью циклов. Выбор необходимых элементов и их значений производится с помощью алгоритмической структуры «Ветвление», логических операторов и операторов сравнения.1.3 Планирование курса информатики в основной и средней школе с учетом возможной сдачи экзамена
Для более основательной подготовки к экзамену целесообразно скорректировать рабочую программу таким образом, чтобы исключить несоответствия тем в кодификаторе и тематическом плане.
В нашем случае рабочая программа составлена на основе авторских программ и . В программу внесен дополнительный материал, необходимый для более детальной подготовки к экзамену.
Что касается нашей темы, то с элементами программирования учащиеся знакомятся еще в 6-7 классах, а в 9-11 классах изучают данный вопрос на более высоком уровне.
Ниже приводятся фрагменты календарно-тематических планов.
Что такое алгоритм. Практическая работа №18. Знакомимся со средой программирования QBasic. | п.3.1 |
Исполнители вокруг нас. Графические исполнители. | п.3.2; п.4.19 |
Формы записи алгоритмов. Практическая работа №19. Исполнитель DRAW. | п.3.3 |
Типы алгоритмов. Практическая работа №20. Исполнитель Line. | п.3.4 |
IV четверть | ||
3. Алгоритмика (7 ч). | ||
27. | Алгоритм — модель деятельности исполнителя алгоритмов. Исполнитель Чертежник. Управление Чертежником. Работа в среде «Алгоритмика» | §3.1, §3.2(1, 2) |
ЦОР Презентация «Алгоритм — модель деятельности исполнителя» Виртуальная лаборатория «Алгоритмика» | ||
28. | Исполнитель Чертежник. Использование вспомогательных алгоритмов. Работа в среде «Алгоритмика» | §3.2(3) |
ЦОР Виртуальная лаборатория «Алгоритмика» | ||
29. | Исполнитель Чертежник. Цикл «повторить n раз». Работа в среде «Алгоритмика» | §3.2(4) |
ЦОР Виртуальная лаборатория «Алгоритмика» | ||
30. | Исполнитель Робот. Управление Роботом. Работа в среде «Алгоритмика» | §3.3(1) |
ЦОР Виртуальная лаборатория «Алгоритмика» | ||
31. | Исполнитель Робот. Цикл «пока». Работа в среде «Алгоритмика» | §3.3(2, 4) |
ЦОР Виртуальная лаборатория «Алгоритмика» | ||
32. | Исполнитель Робот. Ветвление. Работа в среде «Алгоритмика» | §3.3 (5) |
ЦОР Виртуальная лаборатория «Алгоритмика» | ||
33. | Проверочная работа | |
ЦОР Файлы для печати ПР2_1.doc, ПР2_2.doc | ||
34. | Итоговый проект. Практическая работа №12. |
Свойства алгоритма и его исполнители. | 4.1.1. |
Выполнение алгоритмов человеком | 4.1.2. |
Выполнение алгоритмов компьютером | 4.1.2. |
Линейный алгоритм | 4.2.1. |
Алгоритмическая структура «ветвление» | 4.2.2. |
Алгоритмическая структура «выбор» | 4.2.3. |
Алгоритмическая структура «цикл» | 4.2.4. |
Переменные: тип, имя, значение. Практическая работа 4.2. Проект «Переменные». | 4.3. |
Арифметические, строковые и логические выражения. Практическая работа 4.3. Проект «Калькулятор». | 4.4. |
Функции в языках объектно-ориентированного и алгоритмического программирования. Практическая работа 4.4. Проект «Строковый калькулятор». | 4.5. |
Основы объектно-ориентированного визуального программирования. Практическая работа 4.5. Проект «Даты и время». | 4.6. Практическая работа 4.9. Проект «Слово-перевертыш». |
Графические возможности объектно-ориентированного языка программирования Visual Basic 2005. Практическая работа 4.6. Проект «Сравнение кодов символов». | 4.7. Практическая работа 4.10. Проект «Графический редактор». |
Обобщающий урок. Основы алгоритмизации и объектно-ориентированного программирования | Практическая работа 4.7. Проект «Отметка». |
Контрольная работа. Основы алгоритмизации и объектно-ориентированного программирования | Практическая работа 4.8. Проект «Коды символов». |
Переменные в языках программирования. Тип, имя и значение переменной. Арифметические, строковые и логические выражения. Присваивание. | п.4.1. п.4.6. Конспект п.4.7(стр.177-178) |
Основные типы алгоритмических структур. Линейная алгоритмическая структура. Алгоритмическая структура «Ветвление». | п.4.2. Конспект. Проект «Решение квадратных уравнений» |
Алгоритмическая структура «Выбор». | п.4.2. Конспект. Проект «Решение квадратных уравнений» |
Алгоритмическая структура «Цикл со счетчиком». | п.4.2. Конспект. Проект «Рисование графических примитивов» |
Алгоритмическая структура «Цикл по условию». | п.4.2. Конспект. Проект «Рисование графических примитивов» |
Массивы. | Проект «Обработка массива» |
Поиск наименьшего и наибольшего элемента в целочисленном массиве. Сумма и среднее арифметическое элементов числового массива. | Проект «Обработка массива» |
Сумма и среднее арифметическое элементов числового массива. | Проект «Обработка массива» |
Поиск максимальной суммы двух подряд идущих элементов числового массива. | Проект «Обработка массива» |
Сортировка массива. | Проект «Обработка массива» |
Подпрограммы. | Проект «Обработка массива» |
Решение типичных задач по теме «Алгоритмические структуры». | Проект «Обработка массива» |
Решение задач повышенного уровня сложности по теме «Алгоритмические структуры» | Проект «Обработка массива» |
Решение задач повышенного уровня сложности по теме «Алгоритмические структуры» | Проект «Обработка массива» |
Обобщающий урок по теме «Алгоритмические структуры» | Повторение. Конспект |
Контрольная работа. Алгоритмические структуры. | Повторение. Проект «Обработка массива» |
Переменные в языках программирования. Тип, имя и значение переменной. Арифметические, строковые и логические выражения. Присваивание. | п.4.1. п.4.6. Конспект п.4.7(стр.177-178) |
Основные типы алгоритмических структур. Линейная алгоритмическая структура. Алгоритмическая структура «Ветвление». | п.4.2. Конспект. Проект «Решение алгебраических уравнений» |
Алгоритмическая структура «Выбор». | п.4.2. Конспект. Проект «Решение алгебраических уравнений» |
Алгоритмическая структура «Цикл со счетчиком». | п.4.2. Конспект. Проект «Количество информации» |
Алгоритмическая структура «Цикл по условию». | п.4.2. Конспект. Проект «Количество информации» |
Основы объектно-ориентированного визуального программирования. Интегрированная среда разработки языка Visual Basic. | п.4.3 п.4.4 Проект «Универсальный калькулятор» |
Форма и размещение на ней управляющих элементов. | п.4.5 Проект «Универсальный калькулятор» |
Функции в языке Visual Basic. Проект «Обычный калькулятор» | п.4.9(4.9.1-4.9.3) Проект «Универсальный калькулятор» |
Функции в языке Visual Basic. Проект «Перевод чисел» | п.4.9(4.9.4-4.9.5) Проект «Универсальный калькулятор» |
Проект «Коды символов». Проект «Инженерный калькулятор». | п.4.9 (повторить) Проект «Универсальный калькулятор» |
Графические возможности языка Visual Basic. | п.4.10 Проект «Универсальный калькулятор» |
Графические возможности языка Visual Basic. | п.4.10 Проект «Универсальный калькулятор» |
Общие процедуры. | п.4.11 Проект «Универсальный калькулятор» |
Массивы. | п.4.13(4.13.1-4.13.3) Проект «Универсальный калькулятор» |
Массивы. | п.4.13(4.13.4-4.13.5) Проект «Универсальный калькулятор» |
Обобщающий урок. Основы алгоритмизации и объектно-ориентированного программирования. | Тест. Основы алгоритмизации и объектно-ориентированного программирования. |
Контрольная работа. Основы алгоритмизации и объектно-ориентированного программирования. | Тест. Основы алгоритмизации и объектно-ориентированного программирования. |
1.4 Создание программы «Обработка целочисленного массива»
на языке QBASIC
В тематический план 9-11 классов внесена проектная деятельность, которая позволяет углубить, систематизировать, обобщить знания обучающихся.
Так в 10 классе при изучении функционально-структурного программирования предусмотрена разработка проекта «Обработка целочисленного массива».
Данный проект представляет собой разработку программы, вычисляющей элементарные характеристики целочисленного массива и по сути объединяет те задачи, которые мы рассматривали выше.
Главной целью данного проекта является создание программы, обрабатывающей целочисленный массив.
Программа должна вычислить следующие показатели:
Найти минимальный и максимальный элемент массива. Определить количество элементов, равных минимальному, а также количество элементов, равных максимальному. Вычислить сумму всех элементов. Рассчитать среднее арифметическое всех элементов массива. Найти максимальную сумму двух подряд идущих элементов. Определить максимальное количество одинаковых подряд идущих элементов целочисленного массива.Ограничения: расчет показателей должен быть выполнен за один проход по массиву.
Данную задачу можно решить с помощью алгоритмических структур «Ветвление» и «Цикл».
'Обработка массива
CLS
DIM i, n, min, max, summa, srarifm, s, z1, z2 AS INTEGER
's-максимальная сумма двух подряд идущих элементов
'z2-максимальное количество одинаковых подряд идущих элементов
'z1-значение одинаковых подряд идущих элементов массива, количество которых максимально
DIM st AS STRING
OPEN "c:\Basic\massiv1.txt" FOR INPUT AS #1
LINE INPUT #1, st
n = VAL(st)
DIM a(1 TO n) AS INTEGER
min = a(1)
max = a(1)
summa = 0
kmax = 1' количество элементов равных максимальному
kmin = 1' количество элементов равных минимальному
z = 1
FOR i = 1 TO n
LINE INPUT #1, st
a(i) = VAL(st)
IF a(i) < min THEN
min = a(i)
kmin = 1
ELSE
IF a(i) = min THEN kmin = kmin + 1
END IF
IF a(i) > max THEN
max = a(i)
kmax = 1
ELSE
IF a(i) = max THEN kmax = kmax + 1
END IF
summa = summa + a(i)
IF i >= 2 THEN
IF s <= a(i) + a(i - 1) THEN s = a(i) + a(i - 1)
'Вычисление максимального количества одинаковых подряд идущих элементов
IF a(i) = a(i - 1) THEN
z = z + 1
z1 = a(i)
ELSE
IF z > z2 THEN z2 = z
z = 1
END IF
END IF
NEXT i
srarifm = summa / n
PRINT "Минимальный элемент массива: min="; min
PRINT "Количество элементов равных минимальному: kmin="; kmin
PRINT "Максимальный элемент массива: max="; max
PRINT "Количество элементов равных максимальному: kmax="; kmax
PRINT "Сумма всех элементов массива: summa="; summa
PRINT "Среднее арифметическое: srarifm="; srarifm
PRINT "Максимальная сумма двух подряд идущих элементов: s="; s
PRINT "Максимальное количество одинаковых подряд идущих элементов и значение этих элементов: z2="; z2, z1
CLOSE
END
Таким образом, разработанная программа позволяет вычислять ряд показателей массива данных. Такого рода расчеты могут применяться на практике, например, в статистических исследованиях.
