Закручивающаяся спираль
Раскручивающаяся спираль есть вот здесь, теперь оставлю заметку о закручивающейся, как памятку о не прошедшей тесты по времени задаче.
Требуется, начав с левого верхнего угла и двигаясь по часовой стрелке вправо, вывести элементы, например, для данных
1 2 3 4 5 6 7 8 9 10 11 12
вывод будет в порядке
1 2 3 4 8 12 11 10 9 5 6 7
Вот вариант с обычными итерациями:
#include <iostream> using namespace std; void spiralPrint(int m, int n, int **a) { int i, k = 0, l = 0; // начать с элемента [k][l] while (k < m && l < n) { for (i = l; i < n; ++i) cout << a[k][i] << endl; k++; for (i = k; i < m; ++i) cout << a[i][n - 1] << endl; n--; if (k < m) { for (i = n - 1; i >= l; --i) cout << a[m - 1][i] << endl; m--; } if (l < n) { for (i = m - 1; i >= k; --i) cout << a[i][l] << endl; l++; } } } int main() { const int R = 3, C = 4; //строк и столбцов int** a = new int* [R]; int k = 1; for (int i = 0; i < R; i++) { //формирование матрицы a[i] = new int[C]; for (int j = 0; j < C; j++) a[i][j] = k++; } spiralPrint(R, C, a); //обработка cin.get(); return 0; }
Ввод здесь просто формированием матрицы матрицы по правилу, с чтением из файла или с консоли не заморачивался.
Либо, как всегда, итерации можно заменить рекурсией, вариант 2:
#include <iostream> using namespace std; void spiralPrint (int **arr, int i, int j, int m, int n) { if (i >= m or j >= n) return; //не лезь за матрицу, там нет синей таблетки for (int p = i; p < n; p++) cout << arr[i][p] << endl; //строка 1 for (int p = i + 1; p < m; p++) cout << arr[p][n - 1] << endl; //последний столбец if ((m - 1) != i)for (int p = n - 2; p >= j; p--) cout << arr[m - 1][p] << endl; //если последняя строка не подобна первой... if ((n - 1) != j) for (int p = m - 2; p > i; p--) cout << arr[p][j] << endl; //и столбец первый не станет последним... spiralPrint (arr, i + 1, j + 1, m - 1, n - 1); //то вызови себя, и постигни истину } int main() { const int R = 3, C = 4; //строк и столбцов int** a = new int* [R]; int k = 1; for (int i = 0; i < R; i++) { //формирование матрицы a[i] = new int[C]; for (int j = 0; j < C; j++) a[i][j] = k++; } spiralPrint (a, 0, 0, R, C); cin.get(); return 0; }
Это приятней, но потенциально памяти съест больше. Возможно, это даже O(n*m)
по времени. Запускал в консоли Visual Studio 2019. А как сделать экономичней?
Ясно, что искать надо в направлении жадных алгоритмов, но они потому и жадные, что решений в общем виде не гарантируют.
16.06.2020, 15:51 [1304 просмотра]