从素数因子中重构一个除数列表（递归地）

问题描述：

我有一个数字的主要因子列表，如下形式： int [] factors = {因子数量，factor1，poweroffactor1，factor2，poweroffactor2， ...};从素数因子中重构一个除数列表（递归地）

我想要得到的动态等效嵌套的循环，将产生的所有因素，这里的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] 因素=上面指定格式的主要因素清单prodsofar [] =所有元素都是1 listsofar =空的列表

如何重置prodsofar，使其不会“爆炸”，而只是做我所概述的？注意：作为测试，使用2310，因为在当前代码下，要添加的除数为负数（int溢出）。

这看起来不必要地复杂化。什么是'prodsofar'和'listsofar'应该代表什么？ – Beta 2011-05-02 19:30:46

当前产品（要传递给函数的下一个实例以使其可以相乘），并且listsofar是除数列表。 – soandos 2011-05-02 19:34:39

我知道C++，但不是C＃。即使如此，我看到了什么样的bug。循环限制看起来不正确，'prodsofar'可以是'int'，而不是'int []'，你可以使用'* ='并且不要使用'Pow'。在尝试2310之前，您是否尝试过在2上运行它？ – Beta 2011-05-02 21:38:58

答

你想到的递归算法的想法是保持积分的除数列表。对于这一点，下面的代码是如何做到这一点的例子（保留您的符号：因为“除数”和“因素”的意思是完全一样的东西，多术语是不幸）：

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

答

这只是一个“产生所有组合”的问题。您可以使用您最喜爱的搜索引擎找到在C＃中执行此操作的方法; here就是一个例子。

请注意，您需要将“使用k次的素数”映射到{p, p, p, ...}（k次）。

我的意思是我可以这样做，但真的，我只是想要所有的产品，而且看起来如果我把它当作组合问题，我会招致额外的开销。 – soandos 2011-05-02 22:02:18

，你可以用你给我发送链接的库编写一个示例来看看它的样子吗？ – soandos 2011-05-02 22:18:26

此外，它不能处理与重复的组合，这是我需要的关键部分。 – soandos 2011-05-02 22:56:11

答

这类似于接受的答案 - 它可能是一个更清晰一点的人试图了解怎么回事...

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

从素数因子中重构一个除数列表（递归地）

相关推荐