Контрольная работа структуры и алгоритмы обработки данных. Контрольная работа. Контрольная работа по предмету Структуры и алгоритмы обработки данных

• Название: Контрольная работа по предмету Структуры и алгоритмы обработки данных
• Анкор: Контрольная работа структуры и алгоритмы обработки данных
• Дата: 01.04.2022
• Размер: 100.46 Kb.
• Имя файла: Контрольная работа.docx
• Тип: Контрольная работа; #434169
• страница: 8 из 8

Ответ: АААВЕЛНННОПХ

Задание 8. Для набора всех символов ФИО студента выполнить вручную быстрый поиск (две версии) первой буквы имени и буквы «Я». Подсчитать количество необходимых для поиска операций сравнения для каждой версии.

Решение:

Возьмём полный набор символов ФИО студента:

ПЛЕХАНОВААННАИГОРЕВНА

Отсортируем по порядку:

АААААВВГЕЕИЛННННООПРХ

1 версия: поиск по первой букве имени.

Буква А является первой буквой в имени студента.

Алгоритм быстрого поиска в массиве сравнивает искомый элемент со средним. Средний элемент вычисляется по формуле: (первый элемент + последний элемент)/2.

Алгоритм проводит поиск по такому принципу:

1. 
   Если искомый элемент совпадает со средним значением массива, то поиск закончен.
   
2. 
   Если искомый элемент оказался меньше среднего значения массива, то из массива убирается вся правая часть, включая средний элемент.
   
3. 
   Если искомый элемент оказался больше среднего значения массива, то из массива убирается вся левая часть, включая средний элемент.
   

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

Проведём поиск:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
А	А	А	А	А	В	В	Г	Е	Е	И	Л	Н	Н	Н	Н	О	О	П	Р	Х
А	А	А	А	А	В	В	Г	Е	Е

• 
  Искомое значение массива находится под номером 5. Для завершения поиска понадобилось совершить две операции сравнения.
  

Ответ: 2 операции сравнения.

2 версия: поиск по букве Я

Как и в первой версии быстрого поиска сравниваются искомый элемент со средним. Но так как сравнение происходит по самому большому элементу массива (мы берём массив, состоящий из букв русского алфавита с максимальным символом: Я), то алгоритм проводит поиск по иному принципу:

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

Проведём поиск:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

А

А

А

А

А

В

В

Г

Е

Е

И

Л

Н

Н

Н

Н

О

О

П

Р

Х

Л

Н

Н

Н

Н

О

О

П

Р

Х

О

О

П

Р

Х

Р

Х

Х

• 
  Искомое значение не было найдено. Для завершения поиска понадобилось 4 операции плюс 1 операция для сравнения последнего символа массива. Итого 5.
  

Ответ: 5 операций сравнения.