- •Предназначено студентам очной формы обучения.
- •Введение
- •1. Оценки сложности алгоритмов
- •1.1. Определение понятия алгоритм
- •1.2. Оценка сложности алгоритмов
- •2. Линейные структуры данных
- •2.1. Методы организации и хранения линейных списков
- •2.2. Операции со списками при последовательном хранении
- •2.3. Операции со списками при связном хранении
- •2.4. Организация двусвязных списков
- •Задания для самоконтроля
- •2.5. Стеки и очереди
- •2.6. Сжатое и индексное хранение линейных списков
- •3. Сортировка и слияние
- •3.1. Пузырьковая сортировка
- •3.2. Сортировка вставкой
- •3.3. Сортировка посредством выбора
- •3.4. Сортировка квадратичной выборкой
- •3.5. Слияние списков
- •3.6. Сортировка списков путем слияния
- •3.7. Быстрая и распределяющая сортировки
- •4. Поиск
- •4.1. Последовательный поиск
- •4.2. Бинарный поиск
- •4.4. Методы вычисления адреса
- •4.5. Выбор в линейных списках
- •5. Рекурсия
- •6. Алгоритмы на графах и сетях
- •6.1. Исходные понятия
- •6.2. Матричные представления графов
- •6.3. Другие представления графов
- •6.4. Поиск в глубину как система исследования графа
- •6.5. Перебор цепей поиском в глубину
- •6.6. Взвешенные графы. Ориентированные графы
- •6.7. Нахождение фундаментального множества циклов
- •6.8. Выявление мостов и точек сочленений
- •6.9. Поиск в ширину как система исследования графа
- •6.10. Кратчайшие пути, ведущие от заданного узла X ко всем прочим
- •6.11. Алгоритм Дейкстры нахождения кратчайших путей во взвешенном графе
- •6.12. Улучшения алгоритма Дейкстры
- •6.13. Построение кратчайшего каркаса
- •6.14. Нахождение всевозможных кратчайших путей в графе
- •6.15. Потоковые задачи
- •6.16. Пример практической задачи на графах
- •7. Генераторы случайных и псевдослучайных последовательностей
- •7.1. Общая постановка задачи
- •7.3. Генератор случайных чисел, поставляемый с системой
- •7.4. Генератор с малым кодом
- •7.5. Генератор Парка-Миллера
- •7.6. Улучшенная версия генератора Парка-Миллера
- •7.7. Быстрый генератор для 32-битового представления целых и действительных чисел
- •7.8. Алгоритм л'Экюера, комбинирующий две последовательности
- •Оглавление
- •7. Генераторы случайных и псевдослучайных последовательностей 144
- •394026 Воронеж, Московский просп., 14
4.5. Выбор в линейных списках
Задан линейный список целых, различных по значению чисел B=<K1, K2,…, Kn>, требуется найти элемент, имеющий i-е наибольшее значение в порядке убывания элементов. При i=1 задача эквивалентна поиску максимального элемента, при i=2 - поиску элемента с вторым наибольшим значением.
Поставленная задача может быть получена из задачи поиска j-го минимального значения заменой i=n-j+1 и поиском i-го максимального значения. Особый интерес представляет задача выбора при i=[an], 0<a<1, в частности, задача выбора медианы при a=1/2.
Все варианты задачи выбора легко решаются, если список B полностью отсортирован, тогда просто нужно выбрать i-й элемент. Такой подход к решению задачи требует при самых благоприятных условиях количества действий порядка О(n*log2n) независимо от значения 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;
}
returns[i];}
Эта функция ищет элемент с индексом i, частично сортируя массив s, требуя количества сравнений порядка O((n-m)*(I-m)). Отсюда следует, что функция findi приемлема для решения задачи при малом значении i, и малоэффективна при нахождении медианы при I=(n+m)/2.
Для решения задачи выбора i-того наибольшего значения в списке B=<K1, K2,…, Kn> модифицируем алгоритм быстрой сортировки. Список B разбиваем элементом K1 на подсписки B' и B", такие, что если KB', то КК1, а если КВ", то К<K1, и список В реорганизуется в В', <K1>, B". Если К1 располагается в списке на j-м месте и j=i, то требуемый элемент уже найден. При j>ii-e наибольшее значение ищется в подсписке B'; при j<i(i-j)-e наибольшее значение – в подсписке В".
Алгоритм выбора на базе быстрой сортировки, в общем, эффективен – для его выполнения требуется количество действий порядка O(N). однако в некоторых случаях он может оказаться неэффективным, поскольку для его реализации потребуется действий порядка O(N2). Это обусловлено тем, что К1 обычно делит список В на B' и B" неравномерно. Для улучшения алгоритма необходимо уметь находить в списке В элемент М, разбивающий В почти пополам.
Алгоритм ВЫБОР (В,N,i) эффективно решает задачу выбора i-го наибольшего элемента в списке B=<K1, K2,…, Kn>, используя элемент М. Алгоритм выполняет определенную работу по шагам и неформально его можно описать следующим образом.
1. Если N<21, то выбрать i-тый наибольший элемент списка B обычной сортировкой.
2. Если N21 разделим список на 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, *w;
if (n<21) return findi(b, n, i); /* шаг 1 */
p=(int)(n/7);
w=(int*)calloc(p+1,sizeof(int)); /* шаги 2 и 3 */
for (t=0; t < p; t++)
w[t]=findi(b+7*t, 7, 3);
if (n%7!=0)
{
w[p]=findi(b+7*p,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<stdio.h>
#include <stdlib.h>
void 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;
}
Используя метод математической индукции, можно доказать, что для функции search требуется выполнить в самом неблагоприятном случае 28*N сравнений.
Действительно, если N<21, то выполнение функции findi потребует сравнений порядка N*(N-1)/2, т.е. меньше чем 28*N. Предположим, что для любого T<N количество сравнений при выполнении функции search не более 28*T и подсчитаем, сколько сравнений потребуется функции search при произвольном значении N. Для поиска медианы в каждом из подсписков функцией findi требуется не более 7*(7-1)/2=21 сравнений, а для формирования массива W в целом не более 21*(N/7)=3*N сравнений. По предположению индукции для поиска медианы в массиве W длины N/7 требуется 28*(N/7)=4*N сравнений. После удаления из B части элементов с помощью медианы в B' (или в B") останется не более N*5/7 элементов, и для удаления ненужных элементов необходимо количество сравнений порядка N. Для поиска в оставшейся части массива (в B' или B") по предположению индукции требуется не более 28*(N*5/7)=20*N сравнений. Таким образом, всего потребуется 3*N+4*N+N+20*N=28*N сравнений, т.е. выдвинутое предположение доказано.