Восстановление списка делителей из простых множителей (рекурсивно)

#c# #math #recursion #prime-factoring

#c# #математика #рекурсия #разложение на простые множители

Вопрос:

У меня есть список простых множителей числа в следующей форме: int[] factors = {количество множителей, factor1,poweroffactor1,factor2,poweroffactor2, …};

Я хочу получить эквивалент динамически вложенных циклов for, который даст все коэффициенты, где циклы for будут выглядеть примерно так:

 int currentpod = 1;
for(int i=0;i<factors[2];i  )
{
    currentprod *= Math.Pow(factors[1],i);
    for(int j=0;j<factors[4];j  )
    {
         currentprod *= Math.Pow(factors[3],i);
         ...
         //When it hits the last level (i.e. the last prime in the list, it writes it to a list of divisors
         for(int k=0;k<factors[6];k  )
         {
              divisors.Add(Math.Pow(factors[5],k)*currentprod);
         }
    }
}
  

К сожалению, этот код прерывается, поскольку currentprod недостаточно сбрасывается.
Вот фактический код, который я использую, чтобы попытаться выполнить это:

         public static List<int> createdivisorlist(int level, List<int> factors, int[] prodsofar,List<int> listsofar)
    {
        if (level == factors[0])
        {
            prodsofar[0] = 1;
        }
        if (level > 1)
        {
            for (int i = 0; i <= 2*(factors[0]-level) 1; i  )
            {
                prodsofar[level-1] = prodsofar[level] * (int)Math.Pow(factors[2 * (factors[0] - level)   1], i);
                listsofar =  createdivisorlist(level - 1, factors, prodsofar, listsofar);
            }
        }
        else
        {
            for (int i = 0; i <= factors.Last(); i  )
            {
                listsofar.Add(prodsofar[level] * (int)Math.Pow(factors[2 * (factors[0] - level)   1], i));
                if (listsofar.Last() < 0)
                {
                    int p = 0;
                }
            }
            return listsofar;
        }
        return listsofar;
    }
  

исходными аргументами являются:
уровень = факторы[0]
факторы = список простых множителей в формате, указанном выше
prodsfar[] = все элементы равны 1
listsofar = пустой список

Как я могу сбросить prodsfar, чтобы он не «взорвался», а вместо этого просто делал то, что я описал? Примечание: в качестве теста используйте 2310, поскольку в текущем коде добавляемый делитель отрицателен (переполнение int).

Комментарии:

1. Это выглядит излишне сложным. Что prodsofar и listsofar предполагается представлять?

2. текущее произведение (которое должно быть передано следующему экземпляру функции, чтобы его можно было умножить) и listsofar — это список делителей.

3. Я знаю c , но не c #. Несмотря на это, я вижу то, что выглядит как ошибки. Ограничение цикла выглядит неправильно, prodsofar может быть int , а не int[] an, и вы можете использовать *= и покончить с Pow . Вы пробовали запускать его на 2, прежде чем пытаться использовать 2310?

Ответ №1:

Идея рекурсивного алгоритма, который вы имеете в виду, заключается в сохранении накапливающегося списка делителей. Для этого следующий код является примером того, как это сделать (сохраняя ваши обозначения: поскольку «делители» и «факторы» означают одно и то же, множественная терминология неудачна):

 public static List<int> divisors(int[] factors, List<int> foundfactors, int level)
{
    if(level > factors[0]) return foundfactors;

    int current = 1;
    List<int> curpowers = new List<int>();
    for(int i=0; i<factors[2*level] 1;   i)
    {
        curpowers.Add(current);
        current *= factors[2*level-1];
    }
    List<int> newfactors = new List<int>();
    foreach(int d in foundfactors)
        foreach(int n in curpowers)
            newfactors.Add(d*n);
    return divisors(factors, newfactors, level   1);
}
  

Вызовите это чем-то вроде

     // 600 = 2^3 * 3^1 * 5^2
    int[] pfactors = new int[] {3, 2,3, 3,1, 5,2};
    List<int> foundfactors = new List<int> {1};
    List<int> ds = divisors(pfactors, foundfactors, 1);
    foreach(int d in ds) Console.WriteLine(d);
  

который выводит все 24 делителя из 600.

Ответ №2:

Это просто проблема «сгенерировать все комбинации». Вы можете использовать свою любимую поисковую систему, чтобы найти способы сделать это в C #; вот один пример.

Обратите внимание, что вам нужно будет сопоставить «простое число p использовалось k раз» с {p, p, p, ... } (k раз).

Комментарии:

1. я имею в виду, что я мог бы сделать это таким образом, но на самом деле мне просто нужны все продукты, и может показаться, что если я сделаю это как проблему с комбинациями, я понесу дополнительные накладные расходы.

2. и не могли бы вы написать пример того, как это будет выглядеть, используя библиотеку, на которую вы прислали мне ссылку?

3. кроме того, он не может обрабатывать комбинации с повторением, что является ключевой частью того, что мне нужно.

Ответ №3:

Это похоже на принятый ответ — это может быть немного понятнее для того, кто пытается понять, что происходит…

 def divisors_from_primes(primes, v = 1)
  if primes.empty?
    puts v
    return
  end
  p = primes.keys.first
  m = primes[p]
  primes.delete(p)
  0.upto(m) do |power|
    divisors_from_primes(primes, v * (p**power))
  end  
  primes[p] = m
end

/* 72 = 2**3 * 3**2  */

divisors_from_primes({ 2 => 3, 3 => 2})
  

Итак, в этом примере (72) это в основном рекурсивная версия:

 0.upto(3) do |twopower|
  0.upto(2) |threepower|
    puts 2**twopower * 3**threepower
  end
end