ВУЗ:
Составители:
10
3.2. Поиск элемента в массиве
Поиск элемента в массиве предполагает, что необходимо найти первое
вхождение некоторого значения в массив.
Алгоритмы рассмотренных ниже трех задач имеют общую характер-
ную черту: в худшем случае требуется, чтобы циклический процесс выпол-
нялся n раз, то есть просматриваются все элементы массива. Такие алгорит-
мы называют линейными
.
Задача 1. Найти элемент
x в массиве a[1..n].
Постановка задачи.
Входные данные
: n − количество элементов массива,
n ∈ N (множеству натуральных чисел);
a[1], a[2], … , a[n] − элементы массива,
a[1..n] ∈ Z (множеству целых чисел);
x ∈ Z (значение, которое требуется найти в масси-
ве).
Выходные данные
: если x содержится в массиве: x = a[i], то i
его номер; если x отсутствует в массиве, то
i = n+1.
Метод решения.
Определим, что нужно найти, используя формальный язык:
(∃ i:1≤i≤n:a[i]= x) or (∀ i:1≤i≤n:a[i]≠ x)and (i=n+1)
Если первый дизъюнктивный член имеет значение true (в этом случае
i≤n и a[i]= x ), то значение x есть в массиве и его номер i.
Если второй дизъюнктивный член имеет значение
true (в этом случае
i>n и a[i]≠ x ), то значения x нет в массиве (i=n+1).
Страницы
- « первая
- ‹ предыдущая
- …
- 8
- 9
- 10
- 11
- 12
- …
- следующая ›
- последняя »
