Пример решения классической рекурсивной задачи итерационным способом средствами 1С::Журнал СА 7-8.2017
www.samag.ru
     
Поиск   
              
 www.samag.ru    Web  0 товаров , сумма 0 руб.
E-mail
Пароль  
 Запомнить меня
Регистрация | Забыли пароль?
Журнал "Системный администратор"
Журнал «БИТ»
Наука и технологии
Подписка
Где купить
Авторам
Рекламодателям
Архив номеров
Контакты
   

  Опросы
  Статьи

Разбор полетов  

Ошибок опыт трудный

Как часто мы легко повторяем, что не надо бояться совершать ошибки, мол,

 Читать далее...

Принципы проектирования  

Dependency Inversion Principle. Принцип инверсии зависимостей в разработке

Мы подошли к последнему принципу проектирования приложений из серии SOLID – Dependency

 Читать далее...

Рынок труда  

Вакансия: Администратор 1С

Администратор 1С – это специалист, который необходим любой организации, где установлены программы

 Читать далее...

Книжная полка  

Книги для профессионалов, студентов и пользователей

Книги издательства «БХВ» вышли книги для тех, кто хочет овладеть самыми востребованными

 Читать далее...

Принципы проектирования  

Interface Segregation Principle. Принцип разделения интерфейсов в проектировании приложений

Эта статья из серии «SOLID» посвящена четвертому принципу проектирования приложений – Interface

 Читать далее...

1001 и 1 книга  
19.03.2018г.
Просмотров: 10280
Комментарии: 0
Потоковая обработка данных

 Читать далее...

19.03.2018г.
Просмотров: 8473
Комментарии: 0
Релевантный поиск с использованием Elasticsearch и Solr

 Читать далее...

19.03.2018г.
Просмотров: 8568
Комментарии: 0
Конкурентное программирование на SCALA

 Читать далее...

19.03.2018г.
Просмотров: 5462
Комментарии: 0
Машинное обучение с использованием библиотеки Н2О

 Читать далее...

12.03.2018г.
Просмотров: 6146
Комментарии: 0
Особенности киберпреступлений в России: инструменты нападения и защита информации

 Читать далее...

Друзья сайта  

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

Архив номеров / 2017 / Выпуск №7-8 (176-177) / Пример решения классической рекурсивной задачи итерационным способом средствами 1С

Рубрика: Разработка /  Изучаем «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.

Комментарии отсутствуют

Добавить комментарий

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

               Copyright © Системный администратор

Яндекс.Метрика
Tel.: (499) 277-12-41
Fax: (499) 277-12-45
E-mail: sa@samag.ru