Ресурсы сети Интернет

Мая группа № 13 (Информатика и ИКТ)

Урок № 69

Тема программы: Работа с массивами

Тема урока: Решение задач на обработку массивов

Цель: научиться решать типовые задачи обработки массивов: поиск элемента и сортировка"

. ПЛАН

1. Видеоурок

3. Решение задач

Просмотреть видео: https://videouroki.net/video/32-tipovye-zadachi-obrabotki-massivov-poisk-ehlementa-i-sortirovka.html

Теоретический материал

Вопросы:

Поиск элемента массива с заданным значением.

Сортировка элементов массива.

Часто при решении некоторых задач требуется найти элемент массива со значением, равным чему-либо.

Задача: Написать программу, которая определяет, есть ли в массиве из 100 случайных целых чисел, на промежутке от 1 до 200, число, введённое пользователем.

Начнём написание программы для решения задачи. Назовём нашу программу zadannoe_chislo. Для работы программы нам потребуется массив из 100 элементов. Назовём его a. Так как элементами массива будут целые числа на промежутке от 1 до 200, укажем тип элементов массива byte. Также нам понадобятся переменные для хранения номера текущего элемента - i и для хранения числа, введённого пользователем - num. Объявим принадлежащими к целочисленному типу byte.

Напишем логические скобки. Тело программы будет начинаться с оператора writeln, который будет выводить на экран сообщение о том, что это программа, определяющая, есть ли в массиве случайных чисел число, введённое пользователем. Теперь запишем цикл для заполнения массива случайными числами. Это будет цикл для i, изменяющегося от 1 до 100. В нём будет оператор присваивания i -тому элементу массива a, суммы случайного целого числа на промежутке от 0 до 199 и 1. После того как мы заполнили массив случайными числами, напишем оператор write, выводящий на экран запрос на ввод числа на промежутке от 1 до 200, а также оператор readln для считывания значения переменной num.

Для того чтобы определить, есть ли введённое число в массиве a, мы позже опишем логическую функцию, которую назовём poisk, поэтому сейчас напишем условный оператор if, условием которого будет значение функции poisk, с введённым числом num в качестве аргумента. После служебного слова then в этом условном операторе, напишем оператор writeln, выводящий на экран сообщение о том, что число num есть в массиве. После слова else также напишем оператор writeln, который будет выводить на экран сообщение о том, что числа num нет в массиве.

Для того чтобы пользователь мог убедиться в том, что программа работает правильно, напишем оператор write, выводящий сообщение о том, что это массив, а также цикл с для i для вывода элементов массива через пробел. На этом описание основной программы завершено.

program zadannoe_chislo;

Var

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

i, num: byte;

Begin

writeln ('Программа, определяющая, есть ли в массиве случайных чисел число, введённое пользователем.');

for i:=1 to 100 do

a[i]:=random (200)+1;

write ('Введите число на промежутке [1; 200]>>> ');

readln (num);

if poisk (num)

then write ('Число ', num, ' есть в массиве.')

else write ('Числа ', num, ' нет в массиве.');

end.

Заголовок, переменные и операторный блок основной программы

Теперь рассмотрим, как же проверить, есть ли в массиве Элемент с указанным значением. Для этого будем проверять последовательно все элементы массива от первого к последнему, пока не найдём нужный или же пока они не закончатся. Такой поиск элемента в массиве называется линейным.

Напишем для нашей программы логическую функцию, определяющую, есть ли в массиве a заданное число. Как мы помним, она должна называться poisk. Эта функция должна иметь один аргумент целочисленного типа byte, назовём его t. Также функция должна возвращать значение логического типа boolean. Для работы функции нам потребуется дополнительная переменная, которая будет хранить номер текущего элемента массива. Назовём её i и укажем принадлежащей к целочисленному типу byte. В логических скобках опишем операторный блок функции. В его начале присвоим переменной i начальное значение – 0. Дальше напишем цикл с постусловием. Условием окончания работы цикла будет то, что i -тый Элемент массива a равен t или что достигнут конец массива и i равно 100. Тело цикла будет содержать единственный оператор, увеличивающий значение переменной i на 1. После завершения работы цикла нам будет достаточно проверить равен ли i -тый элемент массива a t и присвоить значение истинности этого высказывания переменной функции poisk. На этом описание функции закончено.

function poisk (t: byte): boolean;

Var

i: byte;

Begin

i:=0;

Repeat

i:=i+1;

until (a[i]=t) or (i = 100);

poisk:=a[i]=t;

end;

Функция poisk

Запустим программу на выполнение. Введём число 75. Программа вывела сообщение о том, что такое число есть в массиве. Просмотрев элементы массива, мы можем убедиться, что такое число действительно в нём есть.

Снова запустим программу и введём число 120. Программа вывела сообщение о том, что такого числа нет в массиве. Программа работает правильно. Задача решена.

Рассмотрим функцию poisk. Очевидно, что в лучшем случае при её выполнении будет выполнена 1 проверка, а в худшем – 100. Это не очень много, но предположим, что у нас есть программа, которая будет выполнять поиск тысячи или даже миллионы раз. Тогда для этого может потребоваться много времени, но поиск в массиве можно организовать проще, если элементы массива расположены в соответствии с некоторыми правилами, например, по возрастанию или по убыванию своих значений.

Мы можем изменить порядок следования элементов массива, отсортировав их. Сортировкой элементов массива называется изменение порядка их следования в соответствии с некоторыми правилами. По значениям элементы массива можно отсортировать разными способами. Рассмотрим наиболее распространённые. Если в массиве не может быть равных элементов, то его можно отсортировать по возрастанию или по убыванию. Если же в массиве могут быть равные элементы, то его можно отсортировать по неубыванию или по невозрастанию.

Варианты сортировки элементов массива

Как же можно отсортировать элементы массива, например, по возрастанию. Мы можем последовательно проверять все пары элементов массива, расположенных рядом, то есть первый и второй, второй и третий и так далее. Если в паре элементы расположены не по возрастанию, то их нужно менять местами. Таким образом, постепенно все элементы массива станут расположены по возрастанию. Такой способ сортировки называется методом пузырька. Он был назван так потому, что подобно пузырькам воздуха в стакане воды, элементы массива с наименьшими значениями перемещаются в начало массива.

Итак, что же нужно сделать чтобы отсортировать массив по возрастанию методом пузырька. Вначале предположим, что элементы массива уже расположены по возрастанию. Дальше будем последовательно проверять пары элементов массива. Если найдём пару, в которой элементы расположены не по возрастанию, то мы опровергнем начальное предположение о том, что элементы уже расположены по возрастанию. Мы поменяем местами элементы массива в паре, и продолжим проверять его дальше. После того, как мы проверили все пары элементов массива, мы должны проверить, осталось ли наше начальное предположение о том, что элементы массива расположены по возрастанию не опровергнутым. Если предположение было опровергнуто – мы начнём выполнять алгоритм сначала, в противном случае – алгоритм завершит свою работу. Когда после завершения работы алгоритма начальное положение останется не опровергнуто алгоритм завершит свою работу.

Для написанной нами программы для поиска элементов массива напишем процедуру сортировки элементов массива a но не убыванию. Назовём её sort. Для работы процедуры нам нужна переменная для хранения, номера текущего элемента массива – i и переменная для хранения одного из элементов массива, когда мы будем менять их местами – k, а также логическая переменная – p. Напишем программный блок процедуры. В нём будет цикл с постусловием, в качестве условия завершения работы которого будет значение логической переменной p. Тело цикла будет начинаться с того что мы предположим, что элементы массива уже расположены по возрастанию. Для этого переменной p мы присвоим значение true. Дальше будет следовать цикл с параметром i, изменяющимся от 1 до 99. Это будет цикл для проверки пар элементов массива. В нём будет условный оператор, который проверяет расположены ли элементы массива с индексами i и i + 1 не по неубыванию. То есть что a[i] > a[i + 1]. Если это условие выполняется, мы должны поменять эти два элемента массива местами. Для этого после слова then в логических скобках запишем четыре оператора присваивания: переменной p – значения false, так как мы опровергли начальное предположение, переменной k – значения a[i], a[i] – значение a[i + 1], a[i + 1] – значение переменной k. Таким образом, мы опровергли начальное предположение и поменяли местами элементы массива с индексами i и i + 1. На этом описание процедуры завершено.

procedure sort ();

Var

p: boolean;

i, k: byte;

Begin

Repeat

p:=true;

for i:=1 to 99 do

if a[i]>a[i+1]

Then begin

p:=false;

k:=a[i];

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

a[i+1]:=k;

end;

until p;

end;

Процедура сортировки элементов массива по неубыванию методом пузырька

В программном блоке основной программы перед запросом на ввод числа запишем вызов процедуры sort. Запустим программу на выполнение. Зададим число 28. Программа вывела сообщение о том, что это число есть в массиве. Просмотрев элементы массива, мы можем убедиться в том, что они действительно отсортированы по невозрастанию.

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

Теперь рассмотрим, как мы можем организовать поиск элемента с заданным значением в массиве, отсортированном по неубыванию. Очевидно, что элементы с наименьшим и наибольшим значениями располагаются по краям. Для поиска элемента с заданным значением можно использовать метод деления отрезка пополам (метод двоичной дихотомии). Если элементы массива расположены по возрастанию, то мы можем проверить его средний элемент. Так мы можем точно сказать где нужно искать элемент с искомым значением. Если средний элемент массива будет меньше искомого, то искомый элемент нужно искать после среднего, а в противном случае от первого до среднего. Таким образом мы сократим область поиска сразу в два раза. Точно также мы найдём средний элемент на новом промежутке поиска, сравним его с искомым и так далее. Так будет продолжаться до тех пор, пока начальный или конечный элемент промежутка поиска не будет равен искомому или пока промежуток поиска не станет равен одному элементу.

В написанной нами программе изменим функцию poisk. В ней нам понадобится дополнительные переменные для хранения номеров первого и последнего элемента массива на промежутке поиска, назовём их соответственно f и l, объявим их целочисленного типа byte. Запишем логические скобки. Операторный блок процедуры будет начинаться с того, что мы присвоим переменным f и l их начальные значения, то есть соответственно 1 и 100. Дальше мы запишем цикл с постусловием. Условием завершения его работы будет, то что один из элементов массива с индексами f и l равен искомому элементу t или что промежуток поиска сузился до одного элемента, то есть f = l. В теле цикла будет условный оператор, который будет проверять меньше ли средний элемент массива, с индексом равным (f + l) div 2, искомого t. Если это условие выполняется, то мы должны сократить промежуток поиска элемента. Поэтому после слова then присвоим переменной f значение (f + l) div 2 + 1. В противном случае – сократим промежуток поиска в другом направлении и присвоим переменной l значение (f + l) div 2. После завершения работы цикла проверим, равен ли один из элементов с индексами f и l искомому t. И присвоим значение истинности этого высказывания переменной функции – poisk.