Презентации по Математике

Алгоритмы линейного поиска. Тема 1
Алгоритмы линейного поиска. Тема 1
Линейный поиск Дано: массив А с n элементами. Выяснить: присутствует ли в массиве А значение х. Если да, то мы хотим знать индекс i, такой, что A[i] = х. Если нет – вывести соответствующее сообщение. При этом x может встретиться в массиве более одного раза. Алгоритм линейного поиска: мы начинаем с начала массива (первого его элемента), поочередно проверяя все его элементы (А[1] затем A[2], затем A[3] и так далее до А[n]) и записывая место, где мы находим x (если мы вообще находим его). Процедура линейного поиска Процедура Linear-Search(A,n,x) Вход: • A – массив; • n – количество элементов массива А, среди которых выполняется поиск; • x – искомое значение. Выход: значение переменной answer – либо индекс i, для которого A[i] = x, либо специальное значение not-found, которое может представлять собой любой некорректный индекс массива, например, произвольное отрицательное значение. Шаги процедуры: 1. Установить значение answer равным not-found. 2. Для каждого индекса i, пробегающего поочередно значения от 0 до n-1: А. Если A[i] = x, установить значение answer равным i. 3. В качестве выходного вернуть значение answer.
Продолжить чтение