- •Билет №8 Вычисления с вещественными числами и машинное эпсилон №8
- •Машинное эпсилон может быть вычислено с помощью следующей программы:
- •Билет №9 Общая схема итерации и №9 рекуррентные вычисления
- •Вычисления с целыми числами
- •Билет№10 Схема интерации. Вычисление частичной суммы (вещ числа) №10
- •Общая формулировка задания
- •Пример выполнения задания
- •Вопрос №12 . Основные правила аналитической верификации программ №12
- •Вопрос №14 Ограничивающая ф-ция оператора цикла.Примеры №14
- •Билет№15. Теорема о цикле, его инварианте и ограничивающей функции №15
- •Билет №17 Теорема о цикле repeat- until ,его инварианте и ограничивающей его ф-ции. Аннотирование цикла и понимание аннотации №17
- •Вопрос№18 Алгоритм анализа двоичной записи натурального числа в двоичной сист счисления №18
- •Последовательности и файлы
- •Индуктивные функции
- •Стационарные значения индуктивных функций
- •Индуктивные расширения функций
- •Примеры задач с индуктивными функциями
- •Кванторы и запись утверждений о массивах
- •Правила вывода для цикла с параметром
- •Примеры программ работы с массивами
- •Решение последовательными обменами
- •Задача перестановки сегментов разной длины (второе решение)
- •Задача перестановки сегментов разной длины (третье решение)
- •Билет№35 Задача о равнинах (с испол массива) №35
- •Линейный поиск
- •Оптимизация программы бинарного поиска
- •Билет№44 Массивы в качестве параметров:открытые массивы №44 Сведения о массивах в языке Паскаль
- •Билет№45 Двумерные (многомерные массивы). Индексация. Исполбзование процедур. Задача: о МиниМаксе(матрица как массив строк) №45 обработка двухмерных массивов
Решение последовательными обменами
Можно ли помещать сдвигаемый эл-т массива сразу на нужную позицию? Рассмотрим несколько простых примеров. Пусть n = 8, а k = 3. Исходное и конечное состояния массива изображены на рис. 4.2.
Начнём с элемента a[1]. Он должен попасть в позицию 5, но она пока что занята. Отложим элемент a[1]. На его место должен попасть элемент с индексом 1 + 3 = 4 (в более общем случае – элемент с индексом 1 + k). Переместим a[4] в позицию с номером 1. Далее на место с номером 4 должен попасть элемент a[4 + 3], т. е. a[7]. Переместим a[7] в позицию с номером 4. Затем определим элемент, который должен занять прежнее место элемента a[7]. Для этого вычислим его номер: 7 + 3 = 10. Элемента с таким номером в массиве нет. Очевидно, что нужный нам номер можно получить, «замкнув массив в кольцо», как показано на рисунке слева, и переместиться по кольцу на три позиции по часовой стрелке от элемента с номером 7. Нужным элементом будет элемент с номером 3. Его индекс можно получить, вычитая 7 из 10. В общем случае на место эл-та a[i] должен записываться эл-т a[i + k], если i + k n. Если же i + k n, то номер записываемого эл-та следует вычислить как (i + k) n + 1. Далее, действуя таким образом, получим ещё три перемещения 6 3, 2 6, 5 2 (здесь указаны номера позиций). Следующим должно бы стать перемещение 1 5, но эл-т a[1] уже участвовал в этом процессе, а именно, вспомним, что он был «отложен», а его место занял исходный эл-т a[4]. Таким образом, процесс перемещений завершается записью отложенного эл-та в позицию с номером 5. В итоге все 7 эл-тов заняли новые места, что схематично отражено на рис. 4.3.
Однако не во всех случаях результат получается так просто. Рассмотрим пример с n = 9 и k = 2. Действуя, как и ранее, получим последовательность перемещений 1 x, 3 1, 5 3, 7 5, x 7. Здесь x обозначает хранилище для первого (отложенного) эл-та. Процесс перемещений (рис. 4.4) завершается при попадании в массиве на исходное место отложенного эл-та (в данном случае a[1]).
Очевидно, что переместилась только часть эл-тов массива, а именно эл-ты 1, 3, 5, 7. Перемещения этих эл-тов образуют замкнутую «траекторию» (цикл). Эл-ты 2, 4, 6, 8 остались вне наших действий. В данном примере можно продолжить перемещения, начав их теперь уже с эл-та 2. Эти перемещения также образуют цикл, как показано на рис. 4.5 (этот второй цикл изображен сверху над изображением массива).
В данном примере потребовались перемещения всего по двум замкнутым траекториям (циклам). В других случаях, например при n = 10 и k = 3, перемещения образуют три цикла. Оказывается, что количество циклов равно НОД(n 1, k). Для того чтобы убедиться в этом, удобнее нумеровать эл-ты массива от 0 до n 1. При этом переход через границу массива («закольцовывание») осуществляется операцией mod n над текущим индексом. Для начального эл-та i0 (0 i0 < n) цикл замыкается, если (i0 + p k) mod n = i0, при этом p должно быть минимальным из удовлетворяющих этому уравнению. Отсюда следует, что должно выполняться (p k) mod n = 0 или p k = q n, где q = (p k) div n. Поскольку, кроме того, (p k) mod k = 0 и p минимальное из возможных, то p k = НОК(k, n). Таким образом, длина цикла (замкнутой траектории) p = НОК(k, n) k, а в силу соотношения k n = НОК(k, n) НОД(k, n) длина цикла p = n НОД(k, n) и, следовательно, число таких траекторий НОД(k, n) = n p.
Итак, данный алгоритм обрабатывает Nc = НОД(k, n) замкнутых траекторий. Перемещение эл-тов i-й траектории начинается с эл-та с номером i. Пусть номер текущего эл-та обозначен как Cur, а номер следующего как Next. Тогда каждый шаг цикла перемещений по замкнутой траектории заключается в перенесении э-та Next на уже «подготовленное» место Cur и изменении значений Cur и Next. Эти соображения приводят к следующему алгоритму (здесь элементы массива нумеруются от 1 до n).
Nc := gcd(n, k);
for i := 1 to Nc do
begin {i – начальный эл-т i-й траектории}
x := a[i]; {отложенный первый эл-т}
Cur := i;
Next := Cur + k; if Next > n then Next := Next n;
{Cur куда перемещать}
while Next i do
begin
a[Cur] := a[Next];
Cur := Next;
Next := Next + k; if Next > n then Next := Next n;
end {while};
{Next = i}
a[Cur] := x
end {for}
Подчеркнём, что в этом алгоритме каждый элемент перемещается сразу на своё окончательное место.
Билет№33 Задача перестановки сегментов массива разной длины.Решение испол. Вспом проц перестан сегментов равной длины №33
Пусть задан отрезок массива а[m..n) и (nm) чётно. Сплошные части отрезка назовём сегментами. Выделим в а[m..n) два сегмента равной длины: а[m..k) и а[k..n), где k = (m + n)/2. Размер каждого сегмента есть s = (n m)/2 и k = m + s. Этому соответствует картинка
|
m |
k |
n |
a: |
Сегмент 1 |
Сегмент 2 |
|
Задача состоит в перестановке сегментов 1 и 2. Запишем предутверждение и постутверждение этой задачи:
Pred: (m + n = 2 k) & (m < k < n) & (а[m..n) = A[m..n)),
Post: (m + n = 2 k) & (m < k < n) & (а[m..k) =
=A[k..n)) & (а[k..n) = A[m..k)).
Очевидно, что задачу можно решить, используя цикл, на каждом шаге которого два эл-та (по одному из каждого сегмента) меняются местами. Инвариантом цикла может быть утверждение:
|
m |
i |
k |
j |
n |
a: |
Обменены |
Исходные |
Обменены |
Исходные |
& (m i k) & (j = s + i) |
Тогда, используя цикл for-to-do, получим программу:
k := (m + n) div 2; for i := m to k 1 do a[i] a[s + i].
Чтобы избежать на каждом шаге сложения при вычислении индекса s + i, можно наращивать на 1 переменную j = s + i синхронно с изменением i:
k :=(m + n) div 2; j := m + s 1;
for i := m to k 1 do begin j := j + 1; a[i] a[j] end.
Если требуется переставить два неприлегающих сегмента a[m..m + s) и a[k..k + s), то эта задача может быть решена аналогичным образом:
procedure SwapEq ( var a: Vector; m, k: index; s: index0);
{Pred: (Low(a) m)&(m+sk)&(k+sHigh(a)+1)&(a[m..k+s)=A[m..k+s))}
{ Post: (m+s k) & (a[m..m+s) = A[k..k+s)) & (a[k..k+s) = A[m..m+s))& (a[m+s..k) = A[m+s..k))}
var i, j: index;
begin
j := k 1; { в цикле будет j = k – m + i }
for i := m to m + s 1 do begin j := j + 1; a[i] a[j] end;
end {SwapEq}
Здесь следующая картинка
|
m |
i |
m + s |
k |
j |
k + s | |
a: |
Обменены |
Исходные |
Не менять |
Обменены |
Исходные |
& (m i < m + s) & | |
|
|
|
|
&(m + s k) |
& (j = k – m + i) |
является основной частью индуктивного утверждения P([m..i)) для цикла for.