Практика программирования (Бейсик, Си, Паскаль)



         

Задачи, советы и ответы - часть 2


Конечно, можно принять предложенный алгоритм на веру и убедиться на нескольких примерах, что он работает правильно. Но это не может дать абсолютной уверенности в том, что также произойдет на любых сочетаниях исходных данных. Поэтому можно попытаться доказать правильность алгоритма, проследив за местоположением (индексом) каждого элемента после указанных перестановок.

Если элемент с исходным индексом i принадлежал голове массива (i < i < k), то инвертирование головы перемещает:

1-й элемент в позицию с индексом k, 2-й элемент в позицию с индексом k-l,

k-й элемент в позицию с индексом 1.

Сумма индексов элементов, меняющихся своими местами, при этом равна k+l. Поэтому 1-й элемент из головной части после инвертирования головы массива окажется на месте с индексом k-i+1. При последующем инвертировании всего массива сумма индексов взаимных пар меняющихся элементов равна п+1. Следовательно, элемент с первоначальным индексом i из головной части окажется на месте элемента с индексом (n+l) - (k-i+l)=n-k+i. Таким образом:

1-й элемент окончательно окажется в позиции n-k+l, 2-й элемент окончательно окажется в позиции n-k+2,

k-й элемент окончательно окажется в позиции n-k+k.

Это означает, что прежняя голова массива переместится в его хвост, сохранив взаимное расположение элементов.

Теперь рассмотрим поведение 1-го элемента из хвостовой части (k + i < i < n). После инвертирования хвоста:

элемент с индексом k+l окажется в позиции п, элемент с индексом k+2 окажется в позиции n-1,

элемент с индексом п окажется в позиции k+l.

Сумма индексов пар, меняющихся при этом местами, равна n+k+i. Поэтому 1-й элемент из хвостовой части после инвертирования хвоста перемещается в по-

зицию n+k+l-i. При последующем инвертировании полного массива, когда сумма индексов соответствующих пар равна n+1, произойдет следующее:

элемент с индексом k+l, предварительно перемещенный в позицию n, займет место элемента с номером (n+l)-n=l;

элемент с индексом k+2, предварительно перемещенный в позицию п-1, займет место элемента с номером (n+1)-(n-1)=2;




Содержание  Назад  Вперед