Материал для практических занятий

Решение задач из курса исследования операций опирается на ряд  элементарных действий, среди которых основными являются операции сортировки , поиска и перебора.

6.1 Сортировка.

Пусть дан файл, состоящий из записей

f(1),f(2),....,f(n)

Будем сортировать записи по некоторому полю Kf(i) (i=1...n)-ключ. Считаем, что ключи можно упорядочить по некоторому принципу, т.е. указать последовательность кто за кем стоит.

Задача: найти такую перестановку записей, чтобы ключи располагались в неубывающем порядке

f(11) f(12)... f(1n)       (2)

Kf(i1)<=Kf(i2)<=...<=Kf(in)   (3)

Для получения из файла (1) не нужно физического перемещения записей. Достаточно задать доступ к записям файла (1) в соответствии с  порядком (3).

Пример       1  2  3  4  5- номера

             3  1  5  7  2  (1)

             1  2  3  5  7  (2)-делается человеком

создаем адреса

             2  5  1  3  4 - индексный файл, показывающий в каком порядке нужно брать записи из исходного файла, чтобы получился возрастающий ряд.

Методы сортировки:

1)сортировка пузырьком- производится сравнение соседних элементов снизу вверх попарно, элементы меняются местами, если они не удовлетворяют условию, т.е. образуют инверсную пару. Для полного выполнения процедуры понадобится n*n срaвнений. Инверсной парой называется пара элементов a(i) и a(j), для которой

        a(i)>a(j) при  i<j.

2) среди n элементов находим самый малый, меняем его мeстами с первым  элементом. Среди оставшихся (n-1) элементов находим самый малый и меняем его местом со вторым и т.д. Всего понадобится n(n-1)/2  операций.

3) сортировка методом Шелла. Делим весь массив элементов на N/2 групп по два элемента. Внутри группы сортируем элементы. Затем делим весь массив на N/4 группы по 4 элемента и опять сортируем и т.д. Всего понадобится N log N операций. Если число N нельзя

представить в виде 2 в степени N,  то в качестве N берется число большее числа элементов и кратное 2. Например, для группы из 5 элементов N=8, а для группы из 13 элементов N=16.

Алгоритмы сортировки

1. Алгоритм упорядочения 1 (цел N, вещ таб А [1:N])

   арг А,N

   рез таб А

начало

цел i,k,l;

вещ М;

k=1;

пока k<N

нц

M=A[k];l=k;i=k+1;

пока i<=N

нц

если М>A[i] то М=A[i];l=i все

i=i+1;

кц

A[l]=A[k];A[k]=M;k=k+1;

кц

конец

2. алгоритм Шелла (цел N, вещ таб A[1:N])

арг А,N

рез А

начало

цел i,j,k,l,M, вещ R

k=1;

пока k<N

нц

k=k*2

кц

m1: k=k/2;

если k<1 то переход на конец все

M=N-k;

i=1;

пока i<=M

нц

j=i;

пока j>0

нц

l=j+k;

если A[l]<A[j] то R=A[j];

A[j]=A[l];A[l]=R все

j=j-k;

кц

i=i+1;

кц

переход на m1;

конец

2. Алгоритм быстрая сортировка Хоара (сортировка с разделением) Идея: массив S(k),k=1...n, пусть x принадлежит S. Разбиваем массив  на два непересекающихся непустых подмножества S₁ и S₂. Разбиение  делаем так, чтобы в одном массиве S₁ оказались все элементы не превосходящие x, a<=x, a принадлежит  S₁, а во втором массиве были  все остальные элементы b>x,b из  S₂.

        6  23  17  18  14  25  3  30  7

Выбираем средний элемент 14, как граничный , тогда в левой группе нужно переставить число 23 за число 18 , а во второй группе  переставить число 7 за число 3

                    Практика

5 rem нахождение min и max элемента в массиве

10 dim a(10)

20 for i=1 to 0

30 read a(i)

40 next

50 data 26,13,7,9,31,71,5,5,8,2,11

60 b=a(19:c=a(1) rem max ,min

70 for i=2 to 10

80 if a(i)>b then b=a(i)

90 if a(i)<c then c=a(i)

100 next

110 print "максимальное число=";b

120 print "минимальное число=;c

130 end

Если числа должны быть в массиве построены машиной, то используем генератор случайных чисел

30 a(i)=int(rnd*100): print a(i);

Чтобы при каждом новом запуске числа менялись, добавим строку

7 randomize 1000

Для выхода из Бейсика: набираем system, затем нажимаем клавишу ввода.

Сортировка пузырьком

5 randomize 1000

10 dim a(10)

20 for i=1 to 10

30 a(i)=int(rnd*100):print a(i);

40 next

50 for g=2 to 10

60 for t=1 to g step -1

70 if a(t)>a(t-1) then swap a(t),a(t-1)

80 next t

90 next g

100 for t=1 to 10

110 print a(t);

120 next

Пример   39 54 3 89 73 63 58 97 54 31

         97 89 73 63 58 54 39 31 3

swap меняет местами

Алгоритм упорядочения 1

5 randomize 1000

10 input "введите размерность";n

10 dim a(n)

20 for i=1 to n

30 a(i)=int (rnd*100):print a(i)

45 print

40 next

50 for i=1 to n-1

60 m=a(k):l=k:i=k+1

70 if i>n then goto 100

80 if m>a(i) then m=a(i):l=i

90 i=i+1:goto 70

100 a(l)=a(k):a(k)=m

110 next

120 for i=1 to n

130 print a(i);

140 next

алгоритм Шелла

10 randomize 1000

20 input"введите размерность";n

30 dim a(n)

40 for i=1 to n

50 a(i)=int(rnd*100):print a(i);

60 next

70 print

80 for k=1 to n-1

90 if k<n then k=k*2

100 next

110 k=int(k/2):print k:print

120 if k<1 then goto 190

130 m=n-k

140 for i=1 to m

150 j=i

160 if j<=0 then goto 170

170 l=j+k

180 if a(l)<a(j) then swap a(l),a(j)

190 j=j-k

200 goto 160

210 next

220 goto 110

230 for i=1 to n

240 print a(i);

250 next