Back to top

Использование рекурсивных вычислений

Опубликовано e-1c@mail.ru - сб, 05/13/2017 - 18:41

Из курса программирования известно, что рекурсией называется вызов функцией самой себя. Фактически, рекурсия является первым шагом к логическому программированию, потому что грамотное ее использование позволяет составить алгоритм, не решая задачи окончательно.

Как решить задачу рекурсивно? Запомним простую аксиому: задачу, имеющую рекурсивное решение, всегда можно сформулировать индуктивно. Покажу это на простом примере. Допустим, мы ищем путь из точки А в точку В в лабиринте. Мы оказались на очередном перепутье. Перед нами несколько направлений возможного пути. Что будет, если мы выберем одно из направлений? Правильно, мы окажемся на следующем этапе-перепутье, опять с несколькими направлениями, и вновь перед нами встанет задача выбора. Когда же в некоторый момент мы заходим в тупик или в точку, в которой уже были ранее, нам необходимо просто возвратиться на шаг назад и выбрать другое направление пути из возможных. И так до тех пор, пока мы не придем в конечную точку. Таким образом, сложная задача поиска пути в лабиринте была сведена к однотипным операциям выбора в каждой очередной его точке. Алгоритм рекурсивного решения этой задачи будет выглядеть примерно так:

Функция ПоискПути(Х) 
Если Х=А Тогда Возврат 1; // Конец пути достигнут здесь 
КонецЕсли; 
Пока Есть_Возможные_Пути(Х)=1 Цикл У=Очередная_Точка(Х); 
Если ПоискПути(У)=1 Тогда Возврат 1; // Конец пути был достигнут где-то там 
КонецЕсли; 
КонецЦикла; 
Возврат 0; // Тупик, или не осталось вариантов 
КонецФункции 

Но вернемся к теме 1С. Неужели рекурсию можно использовать и здесь успешно, спросит дока? Надо отметить, что у большинства рекурсивных алгоритмов есть существенный недостаток: они ресурсоемки и достаточно медленны по сравнению с обычными циклами, поэтому, вопрос звучит вполне уместно. Без сомнения, приведенный пример можно решить и не прибегая к рекурсивным вызовам. Но иногда без них бывает почти не обойтись.

Рассмотрим задачу, решение которой для отдельных бухгалтеров может стать исполнением одного из их заветных желаний. Попробуем привязать долги покупателей к конкретным расходным накладным в программе 1С:Бухгалтерия 7.7. Без сомнения, решить эту задачу в лоб – означает, пересчитать всю базу с начала времен, ведь каждый контрагент, собственно говоря, может что-то покупать, потом частично это оплачивать, потом покупать что-то еще и т.д.

Будем решать эту задачу в обратном направлении. Вспомним, что метод FIFO, вообще говоря, должен распространяться и на оплату. Иными словами, если от какого-то клиента поступает оплата, то ни что не мешает нам привязать ее к самому раннему неоплаченному документу по этому клиенту. Итак, если клиент А должен нам 1000 рублей, то можно с уверенностью считать неоплаченными последние N документов, по которым он что–либо у нас приобрел на сумму, не меньше, чем 1000 рублей.

Что ж, будем перебирать все операции по контрагентам в обратном порядке, разнося по ним сумму имеющегося долга. Разумеется, это было бы быстрее, чем перебирать и пересчитывать все документы с начала. Построим рекурсивную обработку операций. Будем рассматривать операции отрезками в 31 день.

Функция ПолучитьДокументы(Контрагент,Т,Знач Д1,Знач Д2,СальдоКон=0) // Т – таблица значений, которая заполняется документами на выходе рекурсии // Д1 и Д2 – очередной рассматриваемый период // СальдоКон – сальдо по контрагенту на конец периода. Значение в // самом начале равно нулю. В дальнейшем оно будет расчитано

Составим запрос по операциям контрагента за месяц

Ит=СоздатьОбъект("БухгалтерскиеИтоги"); 
Ит.ИспользоватьСубконто(ВидыСубконто.Контрагенты,Контрагент,2,0);
Если Ит.ВыполнитьЗапрос(Д1,Д2,"62.1",,,1,"операция","С")=0 
Тогда Сообщить("Ошибка!"); Возврат 0; 
КонецЕсли; 

Определим условие завершения рекурсии

Если СальдоКон=0 
Тогда СальдоКон=Ит.СКД("С")-Ит.СКК("С"); 
КонецЕсли; 
Если СальдоКон<=0 Тогда Возврат 1; 
КонецЕсли; 

Нам понадобится вспомогательная таблица значений

Таб=СоздатьОбъект("ТаблицаЗначений"); 
Таб.НоваяКолонка("Приход","Число",15,2); Таб.НоваяКолонка("Дата","Дата"); 
Таб.НоваяКолонка("Позиция"); 
Таб.НоваяКолонка("Документ","Документ"); 

Заполним таблицу найденными в запросе операциями

Ит.ВыбратьПериоды();
Пока Ит.ПолучитьПериод()=1 
Цикл Таб.НоваяСтрока(); 
Таб.Приход=Ит.ДО("С");
Таб.Документ=Ит.Операция.Документ; 
Таб.Дата=Ит.Операция.Документ.ДатаДок; 
Таб.Позиция=Ит.Операция.Документ.ПолучитьПозицию(); 
КонецЦикла; 

Если в текущем месяце не было докуменетов, то рассмотрим месяц ранее по рекурсии. Это будет косвенное условие завершения.

Если Таб.КоличествоСтрок()=0 Тогда Возврат
 ПолучитьДокументы(Контрагент,Т,Д1-31,Д1-1,СальдоКон); 
КонецЕсли; 

Если полученная таблица операций не пуста, то отсортируем ее по убыванию позиции документов

Таб.Сортировать("-Позиция"); 

Разнесем долг контрагента по документам, формирующим этот долг. В тот момент, когда остаток долга станет меньше нуля, будем считать, что долг полностью привязан к документам.

Таб.ВыбратьСтроки(); 
Пока (Таб.ПолучитьСтроку()=1)и(СальдоКон>0) Цикл 
Если Таб.Приход>0 Тогда Т.НоваяСтрока(); 
Т.Документ=Таб.Документ;
 Т.Дата=Таб.Дата; 
Т.Долг=Таб.Приход; 
Т.ОстатокДолга=СальдоКон; 
СальдоКон=СальдоКон-Таб.Приход; 
КонецЕсли;	
КонецЦикла; 

Если документы в текущем месяце не покрыли долг, то берем в рассмотрение еще один месяц рекурсивно.

Если СальдоКон>0 Тогда
Возврат ПолучитьДокументы(Контрагент,Т,Д1-31,Д1-1,СальдоКон); 
КонецЕсли;
 

Если покрыли, то возвращаем 1

Возврат 1; КонецФункции 

Думаю, теперь каждый без труда поймет, как использовать эту функцию в основном расчетном модуле. Приведу примерный, упрощенный вариант.

Таблица=СоздатьОбъект(«Таблица»); 
Таблица.ВывестиСекцию(«Шапка»); 
Т=СоздатьОбъект(«ТаблицаЗначений»); 
Т.НоваяКолонка(«Документ»); 
Т.НоваяКолонка(«Дата»); 
Т.НоваяКолонка(«Долг»); 
Т.НоваяКолонка(«ОстатокДолга»);
Контрагенты=СоздатьОбъект(«Справочник.Контрагенты»); 
Контрагенты.ВыбратьЭлементы(); 
Пока Контрагенты.ПолучитьЭлемент()=1 Цикл
 Д=РабочаяДата(); 
Т.УдалитьСтроки(); 
ПолучитьДокументы(Контрагенты.ТекущийЭлемент(),Т,Д-30,Д); ВывестиВТаблицу(Таблица,Контрагенты.ТекущийЭлемент(),Т);
КонецЦикла; Таблица.ВывестиСекцию(«Подвал»); Таблица.Опции(0,0,0,0,«ДолгиКонтрагентов1»,«ДолгиКонтрагентов2»); 
Таблица.ТольоПросмотр(1); 
Таблица.Показать(«Долги»);
 

Мы рассмотрели упрощенный вариант задачи, предполагая применение метода FIFO к оплате, и как видите, рекурсия в приведенном случае вполне оправдана. Без сомнения, больший интерес представляет алгоритм, в котором учитывается как дебетовые, так и кредитовые обороты по счету 62, и в этом случае, на выходе мы можем получить что-то вроде книги покупок, но без применения забалансовых счетов. Что ж, дерзайте, коллеги!

Приведенный алгоритм применен в наших обработках "Кто нам должен" и "Кому мы должны"