Как организовать алгоритм расстановки арифметических знаков и скобок между числами в 1С?

← На главную

В практике программирования иногда возникают комбинаторные задачи, когда задан массив чисел и итоговый результат, а требуется автоматически построить математическое выражение (расставив между операндами операции и скобки), дающее в итоге целевое значение. В этой статье мы разберем по шагам, как правильно составить алгоритм перебора формул на языке 1С, с какими подводными камнями можно столкнуться при использовании рекурсии и как оптимизировать вычисления по памяти.

Суть задачи и алгоритмический подход

Рассмотрим постановку задачи: имеется цепочка операндов от n1 до n_max и необходимо получить целевой результат Rez. Задача сводится к систематическому перебору всех возможных сочетаний операндов, бинарных операций (сложение, вычитание, умножение, деление) и порядка выполнения действий, задаваемого скобками.

Наиболее элегантный способ формирования таких формул — **разделяй и властвуй** с использованием рекурсии. Посмотрим на логику построения древовидной структуры вычислений:

Цепочка операндов поочередно разбивается на две части по индексу соединения: левую (от От до Сч) и правую (от Сч + 1 до До).
Для каждой части рекурсивно формируется полный набор допустимых подвыражений.
Далее варианты комбинируются путем объединения каждой левой и правой части с помощью каждой из поддерживаемых арифметических операций.
Базовый случай рекурсии достигается, когда интервал сокращается до одного элемента — тогда возвращается сам элемент (или его отрицательное значение для учета унарного минуса).

Реализация рекурсивной функции генерации формул

Проанализируем базовый вариант рекурсивной функции в 1С, которая генерирует список всех текстовых формул со скобками для последовательности аргументов с заданными номерами:


Функция СписокФормул(От, До)
    Результат = Новый СписокЗначений;
    Если От >= До Тогда
        Результат.Добавить("n" + От);
        Результат.Добавить("(-n" + От + ")");
    Иначе
        Для Сч = От По До - 1 Цикл
            Для каждого Слева Из СписокФормул(От, Сч) Цикл
                Для каждого Справа Из СписокФормул(Сч + 1, До) Цикл
                    Для Оп = 1 По 3 Цикл
                        Результат.Добавить("(" + Слева + Сред("+*/", Оп, 1) + Справа + ")");
                    КонецЦикла;
                КонецЦикла;
            КонецЦикла;
        КонецЦикла;
    КонецЕсли;
    Возврат Результат;
КонецФункции

Данная функция формирует комбинации строк вида ((n1 + n2) * n3). Однако при её запуске на практике можно столкнуться с критической проблемой — переполнением стека рекурсии или исчерпанием оперативной памяти.

Ошибки области видимости переменных и падение по памяти

Выясним причину, почему при незначительном количестве элементов (например, от 1 до 4) рекурсивный алгоритм в 1С может уйти в бесконечные циклы или аварийно завершиться с ошибкой нехватки памяти. В платформе 1С, если внутри функции явно не перечислить локальные переменные через ключевое слово Перем, а в контексте модуля или формы уже объявлены реквизиты или переменные с такими же именами (например, Результат или счетчики Сч, Оп), рекурсивные вызовы начнут перезаписывать счетчики внешних уровней рекурсии.

Разберем исправленный и оптимизированный вариант функции. В нем добавлено явное объявление локальных переменных, а также сделано вычисление результатов для правой части цепочки до входа во внутренний цикл, чтобы исключить лишние рекурсивные вызовы:


Функция СписокФормул(От, До)
    Перем Результат, Сч, Оп, ПравыеЧасти, Слева, Справа; // Важно: локализация переменных!
    
    Результат = Новый СписокЗначений;
    Если От >= До Тогда
        Результат.Добавить("n" + От);
        Результат.Добавить("( - n" + От + ")");
    Иначе
        Для Сч = От По До - 1 Цикл
            ПравыеЧасти = СписокФормул(Сч + 1, До); // Вычисляем один раз для повышения скорости
            Для каждого Слева Из СписокФормул(От, Сч) Цикл
                Для каждого Справа Из ПравыеЧасти Цикл
                    Для Оп = 1 По 3 Цикл
                        Результат.Добавить("(" + Слева + " " + Сред("+*/", Оп, 1) + " " + Справа + ")");
                    КонецЦикла;
                КонецЦикла;
            КонецЦикла;
        КонецЦикла;
    КонецЕсли;
    
    Возврат Результат;
КонецФункции

Практические рекомендации по оптимизации вычислений

Генерация миллиона текстовых строк и последующая их проверка через встроенную функцию Вычислить() может занимать продолжительное время. Рассмотрим подходы к оптимизации производительности:

Перебор значений вместо текста (Backtracking): Вместо формирования строковых выражений целесообразнее выполнять арифметические операции непосредственно над числовым массивом во время рекурсивного спуска. Формировать итоговую текстовую строку со скобками стоит только в момент, когда результат совпал с Rez.
Проверка деления на ноль: При выполнении операции деления необходимо проверять делитель на равенство нулю или оборачивать вычисления в конструкцию Попытка ... Исключение ... КонецПопытки.
Погрешность вычислений с плавающей точкой: При делении и умножении вещественных чисел условие точного равенства ВычисленноеЗначение = Rez может не сработать. Сравнение следует выполнять с учетом погрешности, например: Math.Abs(Результат - Rez) < 0.000001 (или используя встроенный Мин()/Макс() и модуль разности в 1С: Mакс(Результат - Rez, Rez - Результат) < 0.000001).
Перестановка операндов: Если по условию задачи исходные числа можно менять местами, перед поиском расстановки знаков нужно применить алгоритм генерации всех перестановок исходного массива (перебор $n!$ вариантов).

Применяя предложенную рекурсивную функцию с корректно объявленными локальными переменными Перем, вы сможете надежно и быстро находить решения для задач на расстановку скобок и знаков в 1С.