1

次の形式の数の素因数のリストがあります。int[]factors= {number of 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;
    }

元の引数は次のとおりです。level=factors[0]factor=上記で指定された形式の素因数のリストprodsofar[]=すべての要素は1ですlistsofar=空のリスト

「爆発」せず、代わりに私が概説したことを実行するように、prodsofarをリセットするにはどうすればよいですか？注：テストとして、2310を使用します。現在のコードでは、追加される除数は負です（intオーバーフロー）。

4

3 に答える 3

1

これは単なる「すべての組み合わせの生成」の問題です。お気に入りの検索エンジンを使用して、C＃でこれを行う方法を見つけることができます。これがその一例です。

{p, p, p, ...「primepusedktimes」を}（k times）にマップする必要があることに注意してください。

于 2011-05-02T21:33:53.897 に答える
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);

600の24の約数すべてを出力します。

于 2011-05-02T23:59:37.953 に答える
0

これは受け入れられた答えに似ています-何が起こっているのかを理解しようとしている人にとっては少し明確かもしれません...

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
于 2013-10-24T18:52:11.013 に答える