Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Интересные и занимательные задачи по программированию > Заполнение прямоугольника квадратами.

Автор: IvanB 12.12.2005, 12:25

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

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

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

Автор: Snowy 12.12.2005, 12:32

Код


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

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

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

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

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

Автор: Akina 12.12.2005, 12:38

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

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

Рекурсией.

Автор: Snowy 12.12.2005, 12:45

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

Рекурсией.

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

Автор: Akina 12.12.2005, 12:58

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

Автор: IvanB 12.12.2005, 13:28

Цитата

Рекурсией.

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

Цитата

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

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

Цитата

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

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

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

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

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

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

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

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

Автор: Akina 12.12.2005, 14:01

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

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

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

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

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

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

Автор: IvanB 12.12.2005, 15:13

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