2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Поиск всех возможных разложений числа на множители
Сообщение17.01.2007, 16:15 
Добрый день!
Решаю задачу, в которой в одном из действий нужно найти ВСЕ возможные разложения числа 120 на целые множители (т.е. не только на простые).
Например,
120 = 30*4 - одно возможное разложение.
Но 30 = 15*2, т.е. 120 = 15*2*4 - второе возможное разложение.
Но 4 = 2*2, т.е. 15*2*2*2 - третье возможное разложение.
Я пытался пользоваться следущим алгоритмом: сначала ищем все делители числа 120: 1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120, затем делители этих делителей и т.д., но этот алгоритм слишком громоздкий и в нем легко запутаться. Может быть кто-нибудь знает другие способы нахождения таких разложений? И вообще, можно ли оценить, сколько всего вариантов таких разложений будет?
Заранее спасибо.

 
 
 
 
Сообщение17.01.2007, 17:14 
Аватара пользователя
Попробуйте так:
Код:
Разложить(число N, мин.делитель M): список разложений
  Результат = список, состоящий из одного разложения N = [N];
  Цикл по всем A, делящим N, A >= M, A <= кв. корня из N:
    Промежуточный список K = Разложить(число/A, A)
    Цикл по всем разложениям k из K
      Добавить в Результат разложение [A, элементы разложения k]
    Конец цикла
  Конец цикла
Конец

 
 
 
 
Сообщение17.01.2007, 22:11 
Разложите число на простые $A=p_1^{a_1}*...*p_n^{a_n}$ А затем таблица, всех вариантов.
Сам не заметил, что хрень написал. Извините, вот правильно:$((a_1+1)*...*(a_n+1))/2$
Да...и как я мог так.

 
 
 
 
Сообщение17.01.2007, 22:19 
Аватара пользователя
xolms писал(а):
Разложите число на простые $A=p_1^{a_1}*...*p_n^{a_n}$ А затем таблица, всех вариантов.
А всего разложений- $((p_1+1)^{a_1}*...*(p_n+1)^{a_n})/2$

Мне кажется что число разложений найдено неверно. Например, для числа 169 я нашёл только два различных разложения на натуральные сомножители, и 4 - на целые, а по Вашей формуле их должно быть, как минимум, 98 штук?

 
 
 
 
Сообщение18.01.2007, 07:43 
Спасибо всем за помощь!
Извиняюсь за неточность в вопросе - множители должны быть натуральными числами.
У меня получилось 20 возможных комбинаций (без повторений). Вот таблица (серым отмечены повторяющиеся разложения):

Изображение

 
 
 
 
Сообщение18.01.2007, 12:09 
Аватара пользователя
Если число in question является, скажем, n-й степенью простого, то искомое количество разложений равно числу неупорядоченных разбиений n, для которого простой формулы нет.
Из этого заключаю, что нет её и выше (в общем случае, т.е. для n любого вида).
Ну а уж как перебирать - дело вкуса. Я бы шёл от разложения на простые и делал бы примерно так:
Код:
перебор по кол-ву сомножителей (от 2 до скольки можно){
  перебор способов распределения p1 между сомножителями{
    перебор способов распределения p2...{
      ...
    }
  }
}

... чёрт, тоже сложно как-то выходит...

 
 
 
 Re:
Сообщение23.12.2009, 12:14 
Аватара пользователя
xolms в сообщении #49360 писал(а):
Разложите число на простые $A=p_1^{a_1}*...*p_n^{a_n}$ А затем таблица, всех вариантов.
Сам не заметил, что хрень написал. Извините, вот правильно:$((a_1+1)*...*(a_n+1))/2$

Сочуствую, но опять не заметили ... Для 169 и 4 теперь одинаково вариантов получится, но по полтора. :D
Множество разбиений можно частично упорядочить естественным образом - порядок даже решёточным получится, но перечислять элементы этой решётки или даже посчитать их число не так просто. Для последнего можно попробовать рекуррентность написать (возможно она в комбинаторике Холла есть), но толку с неё мало будет.

 
 
 
 Re: Поиск всех возможных разложений числа на множители
Сообщение23.12.2009, 20:46 
Аватара пользователя
см.
topic9585.html
http://mathworld.wolfram.com/UnorderedF ... ation.html
A001055

 
 
 
 Re: Поиск всех возможных разложений числа на множители
Сообщение23.12.2009, 21:13 

(Оффтоп)

Я так понимаю, это в рамках разбора завалов дискуссия возобновилась? А то через три года как-то немного странно выглядит :)

 
 
 
 Re: Поиск всех возможных разложений числа на множители
Сообщение12.04.2010, 12:30 
Эта задача эквивалентна задачи подсчета всех разбиений мультиножества на подмультимножества и пока в общем случае не решена.

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group