Navigation bar
  Print document Start Previous page
 136 of 179 
Next page End  

136
Это утверждение доказывается с помощью математической индукции. На его основании можно
сделать заключение о том, что конечным результатом выполнения цикла и алгоритма в целом будет
сумма
S
N
= (с(1) - s(l))
(m(l) - р(1)) + ... + (c(N) - s(N))
(m(N) - p(N)).
Что и требовалось доказать.
Для сортировки данных воспользуемся алгоритмом упорядочения чисел по методу «пузырька»,
предполагая, что исходная и упорядоченная последовательность чисел r1, r2, ..., r
N
будут записаны в мас-
сиве x[l:N].
Для формирования результирующих упорядоченных данных используется массив индексов L(1:N), в
котором будут записаны номера элементов исходной последовательности так, что x(k) = p(L(k)) для
всех k = 1, ..., N.
алг «сортировка данных»
sortdan: 'сортировка данных
массив x[1:N]
dim x(N)
нач
'
от k = 1 до N цикл
   for k = 1 to N
L(k) = k
      L(k) = k
x(k)=p(L(k))
      x(k)=p(L(k))
кцикл
   next k
сортировка-массива
   gosub sortmas 'сортировка
от k = 1 до N цикл
   for k = 1 to N
i := L(k)
      i = L(k)
вывод (tv(i),c(i),p(i))
      ? tv$(i);c(i);p(i)
кцикл
    next k
кон
return
Модификация алгоритма упорядочения чисел, размещаемых в массиве x[l:N], с учетом перестановок
значений в массиве индексов L[1:N] получает следующий вид:
алг «сортировка массива»
sortmas: 'сортировка массива
нач
'
от k = 1 до N-1 цикл
    for k = 1 to N-1
xmn := x(k)
       xmn = x(k)
imn := k
       imn = k
от i = k + 1 до N цикл
       for i = k + 1 to N
если x(i) < xmn то
          if x(i) < xmn then
xmn := x(i)
          xmn = x(i)
imn := i
          imn = i
кесли
       end if
кцикл
    next i
Imn := L(imn)
    Imn = L(imn)
xmn := x(imn)
    xmn = x(imn)
L(imn) := L(k)
    L(imn) = L(k)
x(imn) := x(k)
        x(imn) = x(k)
L(k) :=Imn
        L(k) = Imn
x(k) := xmn
        x(k) = xmn
кцикл
    next k
кон
return
Лемма 4. Результатами выполнения алгоритма сортировки массива будут последовательность чисел,
упорядоченная по возрастанию
х(1)'
х(2)'
...
x(N)'
Сайт создан в системе uCoz