Нахождение квадратов – 2
На этой сетке красным цветом обозначены два квадрата 1 на 1 и один квадрат 2 на 2 с горизонтальной и вертикальной сторонами.
CHALLENGE
Найдите количество квадратов всех размеров и ориентаций в этой сетке. В отличие от того, что показано во введении, не все эти квадраты будут иметь горизонтальные и вертикальные стороны!
РАЗВЕДКА
Поэкспериментируйте с тем, что происходит с большими сетками и с сетками, не состоящими из квадратов.
Заметки
CHALLENGE
Возможные квадраты с горизонтальными и вертикальными сторонами имеют длину от 1 до значения, меньшего, чем количество строк/столбцов.
Для каждого размера квадрата верхний левый угол считается начальной позицией. Вы можете создать все квадраты этого размера в сетке, перемещая этот начальный квадрат. Вы можете переместить его вправо или вниз на оставшееся количество позиций. Это независимые выборы, поэтому вы получаете квадрат такого размера квадрат.
Например, предположим, вы считаете квадраты 2х2 в этой сетке 5х5. Квадрат 2х2 в верхнем левом углу может быть сдвинут на 1 или 2 вправо и на 1 или 2 вниз. Таким образом, существует 3 возможных положения по горизонтали (считая исходное положение) и 3 возможных положения по вертикали. Следовательно, таких квадратов 1х1 всего 3х3.
В исходной задаче с сеткой 5 на 5 это дает следующее количество квадратов с горизонтальными и вертикальными сторонами:
- Квадраты 1х1: 4х4 = 16
- Квадраты 2х2: 3х3 = 9
- Квадраты 3х3: 2х2 = 4
- Квадраты 4х4: 1х1 = 1.
Всего существует 16 + 9 + 4 + 1 = 30 возможных квадратов с горизонтальными и вертикальными сторонами.
Главное при работе с оставшимися квадратами — продолжать систематизировать подсчет. Я буду описывать квадрат по тому, что делает одна из его сторон. Например, квадрат, сторона которого идет на единицу вправо и на единицу вверх, или квадрат, сторона которого идет на две единицы вправо и на единицу вверх — это два квадрата, изображенные на этой иллюстрации.
Считая скольжением, как и прежде, мы имеем:
- 1 вправо и 1 вверх: 3 x 3 = 9
- 2 вправо и 1 вверх: 2 x 2 = 4
- 3 вправо и 1 вверх: 1 x 1 = 1
- 2 влево и 1 вверх: 2 x 2 = 4
- 3 влево и 1 вверх: 1 x 1 = 1
- 2 вправо и 2 вверх: 1 x 1 = 1
Таким образом, общая сумма составляет: 30 (из предыдущего вычисления) + 9 + 4 + 1 + 4 + 1 = 49.
РАЗВЕДКА
Вы можете изучить другие размеры, разработав упорядоченную систему подсчета!