15 Билет. Задача поиска.

а₀,а₁...а_n-1<- найти х - аргумент поиска

{а₀,а₁...а_n-1} i:(0<=i<n):a_i==x

Результаты:

Ǝi : (0<=i<n):a_i==x - успех :i

Для любого (0<=i<n):a_i!==x - неуспех: -1

Const n = 100; int a[n]; int x;

Линейный поиск  Данный алгоритм является простейшим алгоритмом. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило, поиск происходит слева направо, то есть от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым.

Int LS(int k, int a[], int x)

{for (int I = 0; i<k; i++)

If (a[i] == x) return I;

Return -1;}

С барьером К массиву добавляется один элемент и в него записывается искомое значение. Тогда при поиске в условии цикла не нужно проверять индекс на количество. Достаточно проверять просто найден элемент или нет - а он по-любому будет найден, так как мы поставили его в конце. На каждом цикле экономится одно сравнение.

Int LsBr(int k, int a[], int x)

{int R = a[k-1];

a[k-1]=x;

int i=0;

while(a[i]!=x) i++;

a[k-1] = R;

if (a[i]==x) return i;

else return -1;}

Бинарный -совокупность нужно упорядочить. Алгоритм двоичного поиска исключает половину еще непроверенных элементов массива после каждого сравнения. Алгоритм определяет местоположение среднего элемента массива и сравнивает его с ключом поиска. Если они равны, то ключ поиска найден и выдается индекс этого элемента. В противном случае задача сокращается на половину элементов массива. Если ключ поиска меньше, чем средний элемент массива, то дальнейший поиск осуществляется в первой половине массива, а если больше, то во второй половине. Если ключ поиска не совпадает со средним элементом выбранного подмассива (части исходного массива), то алгоритм повторно применяется и сокращает область поиска до четверти исходного массива. Поиск продолжается до тех пор, пока ключ поиска не станет равным среднему элементу или пока оставшийся подмассив содержит хотя бы один элемент, не равный ключу поиска.

Int BS1(int k, int a[], int x)

{int l=0,r=k-1;

While (l<=r)

{int m=(l+r)/2;

If (a[m]==x) return m;

If (a[m]>x) r=m-1;

Else l=m+1;}

Return -1;}

Int BS2(int k, int a[], int x)

{int l=0,r=k-1;

While(l<r)

{int m=(l+r)/2;

If(a[m]<x) l=m+1;

Else r=m;}

Return a[r]==x?r:-1}

Int BS3(int k, int a[], int x)

{int l=0,r=k-1;

While(l<r)

{int m = (l+r+1)/2;

If(a[m]>x) r=m-1;

Else l=m;}

If(a[l]==x) return l;

Else return -1;}

LS:O(n); BS: O(log₂n)

Поиск по ключу

Struct TS

{t1 p1;

t2 p2;

……………….

t_k p_k; - поле ключа

………………

t_n p_n;

}

TS a[n];

t_k x;

a[i].p_k==x ?

a[i]==x

Обобщенный поиск

A[0]a[1]…a[n-1]

F(a[i])=x

16 билет. Задача сортировки

A₀a₁a₂…a_n-1->a_i0a_i1…a_in-1

F(a_i0)<=f(a_i1)<=…<=f(a_in-1)f(x) – упорядочивающая функция

Методы (прямые): выбором, включением, обменом.

Эффективность методов: С(n) – кол-во сравнений;M(n) – кол-во перемещений; временная сложность –T(n),O(f(n)).

Const int nn = 100; int a[nn];

Выбор

Идея:

1).Min{ A₀a₁…a_n-1}a₀

2).Min{ a₁…a_n-1}a₁

i).Min{ a_i…a_n-1}a_i

n-2).Min{ a_n-2a_n-1}a_n-2

Схема:

For(i=0;i<n-1;i++)

{поиск места К мин. эл-та в совокупности {A₀a₁a₂…a_n-1}

Переставить a_ka_i}

Void selection(int a[], int n)

{for (int i=0; i<n-1; i++)

{int min = a[i], k=I;

For (int j=i+1; j<n;j++)

If (a[j]<min)

{min =a[j]; k=j}

A[k]=a[i];a[i]=min}

}

Характеристики: C(n) = =; M(n)_min=3*(n-1); M(n)_max=3*(n-1)+[]; T(n)=C*n²;

Модификации.

1). Поиск max{a₀a₁…a_n-1-i}

2). {a_i…a_n-1-i} min k, max m;

A[k] a[i] if(m==i) m=k; a[m]a[n-1-i]

Включение

Идея: S1-упорядоченаS2-неупорядочена

a₀a₁ a₂…a_i-1 |a_i… a_n-1

 R

Схема:

For(i=1;i<n;i++)

{R=a[i]; включитьRв совокупность {A₀…a_n-1}, поиск места вставкиR

в совокупность { A₀a₁…a_ka_k+1…a_i} сдвиг {A_k+1…a_i-1} вставкаa[k+1]=R;}

void insertion(int a[],int n)

{for (int i=1;i<n;i++)

Int R=a[i];

While(k>=0&&a[k]>R)

{a[k+1]=a[k];k--;a[k+1]=R;}

}

Характеристики: C(n)_min=n-1; C(n)_max==; M(n)_min=2(n-1); M_max=2(n-1)+=; T(n)=C*n²;O(n²);

Модификации:

1).поиск линейный (слева направо) с правым барьером.

K=0;

While(a[k]<R) k++;

For(int j = i-1;j>=k;j--) a[j+1]=a[j]; a[k]=R;

2).Поиск линейный с левом барьером.

For(int i=n-1;i>0;i--)

If (a[i]<a[i-1])

{int t = a[i]; a[i] = a[i-1]; a[i-1] = t;}

For(int i=2; i<n;i++) R=a[i];

3).Двоичное включение.

Обменом

Идея: A₀a₁…a_ja_j+1…a_n-2a_n-1 a_j <=a_j+1



Void Bubble(int a[], int n)

{for (int i=n-1; i>0;i--)

For(int j=0;j<I;j++)

If (a[j]>a[j+1])

{int t=a[j]; a[j]=a[j+1]; a[j+1]=t;}

}

Характеристики: C(n) =;M(n)_min=0;M(n)_max=3*

С ЗАПОМИНАНИЕМ ФАКТА ПЕРЕСТАНОВКИ.

While(true){

Bool swapped = false;

For(…){

If (…) swapped = true; //если была перестановка

}

if(!swapped) break;}

ВЕКТОРОМ ИНДЕКСА.

A– исходный массив,V[i]=i- вектор индексов(массив)

For(int i=0; i<count; i++)

{for(int j=0; j < count – I; j++)

{if (A[V[j]]>A[V[j+1]]) swap(V[j], V[j+1])}

}