 |
|
|
|
Пример решения классической рекурсивной задачи итерационным способом средствами 1С
Пример решения классической рекурсивной задачи Классическая задача о восьми ферзях рассматривается в большинстве учебников по программированию. При этом приводимые решения рекурсивны, а нерекурсивные – ресурсозатратны по задействованным переменным и структурам данных. Существует подход, предназначенный для ее решения с использованием итерационных процедур Такой подход может быть применен во многих практических случаях, связанных с построением перестановок для последующей их обработки. Многие разработчики программного обеспечения «способны разглядеть истинную красоту, пусть даже в абстрактных идеях» [1]. Одной из таких идей является применение разнообразных подходов по замене рекурсивных процедур обработки данных на их аналоги в итеративной форме. Таких подходов достаточно много, среди них можно отметить широко известные и хорошо формализованные, в частности с использованием автоматов. Но для одного случая, ориентированного на генерацию перестановок целых чисел с ограничениями на их попарные значения элементов, можно выявить интересные свойства. Он может ограничиться использованием минимального числа переменных относительно компактных и простых в обработке типов: одного массива, двух индексов, одного флажка, при решении классической общеизвестной задачи о восьми ферзях. Целью публикации является описание разработки и приведение результирующей программы на языке 1С, которая реализует решение задачи о восьми ферзях, а именно получение всех возможных расстановок взаимно не бьющихся ферзей на шахматной доске, с использованием подхода без рекурсии. Задача о восьми ферзях – наиболее известная и распространенная для обучения началам программирования. Это вызвано исключительной простотой формулировки и не слишком сложным решением. Достаточно просто получить рекурсивное решение, которое приводится в той или иной степени полноты во многих источниках, например [2]. Но уже переход к нерекурсивной форме приводит к резкому возрастанию сложности строимых алгоритмов сравнительно срекурсивными и получаемых на их основе программ [2], что нельзя не отметить, поскольку подход к решению может быть применен для значительной доли практических ситуаций. Лаконичная итеративная реализация в процедурной парадигме на языке программирования Фортран приводится в пособии [3]. Для широко используемых в настоящее время учебных и промышленных языков программирования (C, Java, Python) перенос выполнен в [4]. Можно эти наработки адаптировать для уровня 1С, что упростит нетривиальные случаи в задачах учета. Прежде чем приступать непосредственно к программированию, необходимо определить способ хранения игрового поля. Очевидно, что не может быть на одной вертикали более чем одного ферзя в допустимом решении, поэтому для доски заводится одномерный массив целых (для задачи – неотрицательных) чисел, в котором в нулевом элементе хранится номер горизонтали для «a», в первом – для «b» и так далее, в седьмом – для «h». Полученное в таком массиве решение можно вывести множеством способом, не усложняя, для примера можно использовать, в частности, нижеследующий: Процедура ПечатьДоски(доска) Перем i, s; s = ""; Для i = 0 По 7 Цикл s = s + " " + доска[i]; КонецЦикла; Сообщить(s); КонецПроцедуры Для попарных сравнений неоднократно потребуется функция для нахождения абсолютной величины числа. Можно использовать для этого собственно тернарный оператор 1С, обрамленный в тело функции для удобства вызова: Функция Abs(А) Возврат ?(А >= 0, А, -А); КонецФункции Подпрограмма, осуществляющая поиск всех решений, начинается с объявления переменных: Перем доска, i, j, подАтакой; доска – одномерный целочисленный массив, в котором хранится решение или его фрагмент на текущий момент, элемент массива доска [l] хранит в себе номер горизонтали для первой вертикали, которую может занимать ферзь. подАтакой – булева переменная, хранящая факт нахождения хотя бы одной пары ферзей под взаимной атакой. i – целочисленный номер текущей обрабатываемой вертикали, а соответственно j – вспомогательный целочисленный номер вертикали. Создается новое игровое поле: доска = Новый Массив(8); И устанавливается текущий номер рабочей вертикали в единицу: i = 1; Это вполне удобно, хотя для остальной части работы приходится учитывать нумерацию в 1С массивов с нуля. Основная деятельность находится в бесконечном цикле: Пока Истина Цикл … КонецЦикла; В этом цикле на первую, еще не обработанную подпрограммой, вертикаль устанавливается ферзь в начальную возможную горизонталь: доска[i - 1] = 1; И вновь запускается бесконечный цикл: Пока Истина Цикл … КонецЦикла; Первая треть его посвящена отысканию момента прерывания обработки в процедуре для завершения работы в том числе на основе выявления факта взаимной атакуемости ферзей. Вначале взаимная атака ферзей считается отсутствующей: подАтакой = Ложь; Когда не находимся на первой вертикали, то есть ферзь не единственный на доске: Если i <> 1 Тогда Для всех поставленных на доску ферзей ищутся пары бьющих друг друга: Для j = 1 По i - 1 Цикл Биение проверяется для горизонталей и диагоналей. Для горизонталей условие биения есть равенство горизонталей, а для горизонталей (всех возможных на доске, а не только главной и дополнительной) – это равенство модулей разностей горизонталей и вертикалей: Если (доска[i - 1] = доска[j - 1]) Или (Abs(доска[i - 1] - доска[j - 1]) = Abs(i - j)) Тогда Когда бьют, то соответствующий флажок становится истинным, а цикл прерывается: подАтакой = Истина; Прервать; КонецЕсли; КонецЦикла; В конце концов, чтобы отбросить симметричные решения, можно прекратить счет после перехода через центр доски и покинуть подпрограмму: ИначеЕсли доска[i - 1] >= 5 Тогда Возврат; КонецЕсли; Вторая треть выполняет несложную задачу – если произошел выход за пределы игрового поля, то оно печатается, иначе процесс продолжается циклически: Если Не подАтакой Тогда i = i + 1; Если i <= 8 Тогда Прервать; КонецЕсли; ПечатьДоски(доска); i = 8; КонецЕсли; В конце цикла ищется место для перемещения ферзя вверх, после чего он поднимается по вертикали. Пока доска[i - 1] >= 8 Цикл i = i - 1; КонецЦикла; доска[i - 1] = доска[i - 1] + 1; Все эти действия в подпрограмме позволяют получить все возможные решения, исключая симметричные. Листинг готовой программы приводится (файл на сайте samag.ru) и должен быть записан в модуль управляемого приложения. Полный перечень полученных мест ферзей (файл на сайте samag.ru) повторяет опубликованные ранее списки и результаты работы [3, 4], что говорит в том числе и о корректности предложенной в настоящей работе программы. Подход и реализация могут использоваться в решении оперативных задач учета при замене ранее примененной рекурсивной части на нерекурсивную. Это позволит избежать ресурсоемких структур и структур представления данных, ограничившись их примитивными малопотребляющими ресурсы и простейшими в обработке аналогами.
|
КИРИЛЛ ТКАЧЕНКО, инженер 1-й кат., ФГАОУ ВО «Севастопольский государственный университет», Комментарии отсутствуют
| Добавить комментарий |
|
Комментарии могут оставлять только зарегистрированные пользователи |
|
