|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
14.02.2020, 22:05 | #1 |
Новичок
Джуниор
Регистрация: 14.02.2020
Сообщений: 1
|
Поиск с возвратом
Всем приятного времени суток!! Подскажите пожалуйста идею алгоритма поиска с возвратом для решения такой задачи: дан квадрат (сторона длиной L условно), нужно найти минимальное (по количеству кусков) разбиение на квадраты со стороной от 1 до L-1. Куски (ну то есть квадратики) могут повторяться.
|
15.02.2020, 01:21 | #2 | |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Это похоже на "Представить число N суммой минимального количества квадратов". В общем-то, "правильный" алгоритм решения - динамическое программирование - вариант алгоритма Дейкстры.
Ваш метод - поиск с возвратом. Смысл поиска с возвратом - обычный перебор в нескольких вложенных циклах for. Т.к. точное количество вложений циклов заранее не известно, их имитируют тем или иным способом, например, рекурсией. Чтобы сократить перебор, при достижении невыполнимых условий завершают текущий уровень рекурсии и "наверх" передают результат "нет ответа", т.е. "не запоминать" значение переменной цикла, как найденное решение. Для задачи в такой постановке Цитата:
Теорема Лагранжа о сумме четырёх квадратов позволяет оценить число слагаемых не более 4 с учётом слагаемых, равных L^2. Для данной задачи это неприемлемо. Тогда поступим так, возьмём первое слагаемое (первый квадрат) со стороной (L-1) и получим, что осталось представить в виде суммы квадратов число (L)^2-(L-1)^2=(L+L-1)(L-L+1)=(2L-1) И на это число уже не распространяется ограничение о невозможности представления одним слагаемым в случае, когда (2L-1) является полным квадратом. И, согласно теореме, (2L-1) можно представить суммой не более 4 квадратов. Получаем, что максимальное количество слагаемых для представления числа (L)^2 не превышает 5. Это число - 5 - пригодится для ограничения глубины рекурсии (ну или количества вложенных циклов - в других терминах). Пусть в рекурсивную функцию поступает параметр S - сумма, которую нужно выразить через слагаемые. В рекурсивной функции организуете цикл i от sqrt(S) до 1, и вызываете рекурсию f(S-i*i). Добавляете проверки, чтобы на входе не было отрицательных чисел, ещё какие-нибудь. В случае, когда на входе S==0, запоминаете в глобальной переменной результат. |
|
15.02.2020, 17:52 | #3 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Нет, я ошибся.
Это не арифметическая задача, а задача на разрезание исходной фигуры. Нужно несколько иное решение. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Как модифицировать поиск с возвратом на си | Wysler | Помощь студентам | 0 | 07.12.2014 11:27 |
рекурсивный поиск с возвратом | mego4el | Помощь студентам | 0 | 25.04.2011 22:45 |
поиск с возвратом | Electr0Fly | Помощь студентам | 0 | 28.03.2011 15:44 |
Раскраска графа(поиск с возвратом) | Electr0Fly | Помощь студентам | 0 | 22.03.2011 01:58 |