2

整数の素数分解要素を昇順で出力する再帰関数を作成する必要があります。

void printPrimeFactors(int num)
{
int div;

if (isPrime(num) == true)
    cout << num << " ";

else
{
    for (div = 2; div < num; div++)
    {
        if (isPrime(div) == true && num%div == 0)
            printPrimeFactors(num/div);
    }
}

私は何が間違っているのですか？20の私の出力は次のとおりです。

5 2 5 2 2

私の最小の入力は素数であり、再帰関数の小さい入力はですnum div (smallest prime divider of num)。

4

2 に答える 2

5

私は次のことがうまくいくと信じています：

void printPrimeFactors(int num, int div = 2)
{
        if (num % div == 0) {
                std::cout << div << " ";
                printPrimeFactors(num / div, div);
        } else if (div <= num) {
                printPrimeFactors(num, div + 1);
        }
}

要求に応じて、再帰は必要ではなく、簡単に反復に変換できますが、再帰的です。

元のバージョンが完全に機能しない理由は2つあります。

  1. 印刷の位置が間違っているため、要素が降順で印刷されます。
  2. 再帰呼び出しの後、さらに除数を試し続けると、出力に重複する要素が表示されます。
于 2012-12-07T18:14:43.473 に答える
1

NPEは（末尾）再帰バージョンを提供しています。反復バージョンは次のとおりです。

ここで行うことは次のとおりです。

  1. 最初に考えられる除数は2です。その値を試してください。
  2. 数値を均等に除算する場合は、除数を出力し、目標数をその除数で除算します。
  3. 除数されない場合は、次の除数を試してください。div += 1。

div分割するときは増分しないことに注意してください。これは、のように複数回分割する場合が原因20です2。

void printPrimeFactors(int num) {
    int div = 2;

    while (num != 1) {
        if (num % div == 0) {
            cout << num << " ";
            num /= div;
        } else {
            div += 1;
        }
    }
}
于 2012-12-07T18:24:13.707 に答える