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
  • Я тоже думал об этом варианте, теперь убедился что он подходит. И ещё, ваш вариант, для сдвига против часовой стрелки) 26 окт 2014 в 8:32
  • могу ошибаться но матрицу вроде можно вращать умножением ru.wikipedia.org/wiki/…
    – perfect
    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
    26 окт 2014 в 12:39
0

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

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

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