Lab4(поиск,бинарный поиск). Отчет по лабораторной работе 4 по дисциплине Информационные технологии

• Название: Отчет по лабораторной работе 4 по дисциплине Информационные технологии
• Анкор: Lab4(поиск,бинарный поиск).pdf
• Дата: 31.03.2021
• Размер: 0.61 Mb.
• Имя файла: Lab4(поиск,бинарный поиск).pdf
• Тип: Отчет; #190148

МИНОБРНАУКИ РОССИИ
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ
ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
«ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА)
Кафедра электронных приборов и устройств
ОТЧЕТ
по лабораторной работе №4
по дисциплине «Информационные технологии»
Тема: Алгоритмы и программы решения задач комбинаторики
Студент гр. 9205
Хамитов К.А.
Преподаватель
Староверов Н.Е.
Санкт-Петербург
2020

2
Цель работы.
Изучение и программирование алгоритма поиска.
Задачи.
1)Реализовать в Matlab алгоритм поиска элемента из вектора исходных данных
2)Получить в Excel тестовые результаты поиска
3)Провести сортировку вектора исходных данных (в необходимых случаях)
4)Сравнить полученные результаты с тестовыми
4.1. «Алгоритм простого поиска»
Основные теоретические положения.
На вход алгоритма подаётся последовательность чисел и искомый элемент. Входная последовательность на практике представляется в виде массива. На выходе алгоритм должен вернуть индекс необходимого элемента.
Далее приведена блок-схема данного алгоритма.

3

4
Код программы написанный в Matlab:
clc; clear all;
[r,t]=str2num(input('Введите размер массива:','s')); while t==false || r<=0
[r,t]=str2num(input('Вы ввели не верный размер массива, введите число большее нуля:','s')); end
%a=randi(r,1,r);
%a=randi([10 100],1,r);
%while length(a)

=length(unique(a))
%a=randi(r,1,r);
% a=randi([10 100],1,r);
%end for k=1:r a(k)=input('Вводите элементы:'); end disp('Исходный массив:');disp(a);
[key,g]=str2num(input('Введите необходимый элемент:','s')); while g==false
[key,g]=str2num(input('Вы ввели не верные данные, введите число:','s')); end bool=0; for i=1:r if a(i)==key bool=1; disp('Элемент найден(его индекс):');disp(i); end end if bool==0 disp('Нужный элемент не найден'); end
Экспериментальные результаты. Таблица 1.
Исходные элементы массива(входные данные)
Необходимый элемент
Возвращаемый индекс
21 61 52 11 40 61 2
24 82 38 58 25 world
Вы ввели не верные данные, введите число:
85 58 100 17 50 19 97 10 80 84 1
Нужный элемент не найден

5
Выводы.
Проведя анализ того по какому принципу построен алгоритм поиска элемента массива, мы построили соответствующую блок-схему, что позволило нам написать программу на языке Matlab, которая выполняет свою задачу в соответствии с теоретическими представлениями о том какой элемент должен выводиться в окно вывода. (Входные данные - абсолютно рандомные числа, от
10 до 100) Также была добавлена проверка на соответствие входных данных, т.е. чтобы были только числа.

6 4.2. «Алгоритм бинарного поиска»
Основные теоретические положения.
Бинарный поиск производится в упорядоченном не повторяющемся массиве.
При бинарном поиске искомый ключ сравнивается с ключом среднего элемента в массиве. Если они равны, то поиск успешен. В противном случае поиск осуществляется аналогично в левой или правой частях массива. Далее
приведена блок-схема данного алгоритма.

7
Код программы написанный в Matlab:
clc; clear all;
[r,t]=str2num(input('Введите размер массива:','s')); while t==false || r<=0
[r,t]=str2num(input('Вы ввели не верный размер массива, введите число большее нуля:','s')); end
%a=randi(r,1,r); a=randi([10 100],1,r); while length(a)=length(unique(a))
%a=randi(r,1,r); a=randi([10 100],1,r); end
%for k=1:r
% a(k)=input('Вводите элементы:');
%end disp('Исходный массив:');disp(a); gap=r/1.25; d=fix(gap); p=0; while d>=1 for i = 1:(r-d) if a(i)>a(i+d) p=a(i+d); a(i+d)=a(i); a(i)=p; end end d=fix(d/1.25); end disp("Отсортированный массив:");disp(a); key=input('Введите необходимый элемент:'); left=1;right=r;bool=0; while left<=right mid=fix((left+right)/2); if a(mid)==key bool=1; disp('Найден необходимый элемент(его индекс):');disp(mid); end if a(mid)>key right=mid-1; else

8 left=mid+1; end end if bool==0 disp('Необходимый элемент не найден'); end
Экспериментальные результаты.
Таблица 2.
Исходные элементы массива(входные данные) элементы отсортированного массива
Необходимы й элемент
Возвращаемы й индекс
96 13 49 44 79 82 27 54 50 68 13 27 44 49 50 54 68 79 82 96 44 3
50 79 55 97 83 50 55 79 83 97 world
Вы ввели не верные данные, введите число:
50 79 55 97 83 50 55 79 83 97 1
Необходимый элемент не найден
Выводы.
Проведя анализ того по какому принципу построен алгоритм бинарного поиска, мы построили соответствующую блок-схему, что позволило нам написать программу на языке Matlab, которая выполняет свою задачу в соответствии с теоретическими представлениями о том какой элемент программа должна вывести в окно вывода. Также были внесены предосторожности от неверного ввода массива (теперь, когда программа просит внести данные, она проверяет их на правильность, т.е. массив должен быть длиной (>0)). И для искомого элемента работает данная проверка. Стоит заметить, что данный алгоритм не будет работать в том случае если искомый элемент будет по обе части от центра массива, например: для отсортированного массива 1,2,3,5,5,5,6,7,8,9, программа выдаст только 5 и 6, что неверно в действительности, следовательно для таких целей необходимо модернизировать алгоритм.