Автор Тема: Завъртане на NxN матрица с 90° - имплементация  (Прочетена 1023 пъти)

!ntel

  • Участник
  • *****
  • Публикации: 444
    • Профил
Днес се хванах да ровя за имплементация решаваща проблема със завъртане на NxN матрица с 90°
Питах чичо Гошо, но намерих само два вида решения - чрез xor или чрез временна променлива.
Понеже знаем, че алгоритъма решаващ това In-place_matrix_transposition#Square_matrices е доста неприятен за кеша на процесорите, а и най-добрия случай е big O(n²).
Та се питах дали няма някакъв, така да се каже, логаритмичен начин за решаване на този проблем?
Ако сте запознати с някаква имплементация от рода на разделяне на проблема на две при всяка стъпка, моля да го споделите.

ПС: Намерих нещо елегантно, но все още се чудя дали няма нещо по-добро:

Код
GeSHi (C):
  1.    int tmp, l;
  2.    for(int i = 0; i < M_SIZE/2; i++)
  3.    {
  4.        for(int j = i, k = M_SIZE - i - 1; j < k; j++)
  5.        {
  6.            tmp = m[i][j];
  7.            l = M_SIZE - j - 1;
  8.  
  9.            m[i][j] = m[l][i];
  10.            m[l][i] = m[k][l];
  11.            m[k][l] = m[j][k];
  12.            m[j][k] = tmp;
  13.        }
  14.    }
« Последна редакция: Мар 20, 2013, 00:52 от !ntel »
Активен

arda_kj

  • Участник
  • *****
  • Публикации: 631
  • Distribution: Debian Sid/Unstable; Ubuntu 12.04
  • Window Manager: Gnome/KDE
    • Профил
Най-елегантния метод е да не транспонираш нищо. Просто маркираш матрицата като транспонирана и когато достъпваш съответния елемент разменяш индексите.

Пример:

Код:
вместо m[i][j] взимаш m[j][i]

Аз по елегантно и бързо от това не мога да измисля. Естествено всяко предимство си има недостатъци - в случая трябва да помниш, че трябва да разменяш индексите, когато достъпиш транспонираната матрица. Предимство е очевадно - няма никакви излишни операции, а оттам бързодействието е максимално.

Ако наистина искаш реално да транспонираш матрицата, просто правейки си някакви тестове, тогава това, което предложих не е за теб.
Активен

Debian Sid/Unstable; Ubuntu 12.04
"За да открием истината, е нужно поне веднъж в живота си да подложим всичко на съмнение" - Р. Декарт

zxz

  • Участник
  • *****
  • Публикации: 614
  • Distribution: Linux Mint 18.2
  • Window Manager: XFCE
    • Профил
Е то с два цикъла може да презапише самата матрица със "вместо m[j] взимаш m[j]". По интересно е да я завъртиш на 45 градуса  :D ;)
Активен