Структурные типы данных. Массивы (стр. 5 )

3.  Предусмотреть вывод в строку исходного массива.

4.  Организовать комментированный вывод результата.

5.  Предусмотреть повторение программы по желанию пользователя.

Задача 1.

Сформировать одномерный массив А, состоящий из N элементов. Элементам массива А последовательно присвоить значения первых N чисел Фибоначчи.

Задача 2.

Сформировать одномерный массив А, состоящий из N элементов, элементы которого А[i] равны значениям функции y = x2+2x+5 для x = 1.1; 1.2; … 1+0.1*N.

Задача 3.

Дан целочисленный одномерный массив А, состоящий из N элементов. Составить программу вычисления S = A1+A1A2+ … +A1A2 … An.

Задача 4.

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

Задача 5.

Дан одномерный целочисленный массив А, состоящий из N различных элементов. Поменять местами наибольший и наименьший элементы массива. Исходный и полученный массивы вывести на экран.

Задача 6.

Дан одномерный целочисленный массив А, состоящий из N различных элементов. Составить программу, позволяющую определить, со скольких отрицательных элементов он начинается.

Сортировка одномерного массива.

Сортировка – это такая перестановка элементов в массиве, после которой они оказываются упорядоченными требуемым образом.

Сортировка методом "пузырька".

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

Обсудим сортировку числовых значений в порядке убывания.

Массив А из четырёх элементов: А[1], А[2], А[3], А[4]. Пройдёмся по массиву от первого элемента до последнего, выбирая по очереди пару смежных значений. Если левое значение меньше правого, то выполняется обмен значениями. Это гарантирует перемещение наименьшего значения в последний элемент массива, хотя остальные значения могут и не быть пока упорядоченными. Дальше будем рассматривать элементы от первого до предпоследнего и т. д.

Стадии пузырьковой сортировки массива из четырёх значений.

7	13	2	19	Начальное содержимое
¾¾¾¾¾¾Пробегаемые значения¾¾¾¾¾¾®
13	7	19	2	После первого прохода
¾¾¾¾Пробегаемые значения¾¾®
13	19	7	2	После второго прохода
Пробегаемые значения®
19	13	7	2	После третьего заключительного прохода

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

Каждый проход обеспечивает перемещение наименьшего значения в конец рассматриваемой порции массива, т. е. «подъём вверх» в правильную позицию.

Метод «Пузырька».

На первом шаге просматриваем все элементы массива (n). На следующем – количество просматриваемых элементов уменьшилось, на 1, т. к. элемент, имеющий наименьшее значение уже стоит в конце массива и его ещё раз просматривать не надо. На последнем шаге мы просматриваем два элемента (первый и второй).

Как можно записать эти действия по правилу языка Pascal?

for i: = N downto 2 do.

На каждом из проходов мы сравниваем два соседних элемента и на первом шаге сравнение идет всех элементов, на следующем шаге сравниваются n-1 элемент, на следующем: n-2 элемент и т. д.

Как можно записать эту конструкцию?

for i: = n downto 2 do

for j: = 1 to i-1 do

if a[j] < a[j+1] then {обмен значениями}

Фрагмент программы пузырьковой сортировки (в порядке убывания).

for i: = n downto 2 do

for j = 1 to i – 1 do

if a[j] < a[j + 1]

then begin

t: = a[j];

a[j]: = a[j + 1];

a[j + 1]: = t;

end

Задание для работы на компьютере.

Составить программу, позволяющую отсортировать массив по возрастанию.

Для тех, кто быстро справился с заданием, дать дополнительно:

В отсортированный массив вставить в нужное место массива, не нарушая его сортировку, какое-то значение, запрошенное у пользователя. Примечание: дополнительный массив не использовать.

Сортировка выбором (в порядке возрастания).

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

program vybor;

{описания};

begin

{ввести массив х};

for i = 1 to n do

begin

{найти индекс k наименьшего элемента среди xi, xi+1, …, xn};

{переставить xi с xk};

{вывод очередного элемента массива};

end;

end

Будем детализировать схему.

ввод массива не вызывает затруднений

for i: = 1 to n do

read (x[i])

{поиск индекса k – наименьшего элемента среди x[i], … x[n]};

k: = i;

for j: = i + 1 to n do

if x[j] < x[k] then k: = j;

{для перестановки x[i] с x[k] используется переменная v}

v: = x[i]; x[i]: = x[k]; x[k]: = v;

Теперь напишем программу.

program vybor;

const n = 20;

type u = array [1 .. n] of real;

var x: u;

v: real;

i, j, k: integer;

begin

for i: = 1 to n do

read (x[i]);

for i: = 1 to n-1 do

begin

k: = i;

for j: = i + 1 to n do

if x[j] < x[k] then k: = j;

v: = x[i]; x[i]: = x[k]; x[k]: = v;

writeln (x[i]);

end

end.

Сортировка массива с использованием индекса.

a — массив исходных данных

b — массив индексов

program index;

uses crt;

type mas = array [1 .. 100] of integer;

var a, b: mas

i, j, t, n, k, it, i1, i2, l: integer;

c: char;

begin

repeat

writeln (‘Сортировка массива с использованием индекса’);

writeln (‘Введите количество элементов массива’);

readln (n);

for i: = 1 to n do a[i]: = random (100);

{задаём начальные значения элементов массиву индексов}

{перед началом сортировки массив индексов b[i] имеет значения }

{b[1] = 1, b[2] = 2, …, b[n] = n}

for i: = 1 to n do

b[i]: = i;

writeln (‘исходный массив’);

for i: = 1 to n do

write (a[i], ‘ ’); writeln;

{Вместо переупорядочения самих значений в процессе сортировки}

{ можно образовать массив индексов, в котором отмечаются правильные}

{ места значений массиве. Во время сортировки значения остаются}

{ на исходных местах, а изменяется индекс}

for i: = n downto 2 do

for j: = 1 to i – 1 do

{Для индексов должно выполняться соотношение :}

{b[исходная позиция] = новая позиция}

begin

i1: = b[j];

i2: = b[j + 1];

{При сортировке во время каждого прохода сравниваются}

{ значения из a, определённые по b[ ], }

{а переставляются значения индекса в b[ ]}

if a[i1] < a[i2] then

begin

b[j]: = i2;

b[j + 1]: = i1;

end;

end;

writeln (‘Отсортированный массив’);

for i: = 1 to n do

begin

i1: = b[i];

write (a[i1], ‘ ’);

end;

writeln;

writeln (‘y/Y’); readln (c);

until (c = ‘n’) or (c = ‘N’;)

end.

Задачи для самостоятельного решения на компьютере.

Требования к оформлению задачи:

1.  Предусмотреть запрос у пользователя размера массива.

2.  Предусмотреть возможность ввода массива по желанию пользователя: или в диалоге, или формирование массива с использованием датчика случайных чисел.

3.  Предусмотреть вывод в строку исходного массива.

4.  Организовать комментированный вывод результата.

5.  Предусмотреть повторение программы по желанию пользователя.

Задача.

Дан одномерный целочисленный массив А, состоящий из 2N элементов (N – заданное натуральное число). Получить новую последовательность

А1, А2n, A2, A2n-1, A3, A2n-2, …, An, An+1.

Проверочная работа № 1

По теме «Одномерные массивы».

Задание 1.

Имеются описания массивов:

Const d=21; S=1..d;