Damir Tenisheff, 24 April 2005. Назначение документа: сопровождающий материал лекций ЛО и ПО АС. Уровень подготовки: новичок.

Постановка задачи

Задан массив на N элементов. Требуется написать функцию, сдвигающую элементы в массиве (значения) циклически вправо на K позиций.

Дополнительные условия:

Память можно выделять только для ограниченного числа временных переменных. Нельзя выделять массивы, размер которых зависит от N или K. То есть задача должна быть решена в исходном массиве.

Пример:

Для массива { 1,2,3,4,5 } при величине K=2 результат будет { 4,5,1,2,3 }.

Основные ошибки, допущенные при выполнении работы

Неправильное определение данных и функции

Неправильное оформление интерфейса функции

1
2
3
4

void func() {
  int n=6, k=2;
  int matrix[6]={7,2,6,5,4,1,4};
  int matrix2[6];

Имя функции должно отражать её назначение. Имя данной функции должно было быть rotate_right. В крайнем случае shift, cyclic_shift. Называть функцию незначимым названием допустимо лишь в абстрактном примере.

Функция создаётся с расчётом на возможность работы с массивами различного размера и различной величиной сдвига. «Зашивать» эти данные в код (строка 2) – недопустимо. В дополнение это привело к появлению в коде «магических констант», которые сложно будет объяснить пользователю. Сам массив тоже недопустимо было «зашивать» в код. Хотя это явно и не указано в постановке задачи, здесь ставящий задачу уповает на здравый смысл исполнителя.

В строке [3] допущено сразу несколько ошибок. Задан размер массива (снова «магическое число»), хотя значение n к этому моменту уже известно. В данном же случае размер вообще не требуется задавать, поскольку он определяется компилятором при инициализации массива.

В строке [4] создаётся дополнительный временный массив, что нарушает дополнительные условия в постановке задачи.

Выход за пределы массива

Типичный пример:

1
2

for (int i=0; i < n; ++i)
  arr[i]=arr[i+1];

При размере массива в n элементов, нумерация элементов массива начинается с нуля и заканчивается элементом с индексом n-1. В данном случае в последней итерации цикла значение i будет равно n-1, а значение индекса i+1 будет, соответственно, равно n. В результате программа обратится за пределы массива, что недопустимо.

Были и скрытые случаи выхода за пределы массива, связанные с неправильными проверками:

1
2
3
4
5
6

for (int i=0; i < n; i++) {
  if ( n-k+i < n )
    swap(arr[i],arr[n-k+i]);

  if ( k+i < n )
    swap(arr[k+i],arr[n-k+i]);

Не говоря о том, что здесь неправилен алгоритм, в пятой строке производится обращение к элементу массива, но при этом никто не гарантирует, что n-k+i будет меньше n. В пятой строке проверяется совершенно другое условие.

И ещё один прекрасный утончённый случай:

1
…
4
5
6

for (int i=0; i < n; ++i) {
…
if ( i+k != n ) {
  int temp;
  temp = arr[i+k];

Да, n-ого элемента в массиве не существует и к нему нельзя обращаться. Но это не значит, что можно обращаться к элементу n+1. Это достаточно типичная ошибка для начинающих: точная проверка индекса на равенство граничному значению тогда, когда необходимо использовать неравенство. В данном случае код должен был выглядеть следующим образом:

1

…
4
5
6

for (int i=0; i < n; ++i) {
  temp = arr[i+k];
…
  if ( i+k < n ) {
   int temp;
   temp = arr[i+k];

Потеря элемента

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

Пример:

1
2 

for (int i=0; i < n; ++i) {
 arr[i+k]=arr[k];

Здесь сразу две ошибки: выход за пределы массива по i+k и потеря значения, хранившегося в элементе arr[k]. При первой итерации i=0 следовательно первое обращение будет к элементу arr[k], которое будет перезаписано и восстановить которое уже никогда не удастся. Дальнейший код можно не изучать.

Использование ключевых слов языка в качестве идентификаторов

Ключевые слова языка С++ не могут использоваться в качестве идентификаторов.

Пример:

1 

void return(int arr[], int n) {

В данном случае return является ключевым словом языка С++ и его нельзя использовать как имя функции.

Неправильное определение размера массива, переданного как аргумент функции

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

1
2

void shift(int arr[], int k) {
  int n = sizeof(arr)/sizeof(arr[0]);

В данном случае arr уже рассматривается как указатель. С тем лишь отличием, что синтаксическое его описание не позволяет его (сам указатель) изменять. В данном случае sizeof(arr) возвращает размер указателя на int, а не размер массива.

Выход: размер массива необходимо передавать явно в качестве аргумента функции shift:

1 

void shift(int arr[], int n, int k) {

Неправильное продвижение индекса массива

Полагаю, что это в большей степени невнимательность автора:

1 

for (int i=1; i < n; --i)

Поскольку значение i уменьшается, то цикл имеет мало шансов быстро закончиться, что, видимо, не входило в планы автора.

Алгоритмические ошибки

Наиболее типичной алгоритмической ошибкой является ситуация, когда автор пытается пересылать значения сразу на дистанцию k в массиве. Это один из правильных методов, но в случае, когда n кратно k есть опасность «зацикливания». Например, в массиве из 8-ми элементов при сдвиге на четыре элемента пересылки будут происходить между нулевым и четвёртым элементом.

В отсутствии комментариев сложно понять, что именно автор хотел выразить написанным алгоритмом, поэтому полный анализ неправильных алгоритмов затруднён. Я лишь покажу, какие ошибки позволяют показать, что программа не будет выполняться правильно и почему.

1
2
3 

for (int i=n-k; i < n; i++)
  for (int i=0, int j=n-k; j < n; i++,j++)
    swap(arr[i],arr[j]);

Если посмотреть внимательно на приведённый код – становится ясно, что при k=1 произойдёт лишь один вызов функции swap, чего явно недостаточно для сдвига массива из n элементов даже на одну позицию.

Правильная программа

Простейший (наиболее понятный) вариант написания программы выглядит следующим образом:

1
2
3
4
5
6
7
8 

void rotate_right(int arr[], int n, int k) {
  for (int i=0; i < k; ++i) {
     int temp=arr[n-1];
     for (int j=n-1; j > 0; --j)
      arr[j] = arr[j-1];
    arr[0]=temp;
  }
}

Такого текста было бы достаточно на «летучке» для получения максимальной оценки.

Здесь есть, несколько моментов, которые можно улучшить.

Можно явно указать, что размер и величина сдвига должны быть положительными:

1

void rotate_right(int arr[], unsigned int n, unsigned int k) {

Впрочем, я лично считаю эту меру излишней. Наиболее красиво, пожалуй, будет выглядеть:

1

void rotate_right(int arr[], size_t n, size_t k) {

Однако, для использования типа size_t придётся подключать файл stdio.h, поскольку этот тип не является встроенным в язык. Для маленького фрагмента кода это существенно. В большой программе я поступил бы именно так.

Можно убедиться, что величина сдвига не превышает размер массива. Если величина сдвига больше размера массива – получается лишний круг, который проходят значения. Такие «холостые» прогоны желательно исключить. Всё это сложное объяснение выражается простой строкой:

2

k%=n;

То есть остаётся только величина сдвига, не кратная размеру массива. Маловероятно, что кто-то будет вызывать функцию с таким значением k, но такая небольшая проверка может порой быть весьма эффективной. К тому же всегда лучше проверять это в функции, чем на стороне клиентской части.

Дополнительно можно проверить, что массив имеет хотя бы один элемент. В случае пустого массива в строке [3] мы сразу получим обращение за начало массива, что недопустимо.

Это можно сделать в отдельном операторе if:

3

if ( n < 1 ) return;

что просто, наглядно и понятно читающему.

Таким образом, после простейших улучшений получаем:

1
2
3
4
5
6
7
8
9
10

void rotate_right(int arr[], unsigned int n, unsigned int k) {
  k%=n;
  if ( n < 1 ) return;
  for (int i=0; i < k && n >= 1; ++i) {
    int temp=arr[n-1];
    for (int j=n-1; j > 0; --j)
      arr[j] = arr[j-1];
    arr[0]=temp;
  }
}

Любители оптимизации могут избавиться от явно лишней переменной:

1
2
3
4
5
6
7
8
9
10

void rotate_right(int arr[], unsigned int n, unsigned int k) {
   k%=n;
   if ( n < 1 ) return;
   for ( ; k > 0; --k) {
     int temp=arr[n-1];
     for (int j=n-1; j > 0; --j)
       arr[j] = arr[j-1];
     arr[0]=temp;
   }
}

После всех оптимизаций алгоритм достаточно хорош, однако обладает одним принципиальным недостатком – количество пересылок, необходимых для решения задачи пропорционально n*k. В случае достаточно больших величин n и k, выполнение программы может быть достаточно долгим. При этом интуитивно ясно, что число пересылок не должно зависеть от величины сдвига – ведь переслать надо n элементов. А расстояние пересылки не должно в хорошем алгоритме влиять на число пересылок и время выполнения.

Наиболее красивое известное мне решение приводится в книге Дж.Бентли «Жемчужины программирования» (стр. 32-33).

1
2
3
4
5
6
7
8
9
10
11
12

// Вспомогательная функция – разворот массива
void reverse(int arr[], int n){
  for (int i=0; i < n/2; ++i )
    swap(arr[i],arr[n-i-1]);
}

void rotate_right(int arr[], int n, int k) {
  k%=n;
  reverse(arr,k);     // Разворот левой части массива
  reverse(arr+k,n-k); // Разворот правой части массива
  reverse(arr,n);     // Разворот всего массива
}

На лекции я показывал, почему данный алгоритм работает. Если по лекционному материалу это непонятно – отсылаю к указанной выше книге. Там все прекрасно изложено.

В данном случае мы получаем время работы алгоритма, пропорциональное числу элементов массива n.

Отсюда можно сделать следующие выводы:

Что подтверждает одно из основных правил:

Правило

Дата последнего обновления 2007 год