Вычисление произвольного факториала

04.12.15

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

Обработка вычисления произвольного факториала. Just for lulz. =)

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

Наименование Файл Версия Размер
Вычисление факториала (обработка)
.epf 8,74Kb
0
.epf 8,74Kb Скачать

Обработка вычисляет произвольный факториал и сумму цифр результата.

Написана просто в качестве развлечения.

Может пригодиться в качестве некоего учебного пособия.

=)

Использовано разбиение строкового представления числа на части по N цифр (устанавливается в коде, по умолчанию выставлено в 8) и дальнейшее умножение данных частей "в столбик". Также внутри функции умножения используется сложение "в столбик" в промежуточных вычислениях.

Функции снабжены комментариями. Функция умножения подробными, сложения - общими (т.к. сложение много проще умножения).

Как-то так...

Пользуйтесь на здоровье! =)

Т.к. теперь невозможно разместить абсолютно бесплатный файл, то прилагаю код обработки:

Перем обMSScriptControl; // Использование MSScript
Перем мЗамерыПроизводительности;

Перем чДлинаСегмента;
Перем сФорматСегмента;

Функция НачатьЗамерПроизводительности()
	
	Если обMSScriptControl = Неопределено Тогда
		СтартВыполнения = ТекущаяДата();
	Иначе
		СтартВыполнения = обMSScriptControl.Eval("(new Date()).valueOf()");
	КонецЕсли;
	
	мЗамерыПроизводительности.Добавить(СтартВыполнения);
	
	Возврат мЗамерыПроизводительности.ВГраница();
	
КонецФункции

Функция ЗавершитьЗамерПроизводительности(бСообщитьВремя = Ложь)
	
	мРезультат = Новый Массив;
	
	ВГраницаЗамеров = мЗамерыПроизводительности.ВГраница();
	Если ВГраницаЗамеров > -1 Тогда
		СтартВыполнения = мЗамерыПроизводительности[ВГраницаЗамеров];
		мЗамерыПроизводительности.Удалить(ВГраницаЗамеров);
	Иначе
		Если бСообщитьВремя Тогда
			Сообщить("Нарушен порядок вызовов вложенных замеров. Замер не выполнен!");
		КонецЕсли;
		
		мРезультат.Добавить(0);
		мРезультат.Добавить("0");
		мРезультат.Добавить(-1);
		
		Возврат мРезультат;
	КонецЕсли;
	
	Если обMSScriptControl = Неопределено Тогда
		ФинишВыполнения = ТекущаяДата();
		ВремяВыполнения = ФинишВыполнения-СтартВыполнения;
		ВремяВыполненияСтр = Формат(ВремяВыполнения, "ЧРД=.; ЧГ=");
	Иначе
		ФинишВыполнения = обMSScriptControl.Eval("(new Date()).valueOf()");
		ВремяВыполнения = (ФинишВыполнения-СтартВыполнения)/1000;
		ВремяВыполненияСтр = Формат(ВремяВыполнения, "ЧДЦ=3; ЧРД=.; ЧН=0; ЧГ=");
	КонецЕсли;
	
	Если бСообщитьВремя Тогда
		Сообщить("Замер производительности "+Формат(ВГраницаЗамеров, "ЧН=; ЧГ=") + ": " + ВремяВыполнения + " сек.");
	КонецЕсли;
	
	мРезультат.Добавить(ВремяВыполнения);
	мРезультат.Добавить(ВремяВыполненияСтр);
	мРезультат.Добавить(ВГраницаЗамеров);
	
	Возврат мРезультат;
	
КонецФункции

Функция СложитьСегментыЧисел(мЧисел)
	
	// мЧисел содержит массивы сегментов складываемых чисел
	// Соответственно:
	// 1. Берем в Результат массив 0-го индекса
	// 2. Посегментно (по правилам сложения в столбик) складываем Результат с массивом 1-го индекса
	// 3. Помещаем результат (также массив сегментов) в Результат.
	// 4. Повторяем, пока не закончились массивы сегментов в мЧисел.
	// 5. Возвращаем Результат.
	
	мРезультат = Новый Массив;
	мРезультат.Добавить("0");
	
	Для каждого мСледЧисло из мЧисел Цикл
		// Определим большее число
		Если мСледЧисло.Количество() > мРезультат.Количество() Тогда
			мЧисло0 = мСледЧисло; // Большее
			мЧисло1 = мРезультат; // Меньшее
		Иначе
			мЧисло0 = мРезультат;
			мЧисло1 = мСледЧисло;
		КонецЕсли;
		
		// Теперь нужно по правилам сложения в столбик прибавить к большему числу, меньшее.
		// Перебираем меньшее и складываем согласно индексов.
		мРезультатСложения = Новый Массив;
		мСуммаСегментов = Новый Массив;
		чВГраницаЧисло0 = мЧисло0.ВГраница();
		чВГраницаЧисло1 = мЧисло1.ВГраница();
		Для Т = 0 по чВГраницаЧисло0 Цикл
			Если Т > чВГраницаЧисло1 Тогда
				Если мСуммаСегментов.Количество() > 1 Тогда
					чСуммаСегментов = Число(мСуммаСегментов[1]) + Число(мЧисло0[Т]);
					мСуммаСегментов = РазбитьЧислоНаСегменты(чСуммаСегментов);
					
					мРезультатСложения.Добавить(мСуммаСегментов[0]);
				Иначе
					мРезультатСложения.Добавить(мЧисло0[Т]);
				КонецЕсли;
				
				Продолжить;
			КонецЕсли;
			
			чСуммаСегментов = Число(мЧисло1[Т]) + Число(мЧисло0[Т]);
			Если мСуммаСегментов.Количество() > 1 Тогда
				чСуммаСегментов = чСуммаСегментов + Число(мСуммаСегментов[1]);
			КонецЕсли;
			мСуммаСегментов = РазбитьЧислоНаСегменты(чСуммаСегментов);
			
			мРезультатСложения.Добавить(мСуммаСегментов[0]);
		КонецЦикла;
		
		Если мСуммаСегментов.Количество() > 1 Тогда
			мРезультатСложения.Добавить(мСуммаСегментов[1]);
		КонецЕсли;
		
		мРезультат = мРезультатСложения;
	КонецЦикла;
	
	Возврат мРезультат;
	
КонецФункции

Функция ПеремножитьСегментыЧисел(мСегменты0, мСегменты1)
	
	// Смысл таков, как при умножении в столбик:
	// 00. Т = 0;
	// 01. Е = 0;
	// 02. Сегмент [Т] индекса массива 1 умножаем на сегмент [Е] индекса массива 0.
	// 03. Если есть результат прошлой итерации вычисления, прибавляем к результату вычисления (02) содержимое его индекса [1].
	// 04. Разбиваем результат вычисления (03) на сегменты.
	// 05. Добавляем в мПромежуточный сегмент результат вычисления (04).
	// 06. Е = Е + 1. Повторяем с (02), пока Е <= ВГраница массива 0.
	// 07. Добавляем разряды чДлинаСегмента * Т в мПромежуточный (также, сегментами, по чДлинаСегмента цифр, нулей).
	// 08. Добавляем в мПредрезультатный мПромежуточный.
	// 09. Очищаем мПромежуточный.
	// 10. Е = 0. Т = Т + 1. Повторяем с (02), пока Т <= ВГраница массива 1.
	// 11. Вызываем функцию сложения в столбик с параметром мПредрезультатный.
	// 12. Результат исполнения функции (11) помещаем в массив мРезультат.
	// 12. Возвращаем мРезультат.
	
	сРазрядность = Формат(0, сФорматСегмента);
	
	чВГраница0 = мСегменты0.ВГраница();
	чВГраница1 = мСегменты1.ВГраница();
	
	мПредрезультатный = Новый Массив;
	Для Т = 0 по чВГраница1 Цикл
		мПромежуточный = Новый Массив;
		мРезультатПрошлойИтерации = Новый Массив;
		Для Е = 0 по чВГраница0 Цикл
			чРезультатУмноженияСегментов = Число(мСегменты0[Е]) * Число(мСегменты1[Т]);
			Если мРезультатПрошлойИтерации.Количество() > 1 Тогда
				чРезультатУмноженияСегментов = чРезультатУмноженияСегментов + Число(мРезультатПрошлойИтерации[1]);
			КонецЕсли;
			
			мРезультатПрошлойИтерации = РазбитьЧислоНаСегменты(чРезультатУмноженияСегментов);
			мПромежуточный.Добавить(мРезультатПрошлойИтерации[0]);
			Если Е = чВГраница0
				 И мРезультатПрошлойИтерации.Количество() > 1 Тогда
				мПромежуточный.Добавить(мРезультатПрошлойИтерации[1]);
			КонецЕсли;
		КонецЦикла;
		
		// Для индексов, начиная с 1 добавляем чДлинаСегмента нулей в конец массива для каждой итерации Т
		Для Е = 1 по Т Цикл
			мПромежуточный.Вставить(0, сРазрядность);
		КонецЦикла;
		
		мПредрезультатный.Добавить(мПромежуточный);
	КонецЦикла;
	
	мРезультат = СложитьСегментыЧисел(мПредрезультатный);
	
	Возврат мРезультат;
	
КонецФункции

Функция РазбитьЧислоНаСегменты(Знач сЧисло)
	
	Если ТипЗнч(сЧисло) = Тип("Число") Тогда
		сЧисло = Формат(сЧисло, "ЧН=; ЧГ=");
	КонецЕсли;
	
	// Сюда будем помещать сегменты числа
	мРезультат = Новый Массив;
	
	Пока НЕ ПустаяСтрока(сЧисло) Цикл
		// Вставляем крайний правый сегмент из чДлинаСегмента цифр
		сСегмент = Формат(Число(СокрЛ(Прав(сЧисло, чДлинаСегмента))), сФорматСегмента);
		мРезультат.Добавить(сСегмент);
		
		// Удаляем крайний правый сегмент из числа
		сЧисло = Лев(сЧисло, СтрДлина(сЧисло)-чДлинаСегмента);
	КонецЦикла;
	
	Если мРезультат.Количество() = 0 Тогда
		мРезультат.Добавить(Формат(0, сФорматСегмента));
	КонецЕсли;
		
	// Возвращаем результирующий массив, содержащий сегменты числа в обратном порядке их следования.
	// Индекс массива обозначает разрядность. Рассчитывается по формуле: чДлинаСегмента*Индекс
	Возврат мРезультат;
	
КонецФункции

Процедура ВычислитьСуммуЦифрРезультата()
	
	СтрДлинаРезультата = СтрДлина(Результат);
	
	СуммаЦифрРезультата = 0;
	Для Т = 1 по СтрДлинаРезультата Цикл
		СуммаЦифрРезультата = СуммаЦифрРезультата + Число(Сред(Результат, Т, 1));
	КонецЦикла;
	
КонецПроцедуры

Процедура КнопкаВычислитьНажатие(Элемент)
	
	Если ГраницаФакториала > 2000 Тогда
		Если Вопрос("Вычисление может занять ОЧЕНЬ длительное время (до 10 минут при вычислении 4900 факториал, овер 10 минут далее)!
					|Вы уверены, что действительно хотите вычислить "+Строка(ГраницаФакториала)+" факториал?!", РежимДиалогаВопрос.ДаНет, , КодВозвратаДиалога.Нет, "ВЫ ТОЧНО УВЕРЕНЫ?!") = КодВозвратаДиалога.Нет Тогда
			Возврат;
		КонецЕсли;
	КонецЕсли;
	
	Сообщить("Начато вычисление "+Формат(ГраницаФакториала, "ЧН=; ЧГ=")+"!...");
	НачатьЗамерПроизводительности();
	
	Результат = "";
	СуммаЦифрРезультата = 0;
	
	мСегментыРезультата = Новый Массив;
	мСегментыРезультата.Добавить("1");
	Для Т = 2 по ГраницаФакториала Цикл
		сТекЧисло = Формат(Т, "ЧН=; ЧГ=");
		
		мСегментыТекЧисла = РазбитьЧислоНаСегменты(сТекЧисло);
		
		мСегментыРезультата = ПеремножитьСегментыЧисел(мСегментыРезультата, мСегментыТекЧисла);
	КонецЦикла;
	
	Для каждого Сегмент из мСегментыРезультата Цикл
		Результат = Сегмент + Результат;
	КонецЦикла;
	
	Если ПустаяСтрока(Результат) Тогда
		Результат = "0";
	Иначе
		Пока Лев(Результат, 1) = "0" Цикл
			Результат = Сред(Результат, 2);
		КонецЦикла;
	КонецЕсли;
	
	ВычислитьСуммуЦифрРезультата();
	
	мРезультатЗамера = ЗавершитьЗамерПроизводительности();
	Сообщить("Вычисление "+Формат(ГраницаФакториала, "ЧН=; ЧГ=")+"! завершено. Время вычисления: " + мРезультатЗамера[0] + "сек.");
	
КонецПроцедуры

чДлинаСегмента = 8;

сФорматСегмента = "ЧЦ=" + чДлинаСегмента + "; ЧН=; ЧВН=; ЧГ=";

Попытка
	обMSScriptControl = Новый COMОбъект("MSScriptControl.ScriptControl");
	обMSScriptControl.language = "javascript";
Исключение
	Сообщить("Невозможно подключить MSScriptControl.ScriptControl, некоторые функции будут недоступны.");
КонецПопытки;
мЗамерыПроизводительности = Новый Массив;

Факториал расчет факториала сумма цифр факториала программирование примеры кода

См. также

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

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

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

1 стартмани

30.01.2024    1757    stopa85    12    

33

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

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

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

19.10.2023    4432    user1959478    50    

34

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

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

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

1 стартмани

09.06.2023    7472    4    SpaceOfMyHead    17    

56

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

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

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

1 стартмани

21.03.2022    7857    7    kalyaka    11    

44

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

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

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

16.12.2021    4451    fishca    13    

36

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

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

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

12.10.2021    8846    John_d    73    

46

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

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

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

31.08.2021    7814    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. DrAku1a 1679 07.12.15 02:03 Сейчас в теме
Круто! Давай ещё произвольные степени чисел, например - чему равно: (9^9)^9?
2. pwn 44 07.12.15 12:04 Сейчас в теме
Функция ниже, вроде тоже вычисляет факториал. Или это немного не то?

&НаКлиенте
Процедура ВычислитьФакториал(Команда)
	Факториал = 1;
	Пока Параметр > 0 Цикл
		Факториал = Факториал * Параметр;
		Параметр = Параметр - 1; 
	КонецЦикла; 
	Факториал = СтрЗаменить(Строка(Факториал), Символы.НПП, "");
	Сообщить(Факториал);
	Сообщить(СтрДлина(Факториал));
КонецПроцедуры
Показать
3. pwn 44 07.12.15 12:24 Сейчас в теме
Понял в чем "подвох". Спасибо за решение.
4. catsam 108 07.12.15 14:37 Сейчас в теме
(3) pwn, вот-вот - я сначала тоже так отреагировал. А потом _внезапно_ вспомнил про такую штуковину, как переполнение. =) Кстати, 1С ещё мягко это обрабатывает - просто обрезает левую часть результата. А вот когда не 1С считает, а, например, та же C# - там падение гарантировано. =)))

(1) DrAku1a, а это тоже задача на переполнение - весь необходимый код уже имеется тут. Зачем же плодить лишние сущности? =)
5. alex_4x 85 26.01.16 12:04 Сейчас в теме
Однозначно - ПЛЮС.
Еще бы возведение в произвольную степень, деление, просто умножение, вычисление числа Пи! и поиск простых чисел.
Кстати в поиске простых чисел есть некий подход, который позволяет пропускать те диапазоны, где простого числа не может быть.

Кстати есть интересная форма записи чисел (любых) система счисления, основанная на простых числах
Каждому разряду соответствует простое число и в разряде - 0 или 1. Таким образом любое число может быть представлено как сумма N количества РАЗНЫХ простых чисел. При этом длина записи для чисел больших порядков становится короче, чем например при использовании двоичной системы.
6. ildarovich 7850 26.01.16 12:30 Сейчас в теме
Для саморазвития, конечно, полезно, но вот вопрос: а знал ли автор, затевая программирование, что в платформе уже реализованы вычисления неограниченной разрядности? Что сколько угодно знаков факториала получается и так обычным умножением. То есть вместо
Использовано разбиение строкового представления числа на части по N цифр
в платформе использовано разбиение представление числа на части по 9 разрядов! По этой ссылке есть более подробное обсуждение:
http://forum.infostart.ru/forum24/topic122109/message1275993/#message1275993

Почему именно 9 разрядов? - Думаю, потому, что 32-битное целое как раз укладывается в это представление и элементарные операции над частями по 9 десятичных цифр можно делать как операции над 32-битными целыми.
7. catsam 108 29.01.16 11:24 Сейчас в теме
(6) ildarovich,
Несомненно, автор знал. Как следует из (4).
И несомненно, 1С прекрасно обрабатывает "вычисления неограниченной разрядности". Вот только при выводе результата, он, к сожалению, как это ни печально, обрезается.

Так что теории - это, конечно, хорошо, но попробовать на практике, наверное, все же стоило бы, прежде чем прозрачно намекать на бесполезность кода. ;)
И да - этот код написан и выложен сюда в образовательных целях. =) Несомненно, расчет факториала в бизнесе нафиг никому не нужен. И конечно, есть множество библиотек, которые считают его на порядки быстрее, если он, конечно, вдруг понадобился. Но вот только использование библиотек никак не поможет в, как Вы правильно выразились, "саморазвитии".

С уважением.
8. ildarovich 7850 29.01.16 12:27 Сейчас в теме
(7) а почему не пробовали просто вывод организовать, а сразу стали всю длинную арифметику делать? Вывод по 9 цифр, например? Если сами расчеты делаются, результат хранится, а проблема просто в выводе? Не было бы это проще?
9. catsam 108 17.02.16 16:17 Сейчас в теме
(8) Ну, во-первых, насколько проблема именно в выводе, а не в _хранении_ итогового значения "внутрях" 1С, я не проверял. И, честно говоря, не собираюсь. Ибо это проблема не моя, а 1С.
А во-вторых, как я уже говорил в (7), "этот код написан и выложен сюда в образовательных целях". Знаете, есть такая штука - образование? Вот это оно и есть. Неофит придет сюда, взглянет, код почитает и, есть вероятность, где-то и в чем-то продвинется. Такие вот дела...
Лично мне задача показалась прикольной. Стоящей того, чтобы реализовать именно её, а не "вытаскивание из недр 1С результата вычислений, который она самостоятельно отобразить не в состоянии". =)
Оставьте свое сообщение