Задачка такая:
1) Проверить, можно ли заполнить прямоугольник m*n квадратами в количестве k (стороны прямоугольника и квадратов - натуральные числа).
2) Найти наименьшее число квадратов, которыми можно заполнить данный прямоугольник.

Перебором делать - очевидно, но программа будет долго работать...
А как ещё можно, пока не знаю.

P.S. Пишу её на VB, хотя и на других языках понять смогу...


Это сообщение отредактировал(а) IvanB - 12.12.2005, 12:29

Код

k:=(m div x) * (n div x);

где x - сторона квадрата.
k - сколько квадратов влезет.

Цитата(IvanB @ 12.12.2005, 12:25)

Найти наименьшее число квадратов, которыми можно заполнить данный прямоугольник.

Наименьшее всегда - 0. Не ошибешься.

Цитата(IvanB @ 12.12.2005, 13:25)

Перебором делать - очевидно, но программа будет долго работать...

Рекурсией.

Цитата(Akina @ 12.12.2005, 12:38)

Рекурсией.

Опять задача коммивояжера.
Это в случае, если квадраты разные.
В алгоритмах Coriolis не очень давно поднимал похожую.
Только у него были прямоугольники и их нужно было вертеть.

Snowy
Так ведь каждый думает, что это у него эксклюзивная задача, все остальные дурью маются, а поиск по конфе - это для накрутки хинтов и трафика.

Цитата

Рекурсией.

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

Цитата

Наименьшее всегда - 0. Не ошибешься.

Наименьшее натуральное.

Цитата

В алгоритмах Coriolis не очень давно поднимал похожую.

Теперь буду разбираться с задачей о рюкзаке....



Добавлено @ 13:31

Цитата(Snowy @ 12.12.2005, 12:32)

k:=(m div x) * (n div x); где x - сторона квадрата. k - сколько квадратов влезет.

Не... это не то... мне заполнить нужно, а не найти максимальное число квадратов данного размера, которое в него влезет.

(Кстати, для примера нахождения минимального заполнения можно взять прямоугольник 5*6

Цитата(IvanB @ 12.12.2005, 14:28)

Рекрсия и перебор в данном случае - одно и то же...

как все запущено...

Цитата(IvanB @ 12.12.2005, 14:28)

Иначе переменное (зависящее от количества квадратов) число циклов задать не выйдет

нету в рекурсии циклов, НЕТУ! есть условие окончания погружения, включая отсечение. Поэтому рекурсия будет в разы быстрее, особенно если оптимизировать выбор очередного варианта для погружения, что в данном случае элементарно - не больше меньшего.

Сорри... чушь сморозил...