10.2. Алгоритмы поиска Будем рассматривать на примере поиска в массиве. 10.2.1. Линейный поиск Линейный, последовательный поиск — нахождения заданного элемента в некотором массиве. Поиск значения осуществляется простым сравнением очередного значения и искомого, если значения совпадают, то поиск считается завершённым. Если у массива длина = N, найти решение можно за N шагов. Сложность алгоритма - O (n). В связи с малой эффективностью линейный поиск используют только если N не большое.
Алгоритм: 1. Определяем начало интервала поиска и выбираем элемент для поиска. 2. Сравниваем образец с выбранным элементом. Если элемент совпадает с образцом, то определяем его индекс и переходим к шагу 4. 3. Если элемент не совпадает с образцом, то выбираем следующий, если он есть и переходим к шагу 2. 4. Если индекс определен, то элемент найден, иначе - искомого элемента в массиве нет. int i=0; int x; // образец int n; // размерность массива int a[100]; while (i<n)&&(a[i]!=x)) i=i+1; if (i==n) printf("no"); else printf("%d ",i);
Можно упростить логическое выражение, которое состоит из двух членов. Уберем условие (i<n), но при этом необходимо гарантировать, что совпадение произойдет всегда. Для этого достаточно в конец массива поместить дополнительный элемент со значением x. Такой вспомога-тельный элемент называется “барьером”. Теперь массив будет описан так: int a[101]; a[n]=x; while (a[i]!=x) i=i+1;
int LineSearch (int *a, int n, int x) { for (int i=0;i<n; i++) if (a[i]==x) return i; return -1; //элемент не найден } 10.2.2. Бинарный поиск Или метод дихотомии или метод половинного деления. Как обычно, за скорость взимается плата: массив должен быть упорядочен. Сам по себе этап предварительного упорядочения, или сортировки, обходится недешево, во всяком случае - дороже однократного линейного поиска. Алгоритм: 1. Определяем середину интервала поиска. 2. Сравниваем образец с элементом, расположенным посередине. Если образец оказался больше, то областью дальнейшего поиска становится правая половина; в противном случае - левая половина интервала, но в любом случае индексный интервал уменьшается вдвое. (Если осуществить еще одну проверку, то можно установить и совпадение, после чего дальнейшие шаги не обязательны.) 3. Если остался интервал единичной длины, то переходим к заключительному шагу 4, в противном случае - к шагу 1. 4. Либо единственный элемент интервала совпадает с образцом, либо - искомого элемента в массиве нет.
int BinarySearch(int a[], int n, int x) { int i, j, middle; i=0; j=n-1; while (i<=j) { middle=(i+j)/2; if (x==a[middle]) return middle; else if (x>a[middle]) i=middle+1; else j=middle-1; } return -1; } Оценим алгоритм бинарного поиска в массиве. Первая итерация цикла имеет дело со всем массивом. Каждая последующая итерация делит пополам размер подмассива. Так, размерами массива для алгоритма являются n n/21 n/22 n/23 n/24... n/2m В конце концов будет такое целое m, что n/2m<2 или n<2m+1
Так как m - это первое целое, для которого n/2m<2, то должно быть верно n/2m-1>=2 или 2m<=n Из этого следует, что 2m<=n<2m+1 Возьмем логарифм каждой части неравенства и получим m<=log2n=x<m+1 Значение m - это наибольшее целое, которое <=х. Итак, O(log2n). Упр. Читать “Оценка программ”.
10.3. Преобразования массивов Переворачивание элементов массива void Revers(int *a, int n) // Переворачивание элементов массива {int k; for (int i=0;i<n/2;i++) { k=a[i]; a[i]=a[n-i-1]; a[n-i-1]=k; } }
void ReversP(int *a, int n) { int k; for (int i=0;i<n/2;i++) { k=*(a+i); *(a+i)=*(a+n-i-1); *(a+n-i-1)=k; } }
void ReversL(int *a, int n) { for (int i=0;i<n/2;i++) { *(a+i)^=*(a+n-i-1); *(a+n-i-1)^=*(a+i); *(a+i)^=*(a+n-i-1); } }
Расширение и сжатие массивов При обработке массивов можно вставлять и удалять элементы
void MoveRight(int * a, int *n, int num) { //сдвигает все элементы на // одну позицию вправо до номера num for (int i=*n; i>=(num+1); i--) a[i]=a[i-1]; (*n)++; //увелич реальный размер массива //не путать с *n++!!!!! }
void MoveLeft(int *a, int *n, int num) {//сдвигает все элементы на // одну позицию влево c номера num
for (int i=num; i<*n-1; i++) a[i]=a[i+1]; *n=*n-1; } Дублирование четных в массиве void InsertCh(int *a, int *n) {int i=0; while (i<*n) { if (a[i]%2==0) { MoveRight(a, n, i+1);
//Сдвигаем и добавляем элемент a[i+1]=a[i]; i++; } i++; } }
Удаление чисел равных item в массиве void DeleteCh(int *a, int *n,int item) { int i=0; while (i<*n) { if (a[i]==item) MoveLeft(a, n, i); //Сдвигаем и удаляем элемент else i++; } }
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав!Последнее добавление