java - Java 中的递归和 While 循环

Question

我正在编写一个递归程序:

public static List<Integer> method(int n)

判断是否为正数n是正数 (> 0) 的立方体总数。示例:给定 n = 1944 (12^3 + 6^3)，程序将返回列表 [12, 6]按降序排列。如果n不是立方体的总数，程序应返回空列表。

程序应返回从第一个元素的最高可能值开始的值，然后对其余元素遵循相同的规则。例如，当 n = 1072 ，程序将返回 [10, 4, 2]而不是[9, 7] .

应该发生递归的方法:

private static boolean method(int n, int c, LinkedList<Integer> seen)

哪里c是仍然允许使用的最高数字，soFar是已经见过的数字列表。

我的代码涵盖了基本情况和递归，但我在循环继续时遇到问题。输入 n = 1944我的程序正在返回列表 [12]而不是[12, 6] .

    public static List<Integer> method(int n)
    {
        LinkedList<Integer> result = new LinkedList<Integer>();
        int c = (int) Math.cbrt(n);
        result.add(c);
        method(n, c, result);
        return result;
    }
    private static boolean method(int n, int c, LinkedList<Integer> seen)
    {
        LinkedList<Integer> result = new LinkedList<Integer>();
        boolean b = false;
        if (n == 0)
        {
          return true;  
        }
        else if (c == 0)
        {
            return false;
        }
        else 
        {
            int sum = 0;
            for (int i : seen)
            {
                sum += i*i*i;
            }
            while (b = false)
            {
                c = (int) Math.cbrt(n - sum);
                seen.add(c);
                method(n, c, seen);
                if (sum == n)
                {
                    result = seen;
                    return true;
                }
                else
                {
                    return false;
                }
            }
        }
        return false;
    }

Answer 1

让我们看看你的 while 循环:

LinkedList<Integer> result = new LinkedList<Integer>();
boolean b = false;
// Some code omitted here.
while (b = false)
{
    c = (int) Math.cbrt(n - sum);
    seen.add(c);
    method(n, c, seen);
    if (sum == n)
    {
        result = seen;
        return true;
    }
    else
    {
        return false;
    }
}

首先，使用 while总是有 false 的循环作为循环的条件，它根本不执行任何操作。

无论如何，即使我们假装循环运行，无论 if 采取的分支是什么，一个return将会达到。所以，你的while即使将其条件更改为始终为 true，循环也根本不循环。此外，为 b 分配的唯一值变量是 false ，而且它根本不用于任何用途。

此外，result第二种方法中的列表始终为空。并且，自从 result = seen;指令就在 return 之前，这是一个无害的指令，它呈现 result简直就是没用。

另外，请查看 method(n, c, seen);称呼。它不会对其返回值执行任何操作!所以，即使它最终返回true ，您仍然继续，然后会生成 false结果。

此外，每当您向 seen 添加值时，它永远不会被删除。自 seen在每个递归方法调用中始终是完全相同的列表，一旦在那里添加了错误的数字，它就永远不会被删除以为其他东西让路。

由此，我必须得出结论，你的算法是如此糟糕，必须从头开始重写。

另外，虽然你的问题不是很清楚，但我认为找到的数字一定都是不同的。否则，人们可以制作 2 = 1<sup>3</sup> + 1<sup>3</sup>每个大于 1 的数字都可以用许多立方数之和来表示(即 n = 1<sup>3</sup> + 1<sup>3</sup> + 1<sup>3</sup> + ... )。

算法是这样的:

• 第一步是拥有 for计数i从cbrt(n)下降1 尝试形成立方体。
• 然后，用 n 减去立方体并递归地尝试找到结果数字的立方和。
• 添加一个参数以避免重复数字，该参数比最后使用的数字小 1。
• 当立方体形成时，返回形成它的数字。在外部调用中，将结果添加到非空内部递归调用列表中。
• 如果内部递归调用给出空列表结果，则 for 的当前迭代产生了一个错误的数字，我们应该尝试下一个(如果我们有下一个)。
• 如果 for结束时没有形成立方体，返回一个空列表。

这是代码:

import java.util.LinkedList;
import java.util.List;

public class Main {
    public static List<Integer> findCubeSum(int n) {
        return findCubeSum(n, n);
    }

    public static List<Integer> findCubeSum(int n, int max) {
        if (n <= 0) return List.of();
        int c = (int) Math.cbrt(n);
        for (int i = Math.min(c, max); i > 0; i--) {
            int x = i * i * i;
            if (x == n) {
                List<Integer> result = new LinkedList<>();
                result.add(i);
                return result;
            }
            List<Integer> result = findCubeSum(n - x, i - 1);
            if (result.isEmpty()) continue;
            result.add(0, i);
            return result;
        }
        return List.of();
    }

    public static void main(String[] args) {
        System.out.println(findCubeSum(8));    // [2]
        System.out.println(findCubeSum(64));   // [4]
        System.out.println(findCubeSum(1000)); // [10]
        System.out.println(findCubeSum(1072)); // [10, 4, 2]
        System.out.println(findCubeSum(1944)); // [12, 6]
        System.out.println(findCubeSum(4));    // []
        System.out.println(findCubeSum(0));    // []
        System.out.println(findCubeSum(-1));   // []
        System.out.println(findCubeSum(10));   // []
    }
}

查看它在 ideone 上运行.