Как можно было бы сделать, если использовать массив?

⇐ ПредыдущаяСтр 9 из 23Следующая ⇒

1. Ввести значения и заполнить ими массив.

2. Найти среднее значение в массиве.

Var

a: array[1..10] of integer;

s: integer;

i: byte;

begin

s: =0;

for i: =1 to 10 do

begin

wtite(‘введите --> ’);

readln(a[i]);

s: =s+a[i];

end;

end.

16.Правила разработки цикла

Известно по крайней мере два класса задач, которые приводят к появлению цикла :

· обработка или формирование массивов - при переносе формулировки задачи типа

< обработать массив > //типа < вывести на экран>

или

< сформировать массив> //типа инициализировать/ввести массив>

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

· итерационные алгоритмы – алгоритмы, основанные на использовании рекуррентных формул. При решении задач этого (второго) класса циклы разрабатываются снизу-вверх. Рекуррентные формулы обычно используются потому, что для снижения сложности вычислений (замена умножения - сложением, а возведения в степень - умножением и т.п.) на каждом шаге при каждом новом повторении цикла каждый новый результат получается с использованием старого (ранее полученного) результата. Можно выделить 2 разновидности итерационных алгоритмов:

1. Алгоритмы, связанные с реализацией т.н. n-арных операций:

S = =x₁+x₂+x₃+...+x_n S = = x₁∙ x₂∙ x₃∙...∙ x_n S = X! =1∙ 2∙ 3∙ 4∙...∙ X и т.п.

Реализация n-арных операций требует преобразования их в последовательность двухместных (бинарных) операций, что приводит к появлению повторяющихся действий и необходимости сворачивания этих повторяющихся действий в цикл.

2. Алгоритмы приближенных вычислений - алгоритмы, разрабатываемые для поэтапного (пошагового) приближенного нахождения решения задач (например, поиск корня уравнения), для которых неизвестно, как найти точное решение.

Обе задачи второго класса приводят к появлению циклов, которые разрабатываются методом " снизу вверх ". При этом первая разновидность задач второго класса реализуется с помощью циклов с известным числом повторений (цикла for - для каждой n-арной операции, зная n, можно определить число повторений), а вторая разновидность - с помощью циклов с неизвестным числом повторений.

Известно, что структура цикла (с известным числом повторений) включает в себя три компонента: подготовка цикла, заголовок цикла, тело цикла (те действия, которые необходимо многократно повторить). Заголовок цикла задает правила изменения параметра цикла (тело цикла повторяется для каждого значения параметра цикла).

Как правило, очередное повторение тела цикла строится с использованием результата, полученного при предыдущем повторении тела цикла, наприемр, как в данном случае

x_i = x_i-1 + h

y_i = f(x_i).

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

Однако, если цикл организован таким образом, что очередное повторение тела цикла не использует результат предыдущего повторения, как в данном случае

x_i = (i-1)*h и y_i = f(x_i)

то в этом случае подготовка цикла не нужна.

Порядок разработки циклов восходящим методом:

1. Записываем линейный алгоритм (в котором, например, многоместная операция реализуется с помощью последовательности большого количества бинарных операций).

2. Находим рекуррентную формулу (замечаем повторяемость) для определенной последовательности шагов.

3. Те повторяющиеся действия, для которых удалось получить обобщенную формулу, сворачиваем в цикл. При этом в тело цикла попадают те действия, которые записаны в виде рекуррентной формулу; в заголовке цикла записываем правило, с помощью которого устанавливается, повторять далее цикл или нет; в подготовку цикла включаются те действия, которые не удалось обобщить.

4. Если подготовка цикла не простая, то необходимо выполнить ее упрощение.

5. Если попытка упрощения подготовки цикла удалась, то необходимо скорректировать заголовок так, чтобы число повторений стало на 1 больше.

6. Необходимо выполнить операцию отбрасывания лишних индексов.

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

При появлении команд:

Сформировать массив

или

Обработать массив

Пример:

ввести массив

или

вывести массив не связано с вычислением и накоплением значений

или

присвоить массив массиву

Но не:

Найти сумму элементов массива связано с накоплением

Найти минимальный или максимальный элемент массива значений

эти команды (из верхних примеров) уточняются следующим образом: в силу того, что объект (массив) обладает однородной внутренней структурой, мы можем воспользоваться стандартным правилом уточнения команд и перенести исходную задачу на каждый элемент массива (компонент объекта).

В результате получается большое количество формулировок команд следующего вида:

обработать первую компоненту

обработка массива обработать вторую компоненту

........................................................

обработать n-ую компоненту

уточнение

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

1. Сразу можно записать тело цикла, имеющее одну из следующих 2 форм:

сформировать i-ю компоненту или обработать i-ю компоненту

2. Можно сразу записать заголовок цикла, в котором в качестве параметра цикла можно использовать индекс (номер) элементов массива. Закон изменения параметра цикла, или количество повторений цикла, будет определяться числом компонент, которые необходимо обработать.

Например:

For i: = < нач. знач.> to < кон. знач.> do …

где i – параметр цикла.

3. Согласно ранее сформулированному правилу с учетом того, что тело цикла обычно не использует результат предыдущего, подготовка цикла обычно не нужна. Выше было показано, что подготовка цикла нужна только в случае формулировок задач вида

- Найти сумму элементов массива

- Найти минимальный или максимальный элемент массива

и т.п.

Действия над массивами

15.6.1 Можно присваивать содержимое одного массива другому, но не всегда.

Type

t = array [1..10] of byte;

Var

a, b: array [1..10] of byte;

c: array [1..10] of byte

e, f: t;

Правильно

begin

a: = b;

e: = f;

Неправильно

a: = c;

e: = a;

Правило, по которому неправильное отделяется от правильного, очень простое: вы можете присвоить содержимое только таких массивов, у которых эквивалентны типы согласно объявлению.

Тип С неэквивалентен типам А и В. Если бы нужно было сделать тип С эквивалентным типам А и В, то нужно:

a, b, c: array [1..10] of byte;

Замечание: хотя можно присваивать содержимое одного массива другому, вы нельзя их сравнивать.

if a = b then... - нельзя.

Поэтому, если нужно сравнить 2 массива, то их сравнивать придется посимвольно (кроме символьных массивов, которые в Паскале эквивалентны строкам).

15.6.2 Инициализация массивов.

Замечание: в отличие от языка Си, где есть старт языка т согласно этому стандарту все глобальные переменные, в том числе массивы, в начале выполнения программы инициализируются нулями, для Паскаля (Турбо-Паскаля) нет стандарта (этот язык - внутренняя разработка фирмы Борланд) и массивы (в зависимости от реализации) могут не инициализироваться (инициализироваться всяким мусором - не обязаны инициализироваться обязательно 0). Поэтому для определенности необходимо перед использованием массивов задать им начальное значение. Для этого есть три пути:

1. Использование типизированных констант (уже рассмотрели выше)

2. Использование цикла (по элементам)

3. Использование специализированной функции Fillchar().

Использование цикла (по элементам)

Var

a: array [1..5] of byte;

i: byte;

begin

randomize;

for i: = 1 to 5 do

a[i]: = i; // элементы массива инициализируются значениями параметра цикла

или

a[i]: = random(100); // элементы массива инициализируются псевдослучайными числами

или

begin write(‘a[‘, i, ‘] = ‘);

readln(a[i]) end;

// элементы массива инициализируются в диалоге с пользователем

Использование процедуры Fillchar(): типа char

Fillchar(имя массива, число байт (не элементов), значение) - заполняет побайтно всю область памяти под массив заданным значением {fillchar (a, 5, #0); }, причём проверка на выход за границы массива не выполняется.

Пользоваться этой процедурой необходимо аккуратно: если тип элемента массива будет не byte, а integer, то fillchar (a, 5, #1) забьет массив значением 257, а не 1. Кроме того, если бы тип элементов был integer, надо было бы писать 5*sizeof(integer) вместо 5.

15.6.3 Элементы массива можно использовать везде, где можно использовать обычные скалярные переменные (в операторах присваивания и процедурах ввода-вывода и т.п.)

15.6.4 Обмен значениями между подмассивами и между массивом и подмассивами

15.6.4.1 Обмен между подмассивами

Подмассив – часть массива, к которой можно обратиться, используя число индексов, меньшее чем число размерностей массива. Более общее название подмассива – сечение. В языке PL/I: А(1, *) – 1-я строка, А(*, 1) – 1-я колонка массива. В Паскале сечения возможны только для строк: A[1] – первая строка n-мерного массива.

Правило (выше было дано): тип элемента массива определяется тем, сколько индексов указано после имени массива.

Рассмотрим пример:

Const N=3;

Var

A: array[1..2, 1..N] of byte;

B: array[1..2, 1..N] of byte;

Begin можно использовать sizeof(тип элемента)*число_ячеек

Fillchar(a, sizeof(a) div 2, 1); ------------- заполнение 1-ой строки единицами (правильно)

Fillchar( a[2, 1], sizeof(a) div 2, 2); ------------- заполнение 2-ой строки двойками (неправильно)

можно и так: round(sizeof(a)/2) -- в отличие от DIV деление с помощью ‘/’ всегда дает вещественный результат

Замечание. Так указывать параметр fillchar нельзя (и указатель использовать тоже нельзя)

Надо (можно) один из двух вариантов:

1) Fillchar(a, sizeof(a), 2); //весь массив а заполняем двойками

Fillchar(а, sizeof(a) div 2, 0); //первую строку очищаем от двоек

2) Fillchar( a[2], sizeof(a) div 2, 2); //вторую строкузаполняем двойками

a[1]: = a[2]; -------- можно ------- обмен между 1 и 2 строками одного массива

b[1]: = a[2]; -------- нельзя (типы не эквивалентны)

Правило: Обмениваться могут подмассивы только эквивалентных типов.

Однако это правило можно обойти следующим образом. Пусть надо b[1]: = a[2].

Move( a[2], -- 1 аргумент (откуда брать)

b[1], -- 2 аргумент (куда помещать)

sizeof(a) div 2); -- 3 аргумент (сколько переслать байтов)

Эта процедура просто перемещает байты из одного места в памяти в другое (проверку типа этих байтов она не выполняет).

15.6.4.2 Обмен между подмассивом и массивом

Рассмотрим сразу Пример:

Type

t=array[1..3] of byte;

Var

A: array[1..2, 1..3] of byte;

B: t;

C: array[1..2] of t;

Begin тип A[2] = array[1..3] of byte (≠ t)

A[2]: = b; ------------------------- нельзя (типы не эквивалентны)

тип b = t

C[2]: = b; ------------------------- можно (тип c[2] = t = тип b)

Move(b, a[2], sizeof(b)); ------- можно

B: = a[2]; -------------------------- нельзя

B: = t(a[2]); -------------------------- можно

Move(a[2], b, sizeof(b)); ------- можно

B: = c[2]; --------------------- можно

15.6.5 Сдвиг значений внутри массива

15.6.5.1 Сдвиг элементов одномерного массива вправо

Задача: необходимо выполнить сдвиг заданной части массива M (начиная с позиции i₁ (пусть i₁=3) и заканчивая позицией i₂ (пусть i₂=7) на заданное число позиций вправо (пусть = 2).

Изображение постановки задачи имеет вид:

Var M: array[1..11] of byte; Используем разработку цикла восходящим

m[9]: =m[7] m[8]: =m[6] m[7]: =m[5]

m[6]: =m[4] m[5]: =m[3] i j

Обобщенная запись: M[i]: = M[j] = M[a*i+b]

i₁ i₂ i уменьшается методом и получим следующий линейный

алгоритм:


M_j


M_i

Массив одномерный и для прохода по нему достаточно одного индекса – i (а у нас в обобщенной записи – два индекса). Чтобы избавиться от второго индекса (j), надо в общем случае выразить зависимость j от i. В общем виде эта зависимость линейная (можно по точкам построить зависимость j от i для проверки) и имеет вид: j: = a*i + b

Для нахождения a и b надо составить систему уравнений (из линейного алгоритма):

7 = a*9 + b

6 = a*8 + b

j i

Теперь можно записать цикл. НО:

Нельзя

(глядя на рисунок выше написать)

i₁ + i₃ i₂ + i₃-1

For i: = 5 to 9 do

M[i]: = M[i-2];

Здесь новые значения преждевременно

будут затирать старые

Надо число байт

For i: =9 downto 5 do m[i]: = m[i-2]; т.е. двигаться по массиву при сдвиге вправо надо в направлении, противоположном направлению сдвига, т.е. влево.		Move[a[5], a[3], 5); // сдвиг влево Move[a[3], a[5], 5); // сдвиг вправо для произвольного типа надо писать так: (i₂ – i₁ + 1) * (sizeof(тип элемента)) число пересылаемых число байт на один элемент элементов
	Процедура Move всегда правильно выполняется (она сама в правильном порядке расставляет операторы присваивания)

Самостоятельно: разобрать сдвиг массива влево.

15.6.6 Поиск элемента (одномерного ) массива

Поиск – это нахождение индекса(ов) элемента(ов), значение которого удовлетворяет некоторому установленному правилу (критерию). Обычно в качестве критерия принимают равенство эталону.

Поиск

label уходим; Const L=1; H=10; Var A: array[L..H] of integer; эталон: integer; Результат: Longint; Нашли: Boolean; Середина, Низ, Верх: Longint; //текущие границы интервала Begin Низ: = L; {левая граница интервала} Верх: = H; {правая граница интервала } Нашли: = FALSE; {признак того, что нашли} Середина: = 0; {индекс середины интервала между Верх и Низ} Результат: = 0; {индекс искомого элемента} эталон: =....; {то, что ищем} {Проверка - есть ли искомый эталон в массиве? } IF (A[Низ] > эталон) OR (A[Верх] < эталон) then begin writeln('Совпадение искать бесполезно'); goto уходим; end; Repeat Середина: = round((Верх+Низ)/2); IF A[Середина] > эталон then Верх: = Середина //эталон в левой половине else if A[Середина] < эталон then Низ: = Середина //эталон в правой половине else Нашли: = TRUE; // значит A[Середина] = эталон until (Нашли=TRUE) OR (Низ > = Верх)) IF Нашли = TRUE then Результат: = Середина {в Результат - индекс искомого элемента} else writeln(«Совпадений не найдено.») уходим:; end.

В самом начале двоичного поиска имеем 2 ситуации:

Ситуация	Действие
Эталон в массиве есть	Найти
Эталона в массиве нет (A[Низ] > эталон) OR (A[Верх] < эталон)	Сообщение

цикл, где на каждом повторе вычисляем новую

середину и анализируем 3 ситуации:

Ситуация	Действие
Эталон в левой половине (A[Середина] > эталон)	Верх: = Середина
Эталон в правой половине (A[Середина] < эталон)	Низ: = Середина
Эталон ровно в середине (A[Середина] = эталон)	Нашли: = True Результат: = Середина

выход из цикла: = ((Нашли = True) OR

(Низ > = Верх))

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

см. Однопроходные алгоритмы (индуктивные функции) в Кушниренко, Лебедев «Программирование для математиков»

а) За один проход по массиву (файлу, списку, последовательности) - может быть выполнен, если удовлетворение запроса не связано с накоплением статистики и ее последующим анализом (накопленной статистики).

Например: выбрать из всех студентов только мужского пола ростом выше 1.8м и не старше 20 лет.

Здесь можно записать обобщенный критерий поиска в виде логического выражения

П1 и П2 и П3

Пол = мужской рост > = 180 см возраст < =20

Задача поиска сводится к однократному проходу по массиву и отбору в ходе прохода тех студентов, характеристики которых обращают приведенное логическое выражение в истину (TRUE):

Repeat

if (П1 and П2 and П3)

then отобрать

else искать дальше

перейти к следующему

until закончить

б) За несколько проходов по массиву– если удовлетворение запроса связано с накоплением и анализом статистики.

Например: надо выбрать из всех студентов только 3 студентов моложе 20 лет и ростом не ниже 180см которые чаще всего звонят (пишут) мне после 22: 00.

Слово чаще в условии говорит о том, что необходимо накопить статистику перед выбором.

Здесь уже надо рассматривать не один критерий, а два (второй позволит выбрать из тех, кого отобрали по первому критерию):

- критерий, по которому отбирается (накапливается) статистика;

- критерий отбора из того, что накопили.

Критерий для накопления статистики (сколько раз звонил) должен включать признаки:

- информация о поле студента;

- информация о возрасте студента;

- информация о росте студента;

- информация о времени звонка студента

и будет иметь вид, подобный рассмотренному выше

П1 и П2 и П3 и П4

Пол = мужской рост > = 180 см возраст < =20 время > = 22

Решить поставленную задачу можно по крайней мере так:

Вначале за первый проход выбираем (запоминаем число звонков) для всех тех студентов, которые подходят по критерию, сформулированному выше. Затем за второй проход среди отобранных кандидатов проверяем (или вычисляем, если при первом проходе было лень вычислять) число звонков и выбираем тех, у кого это число больше.

15.6.7 Сортировка элементов (одномерного) массива (для ускорения поиска в массиве)

Сортировка - расположение (переупорядочивание) элементов по определенному критерию. Обычно - по убыванию (descend) или возрастанию (ascend). Существует много методов сортировки. Простейший, но не самый худший (лучший) - сортировка выбором. Рассмотрим, как выполнить сортировку по убыванию. Для этого надо:

- сначала последовательно рассматривать кандидатов на место самого первого элемента (самого большого), после чего наибольший из кандидатов становится первым (обменивается с первым);

- затем среди оставшихся (N-1) элементов массива последовательно рассматриваются кандидаты на место 2-го элемента и наибольший из кандидатов при просмотре становится вторым (обменивается со вторым элементом);

- и т.д.

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

Введем обозначения:

i – индекс элемента, на место которого ищем кандидата

j – индекс элемента, который мы просматриваем в качестве кандидата

i=1 i=2 i=3 i=4 i=5

1 3 4 2 5--- Исходное состояние массива

3 1 4 2 5----После итерации для j=2----------i = 1 j = 2

4 1 3 2 5----После итерации для j=3----------i = 1 j = 3 i = 1

4 1 3 2 5----После итерации для j=4----------i = 1 j = 4

5 1 3 2 4----После итерации для j=5----------i = 1 j = 5

-----------------------------------------------------------------

5 3 1 2 4----После итерации для j=3----------i = 2 j = 3

5 3 1 2 4----После итерации для j=4----------i = 2 j = 4 i = 2

5 4 1 2 3----После итерации для j=5----------i = 2 j = 5

-----------------------------------------------------------------

5 4 2 1 3----После итерации для j=4----------i = 3 j = 4 i = 3

5 4 3 1 2----После итерации для j=5----------i = 3 j = 5

------------------------------------------------------------------

5 4 3 2 1---- После итерации для j=5---------i = 4 j = 5 i = 4

Можно заметить:

- при поиске каждого нового кандидата число просматриваемых элементов уменьшается на единицу;

- при поиске кандидата на I-ое место I фиксируется, а J пробегает значения от I+1 до N.

Очевидно, что требуется два цикла:

- внешний по элементам, для которых ищем кандидата (цикл по параметру I, где I изменяется от 1 до N-1);

- внутренний по элементам-кандидатам (цикл по параметру J, где J изменяется от I+1 до N).

В итоге получим следующий фрагмент программы:

for i: = 1 to N-1 do

for j: =i+1 to N do

ему ищем замену

...

a[i]

...

a[j]

...

if ( a[j] > a[i] ) // если кандидат больше по значению, чем текущий

кандидат

then

begin

1) R: = a[i]; //чтобы не потерять значение переменной a[i]

2) a[i] = a[j];

3) a[j] = R;

end;

Замечания: по поводу реализации массивов в Паскале:

1. Число размерностей массива ничем не ограничено, однако размер массива как любой статической переменной в памяти ограничен 64 Кб (нельзя объявить тип размером > 64 Кб).

2. Индексы могут быть как положительными, так и отрицательными.

3. Тип индексов может быть любым порядковым, кроме типа longint.

4. В Турбо-Паскале имеется два режима компиляции, имеющие отношение к массивам:

{$R+} и {$R-} - выполняется или нет проверка, не выходит ли индекс за объявленные границы диапазона:

- если проверка выполняется, то при нарушении границ диапазона программа аварийно завершается с кодом 201 (Range Check Error);

- если проверка не выполняется, то при нарушении границ диапазона программа аварийно не завершается и никаких сообщений не выдается (но при этом программа сама себя портит).

Примечание:

Если отключить контроль диапазонов, можно создать массив с переменными границами (свободный массив):

{$R-}

Var a: array [1..1] of integer:

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

Если по адресу а динамически выделить память, то получим массив такого размера, какого пожелаем (мы вернемся к этому, когда будем рассматривать тему «Указатели»).

5. При передаче массивов как параметров в подпрограммы не рекомендуется определять тип массива непосредственно в заголовке подпрограммы (из-за невозможности при этом обеспечить эквивалентность типов фактического и формального параметров - массивов).

Замечание. Записать-то так при объявлении подпрограммы можно (сама запись не есть ошибка), но делать так не надо из-за проблем с совместимостью дальше по тексту программы..

6. В качестве формального параметра подпрограммы можно использовать массив без границ (открытый массив).

Var

a: array of char;

Для работы с ними используются функции High (возвращает верхнюю границу индекса - обычно = число элементов массива минус 1; не путать с Hi(x) для целый аргументов) и Low (возвращает нижнюю границу индекса, обычно = 0; не путать с Lo(x) для целых аргументов).

Множества.

⇐ Предыдущая 4 5 6 7 8910 11 12 13 Следующая ⇒