Форум: "Прочее";
Текущий архив: 2006.04.16;
Скачать: [xml.tar.bz2];
Вниз
Задачка в среду Найти похожие ветки
← →
Харько © (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, так что, возможно, и с кубами есть путь решения
← →
MBo © (2006-03-23 13:33) [12]P.S. Если совсем без комбинаторики, то
Left = 0..N-1, Right = L+1..N, и N(N+1)/2 получается, как сумма арифметической прогрессии.
← →
Харько © (2006-03-23 15:03) [13]Ну не знаю. У Перельмана ответ - 225.
← →
TUser © (2006-03-23 15:10) [14]> Да ну... Какое уж тут дин. программирование. Задачка взята из книги Перельмана 1920 года.
Принципы дин программирования (насколько я понимаю) были известны задолго до Беллмана. И именно изза отсутствия вычислительных мощьностей - надо было уметь быстро считать.
← →
MBo © (2006-03-23 15:20) [15]>У Перельмана ответ - 225.
Ага, я для квадрата размером 25x25 написал ;))
Для 5x5 будет (5*6/2)^2=225
← →
Jeer © (2006-03-23 17:34) [16]Ай да Перельман:))
Как он узнал, правильный ответ от Mbo ? :)))
Страницы: 1 вся ветка
Форум: "Прочее";
Текущий архив: 2006.04.16;
Скачать: [xml.tar.bz2];
Память: 0.48 MB
Время: 0.043 c
