А. В. Розина программирование на паскале методическое пособие
| Вид материала | Методическое пособие |
СодержаниеТема 9. Массивы Одномерные массивы Сортировка массива Двумерные массивы |
- Тема урока: Программирование ветвлений на Паскале, 61.32kb.
- Программирование ветвлений на Паскале Оператор ветвления на Паскале, 166.05kb.
- Программа элективного курса «Алгоритмизация и программирование», 95.38kb.
- Контрольная работа по темам «Линейное программирование на Паскале» и«Условный оператор», 4.21kb.
- Методическое пособие по выполнению курсовых работ по дисциплине, 450.1kb.
- В. И. Эльманович нейролингвистическое программирование методическое пособие, 781.36kb.
- В. И. Эльманович нейролингвистическое программирование методическое пособие, 924.82kb.
- В. А. Жернов апитерапия учебно-методическое пособие, 443.6kb.
- Тема урока: Программирование циклов на Паскале (9 класс, базовый уровень), 46.43kb.
- Кемеровский Государственный Университет; Д. Н. Долганов. Белово, 2005. 55. методическое, 704.81kb.
Тема 9. Массивы
Массив - это набор фиксированного числа элементов одного типа. У каждого элемента есть свой индекс (номер). Элементами массива могут быть данные любого типа. Элементы массива располагаются в памяти последовательно.
Одномерные массивы
Описание одномерных массивов выглядит следующим образом:
VAR
T , P : ARRAY [1..20] OF REAL;
R : ARRAY [1..100] OF INTEGER;
S : ARRAY [1..30] OF STRING;
В данном примере массивы Т,P вещественного типа по 20 элементов каждый, массив R целого типа, состоящий из 100 элементов, массив S состоит из 30 строк.
К элементам массива обращаются по имени и индексу, указанному в квадратных скобках. Индекс может быть константой или переменной целого или символьного типа. Если изучение этой темы идет после темы "Строки", то учащиеся уже были ознакомлены с понятием индекса, т.е. номера элемента. Обращаться и работать с элементами массива можно, изменяя значения индекса., при этом изменение происходит как правило в цикле.
Пример
| T[K] | при K=1,2...20 | - все элементы массива |
| T[2*K] | при K=1,2...10 | - элементы на четных местах |
| T[2*K-1] | при K=1,2...10 | - элементы на нечетных местах |
Рассмотрим типичные ситуации, возникающие при работе с одномерными массивами. Для этого сделаем следующее описание:
VAR
A,D : ARAY [1..6] OF REAL;
I, S : INTEGER;
- Ввод/вывод
Паскаль не имеет средств ввода/вывода элементов массива сразу, поэтому ввод и вывод производится поэлементно, с помощью организации цикла FOR:
FOR I := 1 TO 6 DO READLN (A[I]);
FOR I := 1 TO 6 DO WRITELN (A[I]);
- Инициализация (присвоение начальных значений)
Каждому элементу массива присваивается одно и то же значение:
FOR I := 1 TO 6 DO A[I] := 0;
- Копирование
Присвоение значений всех элементов одного массива всем соответствующим элементам другого массива.
FOR I := 1 TO 6 DO A[I] := D[I];
- Перестановка
В массиве А поменять местами 1-ый и последний элемент, 2-ой и предпоследний и т.д. Осуществляется с помощью дополнительной переменной того же типа, что и элементы массива.
FOR I := 1 TO 3 DO
BEGIN S :=A[I]; A[I] := A[7-I]; A[7-I] := S; END;
Целесообразно рассмотреть следующие задачи:
- Ввести массив целых чисел в количестве 10 элементов. Подсчитать сумму элементов, стоящих на четных местах.
PROGRAM SUM;
VAR
S, I: INTEGER;
A: ARRAY [1..10] OF INTEGER;
BEGIN
WRITELN ( 'ВВЕДИТЕ 10 ЧИСЕЛ ' ) ;
FOR I := 1 TO 10 DO READLN (A[I] );
S := 0;
FOR I := 1 TO 5 DO S := S+A[2*I];
WRITELN ( 'СУММА = ', S);
END.
- Подсчитать количество отрицательных чисел, стоящих на нечетных местах в массиве из 10 элементов.
...
FOR I := 1 TO 5 DO
IF ( A[2*I-1] < 0 ) THEN S := S+A[2*I-1];
...
- В массиве А, состоящем из 10 элементов, напечатать индексы нулевых элементов.
...
FOR I := 1 TO 10 DO
IF (A[I] = 0) THEN WRITELN ( ' ИНДЕКС =', I);
...
Сортировка массива
Сортировка – один из наиболее распространенных процессов современной обработки данных. Сортировка элементов массива, в результате которой получается массив, каждый элемент которого больше соседа слева, называется сортировкой по возрастанию.
В рамках школьной программы достаточно рассмотреть подробно один способ сортировки – метод пузырька. Этот метод основан на том, что более "легкие" элементы массива (пузырьки) постепенно "всплывают". Для этого представляем себе массив в виде столбца (трубочки), наполненного элементами. Причем внизу находится последний элемент.
Алгоритм данной сортировки по возрастанию состоит в последовательных просмотрах снизу вверх (от конца к началу) массива. Если соседние элементы таковы, что нижний элемент меньше верхнего, то выполняется обмен значениями этих элементов. Нахождение самого "легкого" (меньшего по значению) назовем проходом. В одном проходе не более N-1 сравнение. Здесь N-количество элементов в массиве. Всего проходов надо выполнить N-1, т.е. за один проход ставится 1-ый элемент, за 2-ой проход второй и т.д. за (N-1)-ый проход ставится на место (N-1)-ый элемент, а N-ый таким образом сам станет на место. Трудоемкость данного алгоритма (количество сравнений) будет (N-1)2.
Сказанное можно проиллюстрировать на примере. Пусть массив М состоит из 5 элементов : 7, 5, 0, 6, 2. отсортируем его в порядке возрастания.
| 7 | 7 | 7 | 0 | 0 | 0 | 0 | 0 |
| 5 | 5 | 0 | 7 | 7 | 2 | 2 | 2 |
| 0 | 0 | 5 | 5 | 2 | 7 | 5 | 5 |
| 6 | 2 | 2 | 2 | 5 | 5 | 7 | 6 |
| 2 | 6 | 6 | 6 | 6 | 6 | 6 | 7 |
| исходный | 1 проход | 2 проход | 3 проход | 4 проход | |||
Текст программы сортировки для 10 элементов приводим:
program sort01;
var x : array[1..10] of integer;
i,k,a : integer;
begin {ввод массива}
for i := 1 to 10 do read (x[i]);
{ Сортировка методом пузырька}
for i := 1 to 9 do
for k := 9 downto 2 do
if x[k] < x[k-1] then
begin a := x[k]; x[k] := x[k-1]; x[k-1] := a; end;
{ Вывод отсортированного массива}
writeln;
for i:=1 to 10 do write ( x[i] : 3 );
end.
Двумерные массивы
Двумерные массивы также называют таблицами или матрицами. Каждый элемент однозначно определяется номером строки и номером столбца.
Массив целых чисел, имеющий 3 строки и 4 столбца, описывается следующим образом:
VAR A: ARRAY [1..3,1..4] OF INTEGER;
В памяти компьютера элементы данного массива будут располагаться по строкам:
A[1,1]
A[1,2]
A[1,3]
A[1,4]
A[2,1]
...
Ввод и вывод элементов массива.
VAR I, J, N, M: INTEGER;
B : ARRAY [1..50,1..40] OF INTEGER;
BEGIN
WRITELN ('ВВЕДИТЕ КОЛИЧЕСТВО СТРОК'); READLN(N);
WRITELN ('ВВЕДИТЕ КОЛИЧЕСТВО СТОЛБЦОВ); READLN(M);
{ВВОД}
FOR I :=1 TO N DO {цикл по строкам}
FOR J :=1 TO M DO {цикл по столбцам}
READ(A[I,J]);
{ВЫВОД}
FOR I :=1 TO N DO
BEGIN
FOR J :=1 TO M DO WRITE(A[I,J]);
WRITELN;
{после вывода элементов столбца переход на новую строку}
END;
END.
В приведенном примере реализован псевдодинамический массив, т.е. если заранее не известна размерность массива, то в описательной части Паскаля задается максимально возможное значение числа строк и столбцов. В таком случае перед вводом массива запрашивается реальное число строк и столбцов.
Полезно рассмотреть несколько задач, фрагменты которых приведены далее:
- Сумма элементов, стоящих на главной диагонали, матрицы, состоящей из 10 строк и 10 столбцов (индексы элементов главной диагонали равны!):
...
S := 0;
FOR I := 1 TO 10 DO S := S + A[I,I];
...
- Сумма элементов, стоящих ниже главной диагонали, матрицы, состоящей из 10 строк и 10 столбцов:
...
S := 0;
FOR I := 2 TO 10 DO
FOR J := 1 TO I-1 DO S := S + A[I,J];
...
- Сумма элементов, стоящих выше главной диагонали, матрицы, состоящей из 10 строк и 10 столбцов:
...
S := 0;
FOR I := 1 TO 9 DO
FOR J := I+1 TO 10 DO S := S + A[I,J];
...