12

正の整数の因数のすべての一意の組み合わせを出力する最も効率的なアルゴリズムは何ですか? たとえば、指定された数値が 24 の場合、出力は次のようになります。

24*1
12*2
8*3
6*4
6*2*2
4*3*2
3*2*2*2

ここで、6*4 が出力されたときに 4*6 が出力されないことに注意してください。したがって、基本的には、順序を考慮せずに一意のサブセットを取る問題です (問題の見方の 1 つ)。ただし、目的は最速で実行される関数を用意することであるため、データ構造に因子を格納してさらに操作を行うには、より多くの時間がかかる可能性があります。アルゴリズムを試してコードを下に貼り付けましたが、目的の結果が得られないようです。再帰呼び出しで間違いを犯しています。これを行う効率的な方法を理解するのを手伝ってもらえますか?

public static void printfact(int num){
        int temp=0;
        for(int i=num-1;i>=num/2;i--){
            if(num % i == 0){
                temp = num/i;
                System.out.println(temp + " * " + i);
                if(isprime(i)==false){
                    System.out.print(temp + " * ");
                    printfact(i);
                }
            }
        }
}
4

9 に答える 9

5

さらに 2 つの入力、つまり for ループで i の現在の値を引き継いで後続のリダクションを実行するための文字列と、重複した反転を出力しないタイミングを知るための一時的な int、つまり 8*3 と 3* をさらに 2 つ受け取るこの再帰的アプローチを試してください。 8.

public static void printFactors(int number, String parentFactors, int parentVal) {
    int newVal = parentVal;
    for (int i = number - 1; i >= 2; i--) {

        if (number % i == 0) {
            if (newVal > i) {
                newVal = i;
            }
            if (number / i <= parentVal && i <= parentVal
                    && number / i <= i) {
                System.out.println(parentFactors + i + "*" + number / i);
                newVal = number / i;
            }

            if (i <= parentVal) {
                printFactors(number / i, parentFactors + i + "*", newVal);
            }
        }

    }

}

そして、printFactors(12,'',12) を使用してこのメ​​ソッドを呼び出し
ます。このアプローチに欠陥がある場合はお知らせください。ありがとう！

于 2013-02-28T01:24:34.767 に答える
2

このコードは、数値のすべての因数を見つけて、それらを (ローカルおよびグローバルに) 並べ替えます。

public class PrimeFactors {

   final SortedSet< List< Integer >> _solutions = new TreeSet<>(
      new Comparator<List<Integer>>(){
         @Override
         public int compare( List<Integer> left, List<Integer> right ) {
            int count = Math.min( left.size(), right.size());
            for( int i = 0; i < count; ++i ) {
               if( left.get(i) < right.get(i)) {
                  return -1;
               }
               if( left.get(i) > right.get(i)) {
                  return +1;
               }
             }
            return left.size() - right.size();
         }});

   public SortedSet< List< Integer >> getPrimes( int num ) {
      _solutions.clear();
      getPrimes( num, new LinkedList< Integer >());
      return _solutions;
   }

   private void getPrimes( int num, List< Integer > solution ) {
      for( int i = num - 1; i > 1; --i ) {
         if(( num % i ) == 0 ) {
            int temp = num / i;
            List< Integer > s = new LinkedList<>();
            s.addAll( solution );
            s.add( temp );
            s.add( i );
            Collections.sort( s );
            if( _solutions.add( s )) { // if not already found
               s = new LinkedList<>();
               s.addAll( solution );
               s.add( temp );
               getPrimes( i, s );
             }
         }
      }
   }
   public static void main( String[] args ) {
      SortedSet< List< Integer >> solutions =
         new PrimeFactors().getPrimes( 24 );
      System.out.println( "Primes of 24 are:" );
      for( List< Integer > l : solutions ) {
         System.out.println( l );
      }
   }
}

出力:

Primes of 24 are:
[2, 2, 2, 3]
[2, 2, 6]
[2, 3, 4]
[2, 12]
[3, 8]
[4, 6]
于 2013-02-27T21:34:05.997 に答える
2

C/C++ で再帰、ソート、またはスタックを使用しないソリューションがあります。

#include <vector>
#include <iostream>

// For each n, for each i = n-1 to 2, try prod = prod*i, if prod < N.

int
g(int N, int n, int k)
{
        int i = k;
        int prod = n;
        std::vector<int> myvec;

        myvec.push_back(n);
        while (i > 1) {
                if (prod * i == N) {
                        prod = prod*i;
                        myvec.push_back(i);
                        for (auto it = myvec.begin();
                                it != myvec.end(); it++) {
                                std::cout << *it << ",";
                        }
                        std::cout << std::endl;
                        return i;
                } else if (prod * i < N) {
                        prod = prod*i;
                        myvec.push_back(i);
                } else { i--;}
        }

        return k;
}

void
f(int N)
{
        for (int i = 2; i <= N/2; i++) {
                int x = g(N, i, i-1);
                // Extract all possible factors from this point
                while (x > 0) {
                        x = g(N, i, x-1);
                }
        }
}

int
main()
{
        f(24);

        return 0;
}

出力は次のようになります。

$ ./a.out
    3,2,2,2,
    4,3,2,
    6,4,
    6,2,2,
    8,3,
    12,2,
于 2016-01-16T20:20:31.850 に答える
2

1) もしi < numとi > num/2ならnum % i == num - i. （証明するのは簡単です。）したがって、forループはより大きなすべての整数を無意味にチェックしnum/2、ifステートメントは . を使用して一度だけ成功しtemp == 2ます。それはあなたが望んでいたことではないと思います。

2）あなたがそれを修正した場合、再帰は多くの答えを生成する必要があるかもしれません。ただし、印刷temp *は 1 回だけです。そのため、出力は少し奇妙に見えます。

3)isprimeは不要です。num以下の点に従えば、素数であるかどうかにかかわらず、常に正当な要素です。

4) 最後に、同じ因数分解を何度も出力しないようにする方法を理解する必要があります。簡単な解決策は、因子が単調に増加しない因数分解のみを生成することです(例のように)。それを行うには、再帰はいくつかの最大因数 (以前に発見された因数になります) で因数分解を生成する必要があります。そのため、再帰関数には (少なくとも) 2 つの引数が必要です: 因数分解する数と最大許容因数です。(ポイント 4 として指摘した問題にも対処する必要があります。)

次の Python コードは (私が信じている) 問題を解決しますが、まだかなりの数の不必要な分割を行っています。Python スタイルとは異なり、ジェネレーターとして機能する代わりに各因数分解を出力します。これは、Java への変換が容易になるためです。

# Uses the last value in accum as the maximum factor; a cleaner solution
# would have been to pass max_factor as an argument.
def factors(number, accum=[]):
  if number == 1:
    print '*'.join(map(str, accum))
  else:
    if accum:
      max_factor = min(accum[-1], number)
    else:
      max_factor = number
    for trial_factor in range(max_factor, 1, -1):
      remnant = number / trial_factor
      if remnant * trial_factor == number:
        factors(remnant, accum + [trial_factor,])

forステートメントを最適化することができます。たとえば、 を計算するremnantと、次remnantは少なくとも 1 つ大きくなければならないことがわかるため、が小さいtrial_factor場合は一連の値をスキップできます。remnant

于 2013-02-27T21:30:16.640 に答える
0 
vector<unsigned int> GetAllFactors(unsigned int number)
{
    vector<unsigned int> factors;

    for (int i = 2; i <= number; i++)
    {
        if (number % i == 0)
        {
            factors.push_back(i);
        }
    }

    return factors;
}

void DoCombinationWithRepetitionFactors(vector<unsigned int> allFactors, unsigned currentProduct, unsigned targetProduct, vector<unsigned int> currentFactorSet, unsigned currentFactorIndex)
{
    if (currentProduct == targetProduct)
    {
        for (auto a : currentFactorSet)
        {
            cout << a << " , ";
        }

        cout << endl;

        return;
    }


    for (int i = currentFactorIndex; i < allFactors.size(); i++)
    {
        if (currentProduct * allFactors[i] <= targetProduct)
        {
            currentFactorSet.push_back(allFactors[i]);
            DoCombinationWithRepetitionFactors(allFactors, currentProduct * allFactors[i], targetProduct, currentFactorSet, i);
            currentFactorSet.pop_back();
        }
    }
}
于 2014-07-12T02:21:15.353 に答える
0 
bool isprime(int n){
for(int i=2; i<=sqrt(n); i++)
    if(n%i==0)
        return false;
return true;
}

void printprime(int n){

int i,j,y=n;

while(y%2==0){
    cout<<"2 * ";
    y/=2;
}

for(i=3; i<=sqrt(y); i+=2){
    while(y%i==0){
        cout<<i<<" * ";
        y/=i;
    }
}

if(y>2)
    cout<<y;
}

void allfacs(int n){

int i;
unordered_set<int> done;

for(i=2; i<sqrt(n); i++){
    if(n%i==0){
        cout<<i<<" * "<<n/i<<endl;

        if(!isprime(i) && done.find(i) == done.end()){
            done.insert(i);
            printprime(i);
            cout<<n/i<<endl;
        }
        if(!isprime(n/i) && done.find(n/i) == done.end()){
            done.insert(n/i);
            cout<<i<< " * ";
            printprime(n/i);
            cout<<endl;
        }
    }
}
}
于 2014-12-18T22:23:37.450 に答える
0

私はこれを思いつきました、読みやすく理解しやすいようです。それが役に立てば幸い！

def getFactors(num):

    results = []

    if num == 1 or 0:
        return [num]

    for i in range(num/2, 1, -1):

        if (num % i == 0):
            divisor = num / i

            if(divisor <= i):
                results.append([i, divisor])

            innerResults = getFactors(divisor)

            for innerResult in innerResults:
                if innerResult[0] <= i:
                    results.append([i] + innerResult)

    return results
于 2017-01-11T23:14:00.170 に答える