ХКОИС
ХРРЦ
Регистрация
Забыли пароль?
Логин:
Пароль:
Поиск
Справочные сведения о системе образования Хабаровского края
Новости образования Хабаровского края
Информация и документы из министерства образования и науки Хабаровского края
Хабаровская краевая заочная физико-математическая школа
РЕГИОНАЛЬНАЯ ОЛИМПИАДА ШКОЛЬНИКОВ
Подготовка к олимпиадам по информатике
Подготовка к олимпиадам по информатикеМетоды и приемы программирования > Типовые задачи с использованием массивов
Типовые задачи с использованием массивов
Массивы в Паскале
 
Решение любой задачи на составление программы требует построение соответствующей модели. Моделирование необходимо для того, чтобы выделить входные данные и результаты, а также установить связь между ними. Другими словами, описать правила (алгоритмы) получения результатов из входных данных. Важной составляющей модели является структура данных, ее выбор определяет основные параметры алгоритмов, используемых для решения задачи, а также способы реализации этих алгоритмов в виде элементов программы. При этом следует соотносить разрабатываемую модель данных с наличием средств и возможностей языка программирования, на котором будет решаться задача. Для этого нужно иметь необходимые знания о средствах разработки структур данных и работы с ними в используемом вами языке программирования. Массивы являются одной из структур данных представленной во всех процедурных языках программирования высокого уровня.
 
Общие свойства массивов
 
-       Массив является набором данных (элементов), связанных общим именем и расположенных в смежной области оперативной памяти компьютера.
-       Для доступа к элементам массива используются индексы.
-       Как правило, все элементы массива имеют один и тот же базовый тип, например, вещественный. Однако в некоторых языках программирования элементы массива могут иметь различные типы.
-       Одной из характеристик массива является его размерность – количество индексов необходимых для доступа к элементу.
 
Некоторые аналогии массивов и реальных объектов
 
Аналогии одномерного массива:
 
-       Одномерная таблица
-       Строка символов
-       Вектор (вектор задается набором координат)
-       Цифровая запись числа – элементами являются цифры записи числа
 
Аналогии двумерного массива:
 
-       Прямоугольная таблица
-       Страница книги – элементом является символ, для каждого символа задаются номер строки и номер столбца.
 
Аналогиями массивов высшей размерности могут быть:
 
-       Книга – (трехмерный) элементом является символ, для каждого символа задаются номера страницы, строки и столбца.
-       Книжная полка — (четырехмерный) элементом является символ, для каждого символа задаются номера книги на полке, страницы, строки и столбца.
-       Книжный шкаф — (пятимерный) элементом является символ, для каждого символа задаются номера полки, книги на полке, страницы, строки и столбца.
-       Библиотека — (шестимерный) элементом является символ, для каждого символа задаются номера шкафа, полки в шкафу, книги на полке, страницы, строки и столбца.
-       И так далее.
 
Некоторые замечания о массивах в Паскале
 
  1. В Паскале массив является переменной. Это значит, что если есть две – переменных одного типа (массивы), то можно присвоить значение одной переменной другой.
  2. Базовым типом элемента массива может быть любой определенный ранее тип. То есть, кроме массивов с базовыми элементами простых типов возможны массивы массивов, массивы файлов, массивы записей и так далее.
  3. Синтаксические правила описания и использования массивов, а также примеры описаны в статье «Элементарное введение в программирование на языке Turbo-Pascal»
 
Задачи
 
Задач, связанных с применение массивов встречается очень много и все их рассмотреть невозможно. Выделим несколько типов наиболее распространенных задач.
 
Простой поиск в массиве
 
К этой категории задач относятся:
-       Найти в массиве элементы, удовлетворяющие определенным условиям
-       Найти в массиве номера элементов, удовлетворяющих определенным условиям
-       Найти в массиве количество (сумму, произведение) элементов, удовлетворяющих определенным условиям
 
Поиск наибольшего (наименьшего)
 
Здесь задачи аналогичные тем, что названы в предыдущем случае, однако условия носят специфический характер. Условие отбора формулируется так, что нужно найти элементы, для которых некоторое выражения будет иметь наибольшее или наименьшее значение из всех остальных. Например:
-       Найти номер элемента числового массива, имеющего наименьшее значение. Задача является стандартной.
-       Найти номер элемента числового массива, наиболее приближенного к точке числовой оси со значением P. В этой задаче сравниваются не значения двух элементов, например A[i] и A[j], а значения выражений, в которые входят эти элементы – abs(P-A[i])  и abs(P-A[j]) – вычисляющие расстояние элемента массива до точки P.
 
Сортировка массива
 
Задачи сортировки сводятся к тому, чтобы элементы массива были выстроены (переставлены) в таком порядке, чтобы для каждой пары соседних элементов выполнялось определенное условие. Самыми простыми условиями являются возрастание или убывание значений элементов массива. В более сложных случаях правило может быть задано некоторым выражением. Например:
 
-       Отсортировать массив по возрастанию расстояния от элемента до точки H на числовой прямой. Здесь условие записывается аналогично как в предыдущем примере.
-       Пара массивов X и Y задают на плоскости набор точек Mi с координатами (X[i],Y[i]). Отсортировать точки по возрастанию расстояния от начала координат. В этой задаче условие сортировки возрастание значения выражения X[i]*X[i]+Y[i]*Y[i] – квадрата расстояния от точки до начала координат. Естественно, что, решая такую задачу нужно переставлять местами как элементы массива X, так и соответствующие элементы массива Y.
     
В некоторых случаях сортировка массива является промежуточной операцией для решения поставленной задачи. Например:
 
-       Найти наиболее часто повторяющееся значение элементов массива и количество элементов имеющих такое значение.
Для решения такой задачи можно сначала отсортировать массив, например по возрастанию, тогда элементы, имеющие одинаковое значение будут стоять рядом и можно за один проход найти ответы на поставленные в задаче вопросы. Программа, решающая такую задачу, приведена ниже.
  
Program skolko;
Type
          Ar=array [1..20] of real;
Var
          A:ar;
          I,J,N,K,M:integer;
          P,C:real;
Begin
Write(‘число элементов N=’);
Readln(n);
Writeln(‘введите значения’);
For i:=1 to n do
Readln(A[i]);
For i:=1 to n-1 do
For j:=i+1 to n do
          If A[i]>A[j] then begin
                    C:=A[i];
                    A[i]:=A[j];
                    A[j]:=C
                    End;
K:=1;
P:=A[1];
M:=1;
For i:=2 to n do
If A[i-1]=A[i] then
M:=M+1
                    Else
Begin
          If M>K then
Begin
                    K:=M;
                    P:=A[i-1]
                    End;
          M:=1
          End;
If M>K then
Begin
                    K:=M;
                    P:=A[n]
                    End;
Writeln(‘число ‘,P,’ встречается наибольшее число раз ’,K)
End.
 
 
Описание типа для массива
 
Описание массива
Описание переменных
 
 
 
Ввод количества элементов
 
 
Ввод значений элементов
!
!
! Сортировка массива по возрастанию
!
!
!
!
Пусть наибольшее число повторений 1
Наиболее повторяющийся элемент A[1]
M-число повторений элемента A[i-1]
Просмотрим все соседние пары
Если элементы равны, то
Увеличиваем число повторений на 1
Иначе
 
Если стало (M) больше чем было (K), то
 
Запомним большее число повторений
И значение соответствующего элемента
 
Число повторений значения A[i] равно 1
 
 
Проверяем число повторений для
последнего значения и выбираем
наибольшее
 
Печатаем ответ
 
Индексирование массивов
 
В олимпиадных задачах иногда требуется перечислить порядок следования номеров элементов массивов, при этом, значения элементов переставлять нельзя. В этих случаях необходимо завести массив, содержащий номера всех элементов основного массива и преобразовать его таким, чтобы его значения соответствовали порядку следования элементов обрабатываемых массивов в заданном порядке. То есть, в искомом массиве будет перечислен порядок следования индексов элементов обрабатываемого массива. Операция формирования такого массива называется индексированием. Рассмотрим пример:
-       Сформировать массив B следования номеров элементов числового массива A в порядке возрастания. Для иллюстрации рассмотрим таблицу:
 
A
12
34
22
44
1
3
4
7
45
B
5
6
7
8
1
3
2
4
9
номер элемента
1
2
3
4
5
6
7
8
9
 
В этой таблице для данного массива A сформирован соответствующий массив B и для каждой пары элементов массива B выполняется условие: если j>=i, то A[B[j]]>=A[B[i]].
  
Program indexes;
Type
          Ar=array [1..20] of real;
          Br=array [1..20] of integer;
Var
          A:ar;
          B:Br;
          I,J,N,K:integer;
          Begin
Write(‘число элементов N=’);
Readln(n);
Writeln(‘введите значения’);
For i:=1 to n do
begin
Readln(A[i]);
B[i]:=i
End;
For i:=1 to n-1 do
For j:=i+1 to n do
          If A[B[i]]>A[B[j]] then begin
                    K:=B[i];
                    B[i]:=B[j];
                    B[j]:=K
                    End;
For i:=1 to n do
Writeln(‘элемент номер ‘,B[i],’ значение ‘,A[B[i]])
End.
 
 
Описание типов для массивов
 
 
Описание массива A
Описание массива A
Описание переменных
 
 
 
Ввод количества элементов
 
 
Ввод значений элементов A
Инициализация массива B
 
Для i от 1 до n-1
Для j от i до n
Если предыдущий больше следующего, то
переставляем элементы
массива индексов
 
 
Вывод результатов
 
Здесь массив B сначала содержал значения в порядке возрастания номеров (инициализация массива B). В процессе выполнения сортировки, элементы массива B переставляются так, чтобы выполнялось условие задачи.
 
Формирование (заполнение) массива по специальному правилу
 
Такие задачи достаточно распространены на первых турах олимпиад по информатике. Они могут состоять в формировании одномерного массива, например:
-       Ввести целое число и сформировать массив, содержащий его цифры.
Такая задача может содержаться как часть решения другой, например:
-       Выбрать такие четырехзначные числа, сумма цифр которых является простым числом. При решении такой задачи возможно сначала сформировать массив цифр числа, потом найти их сумму, затем проверить является ли сумма простым числом. (Заметим, что можно найти сумму цифр и, не помещая их в массив).
Не менее распространенными являются задачи о заполнении двумерного массива числами в специальном порядке, например:
-       Заполнить двумерный массив числами по спирали, как показано в таблице
      
1
2
3
4
5
16
17
18
19
6
15
24
25
20
7
14
23
22
21
8
13
12
11
10
9
 
Для решения подобных задач можно использовать такой подход. Известна позиция первого размещаемого числа – индексы соответствующего ему элемента массива. Известно сколько всего чисел должно быть внесено в массив. Перебираем начиная с первого значения чисел для записи в ячейки массива, записываем значение в текущую позицию, вычисляем значения индексов массива для записи следующего числа. Вычисление новых значений индексов и составляет в таких задачах наиболее сложную часть. В некоторых случаях можно воспользоваться следующей идеей.
Заполним вручную на бумаге несколько примеров таблиц для массивов различной размерности. После внимательного изучения примеров может быть выявлена закономерность изменения индексов. Чаще всего выясняется, что один или оба индекса движутся в определенных направлениях, а по достижении одним из индексов определенной границы направления изменяются. В нашем примере сначала индексы имеют значения (1,1), потом индекс строк остается неизменным (приращениеY = 0), а индекс столбцов увеличивается (приращениеX = 1). После того как будет достигнута правая граница (граница_правая сначала была = 5) направление движения поменяется (приращениеX = 0, приращениеY =1), кроме того правая граница сдвинется на 1 влево (граница_правая = граница_правая -1). После этого заполнение массива пойдет вниз по правой колонке до тех пор, пока не будет достигнута нижняя граница (граница_нижняя была = 5). В этой точке снова произойдет переключение направлений движения (приращениеX = -1, приращениеY =0), кроме того нижняя граница сдвинется на 1 вверх (граница_нижняя = граница_нижняя-1). Движение пойдет влево, затем, после переключения направлений вверх и снова вправо. Обратим внимание, что здесь есть еще две границы левая и верхняя. Значение первой сначала должно быть установлено 1, а второй 2, так как движение вверх должно быть остановлено при выходе на вторую строку. Программа для решения этой задачи приведена ниже. Предлагаем самостоятельно разобраться с тем как она работает.

 

program spiral;
var
 a:array [1..20,1..20] of integer;
 i,j,p,k,n,x1,x2,y1,y2:integer;
begin
readln (n);
x1:=2; x2:=n;
y1:=1; y2:=n;
k:=0;
i:=1; j:=1;
for p:=1 to n*n do
begin
a[i,j]:=p;
case k of
0: if j else begin
    k:=1;
    i:=i+1;
    y2:=y2-1
    end;
1: if i    k:=2;
    j:=j-1;
    x2:=x2-1
    end;
2: if j>y1 then j:=j-1 else begin
    k:=3;
    i:=i-1;
    y1:=y1+1
    end;
3: if i>x1 then i:=i-1 else begin
    k:=0;
    j:=j+1;
    x1:=x1+1
    end;
end;
end;
for i:=1 to n do
begin
   for j:=1 to n do
   write (a[i,j]:3);
   writeln
end;
end.


 

Copyright © 2005–2017 ХабЦНИТ ТОГУ Отправить письмо
Создание сайтов в Хабаровске
Любое агентство горящих путевок Днепропетровск считает должно увеличивать свой ассортимент туров.