Поворот изображения

Опубликовано Sep 30, 2011 в Массивы и строки | 4 коммент.

, , ,

Поворот изображения

Предположим, некоторая система хранит квадратные картинки в виде двумерных массивов n*n с элементами размером в 4 байта. Необходимо разработать метод rotate поворота изображения на 90 градусов. Попробуйте реализовать алгоритм, которому не требуется выделение дополнительной памяти.

void rotate(int** matrix, const int n)
{
 //ваш код
}
1 Цель задания быстрая проверка простых навыков алгоритмического мышления
2 Время выполнения 10 минут
3 Формат выполнения код пишется на листике, без доступа к документации

Критерии оценки FulcrumWeb:

Кандидат должен продемонстрировать умение реализовывать элементарные алгоритмы и заботу об эффективности реализации. В приведенной сигнатуре метода содержится подсказка, что 4 байта – это как раз тип данных int в 32-разрядной ОС.

Ожидаемые вопросы:

  1. Поворачивать по часовой стрелке или против?

Оценка результатов:

Вопрос можно не задавать, а какой-то из двух вариантов выбрать по своему усмотрению, так как от ответа на него суть алгоритма не меняется. От начинающих программистов ожидается, как минимум, реализация с выделением дополнительной памяти.

 

Программисты с опытом должны найти оптимальное решение.


4 Коммент. : “Поворот изображения”

  1. Без выделения дополнительной памяти решить задачу оказалось непросто. Самостоятельно додумался лишь до такого решения:

    void Rotate90(int** matrix, const int n)
    {
    	int tmp;
    	for (int i = 0; i < n; i++)
    	{
    		for (int j = 0; j <= i; j++) 
    		{ 
    			tmp = matrix[i][j]; 
    			matrix[i][j] = matrix[j][i]; 
    			matrix[j][i] = tmp;
    		}
    	}
    	// transposed the matrix
    	for(int i = 0; i < n; i++)
    	{
    		for(int j = 0; j < n/2; j++)
    		{
    			tmp = matrix[i][j];
    			matrix[i][j] = matrix[i][n-j-1];
    			matrix[i][n-j-1] = tmp;
    		}
    	}
    	// made the reverse of each string of the matrix
    }

    Однако хотелось реализовать более эффективно, без дополнительного реверса строк. Самостоятельно так и не смог этого сделать. На stackoverflow подсказали такое решение:

    void Rotate90(int** matrix, const int n)
    {
    	int tmp;
    	for (int i = 0; i < (n / 2 + n % 2); i++) { 
    		for (int j = 0; j < n / 2; j++) { 
    			tmp = matrix[i][j]; 
    			matrix[i][j] = matrix[n - j - 1][i]; 
    			matrix[n-1 - j][i] = matrix[n-1 - i][n-1 - j]; 
    			matrix[n-1 - i][n-1 - j] = matrix[j][n-1 - i]; 
    			matrix[j][n-1 - i] = tmp; 
    		} 
    	}
    }
    • Галина says:

      Задача известная, решение ее конечно найти можно. Вот, например, еще вариант по сложности (количеству выполнений тела внутреннего цикла) такой же, как и на stackoverflow.

       
      int rotate90_best(int** matrix, const int n) 
      {
        int cicleCount = 0; 
       
        for (int layer = 0; layer < n / 2; ++layer) 
        {
          int first = layer;
           int last = n - 1 - layer;
           for(int i = first; i < last; ++i) 
           {
             int offset = i - first;
             int top = matrix[first][i];//save top
             // left -> top
             matrix[first][i] = matrix[last-offset][first];
       
             // bottom -> left
             matrix[last-offset][first] = 
                                 matrix[last][last - offset];
       
      	// right -> bottom
      	matrix[last][last - offset] = matrix[i][last];
       
      	// top -> right
      	matrix[i][last] = top; // right <- saved top
       
      	cicleCount++;
      	}
        }
        return cicleCount;
      }

      cicleCount считает количество итераций.

  2. Артур says:
    void rotateAr(int** mt, const int n){
    	int tmp;
    	for(int t = 0; t < (n/2); t++){
    		for(int i = t; i < n - 1 - t; i++){
    			tmp = mt[n-1-i][t];			
    			mt[n-1-i][t] = mt[t][i];    
    			mt[t][i] = mt[n-1-t][n-1-i];
    			mt[n-1-t][n-1-i] = tmp;     
    			tmp = mt[i][n-1-t];			
    			mt[i][n-1-t] = mt[t][i];	
    			mt[t][i] = tmp;				
    		}
    	}
    }
  3. Артур says:

    Или так

    void rotateAr(int** mt, const int n){
    	for(int t = 0; t < (n/2); t++){
    		for(int i = t; i < n - 1 - t; i++){
    			swap(mt[n-1-i][t],mt[t][i]);
    			swap(mt[t][i],mt[i][n-1-t]);
    			swap(mt[i][n-1-t],mt[n-1-t][n-1-i]);
    		}
    	}
    }

Оставить комментарий

Ваш адрес email не будет опубликован.


*