Лабораторная работа

Тема: АЛГОРИТМЫ ПОИСКА (2 вариант)

ЦЕЛЬ: Учащиеся должны освоить алгоритмы поиска элемента с заданными свойствами в одномерном массиве.

ПО:TURBO PASCAL

ТЕОРИЯ:

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

Интал: Повторять Для i от 1 до n Если a[i]=R То k:=i Конец _Если Завершить

Pascal: for i:=1 to n do if a[i]=R then k:=i;

(примечание) (1) i-параметр цикла, R-разыскиваемый элемент, k-переменная, где находится порядковый номер разыскиваемого элемента в случае удачного поиска.

Алгоритм поиска объекта во множестве, состоящем из n объектов, последовательно перебирает объекты множества. Сложность худшего случая равна n (искомый объект может оказаться последним); средняя продолжительность поиска равна сумме всех номеров от 1 до n, деленной на n, что составляет (n+1)/2. В обоих случаях функция сложности имеет вид a*n+b, т.е. является линейной.

Недостатки:

• если значение R встречается несколько раз, то найдено будет последнее из них.

• в любом случае массив просматривается до конца.

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

Число сравнений при этом неизвестно, надо использовать цикл с предусловием (идею можно реализовать двумя вариантами):

а)k:=0; i:=1; while i<=n do begin

if a[i]=R then begin k:=i; i:=n end; (2а)

i:=i+1;

end;

б) i:=1; while (i<=n) and (a[i]<>R) do inc(i); - продолжаем поиск до конца массива или до обнаружения искомого элемента. В этой конструкции важен порядок вхождения простых условий в составное условие цикла.

ПОСЛЕДОВАТЕЛЬНОСТЬ ВЫПОЛНЕНИЯ ЗАДАНИЯ:

1. Отладить программу с помощью отладчика TP (клавиши <F7> или <F8> – программа выполняется по шагам при каждом нажатии этих клавиш).

2. Выполнить программу.

3. Выполнить остальные пункты задания.

4. Оформить отчет, защитить и сдать его преподавателю.

ЗАДАНИЯ I УРОВНЯ:

1. Реализовать идею (1) алгоритмом или программой. Можно проследить ее в режиме пошагового просмотра.

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

3. Реализовать идею (2б) алгоритмом или программой. Проверьте работу и этой программы при различных n, например. Какая из программ вас больше устроила? (Кстати, как еще можно реализовать данную идею?)

4. Измените программу (1 или 2), для поиска разыскиваемого элемента массива, равного R, с наибольшим номером.

5. Недостаток идеи (2б) - сложное условие в заголовке цикла, что замедляет поиск. Измените программу так, чтобы в заголовке цикла осталось лишь простое условие a[i]<>R. (Можно ввести барьер (дополнительный элемент) в массив a[n+1]=R).

6. Если элементов, равных R, в массиве несколько, вывести индексы каждого из них.

ЗАДАНИЯ II УРОВНЯ:

1. Известны средние температуры суток в городе N за месяц. В массиве данных найти номер дня, когда средняя температура первый раз стала отрицательной.

2. Известны средние температуры суток в городе N за месяц. В массиве данных найти номер дня, когда средняя температура первый раз стала положительной.

3. Известны сведения об осадках за сутки в городе N за месяц. В массиве данных найти номер дня, когда осадки превысили 10мм.

4. Известны сведения об осадках за сутки в городе N за месяц. В массиве данных найти номер дня, когда осадки не превысили 10мм.

5. Известны сведения о направлениях ветра за сутки в городе N за месяц (можно обозначить: север–1, юг–2, запад–3, восток–4, северо-восток–5, северо-запад –6, юго-запад –7, юго-восток –8). В массиве данных найти номер дня, когда первый раз задул ветер с севера.

6. Известны средние температуры суток в городе N за месяц. В массиве данных найти интервал температур за этот месяц.

7. Известны средние температуры суток в городе N за месяц. В массиве данных найти интервал отрицательных температур за этот месяц.

8. Известны наименьшие температуры в городе N за 100 лет. Можно ли завозить в этот город ртутные термометры (ртуть замерзает при температуре -39 C).

9. Известны средние температуры суток в городе N за осенние месяцы. В массиве данных найти день месяца, когда отметка температуры опустилась первый раз за 0С. В какой месяц это произошло?

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

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

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

САМОСТОЯТЕЛЬНАЯ РАБОТА

1. Для конкурса красоты надо отобрать кандидаток: возраст от 17 до 24 лет, рост от 175 см. Распечатайте список возможных участниц конкурса.

2. Сказочному принцу необходимо отыскать Золушку. В комиссии участвуют солдаты, поэтому они хотят создать точный список. Критерии отбора: возраст от 17 до 24 лет, рост до 170 см, волосы белокурые, размер ножки до 34. Распечатайте список возможных претенденток.

КОНТРОЛЬНЫЕ ВОПРОСЫ:

1. Какие способы поиска элемента в массиве по какому-либо критерию Вы знаете?

2. Как найти минимальный элемент в массиве? Максимальный?

3. Как организовать вывод нескольких элементов, отвечающих критерию поиска в массиве данных?

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

Задания 1 уровня выполняются все, задания II уровня – каждому учащемуся дается своя задача.

ЛАБОРАТОРНАЯ РАБОТА

ТЕМА: СОРТИРОВКА ЭЛЕМЕНТОВ ЛИНЕЙНОЙ ТАБЛИЦЫ

ЦЕЛЬ: практическое освоение методов сортировки.

ПО: Turbo Pascal-7.0

ТЕОРИЯ: Имеется массив целых либо действительных чисел а1, ... ,аn. Требуется переставить элементы этого массива так, чтобы после перестановки они были упорядочены по неубыванию:

a1<=a2<= ... <=an.

Эта задача называется задачей сортировки или упорядочения массива (эту же задачу можно рассматривать как упорядочение по невозрастанию: a₁>=a₂>=...>=a_n); если же числа попарно различны, то можно говорить об убывании и возрастании). Предполагаем при этом, что перестановки, приводящие массив в порядок, должны выполняться на том же месте, не используя дополнительную память. Известно много разных алгоритмов сортировки. Для решения этой задачи можно воспользоваться следующими алгоритмами.

1. СОРТИРОВКА ВЫБОРОМ. Найти наименьший элемент массива, поменять его местами с первым элементом, затем проделать то же самое, начав со второго элемента и т.д., пока массив не сократится до одного элемента. Например:

4 5 1 2 3

1 5 4 2 3

1 2 4 5 3

1 2 3 5 4

1 2 3 4 5 –результат

2. СОРТИРОВКА ОБМЕНАМИ. Сравниваем последовательно по 2 соседних элемента таблицы a. Если обнаружим такие пары а[i] и а[i+1], что а[i]>a[i+1], то поменяем их местами и продолжаем сравнение. В результате первого прохода по таблице наибольший элемент передвинется на последнее место. Следующие проходы начинать с первого элемента, уменьшая на единицу количество рассматриваемых элементов. Шаги повторяют до тех пор, пока очередной проход не вызовет ни одного обмена. Например:

4 5 2 1 3

4 2 1 3 5

2 1 3 4 5

2 1 3 4 5

1 2 3 4 5 – результат

3. СОРТИРОВКИ С ПОМОЩЬЮ ВКЛЮЧЕНИЯ. Просматриваем последовательно элементы массива, начиная со второго, и каждый новый элемент a_i вставляем на подходящее место в уже упорядоченную совокупность a_1, ... , a_{i -1}. Это место определяется последовательным сравнением a_i с упорядоченными элементами a_1, ... , a_{i -1.} Пример:

4 5 1 3 2

4 5 1 3 2

1 4 5 3 2

1 3 4 5 2

1 2 3 4 5

Рассмотрим один из вариантов сортировки (на языке Интал и на Паскале):

Пограмма Упорядочение Описание Массив А[10] Целый мах, k, p, i, n, r: Целый Конец _Описания n:=10 Повторять Для i от 1 до n Ввод(A[i,j],'элемент=') Завершить Повторять Для k от 1 до n-1 мах:=a[k]; p:=k Повторять Для i от k+1 до n Если A[i]> мах То мах:= А[i] p:=i Конец_Если Завершить A[p]:=A[k] A[k]:= мах Завершить Повторять Для k от 1 до n Вывод(A[i]),’ ‘) Завершить Конец_Программы

Const n=10; var a:array[1..n] of integer; max ,k,i,p:integer; begin for i:=1 to n do read(a[i]); for k:=1 to n-1 do begin max:=a[k];p:=k; for i:=k+1 to n do if a[i]>max then begin max:=a[i]; p:=i ; end; a[p]:=a[k]; a[k] :=max end; for i:=1 to n do write(a[i],' '); end.

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ:

1. Изучить предложенные методы сортировки и данную программу.

1. Ввести текст программы в память ЭВМ и выполнить программу.

1. Предъявить преподавателю результаты работы программы.

1. Выполнить остальные пункты задания.

1. Оформить отчет по выполненной лабораторной работе, защитить и сдать его преподавателю.

ЗАДАНИЯ I УРОВНЯ:

1. Ввести программу в память ЭВМ, отладить ее проверить на значениях, указанных в тексте программы. Какой метод упорядочения применен?

2. Изменить программу так, чтобы она сортировала данные в порядке возрастания (надо изменить знак ... на ...)

3. Дано множество чисел массива а: [5,-3, 4,-11,6,-25, -1361, 8,-9, 100]. Расположите его элементы в порядке возрастания их абсолютной величины.

4. Дано множество букв латинского алфавита. Упорядочьте его элементы в лексикографическом порядке. Исходное множество: [H, C, A, F, D, E, R, S, V, W, B, Z]. Этот же массив преобразовать в обратном порядке: первым элементом должна стать буква Z (A[1]=Z), а последним –буква А (A[12]=A).

5. Составьте программы сортировки массива другими методами.

ЗАДАНИЯ II УРОВНЯ:

Дана действительная матрица размера m*n. Упорядочить (переставить) строки матрицы:

1. по неубыванию первых элементов строк;

2. по невозрастанию сумм элементов строк;

3. по неубыванию значений наименьших элементов строк;

4. по невозрастанию значений наибольших элементов строк

5. по убыванию первых элементов строк;

6. по возрастанию сумм элементов строк;

7. по убыванию значений наименьших элементов строк;

8. по возрастанию значений наибольших элементов строк;

9. по убыванию последних элементов строк;

10. по возрастанию последних элементов строк;

Задан текст. Слова в тексте разделены пробелами. Отсортировать слова текста по следующим признакам:

1. В порядке, обратном алфавиту;

2. По количеству букв в словах в порядке возрастания;

3. По количеству букв а в словах в порядке убывания;

4. По первым двум буквам в словах в порядке возрастания;

5. По количеству гласных букв в словах в порядке возрастания;

6. По количеству согласных букв в словах в порядке убывания;

7. По количеству различных букв в словах в порядке возрастания;

8. В алфавитном порядке отсортировать только различные слова текста

САМОСТОЯТЕЛЬНАЯ РАБОТА:

• Даны пять различных целых чисел а, b, c, d, e. Отсортируйте их по возрастанию, используя не более семи сравнений.

• Определите, является ли данный массив упорядоченным.

• Задан упорядоченный массив из целых чисел. При помощи генератора псевдослучайных чисел сделайте его неупорядоченным.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Приведите примеры реальных задач, при использовании которых применяется сортировка.

2. Какие принципы (основы) сортировки чисел вам известны? Придумайте свой способ сортировки элементов.

3. Можно ли сортировать нечисловые элементы множеств?

4. Можно ли сортировать геометрические объекты? Какую основу для сортировки в этом случае можно избрать?

5. Опишите процесс упорядочения фамилий в алфавитном порядке.

6. Cоставьте программу упорядочения N фамилий, написанных латинскими буквами, по алфавиту.

ЛАБОРАТОРНАЯ РАБОТА

ТЕМА: ИСПОЛЬЗОВАНИЕ ФУНКЦИЙ ПОЛЬЗОВАТЕЛЯ.

ЦЕЛЬ: Изучить правила объявления и использования функций на языке программирования Паскаль. Получить практические навыки работы с функциями.

ПО: Turbo Pascal-7.0.

КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

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

Для описания функций предусматривается специальный раздел программы (раздел описания процедур и функций).

Описание таких функций начинается со строки – заголовка

FUNCTION < имя> (список формальных параметров): <тип>;

где <имя> – имя функции, <тип> – тип значения, вычисляемого функцией, список параметров – перечень переменных, от которых зависит значение функции с указанием их типов. Так как типы в заголовке обозначаются только именами, использование массивов возможно только после предварительного описания их типа в строке TYPE. В следующих после FUNCTION строках с помощью операторов, расположенных между словами BEGIN – END; описывается процесс вычисления функции. Среди операторов подпрограммы обязательно должен быть оператор, присваивающий функции какое-либо значение:

<имя> := <выражение>

Пример:

Function b(x, y: integer): integer; (*)

begin

if x > 0 then b:= y

else b:= y*y;

end;

Обращение к функции осуществляется следующим образом:

<имя функции>(<список фактических параметров>). В списке фактических параметров порядок следования и типы переменных должны соответствовать порядку следования и типам формальных переменных.

В нашем случае вызов будет следующим, например: f:=b(a,b);.

Структура функции полностью аналогична структуре основной программы, за исключением того, что она начинается со слова FUNCION (а не PROGRAM), и после «END» в конце функции ставится не точка, а знак «;». Метки, константы и переменные, описанные в разделе объявлений и соглашений функции, действуют только в рамках данной функции.

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

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ:

1. Войти в режим редактирования и набрать текст программы (см. ниже)

2. Выполнить программу (если программу выполнять по шагам, то нужно нажимать клавишу <F7>, чтобы попасть внутрь подпрограммы и проследить по шагам за ее выполнением. Добавлять переменные в окно Watch можно нажав <Ctrl+F7> и далее указав нужные переменные. Окна переключать можно с помощью клавиши <F6>.)

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

4. Составить программы для других пунктов задания.

5. Оформить отчет по лабораторной работе, защитить и сдать его преподавателю. Отчет по лабораторной работе должен содержать постановку задачи, краткое описание идеи либо алгоритма, а также программу.