与えられた素因数分解は、再帰なしでC++のすべての要素を反復します。

Question

マップにp1^x1 * p2^x2 *という素因数分解を与えました。 私はすべての要素、プライムとコンポジットを反復処理する必要があります。 再帰を使って解を書くことができました。

#include <iostream> 
#include <map> 
#include <cstdlib> 

using namespace std; 

struct PROBLEM { 

    int mx = 400; 
    map<int, int> mp = {{2, 2}, {3, 1}, {5, 1}, {7, 2}}; 
    int lastPrimeFactor = 7; 
    int num = 1; 

    auto solve() { 
     rec(2, 0); 
     return 0; 
    } 

    int next_prime_factor(int p) { 
     return (p == 2) ? 3 : (p == 3) ? 5 : (p == 5) ? 7 : -1; 
    } 

    void rec(int prime, int power) { 

     if (mx == 0) { 
      cout << "Infinite recursion\n\n"; 
      exit(0); 
     } else --mx; 

     if (prime == lastPrimeFactor && power > mp[prime]) { 
      return; 
     } 

     if (power < mp[prime]) { 
      num *= prime; 
      cout << num << endl; 
      rec(prime, power + 1); 
      num /= prime; 
     } 

     if (prime != lastPrimeFactor) { 
      rec(next_prime_factor(prime), 0); 
     } 

    } 

}; 


int main() { 
    PROBLEM().solve(); 
    return 0; 
} 

質問：

1）これらの要因を生成するための任意のより高速な方法はありますか？

2）可能であれば、再帰をwhileループで置き換えることはできますか？

Answer 1

1. いいえ。あなたの再帰アルゴリズムは、除数の数と全く同じ時間に動作します。漸近的に高速に動作するアルゴリズムでは、これらの数値をすべて印刷することはできません。

2. はい。すべての再帰アルゴリズムは、ローカル変数を格納するためにstd::stackを使用して非再帰的な方法で書き直すことができます。しかし、あなたのケースでは、これはおそらく高速ではなく、コードを読みにくくするので、そのような書き換えは望ましくありません。必要に応じて、コードを提供することができます。再帰なし

Answer 2

、それは次のようになります。

bool increase(const std::vector<std::pair<std::size_t, std::size_t>>& v, 
       std::vector<std::size_t>& it) 
{ 
    for (std::size_t i = 0, size = it.size(); i != size; ++i) { 
     const std::size_t index = size - 1 - i; 
     ++it[index]; 
     if (it[index] > v[index].second) { 
      it[index] = 0; 
     } else { 
      return true; 
     } 
    } 
    return false; 
} 

std::size_t pow(std::size_t n, std::size_t power) 
{ 
    std::size_t res = 1; 
    for (std::size_t i = 0; i != power; ++i) { 
     res *= n; 
    } 
    return res; 
} 

void do_job(const std::vector<std::pair<std::size_t, std::size_t>>& v, 
      std::vector<std::size_t> it) 
{ 
    std::size_t res = 1; 
    for (std::size_t i = 0; i != v.size(); ++i) { 
     res *= pow(v[i].first, it[i]);   
    } 
    std::cout << res << std::endl; 
} 

void iterate(const std::vector<std::pair<std::size_t, std::size_t>>& v) 
{ 
    std::vector<std::size_t> it(v.size(), 0); 

    do { 
     do_job(v, it); 
    } while (increase(v, it)); 
} 

Demo

だから、基本的に、我々は{2, 1, 1, 2}に{0, 0, 0, 0}からを数える。