Алгоритм спирального заполнения массива
Задача:
Заполнить квадратную матрицу произвольного размера элементами, которые вводит пользователь. Заполнение должно производится по спирали, слева — направо — сверху — вниз.
Для реализации данной задачи использовать язык программирования Java.
Начнем с вопроса о том, чем вообще является массив данных.
В любом языке программирования используются массивы, удобные для работы с большим количеством однотипных данных. Если вам нужно обработать сотни переменных, то вызывать каждую по отдельности становится достаточно трудоемким занятием. В таких случаях проще применить массив. Массивы в Java, как и во многих других языках программирования, обозначаются квадратными скобками. Эти скобки могут располагаться справа от имени массива или от типа объектов, из которых составлен массив.
Рассмотрим пример квадратной матрицы (квадратная таблица, состоящая из строк и столбцов на пересечении которых находятся её элементы). Количество строк и столбцов матрицы задают ее размер. Общий вид матрицы размером n x n ( n — количество строк, количество столбцов), выглядит следующим образом:
Каждый элемент матрицы имеет свой индекс, где первая цифра обозначает номер строки на которой находится элемент, а вторая — номер столбца.
В задачах по программированию очень часто встречается необходимость заполнить массив данными и вывести их потом на экран. В первоначальной задаче необходимо заполнить массив следующим образом: начиная с правого верхнего угла, двигаясь по спирали присвоить каждому элементу массива значение, которое ввел пользователь.
Схематически это выглядит так:
То есть, в каждом "квадрате" матрицы нам нужно проходить 4 шага, заполняя 4 стороны "квадрата".
Создадим класс, в котором реализуем 2 метода: само заполнение матрицы и ее вывод. Объявим переменную, в которой будет содержаться количество строк(столбцов) матрицы.
Займемся написанием кода метода заполнения матрицы. Он должен возвращать массив String. Объявление метода будет выглядеть следующим образом:
По мере прохождения сторон "квадрата" мы проходим 4 итерации, в ходе которых проходим N элементов нашего массива. Это повторяется, пока не закончатся "квадраты", то есть N/2 (при этом, если N нечетное, то округление должно производиться в большую сторону) раз. Следовательно, можно выделить 3 цикла:
При условии того, что:
Так как N была объявлена как финальная переменная и не может быть изменена.
Теперь, в зависимости от номера итерации (стороны "квадрата"), нужно определять индексы элемента массива для записи. Введем дополнительную переменную типа int, которая будет увеличиваться с каждым пройденным "квадратом". Создадим объект класса Scanner, подключив нужную библиотеку.
Сейчас код выглядит так:
Все индексы посчитаны, осталось написать метод для вывода матрицы. Для упрощения воспользуемся стандартным методом для вывода одномерного массива. Для этого подключим требуемую библиотеку:
Код данного метода будет выглядеть следующим образом:
Он принимает массив String и выводит в консоль по каждой строке все элементы массива, ничего не возвращая.
Теперь осталось только использовать данный класс и испытать его методы. Для этого создадим главный класс, в котором объявим переменную типа int для хранения размера массива,который задаст пользователь и считаем ее.
Создадим объект класса FillMatrix и вызовем созданные методы. Полностью код главного класса выглядит так:
Заполнение двумерной матрицы по спирали
На днях встретил простую на вид задачу. Как оказалось, не легко решить такую задачу за пять, и даже за 50 минут. Здесь пришлось подумать и поэкспериментировать.
Дана матрица, или, на нашем языке, двумерный массив. Его размеры не могут превышать 10х10. Они задаются пользователем и это может быть не только квадрат, но и прямоугольник. Обозначим длины сторон через N и M. Нам необходимо заполнить эту матрицу числами от 1 и по возрастающей до M*N. Прежде, чем привести код целиком, мне хотелось бы изложить ход мыслей, чтобы стало понятно как все работает. Если же тебе просто нужно решение, то ты можешь пролистать ниже, скопировать его и закрыть страницу как больше не нужную.
Стандартно, нам нужен сам массив и переменные для хранения длин сторон прямоугольного (двумерного) массива.
Также мы будем действовать по слогике, что при заполнении мы очерчиваем прямоугольники, каждый их которых на единицу меньше с каждой стороны. Если смотреть на эти прямоугольники в декартовой системе координат, то начало каждой из сторон сдвигается на 1 вправо или вниз, а конец влево или вверх. Договоримся, что оси направлены вправо и вниз от точки [0,0].
Таким образом нам нужно знать точки начала и конца очерчиваемого прямоугольника. Это и будут точки излома (поворота). Но я еще и решил пойти следующим путем. Точки конца сторон будут равняться длине стороны первого прямоугольника минус длине текущего прямоугольника.
Обозначим их следующим образом:
Ну, и, нам нужна переменная, значением которой мы будем заполнять массив, пока она не достигнет значения M*N
В цикле начинаем заполнять массив. Сначала точке a[i][j] присваиваем значение k. Это удобно тем, что если длина сторон равна 0, то мы не войдем в массив. Иначе в точку a[i][j] положим значение k, в конце же цикла инкреминируем его.
Далее вычисляем следующий шаг
- Если у нас верхняя сторона прямоугольника и мы не достигла правой стороны, то двигаемся вправо: ++j
- Если мы на правой стороне прямоугольника и не достигли нижней стороны, то двигаемся вниз: ++i
- Если мы на нижней стороне прямоугольника и не достигли левой стороны, то двигаемся влево: —j
- Иначе двигаемся вверх: —i
В конце же каждого прохода проверяем, завершился ли прямоугольник и стои ли начинать прочерчивать новый — меньший:
- Если мы находимся на второй строке
- Если мы находимся на первом столбце
- И, в случае, если чертим не прямоугльник, а вертикальную линию, если первая строка не равна последней. (этот пункт самый сложный во всем алгоритме. Его я достиг путем экспериментов)
Тогда увеличиваем отступы от краев первого прямоугольника:
Собственно это весь алгоритм. А ниже код всей программы:
Я видел более изящные решения данной задачи, наполненные математикой и побитовыми операциями. Но для понимания того, как последовательно наполняется пассив по спирали, достаточно данного алгоритма. Буду рад, если вы оставите в комментариях свои решения и поделитесь мыслями.
Круговая матрица (Построить матрицу с номерами от 1 до m * n по спирали)
Учитывая два значения m и n, заполните матрицу размера 'm * n' по спирали (или по кругу) (по часовой стрелке) натуральными числами от 1 до m * n.
Примеры:
Идея основана на печати заданной матрицы в виде спирали . Мы создаем матрицу размером m * n и пересекаем ее по спирали. При обходе мы отслеживаем переменную «val» для заполнения следующего значения, увеличиваем «val» по одному и помещаем ее значения в матрицу.
// C ++ программа для заполнения матрицы значениями из
// 1 к n * n по спирали.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
// Заполняет [m] [n] значениями от 1 до m * n в
// спиральная мода.
void spiralFill( int m, int n, int a[][MAX])
// Инициализировать значение для заполнения в матрице
/ * k — начальный индекс строки
m — индекс конца строки
l — начальный индекс столбца
n — индекс конечного столбца * /
/ * Вывести первый ряд из оставшихся
for ( int i = l; i < n; ++i)
/ * Распечатать последний столбец из оставшихся
for ( int i = k; i < m; ++i)
/ * Распечатать последний ряд из оставшихся
for ( int i = n-1; i >= l; —i)
/ * Распечатать первый столбец из оставшихся
for ( int i = m-1; i >= k; —i)
/ * Программа драйвера для проверки вышеуказанных функций * /
spiralFill(m, n, a);
for ( int i=0; i<m; i++)
for ( int j=0; j<n; j++)
// Java-программа для заполнения матрицы значениями из
// 1 к n * n по спирали.
static int MAX = 100 ;
// Заполняет [m] [n] значениями от 1 до m * n в
// спиральная мода.
static void spiralFill( int m, int n, int a[][]) <
// Инициализировать значение для заполнения в матрице
/ * k — начальный индекс строки
m — индекс конца строки
l — начальный индекс столбца
n — индекс конечного столбца * /
/ * Вывести первый ряд из оставшихся
for ( int i = l; i < n; ++i) <
/ * Распечатать последний столбец из оставшихся
for ( int i = k; i < m; ++i) <
/ * Распечатать последний ряд из оставшихся
for ( int i = n — 1 ; i >= l; —i) <
/ * Распечатать первый столбец из оставшихся
for ( int i = m — 1 ; i >= k; —i) <
/ * Программа драйвера для проверки вышеуказанных функций * /
public static void main(String[] args) <
int a[][] = new int [MAX][MAX];
spiralFill(m, n, a);
for ( int i = 0 ; i < m; i++) <
for ( int j = 0 ; j < n; j++) <
/ * Этот код Java предоставлен PrinciRaj1992 * /
// C # программа для заполнения матрицы значениями из
// 1 к n * n по спирали.
static int MAX = 100;
// Заполняет [m, n] значениями от 1 до m * n в
// спиральная мода.
static void spiralFill( int m, int n, int [,] a) <
// Инициализировать значение для заполнения в матрице
/ * k — начальный индекс строки
m — индекс конца строки
l — начальный индекс столбца
n — индекс конечного столбца * /
/ * Вывести первый ряд из оставшихся
for ( int i = l; i < n; ++i) <
/ * Распечатать последний столбец из оставшихся
for ( int i = k; i < m; ++i) <
/ * Распечатать последний ряд из оставшихся
for ( int i = n — 1; i >= l; —i) <
/ * Распечатать первый столбец из оставшихся
for ( int i = m — 1; i >= k; —i) <
/ * Программа драйвера для проверки вышеуказанных функций * /
public static void Main() <
int [,] a = new int [MAX,MAX];
spiralFill(m, n, a);
for ( int i = 0; i < m; i++) <
for ( int j = 0; j < n; j++) <
<?php
// PHP-программа для заполнения матрицы значениями
// от 1 до n * n по спирали.
// Заполняет [m] [n] значениями от 1 до
// m * n по спирали.
function spiralFill( $m , $n , & $a )
// Инициализировать значение для заполнения
/ * k — начальный индекс строки
m — индекс конца строки
l — начальный индекс столбца
n — индекс конечного столбца * /
/ * Вывести первый ряд из
for ( $i = $l ; $i < $n ; ++ $i )
/ * Распечатать последний столбец из
for ( $i = $k ; $i < $m ; ++ $i )
$a [ $i ][ $n — 1] = $val ++;
/ * Вывести последний ряд из
for ( $i = $n — 1; $i >= $l ; — $i )
$a [ $m — 1][ $i ] = $val ++;
/ * Вывести первый столбец из
for ( $i = $m — 1; $i >= $k ; — $i )
spiralFill( $m , $n , $a );
for ( $i = 0; $i < $m ; $i ++)
for ( $j = 0; $j < $n ; $j ++)
// Этот код добавлен
// от Shivi_Aggarwal
?>
Выход:
Временная сложность: O (m * n)
Пространственная сложность: O (m * n)
Эта статья предоставлена Аюшем Джаухари . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.