Урок #9 «Алгоритмы поиска и сортировки»

Глава #1  «Рейтинг...»

*проще простого*

Сайтостроительство, своя страничка в Интернете, теперь это по силам и пятикласснику, одна проблема его содержание и назначение. Если ваш сайт направлен на большое количество пользователей, постоянно обновляется, зарегистрирован поисковиками, пора подумать о рейтинге своего детища и поставить на него счетчик посещаемости.

Давайте представим такую задачу, счетчик посещаемости сайта регистрировал пользователей вашего сайта в течении N дней, но не более 100 дней, какой день оказался «красным днем» вашего сайта, то есть гостей было больше всего.

Во входном файле INPUT.TXT в первой строке количество дней, во второй строке через пробел количество посещений по дням. Вывести в выходной файл OUTPUT.TXT через пробел «красный день» и количество посещений в этот день.

 Пример :

INPUT.TXT

7

11 12 5 б 50 7 9

OUTPUT.TXT

5 50

Алгоритм достаточно прост и выглядит так:

1.   записать данные в массив а:аггау[1..100] of integer;

2.   ввести переменную МАХ - для сравнения с каждым элементом массива и присвоить ей значение первого элемента массива mах:=а[1];

3.   ввести переменную R - контроль индекса элемента -максимального числа посещений

4.   в цикле организовать просмотр и сравнение каждого элемента массива с max и если элемент больше max переписать max и его индекс

5.   вывести индекс красного дня и его счетчик.

 Составим программу:

var

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

N,I,R:integer;

Max-integer;

 begin

assign(input,’input.txt');

assign(output,'output.txt');

reset(input);

rewrite(output);

readln(N);

            for I: = l to N do read(a[i]);

max:=a[l];

            for I: = 1 to N do IF a[i]>max THEN

Begin R:=I;

MAX:=a[i];

            End;

 Write(r,” “,max);

end.

Практическое задание:

l.Ha диске А создать файл MAX.PAS  и ввести программу

2.Во входной файл INPUT.TXT записать в первой строке «7» и во второй строке

через пробел  и 12 5 б 50 7 9, проверить работу программы

3.Протестировать программу на  2345167

Глава #2 «Сортировка методом «пузырька»»

*это 2x2*

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

INPUT.TXT

7

11 12 5 6 50 7 9

OUTPUT.TXT

5 6 7 9 11 12 50

Это классическая задача сортировки массива данных, а реализуем мы ее простейшей -сортировкой методом «пузырька» благо она легко запоминается и без блокнота. Нам достаточно вспомнить двойные циклы и  ОСВОИТЬ НА «ЛЕТУ» алгоритм обмена местами двух элементов массива с помощью вспомогательной переменной X.

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

var

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

N,I,j:integer;

X:integer;

Begin

assign(input/,input.txt');

assign(output/'output.txt');

reset(input);

rewrite(output);

readln(N); = 1 to N do read(a[i]); = 2 to N do = n downto i do

l]>a[j] then in

x:=a[j-l]; a[j-l]:=a[j];

a[j]:=x;

= 1 to n do write(a[i],' ');

Практическое задание:

l.Ha диске А создать файл SORTI.PAS  и ввести программу

2.Во входной файл INPUT.TXT записать в первой строке «7» и во второй строке

через пробел   и 12 5 б 50 7 9, проверить работу программы

3.Протестировать программу на  2345167

Глава #3 «Вопросы для повторения и ДЗ»

Вопросы для повторения:

1.    Как реализуется алгоритм поиска максимального элемента числового массива?

2.    В чем суть сортировки методом «пузырька»?

3.   Какое количество операций    затрачивает метод «пузырька» и является ли он эффективным?

Домашнее задание:

1.   Изменить программу MAX.PAS на MIN.PAS-определение минимального элемента числового массива.

2.   Изменить программу SORTI.PAS  на сортировку по убыванию то есть:

INPUT.TXT 7

11 12 5 6 50 7 9 OUTPUT.TXT 50 12 11 9 7 б 5