Программирование на языке СИ

РЕКЛАМА	2.3.1. Последовательный поиск
<!--webbot BOT="HTMLMarkup" endspan --> <a href="http://10e2.linkexchange.ru/users/042940/goto.map?bn=1" target="_top"><img src="http://10e2.linkexchange.ru/cgi-bin/rle.cgi?42940-bn=1?Rnd_Num" alt="RLE Banner Network" border="0" height="100" width="100"></a> <!--webbot bot="HTMLMarkup" StartSpan --> TBN.ru	Задача поиска. Пусть заданы линейные списки: список элементов В=<К1,К2,К3,...,Кn> и список ключей V= (в простейшем случае это целые числа). Требуется для каждого значения Vi из V найти множество всех совпадающих с ним элементов из В. Чаще всего встречается ситуация когда V содержит один элемент, а в В имеется не более одного такого элемента. Эффективность некоторого алгоритма поиска А оценивается максимальным Max{А} и средним Avg{А} количествами сравнений, необходимых для нахождения элемента V в В. Если Pi - относительная частота использования элемента Кi в В, а Si - количество сравнений, необходимое для его поиска, то n Max{А} = max{ Si, i=1,n } ; Avg{А} = Pi Si . i=1 Последовательный поиск предусматривает последовательный просмотр всех элементов списка В в порядке их расположения, пока не найдется элемент равный V. Если достоверно неизвестно, что такой элемент имеется в списке, то необходимо следить за тем, чтобы поиск не вышел за пределы списка, что достигается использованием стоппера. Очевидно, что Max последовательного поиска равен N. Если частота использования каждого элемента списка одинакова, т.е. P=1/N, то Avg последовательного поиска равно N/2. При различной частоте использования элементов Avg можно улучшить, если поместить часто встречаемые элементы в начало списка. Пусть во входном потоке задано 100 целых чисел К1,К2,... К100 и ключ V. Составим программу для последовательного хранения элементов Кi и поиска среди них элемента, равного V, причем такого элемента может и не быть в списке. Без использования стоппера программа может быть реализована следующим образом: /* последовательный поиск без стоппера / #include main() { int k[100],v,i; for (i=0;i<100;i++) scanf("%d",&k[i]); scanf("%d",&v); i="0;" while(k[i]!="v" && i<100) i++; if (k[i]="=v)" printf("%d %d",v,i); else printf("%d не найден",v); } С использованием стоппера программу можно записать в виде: / последовательный поиск со стоппером / #include main() { int k[101],v,i; for (i=0;i<100;i++) scanf("%d",&k[i]); / ввод данных / scanf("%d",&v); k[100]="v;" / стоппер / i="0;" while(k[i]!="v)" i++; if (i<100) printf ("%d %d",v,i); else printf ("%d не найден",v); } 2.3.2. Бинарный поиск Для упорядоченных линейных списков существуют более эффективные алгоритмы поиска, хотя и для таких списков применим последовательный поиск. Бинарный поиск состоит в том, что ключ V сравнивается со средним элементом списка. Если эти значения окажутся равными, то искомый элемент найден, в противном случае поиск продолжается в одной из половин списка. Нахождение элемента бинарным поиском осуществляется очень быстро. Max бинарного поиска равен log2(N), и при одинаковой частоте использования каждого элемента Avg бинарного поиска равен log2(N). Недостаток бинарного поиска заключается в необходимости последовательного хранения списка, что усложняет операции добавления и исключения элементов . Пусть, например, во входном потоке задано 101 число, К1,К2,...,К100, V - элементы списка и ключ. Известно, что список упорядочен по возрастанию, и элемент V в списке имеется. Составим программу для ввода данных и осуществления бинарного поиска ключа V в списке К1,К2,...,К100. / Бинарный поиск / #include main() { int k[100],v,i,j,m; for (i=0;i<100;i++) scanf("%d",&k[i]); scanf("%d",&v); i="0;" j="100;" m="50;" while (k[m]!="v)" { if (k[m] < v) i+="m;" else j="m-i;" m="(i+j)/2;" } printf("%d %d",v,m); } 2.3.3. М-блочный поиск Этот способ удобен при индексном хранении списка. Предполагается, что исходный упорядоченный список B длины N разбит на M подсписков B1,B2,...,Bm длины N1,N2,...,Nm, таким образом, что B=B1,B2,..,Bm. Для нахождения ключа V, нужно сначала определить первый из списков Bi, i=1,M, последний элемент которого больше V, а потом применить последовательный поиск к списку Bi. Хранение списков Bi может быть связным или последовательным. Если длины всех подсписков приблизительно равны и M= N, то Max М-блочного поиска равен 2 N. При одинаковой частоте использования элементов Avg М-блочного поиска равен N. Описанный алгоритм усложняется, если не известно, действительно ли в списке имеется элемент, совпадающий с ключом V. При этом возможны случаи: либо такого элемента в списке нет, либо их несколько. Если вместо ключа V имеется упорядоченный список ключей, то последовательный или М-блочный поиск может оказаться более удобным, чем бинарный, поскольку не требуется повторной инициализации для каждого нового ключа из списка V. 2.3.4. Методы вычисления адреса Методы вычисления адреса. Пусть в каждом из М элементов массива Т содержится элемент списка (например целое положительное число). Если имеется некоторая функция H(V), вычисляющая однозначно по элементу V его адрес - целое положительное число из интервала [0,M-1],то V можно хранить в массиве T с номером H(V) т.е. V=T(H(V)). При таком хранении поиск любого элемента происходит за постоянное время не зависящее от M. Массив T называется массивом хеширования, а функция H - функцией хеширования. При конкретном применении хеширования обычно имеется определенная область возможных значений элементов списка V и некоторая информация о них. На основе этого выбирается размер массива хеширования M и строится функция хеширования. Критерием для выбора M и H является возможность их эффективного использования. Пусть нужно хранить линейный список из элементов K1,K2,..,Kn, таких, что при Ki=Kj, mod(Ki,26)= mod(Kj,26). Для хранения списка выберем массив хеширования T(26) с пространством адресов 0-25 и функцию хеширования H(V)= mod(V,26). Массив T заполняется элементами T(H(Ki))=Ki и T(j)=0 если j (H(K1), H(K2),..,H(Kn)). Поиск элемента V в массиве T с присваиванием Z его индекса если V содержится в T, или -1, если V не содержится в T, осуществляется следующим образом int t[26],v,z,i; i=(int)fmod((double)v,26.0); if(t[i]==v) z=i; else z=-1; Добавление нового элемента V в список с возвращением в Z индекса элемента, где он будет храниться, реализуется фрагментом z=(int)fmod((doule)v,26.0); t[z]=v; а исключение элемента V из списка присваиванием t[(int)fmod((double)v,26)]=0; Теперь рассмотрим более сложный случай, когда условие Ki=Kj H(Ki)=H(Kj) не выполняется. Пусть V - множество возможных элементов списка (целые положительные числа), в котором максимальное число элементов равно 6. Возьмем M=8 и в качестве функции хеширования выберем функцию H(V)=Mod(V,8). Предположим, что B=, причем H(K1)=5, H(K2)=3, H(K3)=6, H(K4)=3, H(K5)=1, т.е. H(K2)=H(K4) хотя K2=K4. Такая ситуация называется коллизией, и в этом случае при заполнении массива хеширования требуется метод для ее разрешения. Обычно выбирается первая свободная ячейка за собственным адресом. Для нашего случая массив T[8] может иметь вид T=<0,K5,0,K2,K4,K1,K3,0> . При наличии коллизий усложняются все алгоритмы работы с массивом хеширования. Рассмотрим работу с массивом T[100], т.е. с пространством адресов от 0 до 99. Пусть количество элементов N не более 99, тогда в T всегда будет хотя бы один свободный элемент равный нулю. Для объявления массива используем оператор int static t[100]; Добавление в массив T нового элемента Z с занесением его адреса в I и числа элементов в N выполняется так: i=h(z); while (t[i]!=0 && t[i]!=z) if (i==99) i=0; else i++; if (t[i]!=z) t[i]=z, n++; Поиск в массиве T элемента Z с присвоением I индекса Z, если Z имеется в T, или I=-1, если такого элемента нет, реализуется следующим образом: i=h(z); while (t[i]!=0 && t[i]!=z) if (i==99) i=0; else i++; if (t[i]==0) i=-1; При наличии коллизий исключение элемента из списка путем пометки его как пустого, т.е. t[i]=0, может привести к ошибке. Например, если из списка B исключить элемент K2, то получим массив хеширования в виде T=<0,K5,0,0,K4,K1,K3,0>, в котором невозможно найти элемент K4, поскольку H(K4)=3, а T(3)=0. В таких случаях при исключении элемента из списка можно записывать в массив хеширования некоторое значение непринадлежащее области значений элементов списка и не равное нулю. При работе с таким массивом это значение будет указывать на то, что нужно просматривать со средние ячейки. Достоинство методов вычисления адреса состоит в том, что они самые быстрые, а недостаток в том, что порядок элементов в массиве T не совпадает с их порядком в списке, кроме того довольно сложно осуществить динамическое расширение массива T. 2.3.5. Выбор в линейных списках Задача выбора. Задан линейный список целых, различных по значению чисел B=, требуется найти элемент, имеющий i-тое наибольшее значение в порядке убывания элементов. При i=1 задача эквивалентна поиску максимального элемента, при i=2 поиску элемента с вторым наибольшим значением. Поставленная задача может быть получена из задачи поиска j-того минимального значения заменой i=n-j+1 и поиском i-того максимального значения. Особый интерес представляет задача выбора при i=a/n, 0<a<1, в частности, задача выбора медианы при a=1/2. Все варианты задачи выбора легко решаются, если список B полностью отсортирован, тогда просто нужно выбрать i-тый элемент. Однако в результате полной сортировки списка B получается больше информации, чем требуется для решения поставленной задачи. Количество действий можно уменьшить применяя сортировку выбором только частично до i-того элемента. Это можно сделать, напри мер при помощи функции findi / выбор путем частичной сортировки / int findi(int s, int n, int i) { int c,j,k; for (k=0; k<=i; k++) for (j="k+1;" j<="n;" j++) if (s[k] < s[j]) { c="s[k];" s[k]="s[j];" s[j]="c;" } return s[i]; } Эта функция ищет элемент с индексом i, частично сортируя массив s, и выполняет при этом (ni) сравнений. Отсюда следует, что функция findi приемлима для решения задачи при малом значении i, и малоэффективна при нахождении медианы. Для решения задачи выбора i-того наибольшего значения в списке B модифицируем алгоритм быстрой сортировки. Список B разбиваем элементом K1 на подсписки B' и B", такие, что если Ki -B', то Ki>K1, и если Ki - B", то Ki<K1, и список B реорганизуется в список B',K1,B". Если K1 элемент располагается в списке на j-том месте и j=i, то искомый элемент найден. При j>i наибольшее значение ищется в списке B'; при j<i будем искать (i-j) значение в подсписке B". Алгоритм выбора на базе быстрой сортировки в общем эффективен, но для улучшения алгоритма необходимо, чтобы разбиение списка на подсписки осуществлялось почти пополам. Следующий алгоритм эффективно решает задачу выбора i-того наибольшего элемента в списке B, деля его на подсписки примерно равной величины. 1. Если N<21, то выбрать i-тый наибольший элемент списка B обычной сортировкой. 2. Если N>21 разделим список на P=N/7 подсписков по 7 элементов в каждом, кроме последнего в котором mod(N,7) элементов. 3. Определим список W из медиан полученных подсписков (четвертых наибольших значений) и найдем в W его медиану M (рекурсивно при помощи данного алгоритма) т.е. (P/2+1)-й наибольший элемент. 4. С помощью элемента M разобьем список B на два подсписка B' с j элементами большими или равными M, и B" c N-j элементами меньшими M. При j>i повторим процедуру поиска сначала, но только в подсписке B'. При j=i искомый элемент найден, равен M и поиск прекращается. При j < i будем искать (i-j)-тый наибольший элемент в списке B". / алгоритм выбора делением списка почти пополам / int search (int b, int n, int i) { int findi(int , int, int); int t, m, j, p, s, w; if (n<21) return findi(b, n, i); /* шаг 1 / p="(int)(n/7);" w="calloc(p+1,sizeof(int));" / шаги 2 и 3 / for (t="0;" t < p; t++) w[t]="findi(b+7t," 7, 3); if (n%7!="0)" { w[p]="findi(b+7p,n%7,(n%7)/2);" p++; } m="search(w," p, p/2); free (w); for (j="0," t="0;" t < n; t++) / шаг 4 / if (b[t]>=m) j++; if (j>i) { for (p=0, t=0; p < n; t++) if (b[t]>=m) { b[p]=b[t]; p++; } m=search(b, j, i); / поиск в B" / } if (j < i) { for (p=0, t=0; t < n; t++) if (b[t] < m) b[p++]=b[t]; m=search(b, n-j, i-j); / поиск в B" / } return m; } Рекурсивная функция search реализует алгоритм выбора i-того наибольшего значения. Для ее вызова можно использовать следующую программу #include #include main() { int search (int b, int n, int i); int b; int l, i, k, t; scanf("%d%d",&l,&i); printf ("\nВыбор %d максимального элемента из %d штук",i,l); b=(int )(calloc(100,sizeof(int))); for (k=0; k<100; k++) b[k]="k;" /* заполнение массива / for (k="1;" k < l/4; k++) { t="b[k];" / перемешивание / b[k]="b[l-k];" / массива / b[l-k]="t;" } k="search(b,l,i);" / выбор элемента / printf ("\n выбран элемент равный %d\n\n",k); return 0; } Используя метод математической индукции, можно доказать, что для функции search требуется выполнить в самом неблагоприятном случае 28N сравнений. Действительно, если N<21, то выполнение функции findi потребует сравнений порядка N(N-1)/2, т.е. меньше чем 28N. Предположим, что для любого T<N количество сравнений при выполнении функции search не более 28T и подсчитаем, сколько сравнений потребуется функции search при произвольном значении N. Для поиска медианы в каждом из подсписков функцией findi требуется не более 7(7-1)/2=21 сравнений, а для формирования массива W в целом не более 21(N/7)=3N сравнений. По предположению индукции для поиска медианы в массиве W длины N/7 требуется 28(N/7)=4N сравнений. После удаления из B части элементов с помощью медианы в B' (или в B") останется не более N5/7 элементов, и для удаления ненужных элементов необходимо количество сравнений порядка N. Для поиска в оставшейся части массива (в B' или B") по предположению индукции требуется не более 28(N5/7)=20N сравнений. Таким образом, всего потребуется 3N+4N+N+20N=28N сравнений, т.е. выдвинутое предположение доказано.