Д. М. Златопольский Санкт-Петербург «бхв-петербург» 2011 удк

Приложения 
268 
Внимание!  
Индекс в последней строке левого столбца таблицы нельзя рассчитывать как  n/2, 
т. к.  значение  индекса  элемента  массива  может  только  целым.  Здесь  возникает 
также вопрос, а что будет, если n — нечетное число? Ответ — в этом случае зна-
чения  в  табл. П3.6  не  изменятся,  а  средний  элемент  (его  индекс  n 
div
 2 + 
1)  ме-
няться не будет (убедитесь в этом, рассмотрев конкретные значения n). 
Для записи соответствующего фрагмента программы необходимо знать, с 
каким  элементом  будет  меняться  значениями  i-й  элемент.  Анализ 
табл. П3.6 показывает, что сумма индексов обмениваемых элементов рав-
на n + 1. Значит, i-й элемент будет меняться с (n + 1 – i)-м. 
Итак, задача решается с помощью такого оператора цикла: 
нц для i от 1 до div(n, 2) 
  |Меняем местами i-й и (n + 1 - i)-й элементы 
  вспомогательная := a[i] 
  a[i] := a[n — i + 1] 
  a[n — i + 1] := вспомогательная 
кц 
Примечание  
В  школьном  алгоритмическом  языке  целочисленное  деление  проводится  с  помо-
щью функции 
div
, а не с помощью специальной операции. 
П3.50.  Перестановка двух половин массива. 
Проанализируем,  какие  элементы  с  какими  меняются  значениями.  Пусть 
количество элементов массива 
10
n
. Тогда 1-й элемент должен меняться 
значениями с 6-м, 2-й — с 7-м, ..., 5-й — с 10-м, т. е. разность между ин-
дексами  равна  5,  а  при  любом  четном  n —  n 
div
 2.  А  если  n —  нечетное 
число,  например,  11?  Можно  увидеть,  что  в  этом  случае  указанная  раз-
ность равна 6, или n 
div
 2 + 1. 
С  учетом  проведенного  анализа  можно,  конечно,  рассматривать  в  про-
грамме два варианта оператора цикла: 
если mod(n, 2) = 0 
  то 
    нц для i от 1 до div(n, 2) 
      |Меняем i-й и (i + div(n, 2))-й элементы 
      вспомогательная := a[i] 
      a[i] := a[i + div(n, 2)] 
      a[i + div(n, 2)] := вспомогательная 
    кц 
  иначе 
    нц для i от 1 до div(n, 2) 

Приложение 3. Работа с одномерными числовыми массивами 
269 
      |Меняем i-й и (i + div(n, 2) + 1)-й элементы 
      вспомогательная := a[i] 
      a[i] := a[i + div(n, 2) + 1] 
      a[i + div(n, 2) + 1] := вспомогательная 
    кц 
все 
Здесь 
mod
 —  функция,  возвращающая  остаток  от  деления  своего  первого 
параметра на второй. 
Но при этом размер программы увеличивается. А нельзя ли получить та-
кую  формулу  для  расчета  разности  между  индексами  обменивающихся 
значениями элементов, чтобы она давала соответствующие значения раз-
ности  как  для  четных  n,  так  и  для  нечетных?  Можно!  Если  считать,  что 
при четном n меняются i-й элемент и (i + 
div
(n, 2) + 0)-й, то можно запи-
сать общую формулу для значения индекса элемента из второй половины 
массива: 
нц для i от 1 до div(n, 2) 
  |Меняем i-й и (i + div(n, 2) + mod(n, 2))-й элементы 
  вспомогательная := a[i] 
  a[i] := a[I + div(n, 2) + mod(n, 2)] 
  a[i + div(n, 2) + mod(n, 2)] := вспомогательная 
кц 
Можно сократить "длину" индекса элемента из второй половины массива, 
если ввести вспомогательную величину 
разность
, представляющую собой 
разность между индексами обмениваемых элементов. Анализ показывает, 
что: 
разность
 = (n + 1) 
div
 2. 
Предлагаем  читателям  самостоятельно  убедиться  в  справедливости  сде-
ланного утверждения. 
С  использованием  этой  величины  фрагмент  программы,  решающий  рас-
сматриваемую задачу, получается достаточно компактным: 
разность := div(n + 1, 2) 
нц для i от 1 до div(n, 2) 
  |Меняем i-й и (i + разность)-й элементы 
  вспомогательная := a[i] 
  a[i] := a[i + разность] 
  a[i + разность] := вспомогательная 
кц 

Приложения 
270 
П3.51.  Удаление из массива k-го элемента со сдвигом всех расположенных спра-
ва от него элементов на одну позицию влево. 
Операторы, осуществляющие сдвиг необходимых элементов: 
a[k] := a[k + 1] 
a[k + 1] := a[k + 2] 
... 
a[n - 1] := a[n] 
можно оформить с использованием оператора цикла в виде: 
нц для i от k до n - 1 
| a[i] := a[i + 1] 
кц 
или 
нц для i от k + 1 до n 
| a[i - 1] := a[i] 
кц 
Внимание!  
После сделанных изменений следует учесть, что количество элементов исходного 
массива уменьшилось на 1. 
Обратите  также  внимание  на  прием,  который  был  применен:  если  сразу 
оператор цикла с параметром оформить сложно, следует выписать дейст-
вия, являющиеся телом этого оператора, принять изменяющуюся величи-
ну  в  качестве  параметра  оператора  цикла  и  определить  его  начальное  и 
конечное  значения.  Этот  прием  будет  использован  и  при  решении  не-
скольких следующих задач. 
П3.52.  Циклическое перемещение элементов массива влево. 
Циклическим перемещением элементов массива влево называют такую их 
перестановку, при которой первый элемент массива записывается на место 
последнего, а второй, третий, ..., последний элементы смещаются на одну 
позицию влево (рис. П3.2).
1
 
 
5 
12 
8 
0 
14 
5 
1 
3 
23 
4 
8 
0 
9 
а — исходный массив 
12 
8 
0 
14 
5 
1 
3 
23 
4 
8 
0 
9 
5 
б — конечный массив 
Рис. П3.2 
                                                           
1
 В общем случае задача формулируется так: "s-й элемент массива записать на место k-го, при этом 
сдвинув (s + 1)-й, (s + 2)-й, ..., k-й элементы на одну позицию влево (s < k)". 

Приложение 3. Работа с одномерными числовыми массивами 
271 
Ясно,  что  сразу  записать  в  программе: 
a[n] := a[1]
  нельзя  (исходное 
значение 
a[n]
  будет  утеряно).  Нельзя  также  сначала  провести  и  сдвиг 
элементов  влево  (
a[1] := a[2]
  и  т. д.).  Как  же  быть? —  Правильно! 
Нужно предварительно запомнить значение первого элемента массива во 
вспомогательной  переменной,  после  чего  провести  сдвиг  необходимых 
элементов  влево,  а  потом  запомненное  значение  записать  в  последнюю 
ячейку массива: 
вспомогательная := a[1] 
нц для i от 1 до n - 1 
  a[i] := a[i + 1] 
кц 
a[n] := вспомогательная 
П3.53.  Вставка в массив заданного числа на k-е место со сдвигом k-го, (k + 1)-го, 
(k + 2)-го, ..., последнего элемента на одну позицию вправо. 
Прежде всего, заметим, что для решения задачи массив должен быть опи-
сан с учетом дополнительного элемента. Еще одна особенность заключа-
ется в том, что в данном случае операторы, реализующие сдвиг элементов 
вправо, мы не можем записать следующим образом: 
a[k + 1] := a[k] 
a[k + 2] := a[k + 1] 
... 
a[n] := a[n - 1] 
Почему  не  можем —  понятно?  Правильный  вариант —  сдвиг  проводить, 
начиная с конца изменяемой части массива: 
a[n] := a[n - 1] 
a[n - 1] := a[n - 2] 
... 
a[k + 2] := a[k + 1] 
a[k + 1] := a[k] 
или, используя при этом оператор цикла: 
нц для i от n до k + 1 шаг -1 
  a[i] := a[i - 1] 
кц 
После сдвига можно в k-ю ячейку записать заданное число: 
a[k] := ... 
П3.54.  Циклическое перемещение элементов вправо. 
Циклическим  перемещением  элементов  массива  вправо  называют  такую 
их  перестановку,  при  которой  последний  элемент  массива  записывается  

Приложения 
272 
на  место  первого,  а  первый,  второй, ...,  предпоследний  элементы  смеща-
ются на одну позицию вправо (рис. П3.3).
1
 
 
12 
3 
0 
23 
5 
7 
13 
7 
7 
45 
8 
2 
1 
а — исходный массив 
1 
12 
3 
0 
23 
5 
7 
13 
7 
7 
45 
8 
2 
б — конечный массив 
Рис. П3.3 
Вспомнив решения предыдущих задач, можем записать: 
вспомогательная := a[n] 
нц для i от n до 2 шаг -1 
  a[i] := a[i - 1] 
кц 
a[1] := вспомогательная 
В заключение заметим, что еще одной достаточно распространенной задачей обра-
ботки  числовых  массивов  является  задача  их  сортировки,  т. е.  переразмещения 
элементов в некотором порядке, как правило, в порядке возрастания или убывания. 
Некоторые методы решения этой задачи рассматриваются в следующем разделе. 
 

жүктеу/скачать 7,99 Mb.

Достарыңызбен бөлісу: