Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Поиск номера элемента последовательности с заданным значением





Рассмотрим задачу D. Пусть задана последовательность {Xi} = Х1, Х2,..., XN, где i изменяется от 1 до N. По условию в последовательности {Xi} все элементы имеют разные значения. Необходимо определить номер элемента, значение которого равно значению некоторой заданной переменной Р. Причем в заданной последовательности может не оказаться элемента со значением Р. Первая ситуация - упорядоченная последовательность.

Основной алгоритм поиска имеет следующий вид:

a. Сравнить очередной элемент с переменной Р.

b. Перейти к следующему элементу.

c. Если не все элементы просмотрены, то повторить с п. а.

Алгоритм должен однозначно реагировать на ситуацию, если искомого значения в последовательности нет. Введем переменную k с начальным значением, равным 0. Результат k - номер найденного элемента.
Если элемент со значением Р не найден, то результат k остается нулевым (рис. 1.13). Если последовательность упорядочена, т. е. значения элементов последовательности возрастают или убывают с увеличением порядковых номеров (индексов) элементов, то к ней можно применить другой алгоритм поиска. В процессе поиска можно сдвинуть друг к другу границы промежутка, в котором после каждого сравнения сдвигается либо верхняя, либо нижняя граница. Алгоритм, в котором последовательно уменьшается промежуток исследуемых данных в два раза, называется алгоритмом дихотомии - деление отрезка пополам.
Пусть значение наименьшего элемента исходной последовательности равно А, а значение наибольшего элемента - В. Если разделить рассматриваемый интервал [А, В] пополам, то получится некоторое значение С. Сравнить С с заданным значением Р. Повторять эти действия до тех пор, пока А и В не совпадут. Проверить условие Х[А] = Р. По результатам проверки должен быть сформирован результат.

Рис. 1.13. Схема алгоритма поиска заданного элемента

Словесный алгоритм поиска имеет следующий вид:

a. Вычислить С.

b. Сравнить Х[С] с переменной Р.

c. Определить А и В.

d. Если А и В не совпадают, то повторить с п. а.

e. Проверить совпадение выделенного значения с поисковой Р.

Рис. 1.14. Схема алгоритма дихотомического поиска

Необходимо задать начальные значения А и В. Схема алгоритма дихотомического поиска в упорядоченном массиве представлена на рис. 1.14.

Сортировка
Сортировка стала важной частью вычислительной математики, так как она отнимает значительную часть времени работы компьютера (25%). Сортировка относится к алгоритмам обработки таблиц (массивов) любого типа.
Смысл любой сортировки заключается в перестановке элементов таблицы в определенном заданном порядке. Отсортировать числовую таблицу - это значит переставить элементы в ней так, чтобы они расположились в порядке убывания (возрастания) значений с возрастанием нового номера элемента:

Номер элемента          
Исходный числовой массив          
Упорядочение по возрастанию          
Упорядочение по убыванию          

 

Сортировка символьной (или текстовой) информации заключается в упорядочении значений (текстовых строк) по алфавиту:

Номер элемента          
Исходный символьный массив мул кот як лев вол
Упорядочение по алфавиту вол кот лев мул як

 

Метод сортировки является устойчивым, если относительный порядок элементов с равными значениями не меняется после упорядочения. Сортировку можно рассматривать и как самостоятельную задачу (например, для получения упорядоченного по алфавиту списка сотрудников какого-либо учреждения), и как вспомогательную - для облегчения последующего поиска элементов в упорядоченной таблице. Анализ известных алгоритмов сортировки очень полезен, так как в них используется практически все универсальные приемы конструирования алгоритмов. В пособии представлены алгоритмы упорядочения последовательности A1,A,..., AN, по возрастанию. Переход к упорядочению по убыванию аналогичен.

Date: 2015-07-01; view: 643; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.007 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию