close

Вход

Забыли?

вход по аккаунту

?

lab2inf

код для вставкиСкачать
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
"Ижевский государственный технический университет им. М. Т. Калашникова" Факультет "Информатика и вычислительная техника"
Кафедра АСОИУ
ОТЧЕТ
по Лабораторной работе №2
по дисциплине "Информатика"
на тему "Метод бинарного поиска"
Выполнил
студент гр. Б01-782-1 Чулкин А.Д.
Проверил
Старший преподаватель кафедры АСОИУ Соловьева А.Н.
Ижевск 2013
1 Задание
Массив длины 15 заполнен строками, упорядоченными по алфавиту без повторов: список зарегистрированных посетителей сайта, поступивших абитуриентов, названий книг и т.п. (можно загружать в массив готовый список из отдельного текстового файла, например sorted_list.txt)
Во втором текстовом файле (test.txt) содержится перемешанный набор строк с повторениями, в том числе все строки, записанные в массив, а также новые строки.
Считывая по одной строке из файла test.txt, нужно выполнить поиск каждой строки в массиве, по результатам которого вывести на экран номер ее позиции в массиве и количество ее сравнений с содержимым ячеек массива, произведенных в ходе поиска.
Реализовать два метода поиска строк в массиве: поиск перебором, бинарный поиск. Пользователь должен иметь возможность выбора метода.
В выводе построить график зависимости количества сравнений строки с содержимым ячеек массива от номера ее позиции в массиве для каждого метода. Подсчитать и привести в выводе среднее число сравнений по всем строкам для каждого метода.
2 Задание
На рисунке 2.1 показана блок-схема программы. да нет
нет нет
Рисунок 2.1
На рисунках 2.2 и 2.3 показаны блок-схемы бинарного поиска и поиска перебором.
нет
да нет
Нет Да Рисунок 2.2
Нет
Да Нет
Рисунок 2.3
3 Задание
Исходный текст программы:
program Inf_Lab2;
const
n = 15;
o = 0;
type
TMyArray = array [1..n] of string;
procedure Perebor(s: string; a: TMyArray);
var
i: integer;
k: integer;
begin
i := 1;
k := 1;
while(i<= n) and (a[i] <> s) do
begin
i := i + 1;
k := k + 1;
end;
if(i> n) then
writeln('Stroka ', s, ' ne naidena. Kol-vosravneniy ', k - 1)
else
writeln('Stroka ', s, ' naidena v pozicii ', i, '. Kol-vosravneniy ', k);
end;
procedure Perebor_bin(s: string; a: TMyArray);
var
k,last,first,middle: integer;
u:real;
begin
last:= n;
first:= 1;
middle:=(last+first) div 2;
k:=1;
while(a[middle]<>s) and (first<>middle) and (last<>middle) do begin
k:=k+1;
if a[middle]<s then begin first:=middle;
u:=(last+first)/2;
middle:=round(u+0.2);
end
else begin
last:=middle;
middle:=(last+first) div 2;
end;
end;
if a[middle] = s then
writeln('Stroka ', s, ' naidena v pozicii ', middle, '. Kol-vosravneniy ', k)
else
writeln('Stroka ', s, ' ne naidena ', ' Kol-vosravneniy ', k);
end;
var
sf, f: TextFile;
arr: TMyArray;
st: string;
tip : string;
i: integer;
begin
for i := 1 to n do
arr[i] := '';
Assign(sf, 'sorted_list.txt');
Reset(sf);
i := 1;
while not Eof(sf) and (i<= n) do
begin
Readln(sf, arr[i]);
i := i + 1;
end;
Close(sf);
writeln('Выберете способ поиска:1-перебором, 2-бинарным');
read(tip);
if tip = 1 then
begin
Assign(f, 'test.txt');
Reset(f);
while not Eof(f) do
begin
readln(f, st);
Perebor(st, arr);
end;
Close(f);
end
else begin
Assign(f, 'test.txt');
Reset(f);
while not Eof(f) do
begin
readln(f, st);
Perebor_bin(st, arr);
end;
Close(f);
end;
end.
4 Задание
4.1 Содержание файла sorted_list.txt
Антон
Андрей
Борис
Виктория
Ваня
Гриша
Григорий
Женя
Зоя
Ксюша
Кристина
Леонид
Маша
Паша
Яна
4.2 Содержаниефайлаtest.txt
Яна
Леонид
Гриша
Григорий
Андрей
Даня
Евгений
Алекскей
Антон
Маша
Паша
Борис
Женя
Зоя
Кристина
Виктория
Ваня
Ксюша
4.3 Результат работы программы (перебор)
Stroka Яна naidena v pozicii 15. Kol-vo sravneniy 15
Stroka Леонид naidena v pozicii 12. Kol-vo sravneniy 12
Stroka Гриша naidena v pozicii 6. Kol-vo sravneniy 6
Stroka Григорий naidena v pozicii 7. Kol-vo sravneniy 7
Stroka Андрей naidena v pozicii 2. Kol-vo sravneniy 2
Stroka Даня ne naidena. Kol-vo sravneniy 15
Stroka Евгений ne naidena. Kol-vo sravneniy 15
Stroka Алексей ne naidena. Kol-vo sravneniy 15
Stroka Антон naidena v pozicii 1. Kol-vo sravneniy 1
Stroka Маша naidena v pozicii 13. Kol-vo sravneniy 13
Stroka Паша naidena v pozicii 14. Kol-vo sravneniy 14
Stroka Борис naidena v pozicii 3. Kol-vo sravneniy 3
Stroka Женя naidena v pozicii 8. Kol-vo sravneniy 8
Stroka Зоя naidena v pozicii 9. Kol-vo sravneniy 9
Stroka Кристина naidena v pozicii 11. Kol-vo sravneniy 11
Stroka Виктория naidena v pozicii 4. Kol-vo sravneniy 4
Stroka Ваня naidena v pozicii 5. Kol-vo sravneniy 5
Stroka Ксюша naidena v pozicii 10. Kol-vo sravneniy 10
Stroka ne naidena. Kol-vo sravneniy 15
4.4 Результат работы программы (бинарный поиск)
Stroka Яна naidena v pozicii 15. Kol-vo sravneniy 4
Stroka Леонид naidena v pozicii 12. Kol-vo sravneniy 2
Stroka Гриша naidena v pozicii 6. Kol-vo sravneniy 3
Stroka Григорий naidena v pozicii 7. Kol-vo sravneniy 4
Stroka Андрей naidena v pozicii 2. Kol-vo sravneniy 3
Stroka Даня ne naidena Kol-vo sravneniy 5
Stroka Евгений ne naidena Kol-vo sravneniy 5
Stroka Алексей ne naidena Kol-vo sravneniy 4
Stroka Антон naidena v pozicii 1. Kol-vo sravneniy 4
Stroka Маша naidena v pozicii 13. Kol-vo sravneniy 4
Stroka Паша naidena v pozicii 14. Kol-vo sravneniy 3
Stroka Борис naidena v pozicii 3. Kol-vo sravneniy 4
Stroka Женя naidena v pozicii 8. Kol-vo sravneniy 1
Stroka Зоя naidena v pozicii 9. Kol-vo sravneniy 4
Stroka Кристина naidena v pozicii 11. Kol-vo sravneniy 4
Stroka Виктория naidena v pozicii 4. Kol-vo sravneniy 2
Stroka Ваня naidena v pozicii 5. Kol-vo sravneniy 4
Stroka Ксюша naidena v pozicii 10. Kol-vo sravneniy 3
Stroka ne naidena Kol-vo sravneniy 4
5 Задание
В таблице 5.1 построен график зависимости количества сравнений строки с содержимым ячеек массива от номера ее позиции в массиве.
Среднее количество сравнений.
1)Поиск перебором. Среднее количество сравнений : (1+2+3+4+5+6+7+8+9+10+11+12+13+14+15)/15=8
2)Бинарный поиск. Среднее количество сравнений: (4+3+4+2+4+3+4+1+4+3+4+2+4+3+4)/15=3,2(6)
Таким образом мы видим, что среднее количество сравнений для бинарного поиска меньше более чем в 2 раза. Следовательно бинарный поиск осуществляется быстрее. 
Документ
Категория
Рефераты
Просмотров
51
Размер файла
145 Кб
Теги
lab2inf
1/--страниц
Пожаловаться на содержимое документа