Выведите заданную матрицу в виде спирали, разделив матрицу на циклы
жүктеу/скачать 73,49 Kb.
|
- Бұл бет үшін навигация:
- Вывод 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 Временная сложность
| Вывод
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 Или с применением функции #include using namespace std; #define R 4 #define C 4 void spiralPrint(int m, int n, int a[R][C]) { int i, k = 0, l = 0; /* k - starting row index m - ending row index l - starting column index n - ending column index i - iterator */ while (k < m && l < n) { /* Print the first row from the remaining rows */ for (i = l; i < n; ++i) { cout << a[k][i] << " "; } k++; /* Print the last column from the remaining columns */ for (i = k; i < m; ++i) { cout << a[i][n - 1] << " "; } n--; /* Print the last row from the remaining rows */ if (k < m) { for (i = n - 1; i >= l; --i) { cout << a[m - 1][i] << " "; } m--; } /* Print the first column from the remaining columns */ if (l < n) { for (i = m - 1; i >= k; --i) { cout << a[i][l] << " "; } l++; } } } /* Driver Code */ int main() { int a[R][C] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; // Function Call spiralPrint(R, C, a); return 0; } // This is code is contributed by rathbhupendra Вывод 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 Временная сложность: O (M * N). Для обхода матрицы требуется O (M* M) времени. Дополнительный пробел: O(1). Дополнительный пробел не требуется. Выведите заданную матрицу по спирали, используя рекурсию:Чтобы решить проблему, следуйте приведенной ниже идее: Вышеуказанную проблему можно решить, рекурсивно распечатав границу матрицы. При каждом рекурсивном вызове мы уменьшаем размеры матрицы. Идея печати границы или циклов та же Следуйте приведенным шагам для решения проблемы: создайте рекурсивную функцию, которая принимает матрицу и некоторые переменные (k – индекс начальной строки, m – индекс конечной строки, l – индекс начального столбца, n – индекс конечного столбца) в качестве параметров Проверьте базовые варианты (начальный индекс меньше или равен конечному индексу) и выведите граничные элементы по часовой стрелке Выведите верхнюю строку, т.е. выведите элементы k-й строки из столбца с индексом l в n и увеличьте количество k Выведите правый столбец, т.е. Выведите последний столбец или n-й столбец от индекса строки k до m и уменьшите количество на n Выведите нижнюю строку, т. е. если k > m, затем выведите элементы m-1-й строки из столбца n-1 в l и уменьшите количество m Выведите левый столбец, т.е. если l < n, то выведите элементы l-го столбца из m-1-й строки в k и увеличьте количество l Вызовите функцию рекурсивно со значениями начального и конечного индексов строк и столбцов Ниже приведена реализация вышеупомянутого подхода: // C++. program for the above approach #include using namespace std; #define R 4 #define C 4 // Function for printing matrix in spiral // form i, j: Start index of matrix, row // and column respectively m, n: End index // of matrix row and column respectively void print(int arr[R][C], int i, int j, int m, int n) { // If i or j lies outside the matrix if (i >= m or j >= n) return; // Print First Row for (int p = j; p < n; p++) cout << arr[i][p] << " "; // Print Last Column for (int p = i + 1; p < m; p++) cout << arr[p][n - 1] << " "; // Print Last Row, if Last and // First Row are not same if ((m - 1) != i) for (int p = n - 2; p >= j; p--) cout << arr[m - 1][p] << " "; // Print First Column, if Last and // First Column are not same if ((n - 1) != j) for (int p = m - 2; p > i; p--) cout << arr[p][j] << " "; print(arr, i + 1, j + 1, m - 1, n - 1); } // Driver Code int main() { int a[R][C] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; // Function Call print(a, 0, 0, R, C); return 0; } // This Code is contributed by Ankur Goel жүктеу/скачать 73,49 Kb. Достарыңызбен бөлісу:
|