2

1234567890 までの数値を再帰的に因数分解するメソッドを作成する必要があります。現在のアプリケーションは、StackOverflowError をスローする前に小さな数値でのみ動作します。再帰呼び出しが多すぎることが問題であることは理解していますが、呼び出しの数を減らす方法がわかりません。

再帰的である必要があります。

解決策は、アルゴリズムの背後にある数学に関連していると思います。私はさまざまな反復ソリューションを見てきましたが、少ない呼び出しで再帰的に実行することに頭を悩ませているようには見えません。コード：

public static boolean isPrime(int input, int i) {
    if (i <= 2) {
        return true;
    }
    if (input % i != 0) {
        return isPrime(input, i-1);
    } else {
        factors(input, i);
        return false;
    }
}
public static void factors(int input, int i) {
    if (i <= 1) {
        System.out.printf(" %d", 1);
    } else {
        if (input % i == 0) {
            System.out.printf(" %d", i);
        }
        factors(input, i - 1);
    }
}

によって開始されます。

System.out.println("What integer would you like to factor?");
    num1 = scan.nextInt();
    if(isPrime(num1, num1 - 1)){
        System.out.println("Input is a prime number");
    } else {
        System.out.println(" factors\nInput isn't a prime number.");
    }
4

5 に答える 5

2

Factor メソッドを非再帰的に変更します (再帰的である必要がない場合)。

 public static void factors(int input, int i) {
     for(int j = i; j >= 1; j--) {
         if (input % j == 0)
             System.out.println(j);
     } 
}

編集:以下のようなものは、この問題を解決するための再帰的なアプローチです。

public void isPrime(int num1)
{
int count=countFactors(num1);
if(count==0)
System.out.println("No is prime");
}

public int countFactors(int num,int i)
{

if(i>num/2)return 0;
if(num%i==0)
{
System.out.println(i);
return 1+countFactors(num,i+1);
}

}
于 2013-04-14T09:33:27.727 に答える
1

再帰的である必要があるのは、宿題の問題だからだと思います。したがって、私はそれを行う方法を教えませんが、あなたの数学の何が問題なのかを教えてください. あなたのアルゴリズムは部分的に正しいように見えますが、(a) 見つかった各因数で 'n' を割るのを忘れていることと、(b) 小さい数を上からではなく大きな数から下に因数を探している点が異なります。スタック オーバーフローは解決されませんが、開始して 2 から sqrt(n) までカウントする方がよいでしょう。

素因数を割った後に残りの数を因数分解するために、ループ内の因数を探し、再帰の使用を予約する必要があります (本当に使用する必要がある場合)。6 桁の素数を渡されたくないので、因数がないことを証明するために 100 万レベルのスタックが必要です。つまり、これは再帰ではなく単純なループにする必要があります。

return isPrime(input, i-1);

...そしてこれは再帰的にすることができます:

要因（入力、i）;

于 2013-04-14T10:22:10.703 に答える
0

Java のスタック サイズを増やします。スタックサイズを増やす方法を検索できます

于 2013-04-14T09:27:35.017 に答える