Алгоритм расчета Факториала

23.07.12

Разработка - Математика и алгоритмы

Пример оптимизации алгоритма под органичения 1С.

Скачать файлы

Наименование Файл Версия Размер
Новая обработка (исправлены ошибки и оптимизирована работа алгоритма)
.epf 7,33Kb
14
.epf 7,33Kb 14 Скачать
Факториал_aka_Zeratul
.epf 7,37Kb
12
.epf 7,37Kb 12 Скачать

Факториа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)^n

Теперь 10000! расчитывается за 50 секунд = 2.8е35660.

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1754    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4423    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7464    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7855    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4446    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8840    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

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

31.08.2021    7806    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. JohnyDeath 301 18.07.12 08:40 Сейчас в теме
А есть практическое применение? Или это просто "джаст фо фан"?
2. Iaskeliainen 384 18.07.12 09:29 Сейчас в теме
(1) JohnyDeath,
Для решения нестандартных задач, размышлений и
"джаст фо фан"


Подобный подход можно использовать не только для умножения, но и деления, сложения, вычитания и т.д. и т.п.
7. frc 18.07.12 13:24 Сейчас в теме
(2)
ну вот и прикиньте, как для нестандартных задач везде и всюду бедете разбивать на "поблочные вычисления" :)
Плюс поставлю, но это - чистой воды баловство.
3. tango 506 18.07.12 10:27 Сейчас в теме
(0) Так как максимальная длина числа 32.
это как?
Прикрепленные файлы:
Iaskeliainen; +1 Ответить
5. Iaskeliainen 384 18.07.12 11:12 Сейчас в теме
(3) tango, в конфигураторе больше 32 знаков число не создает.
Справка в конфигураторе
Описание: Числовым типом может быть представлено любое десятичное число. Над данными числового типа определены основные арифметические операции: сложение, вычитание, умножение и деление. Максимально допустимая разрядность числа 38 знаков.

Выбрал меньшее из них дабы точно работало.

Спасибо за идею. Попробую с числами побольше.

(4) aexeel, не кто и не спорит.
9. Iaskeliainen 384 18.07.12 17:57 Сейчас в теме
(3) tango, опытным путем нашел, что длина числа до 311 знаков работает корректно,
выше нет. При таком раскладе алгоритм ускоряется в 10 раз.

Факториал 1000 = ~ 4.0e2568, что явно больше 311 знаков.
Вот и приходиться использовать строку.
10. frc 18.07.12 18:05 Сейчас в теме
(9)
а вы её в регистр накопления, а потом суммировать в строку :)
Я так думаю - 100 тсрок позволят вам побить рекорд расчета n! :)
11. Iaskeliainen 384 18.07.12 18:09 Сейчас в теме
(10) frc, идея хорошая.
Но я бы тогда посмотрел на неё по другому.
Массив из чисел по 311 знаков.
Наверное еще можно будет на порядок скорость поднять.
4. aexeel 73 18.07.12 10:47 Сейчас в теме
Задача со школьной олимпиады по информатике 8 класса :)
6. lvictor58 135 18.07.12 12:45 Сейчас в теме
Ну о-ч-ч-ень нужная вещь для оптимизации работы бухов, манагеров и спецов складского учета!
8. KAPACEB.AA 459 18.07.12 14:23 Сейчас в теме
Я тоже как-то не проникся идеей...

Если делать преобразование в строку непосредственно перед передачей в строковой реквизит, то эти пляски с бубном ни к чему. В коде приложенной обработки достаточно было написать:
"...
знч_фс = Строка(Факт(Знч_ф));
...
"
и результат ее работы был бы такой же.

Если это делалось с осознанием факта, что можно сделать проще но хотелось сложнее, то... сори, но я все-равно не понимаю зачем :)
12. Iaskeliainen 384 19.07.12 12:49 Сейчас в теме
Появилась еще одна проблема.
Это рекурсия в 1С. Глубина вложенности выше 1776 вылетает с ошибкой.
Пришлось заменить на цикл.
13. Iaskeliainen 384 23.07.12 13:42 Сейчас в теме
Поправил обработку и статью.
Оставьте свое сообщение