ФакториаL9;л числа n (обозначается n!, произносится эн факториаL9;л) — произведение всех натуральных чисел до n включительно:
Для n = 6, n! = 6! = 1*2*3*4*5*6 = 720.
Казалось бы все просто, да нет. Число символов очень быстро растет и быстро выходит за пределы числа, в 1С длина числа 32 знака.
Конечно же, многие скажут надо работать с символами строки, но тогда получается очень медленно.
Есть компромисс, идея в следующем.
Разбивать строку при вычислении не по символам, а по блокам.
Так как максимальная длина числа 32. И допустим мы хотим найти факториал 999, тогда длина второго множителя может быть равна не более 32 – 3 = 29 знаков.
Результат храним в строке неограниченной длины.
Строку результата разбиваем на блоки максимальной длины, преобразуем к числу, умножаем на текущий параметр. И формируем новую строку.
Алгоритм можно использовать рекурсии (именно он и был использован):
F(x) = x * F(x-1), где F(1) = 1
Ускорение получается на порядок по сравнению с посимвольным расчетом.
Во вложении пример обработки.
Изменения: Проверка была выполнена на платформе 8.2.15.319 (на других результаты могут отличаться)
Опытным путем было обнаружено, что максимальная длина числа составляет 311 цифр. Решение: замена макс длины на 311.
Максимальная вложенность рекурсии 1776. Решение: замена рекурсии на цикл.
Функция число в строку и наоборот работает медленно, дольше всего остального. Решение: было заменено на ТаблицуЗначений где в каждой строке храниться число, а не строка.
Добавлена формула Стирлинга для вычисления порядка факториала. N! ~ sqrt(2 * PI * n) * (n/e)#k8SjZc9Dxkn
Теперь 10000! расчитывается за 50 секунд = 2.8е35660.
Related Posts
Получение логина и пароля техподдержки 1С из базы
Класс для вывода отчета в Excel
Счет-фактура для УПП
Библиотека классов для создания внешней компоненты 1С на C#- Акт об оказании услуг (со скидками) — внешняя печатная форма для Управление торговлей 11.1.10.86
Прайс-лист с артикулом в отдельной колонке
А есть практическое применение? Или это просто «джаст фо фан»?
(1) JohnyDeath,
Для решения нестандартных задач, размышлений и
Подобный подход можно использовать не только для умножения, но и деления, сложения, вычитания и т.д. и т.п.
(0) Так как максимальная длина числа 32.
это как?
Задача со школьной олимпиады по информатике 8 класса 🙂
(3) tango, в конфигураторе больше 32 знаков число не создает.
Справка в конфигураторе
Выбрал меньшее из них дабы точно работало.
Спасибо за идею. Попробую с числами побольше.
(4) aexeel, не кто и не спорит.
Ну о-ч-ч-ень нужная вещь для оптимизации работы бухов, манагеров и спецов складского учета!
(2)
ну вот и прикиньте, как для нестандартных задач везде и всюду бедете разбивать на «поблочные вычисления» 🙂
Плюс поставлю, но это — чистой воды баловство.
Я тоже как-то не проникся идеей…
Если делать преобразование в строку непосредственно перед передачей в строковой реквизит, то эти пляски с бубном ни к чему. В коде приложенной обработки достаточно было написать:
«…
знч_фс = Строка(Факт(Знч_ф));
…
»
и результат ее работы был бы такой же.
Если это делалось с осознанием факта, что можно сделать проще но хотелось сложнее, то… сори, но я все-равно не понимаю зачем 🙂
(3) tango, опытным путем нашел, что длина числа до 311 знаков работает корректно,
выше нет. При таком раскладе алгоритм ускоряется в 10 раз.
Факториал 1000 = ~ 4.0e2568, что явно больше 311 знаков.
Вот и приходиться использовать строку.
(9)
а вы её в регистр накопления, а потом суммировать в строку 🙂
Я так думаю — 100 тсрок позволят вам побить рекорд расчета n! 🙂
(10) frc, идея хорошая.
Но я бы тогда посмотрел на неё по другому.
Массив из чисел по 311 знаков.
Наверное еще можно будет на порядок скорость поднять.
Появилась еще одна проблема.
Это рекурсия в 1С. Глубина вложенности выше 1776 вылетает с ошибкой.
Пришлось заменить на цикл.
Поправил обработку и статью.