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

将您的因子方法更改为非递归（如果不需要递归）

 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 万级堆栈来证明它没有因数。即这需要在一个简单的循环而不是递归中：

返回是素数（输入，i-1）；

...这可以是递归的：

因素（输入，我）；

于 2013-04-14T10:22:10.703 回答
0

增加你的java中的堆栈大小。您可以搜索如何增加堆栈大小

于 2013-04-14T09:27:35.017 回答
0

您似乎用于素数检查的算法是试验除法算法。

还有许多其他方法，但是，按照这个策略，有一个命题指出你只需要检查n的平方根，其中n是你的input。此外，您的谓词没有适当地处理负整数（返回true）。

因此，在第一种方法中，您的算法将是：

public static boolean isPrime(int n) {
    if (n < 2) { return false; }
    return helper_isPrime(n, 2, (int) Math.sqrt(n));
}

在哪里：

private static boolean helper_isPrime(int n, int i, int max) {
    if (i > max) { return true; }
    if (n % i == 0) { return false; }
    return helper_isPrime(n, i+1, max);
}

以两种方法分离可以隔离n < 2. 请注意，n将保持不变，因此测试只需要在流程开始时执行一次。

此外，保理被抛在后面。在我看来，应该从外面问，像这样：

System.out.println("What integer would you like to factor?");
num1 = scan.nextInt();
if(isPrime(num1)){
    System.out.println("Input is a prime number");
} else {
    System.out.println("Input isn't a prime number.");
    int[] fac = factor(n);
    System.out.println("Factors: " + fac.toString());
}

factor您最喜欢的因子算法在哪里。因式分解算法可能会发现它是使用素数执行的最坏情况，但是，由于已经进行了测试，并且由于仅在数字不是素数时才调用该算法，因此不会发生这种情况。

于 2013-04-14T10:34:22.807 回答
0

您可以使用尾调用优化（Java 不适合您）

public static void factors(int input, int i) {
    while(i > 1) {
        if (input % i == 0) {
            System.out.printf(" %d", i);
        }
        i = i - 1;
    }
    System.out.printf(" %d", 1);
}

当然，除非您不再进行递归。

于 2013-04-14T10:38:25.707 回答