Чтобы понять, взгляните на алгоритм №1. Для первого шаблона (a)
в следующих двух строках (5 и 6 в статье) приведены пояснения.
for all(i,j) such 1<=i<=24 and 1<=j<=24:
for all(h,w) such that i+h-1<=24 and j+2w-1<=24:
Это означает, что вы возьмете все комбинации верхних левых углов (i
- верхний, а j
- левый), а затем все комбинации ширины (w
) и высоты (h
), которые поместятся внутри 24x24.
Алгоритм также будет использовать все комбинации ширины и высоты (1x4, 1x6, 1x8, ..., 1x24, 2x2, 2x4, 2x6, 2x8, ..., 2x24, 3x2, 3x4, 3x6, ..., до 24x24). Пока ширина кратна 2 (указывается 2w
в строке №6).
Самый маленький узор (2 пикселя в ширину и 1 пиксель в высоту) уместится в 24 * 23 = 552 положениях (23 положения по горизонтали и 24 положения по вертикали).
В какой-то момент, например, у вас будет узор 7х10 (высота 7 пикселей и ширина 10 пикселей). Он уместится в 18 x 15 = 270 положениях (18 вертикальных положений и 15 горизонтальных положений).
Самый большой прямоугольник (24x24 пикселя) будет состоять из 12 белых столбцов, за которыми следуют 12 черных столбцов. Он уместится только в одной позиции (на всем изображении).
Если вы просуммируете все позиции по всем возможным размерам, вы получите числа.
Чтобы получить первое число (для шаблона а), следующая программа (я ее не оптимизировал! Но она должна быть легко понятной) печатает 43200
:
# Pattern A
total = 0
for i in range(1,25): # 1 <= i <= 24
for j in range(1,25): # 1 <= j <= 24
for w in range(1,13): # 2*w=2,4,6,...24
for h in range(1,25): # h=1,2,...,24
if (i+h-1<=24) and (j+2*w-1<=24):
total += 1
print total
Для других шаблонов объяснения аналогичны.
person
Sci Prog
schedule
23.10.2016