Задачка в среду

← →
Харько © (2006-03-22 17:29) [0]

Дан квадрат, состоящий из 25 квадратов (5*5). Сколько можно составить прямоугольников из квадратиков?

← →
Sandman25 © (2006-03-22 17:30) [1]

Тупая комбинаторика + логика :)

← →
MBo © (2006-03-22 17:45) [2]

>Харько
Как считается - в квадрате 2x2 - 9 прямоугольников?

← →
Геро (2006-03-22 17:45) [3]

А какие прямоугольники считать разными?

← →
Харько © (2006-03-22 17:57) [4]

> Как считается - в квадрате 2x2 - 9 прямоугольников?

Думаю, да. В задаче это не сформулировано.

← →
TUser © (2006-03-22 18:50) [5]

> Тупая комбинаторика + логика :)

Динамическое программирование. Если для матрицы nхm известно чяисло квадратов, то при добавлении одного столбца добавляется (m+1)*n*(n-1)/2 квадратиков.

← →
DrPass © (2006-03-22 23:09) [6]

Правильный ответ: целую уйму

← →
Пупкин (2006-03-22 23:10) [7]

Удалено модератором

← →
DrPass © (2006-03-22 23:12) [8]

Тяжелый случай...

← →
McSimm © (2006-03-22 23:41) [9]

>Пупкин (22.03.06 23:10) [7]

Ладно, можешь считать, что уговорил.

← →
Харько © (2006-03-23 10:43) [10]

> Динамическое программирование. Если для матрицы nхm известно
> чяисло квадратов, то при добавлении одного столбца добавляется
> (m+1)*n*(n-1)/2 квадратиков.

Да ну... Какое уж тут дин. программирование. Задачка взята из книги Перельмана 1920 года.

← →
MBo © (2006-03-23 13:22) [11]

Пусть угол квадрата NxN находится в начале координат.
Тогда левый и правый край прямоугольника с целочисленными координатами могут иметь координаты 0..N
Число способов выбора - число сочетаний из N+1 мест по 2
С(N+1,2)=N*(N+1)/2
Аналогично для верхнего и нижнего края, так что всего
(N*(N+1)/2)^2 вариантов. Для N=25 получается 105625
Интересно, что последняя формула - сумма кубов чисел 1..N, так что, возможно, и с кубами есть путь решения

P.S. Если совсем без комбинаторики, то
Left = 0..N-1, Right = L+1..N, и N(N+1)/2 получается, как сумма арифметической прогрессии.

Ну не знаю. У Перельмана ответ - 225.

> Да ну... Какое уж тут дин. программирование. Задачка взята из книги Перельмана 1920 года.

Принципы дин программирования (насколько я понимаю) были известны задолго до Беллмана. И именно изза отсутствия вычислительных мощьностей - надо было уметь быстро считать.

>У Перельмана ответ - 225.

Ага, я для квадрата размером 25x25 написал ;))

Для 5x5 будет (5*6/2)^2=225

Ай да Перельман:))
Как он узнал, правильный ответ от Mbo ? :)))

Задачка в среду Найти похожие ветки