gifts2017

Факторизация числа

Опубликовал Андрей Захаров (zaxarovsky) в раздел Программирование - Практика программирования

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

Представлен алгоритм решения задачи методом перебора возможных делителей.
Функция ProtoText для формирования порождающего запроса, генерирующего числовую последовательность, взята из статьи Порождающий запрос от ildarovich.
Обработка прилагается.

Процедура Факторизация()
	ПроверкаЧисло = 0;
	ТабРазложение.Очистить();
	
	Половина = Цел((ЗаданноеЧисло)/2)+1;
	
	МВТ = Новый МенеджерВременныхТаблиц;
	Запрос = Новый Запрос;
	Запрос.МенеджерВременныхТаблиц = МВТ;
	Запрос.УстановитьПараметр("П", ЗаданноеЧисло);	
	Запрос.Текст = ProtoText(Половина)+ 
	";
	|Выбрать X как м Поместить ПотенциальныеМножители0 ИЗ #r 
	|Где X <>1 И  (X = 2 или X = 3 или (X -1)/6 - ВЫРАЗИТЬ((X -1)/6 КАК ЧИСЛО(32, 0)) = 0 или (X +1)/6 - ВЫРАЗИТЬ((X +1)/6 КАК ЧИСЛО(32, 0)) = 0);
	|Выбрать 1 как ПростойМножитель, 1 как Кратность Поместить Результат;
	|Выбрать * ИЗ ПотенциальныеМножители0";
	Запрос.Текст = СтрЗаменить(Запрос.Текст, "#r", "r"+Формат(Половина, "ЧГ="));
	
	КоличествоПотенциальныхМножителей = Запрос.Выполнить().Выбрать().Количество();
	ш = 0;
	Накопление = 1;
	Остаток = ЗаданноеЧисло;
	Пока КоличествоПотенциальныхМножителей <> 0 Цикл
		
		Запрос.Текст = "Выбрать м Поместить ПотенциальныеМножители#Замена2_0 из ПотенциальныеМножители#Замена1 
		|Где &П/м - ВЫРАЗИТЬ(&П/м КАК ЧИСЛО(32, 0)) = 0; 
		|Выбрать м Поместить ПотенциальныеМножители#Замена2 Из ПотенциальныеМножители#Замена2_0  
		|Где Не м В(Выбрать П2.м Из ПотенциальныеМножители#Замена2_0 как П1 
		|				Внутреннее Соединение ПотенциальныеМножители#Замена2_0 Как П2 
		|			       По П2.м/П1.м<>1 и П2.м/П1.м - Выразить(П2.м/П1.м КАК ЧИСЛО(32, 0))=0);
		|Выбрать ПростойМножитель, Кратность  Поместить РезультатВрем ИЗ Результат; Уничтожить Результат;  
		|Выбрать ПростойМножитель, Кратность Поместить Результат ИЗ РезультатВрем 
		|Объединить Все 
		|Выбрать м, 1 Из ПотенциальныеМножители#Замена2; Уничтожить РезультатВрем;
		|Уничтожить ПотенциальныеМножители#Замена2_0;
		|Выбрать * ИЗ ПотенциальныеМножители#Замена2";
		
		Запрос.Текст = СтрЗаменить(Запрос.Текст, "#Замена1", Формат(ш, "ЧРГ=; ЧН=; ЧГ="));
		Запрос.Текст = СтрЗаменить(Запрос.Текст, "#Замена2", Формат(ш+1, "ЧРГ=; ЧГ="));
		
		ТабПроизведение = Запрос.Выполнить().Выгрузить();
		
		НовоеНакопление = 1;
		Для каждого Стр Из ТабПроизведение Цикл
			НовоеНакопление = НовоеНакопление*Стр.м;
		КонецЦикла;
		Накопление = Накопление*НовоеНакопление;
		КоличествоПотенциальныхМножителей = ТабПроизведение.Количество();
		ш = ш + 1;
		Остаток = Остаток/НовоеНакопление;
		Запрос.УстановитьПараметр("П", Остаток);
	КонецЦикла; 
	
	Если Накопление = 1 Тогда
		ПроверкаЧисло = ЗаданноеЧисло;
		Предупреждение("Простое число!", 2);
	Иначе
		Запрос.Текст = "Выбрать ПростойМножитель, Сумма(Кратность) как Кратность ИЗ Результат где ПростойМножитель <> 1 Сгруппировать по ПростойМножитель";
		ТабРазложение.Загрузить(Запрос.Выполнить().Выгрузить());
		ПроверкаЧисло = Накопление;
	КонецЕсли; 
КонецПроцедуры

См. также

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

Комментарии

1. Никита Грызлов (nixel) 13.11.13 15:58
Я пытаюсь вспомнить все отчеты с какой-либо сложной аналитикой или сложные алгоритмы, вроде автоматического формирования расписания, но не могу представить, где может пригодится факторизация числа.

За алгоритм - определенно плюс, люблю математику в 1с.
Просто любопытно, для каких задач это писалось?
2. Андрей Захаров (zaxarovsky) 13.11.13 16:15
(1) nixel, спасибо за + :)
эта вещь понадобилась мне для более крупной задачи, которая, однако, тоже математического толка, нежели прикладного в смысле применимости для реляционных БД.
Статья выйдет здесь же несколько позднее, там и будут даны комментарии.
3. Никита Грызлов (nixel) 13.11.13 16:28
(2) zaxarovsky, хорошо, жду статью, заинтересовали :)
4. DAnry (DAnry) 13.11.13 21:55
Такие вещи, конечно, не на каждый день. Но может пригодиться. За работу плюс
5. Максим Кузнецов (Makushimo) 18.11.13 07:23
мнээ
это, наверное, круто очень.
Но почему все в виде XML разметки написано?
Текст воспринимается как каша.
6. Андрей Захаров (zaxarovsky) 18.11.13 07:57
(5) Makushimo, хм, это проблемка движка Инфостарта. Задал вопрос техподдержке, подождем ответа.
Иногда отображается нормально.
7. Максим Кузнецов (Makushimo) 18.11.13 08:33
(6) zaxarovsky,
спасибо, подождем
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа