из электронной библиотеки / 262983782449737.pdf

var i,n:integer;

a:array [1..50] of integer; begin

for i:=1 to 10 do begin a[i]:=100; (a[i]:= 2*i+1): for i:=1 to 10 do write (a[i]:3); {вывод в строчку} writeln;

readln;

end.

3. Заполнение массива случайными числами из отрезка [a;b] a[i]:=random(b-a+1)+a

random(g) – генерирует случайные числа из интервала [0;g) – (значение g не входит)

randomize; – инициализация функции random(g)

program tabl; var i,n:integer;

a:array [1..50] of integer; begin

randomize;

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

for i:=1 to 10 do write (a[i]:3); {вывод в строчку} writeln;

readln;

end.

Обработка элементов одномерного массива.

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

Постановка задачи.

Создать одномерный целочисленный массив А из n элементов и вывести его на экран (n ввести с клавиатуры, а сами значения элементов задать случайным образом из диапазона [-40,40]). Найти в массиве сумму элементов, кратных 5.

Построение математической модели i,n,s:integer;

s:=s+a[i];

s – результат

71

Блок-схема:

Программный код: program massiv1; var i,n,s:integer;

a:array [1..20] of integer; begin

randomize;

writeln ('введите количество элементов'); readln (n);

for i:=1 to n do begin; a[i]:=random(81)-40; end;

{вывод элементов в строчку} for i:=1 to n do write (a[i]:5);

72

writeln;

for i:=1 to n do if a[i] mod 5 =0 then s:=s+a[i]; writeln ('сумма элементов, кратных пяти', s:3); readln;

end.

2. Подсчет количества элементов, удовлетворяющих определенному признаку

Постановка задачи.

Создать одномерный вещественный массив К из Т элементов и вывести его на экран (Т ввести с клавиатуры, а сами значения элементов задать случайным образом из диапазона [-30,30]). Найти в массиве количество положительных элементов.

Построение математической модели. Исходные данные: i,t:integer; Результат: n

Блок-схема:

нач

Т

i=1,T

n

кон

73

Программный код: program massiv2; var i,t,s:integer;

k:array[1..20] of integer; begin

randomize;

writeln ('введите количество элементов'); readln (t);

for i:=1 to t do begin; k[i]:=random(61)-30; end;

{вывод элементов в строчку} for i:=1 to t do write(k[i]:3); writeln;

for i:=1 to t do if k[i]>0 then n:=n+1;

writeln ('количество положительных элементов', n:5); readln;

end.

Практический блок

Индивидуальные задания:

1. Заполнение одномерного массива.

1.1.Заполнить линейную таблицу 12 случайными числами из [-1;7];

1.2.Заполнить линейную таблицу 15 случайными числами из [-10;5];

1.3.Заполнить линейную таблицу 17 случайными числами из [-6;5];

1.4.Заполнить линейную таблицу 13 случайными числами из [-7;5];

1.5.Заполнить линейную таблицу 14 случайными числами из [-7;2];

1.6.Заполнить линейную таблицу 16 случайными числами из [-5;6];

1.7.Заполнить линейную таблицу 17 случайными числами из [-4;3];

1.8.Заполнить линейную таблицу 11 случайными числами из [-1;5];

1.9.Заполнить линейную таблицу 12 случайными числами из [-5;4];

1.10.Заполнить линейную таблицу 14 случайными числами из

[-4;3];

2.Подсчет количества и суммы элементов, удовлетворяющих определенному признаку.

2.1.Найти количество книг фонда из 20 экземпляров, год издания которых меньше 1954 г. (линейная таблица заполняется случайными числами – годами издания от 1950 по 1990).

74

2.2.Найти количество книг фонда из n экземпляров, год издания которых меньше переменной god (линейная таблица заполняется случайными числами – годами издания от god1 по god2).

2.3.Произвольная линейная таблица заполняется случайными числами [-2;2]. Найти сумму всех положительных элементов линейной таблицы.

2.4.Произвольная линейная таблица заполняется случайными числами [-5;5]. Определить количество отрицательных элементов.

2.5.Линейная таблица заполняется годами рождения читателей библиотеки (допустимо заполнение случайным образом). Определить количество читателей старше 20 лет.

2.6.Линейная таблица заполняется годами рождения читателей библиотеки (допустимо заполнение случайным образом). Определить количество читателей младше 20 лет

2.7.Линейная таблица заполняется годами рождения читателей библиотеки (допустимо заполнение случайным образом). Определить количество пенсионеров.

Задания для самостоятельной работы

1.Какие способы структурирования данных вы знаете?

2.Приведите примеры массивов из библиотечной деятельности.

3.Какие физические объекты можно сопоставить с одномерным массивом? Двумерным массивом? Трехмерным массивом? Четырехмерным массивом?

4.Назовите характеристики элемента одномерного массива.

5.Зачем резервировать место под массив? Как это сделать?

Творческий блок

Алгоритмы поиска (поиск максимального элемента в линейной таблице). Линейная таблица заполняется годами рождения читателей библиотеки (допустимо заполнение случайным образом). Определить самого старшего читателя и его порядковый номер.

75

Тема 11. Структурированные типы данных. Сортировки

Теоретический блок

Сортировка в общем виде заключается в распределении элементов множества по группам в соответствии с определёнными правилами.

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

Существуют различные методы сортировки. Будем рассматривать каждый из методов на примере задачи сортировки по возрастанию массива из N целых чисел.

Сортировка выбором. Идея метода заключается в том, что находится минимальный элемент массива и меняется местами с первым элементом (с номером 1). Затем минимум ищется среди элементов со второго до последнего и ставится на 1 место, и так далее. Необходимо найти N-1 минимум. Можно искать не минимум, а максимум, и ставить его на N-1 место и так далее место. Также применяют модификацию этого метода с одновременным поиском максимума и минимума. В этом случае количество шагов внешнего цикла N div 2.

Вычислительная сложность сортировки выбором – величина порядка N*N, что обычно записывают как O(N*N). Это объясняется тем, что количество сравнений при поиске первого максимума равно N-1. Затем N-2, N-3, и так далее до 1, итого: N*(N-1)/2.

76

program Sort_vibor; uses crt;

var a,b: array[1..10] of integer; n,i,r,k,min:integer;

begin clrscr; randomize; write('Vvedite n'); d:=0;

readln(n);write('perw massiv'); writeln; for i:=1 to n do begin a[i]:=random(11); write(a[i]:3);end;

77

for k:=1 to n-1 do begin min:=k;

for i:=k+1 to n do if a[i]<a[min] then min:=i; r:=a[min]; a[min]:=a[k]; a[k]:=r;

writeln; write(k,' prohod'); writeln; for i:=1 to n do write(a[i]:3); writeln; end; writeln(d);

readln;

end.

Тестирование. Проанализируйте изменения элементов массива после каждого прохода.

Сортировка обменом. Алгоритм сортировки обменам – простой алгоритм сортировки. Для понимания и реализации этот алгоритм – простейший, но эффективен он лишь для небольших массивов.

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

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно

78

сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает – массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде, отсюда и название алгоритма).

79

Program sort;

var i,r,k,n,g:integer; tab:array[1..100] of integer;

begin

writeln ('vvedite n'); readln(n); randomize;

for i:=1 to n do begin tab[i]:=random(10); write(tab[i]:3); end;

for g:=1 to n-1 do begin

for i:=n-1 downto g do

if tab[i]>tab[i+1] then begin r:=tab[i];

tab[i]:=tab[i+1];

tab[i+1]:=r;

end;

writeln;

writeln (g:2,' proxod');

for i:=1 to n do write(tab[i]:3); writeln;

end;

readln;

end.

Тестирование проведите как в предыдущей задаче.

Практический блок

1.Разберите блок-схемы алгоритмов сортировки, введите программные коды и протестируйте алгоритмы.

2.Приведите примеры и словесно объясните, как бы вы действовали, если бы нужно было сортировать книги, например, по размеру?

80