0

Нужно сдвинуть элементы двумерного массива, на k элементов по часовой стрелке (С++).

1  1  1  1  
2  2  2  2  
3  3  3  3  
4  4  4  4 

Допустим, на k = 2, тогда:

3  2  1  1   
4  3  3  1   
4  2  2  1    
4  4  3  2  

Вопрос: можно ли здесь использовать дополнительный массив такого же размера, чтобы в него записывать уже перемещённые элементы?

С дополнительным массивом я уже сделал, но есть подозрение, что это лишнее, и что можно обойтись парой переменных без второго массива. Или, всё же, то, что есть дополнительный массив — нормально?

2 ответа 2

4

По идее, достаточно одной дополнительной переменной.

Для каждого цикла вы запоминаете первый элемент в эту переменную, затем копируете второй в первый, третий во второй и так далее, на место последнего записываете сохранённый первый.

3
  • Я тоже думал об этом варианте, теперь убедился что он подходит. И ещё, ваш вариант, для сдвига против часовой стрелки) Commented 26 окт. 2014 в 8:32
  • могу ошибаться но матрицу вроде можно вращать умножением ru.wikipedia.org/wiki/…
    – perfect
    Commented 26 окт. 2014 в 12:16
  • 1
    @perfect: Нет, умножением реализовать вращение невозможно. Доказательство: При умножении матриц ранг не повышается (т. к. линейное преобразование не может поднять размерность линейной оболочки). Поворот же поднять ранг может. Пример: 0 1 11 0 0 1 0 2 12 -> 0 2 11 0 3 13 3 13 12 Ранг первой матрицы 2, а второй — 3, т. к. у ней ненулевой детерминант.
    – VladD
    Commented 26 окт. 2014 в 12:39
0

Сдвиг такого двумерного массива можно рассматривать как циклический сдвиг двух линейных последовательностей, образованных концентрическими "кольцами" в таком массиве. Алгоритмов циклического сдвига линейного массива без использования дополнительного массива - вагон и маленькая тележка. Не составит никакого труда "спроецировать" выполняемые такими алгоритмами перестановки прямо на "кольца" вашей матрицы, т.е. выполнить из прямо в вашей матрице.

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

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.