我正在编写一个递归程序:
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;
}
最佳答案
让我们看看你的 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 上运行.
关于java - Java 中的递归和 While 循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60714386/