Восстановление списка делителей из простых факторов (рекурсивно) - PullRequest
Новая
       23

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

1 голос
/ 02 мая 2011

У меня есть список основных факторов числа в следующей форме: int [] factor = {количество факторов, 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] factor = список основных факторов в указанном выше формате prodsofar [] = все элементы равны 1 listsofar = пустой список

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

Ответы [ 3 ]

1 голос
/ 03 мая 2011

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

    // 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.

1 голос
/ 03 мая 2011

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

Обратите внимание, что вам необходимо сопоставить "Prime p used k times" с {p, p, p, ...} (k times).

0 голосов
/ 24 октября 2013

Это похоже на принятый ответ - оно может быть немного понятнее тому, кто пытается понять, что происходит ... 

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
...