gifts2017

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

Опубликовал Александр Пыров (catsam) в раздел Программирование - Практика программирования

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

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

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

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

=)

Использовано разбиение строкового представления числа на части по 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, некоторые функции будут недоступны.");
КонецПопытки;
мЗамерыПроизводительности = Новый Массив;

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

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

См. также

Подписаться Добавить вознаграждение

Комментарии

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

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

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

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

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

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

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