Пример решения классической рекурсивной задачи итерационным способом средствами 1С

 КИРИЛЛ ТКАЧЕНКО, инженер 1-й кат., ФГАОУ ВО «Севастопольский государственный университет», tkachenkokirillstanislavovich@gmail.com

Пример решения классической рекурсивной задачи
итерационным способом средствами 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. Вторников А. Lisp: маленький гигант. // «Системный администратор», № 6, 2016 г. – С. 64-69 (http://samag.ru/archive/article/3221).
2. Арсак Ж. Программирование игр и головоломок. – М.: Наука, 1990. – 224 с.
3. Ламуатье Ж.-П. Упражнения по программированию на Фортране-IV. – М.: Мир, 1978. – 168 с.
4. Ткаченко К.С. Интересное решение задачи о восьми ферзях. // «Потенциал: Математика. Физика. Информатика», № 7, 2016 г. – С. 47-52.

Комментарии могут оставлять только зарегистрированные пользователи