@avion123678

Алгоритм поворота динамического массива без доп памяти?

Здравствуйте, какой существует алгоритм для поворота матрицы разной размерности на 90 по и против часовой стрелки. С доп памятью задача тривиальна, но вот без, так еще и разной размерности ...
Имеется динамический массив размерности m x n.
Данный код, работает для размерности n x n:
int tmp;
 for(int i=0;i<n/2;i++)
 {
 for(int j=i;j<n-1-i;j++)
 {
 tmp = matr[i][j];
 matr[i][j] = matr[n-j-1][i];
 matr[n-j-1][i] = matr[n-i-1][n-j-1];
 matr[n-i-1][n-j-1] = matr[j][n-i-1];
 matr[j][n-i-1] = tmp;
 }
 }
}

Как можно реализовать, поворот динамического массива (матрица), без доп памяти?
  • Вопрос задан
  • 147 просмотров
Пригласить эксперта
Ответы на вопрос 4
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Свап ячеек через сумму и вычитание.
Ответ написан
jcmvbkbc
@jcmvbkbc
http://dilbert.com/strip/1998-08-24
Как можно реализовать, поворот динамического массива (матрица), без доп памяти?

Как-то так:

#include <stddef.h>
#include <stdio.h>

typedef int T;

void rotate(T *p, size_t m, size_t n, size_t (*turn)(size_t m, size_t n, size_t idx))
{
        size_t i, j, k;

        for (i = 0; i < m * n; ++i) {
                T tmp0, tmp1;

                for (j = 0; j < i; ++j) {
                        for (k = turn(m, n, j); k != i && k != j; k = turn(m, n, k)) {
                        }
                        if (k == i)
                                break;
                }
                if (j < i)
                        continue;

                tmp0 = p[i];
                for (j = turn(m, n, i); ; j = turn(m, n, j)) {
                        tmp1 = p[j];
                        p[j] = tmp0;
                        tmp0 = tmp1;
                        if (j == i)
                                break;
                }
        }
}

void dump(size_t m, size_t n, T p[m][n])
{
        size_t i, j;

        for (i = 0; i < m; ++i)
                for (j = 0; j < n; ++j)
                        printf("%d%s", p[i][j], j == n - 1 ? "\n" : ", ");
}

size_t turn_ccw(size_t m, size_t n, size_t idx)
{
        return (n - 1 - idx % n) * m + (idx / n);
}

size_t turn_cw(size_t m, size_t n, size_t idx)
{
        return (idx % n) * m + m - 1 - (idx / n);
}

#define M 5
#define N 7

int main()
{
        size_t i, j;
        T a[M][N];

        for (i = 0; i < M; ++i)
                for (j = 0; j < N; ++j)
                        a[i][j] = i * N + j;

        rotate(&a[0][0], M, N, turn_ccw);
        dump(N, M, (T (*)[M])&a[0][0]);
        printf("\n");
        rotate(&a[0][0], N, M, turn_cw);
        dump(M, N, (T (*)[N])&a[0][0]);
}


turn преобразует линейный индекс элемента из оригинального массива в индекс элемента в повёрнутом массиве.
Цикл по i переставляет цепочки элементов отображающихся друг в друга с началом в элементе i. Первый цикл по j проверяет, не был ли элемент i уже переставлен в составе более ранней цепочки. Второй цикл по j переставляет одну цепочку.
Ответ написан
maaGames
@maaGames
Погроммирую программы
В первую очередь рассмотреть вариант сохранения флага "транспонированная матрица" и учёт этого флага в алгоритмах. Причём, это ускорит работу ДВАЖДЫ, т.к. обход по столбцу транспонированной матрицы физически оказывается обходом по строке, что положительно сказывается на кэшировании данных матрицы.
Ответ написан
@mayton2019
Ent. Software engineer.
Можно эту прямоугольную "колбасу" вообще не поворачивать. А хранить вектор повернутости. И перегрузить оператор индекса чтобы доступ вел себя по правилам аффинных преобразований.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
FunBox Томск
от 120 000 ₽
FunBox Екатеринбург
от 120 000 ₽
FunBox Санкт-Петербург
от 120 000 ₽