Задачи второго класса

Особенностью задач этого класса является изменение порядка следования элементов массива. Для этого часто приходится менять местами элементы массива. Поэтому необходимо ввести дополнительную переменную, для того, чтобы не потерять старое значение элемента массива. Это выполняется с помощью приведенных ниже операторов.

Задача 1. Поменяйте местами значения переменных a[i] и a[j].

Решение.

r:= a[i]; {запомнили a[i] во вспомогательной переменной}

a[i]:= a[j]; { записали значение a[j] на место a[i], старое значение

последнего потерялось, но сохранилась его копия в

переменной r}

a[j]:=r; { записали запомненное значение a[i] на место a[j]}

Задача 2. Переверните массив, т.е. запишите элементы массива в обратном порядке.

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

i:= 1; j:= n;

while i <= j do

begin

r:= a[i];

a[i]:= a[j];

a[j]:= r;

i:= i + 1; j:= j +1

end;

Упражнение. Внесите изменения в приведенный выше фрагмент программы для того, чтобы переворачивалась часть массива от элемента с номером p до элемента с номером q, не используя при этом дополнительный массив.

Задача 3. Поменяйте местами пары соседних элементов, т.е. первый и второй, третий и четвертый и т.д. (n-1)-ый и n-ый.

Решение. В этой задаче используется схема обмена элементов при схеме перебора с шагом два.

i:= 2;

while i < n do

begin

r:= a[i];

a[i]:= a[i+1];

a[i+1]:= r;

i:= i + 2

end;

Задача 4. Циклически сдвиньте элементы массива на один элемент влево.

Решение. Циклический сдвиг означает, что происходит следующая замена: первый элемент заменяется вторым, второй - третьим и т.д., последний - старым значением первого. При этом можно потерять только значение первого элемента, которое и необходимо сохранить перед циклом.

r:= a[1];

for i:= 1 to n-1 do

a[i]:= a[i + 1];

a[n]:= r;

Задача 5. Сдвиньте циклически элементы массива на k позиций влево.

Решение. Можно воспользоваться предыдущим решением, повторив k раз сдвиг на один элемент.

for j:= 1 to k do

begin

r:= a[1];

for i:= 1 to n - 1 do

a[i]:= a[i + 1];

a[n]:= r

end.

Можно решить эту задачу с использованием вспомогательного массива, в котором будут сохранены первые k элементов. Затем, после сдвига оставшихся элементов на k позиций влево, в оставшиеся позиции будут переписаны элементы из вспомогательного массива.

for i:= 1 to k do

b[i]:= a[i];

for i:= 1 to n - k do

a[i]:= a[i + k];

for i:= n- k + 1 to n do

a[i]:= b[i - k + 1];

Упражнение. Напишите программу циклического сдвига одномерного массива вправо на k элементов.

Поиск по сайту: