个人中心
文章发布
退出
作者热门文章
- Java 双重比较
- java - 比较器与 Apache BeanComparator
- Objective-C 完成 block 导致额外的方法调用？
- database - RESTful URI 是否应该公开数据库主键？
25
4
这个问题很远。这可能需要很长时间，所以如果您没有时间，我可以理解。
让我先解释一下我想要实现的目标:我和一些 friend 玩这个数学游戏，我们从可能的数字池中随机抽取 6 个数字:1 到 10、25、50、75 和 100。从中选出 6 个数字，不允许重复。然后将在 [100, 999] 范围内选择一个目标编号。有了前面提到的6个数字，我们可以只用基本的运算(加减乘除)就可以达到目的。只允许使用整数，并非需要所有 6 个整数才能得出解决方案。
举个例子:我们从数字 4,8,6,9,25,100 开始，需要找到 328。一个可能的解决方案是:((4 x 100) - (9 x 8)) = 400 - 72 = 328。有了这个，我只使用了 6 个初始数字中的 4 个，没有一个数字被使用过两次。这是一个有效的解决方案。
我们并不总能自己找到解决方案，这就是为什么我认为一个程序会很有用。我编写了一个程序(用 Java)，该程序已经过多次测试并且有效。它并不总是提供所有可能的解决方案，但它在其自身的局限性内起作用。现在我尝试扩展它以便显示所有解决方案。
关于主要问题:我尝试执行的程序运行时间长得令人难以置信。比如，我会让它运行 15 分钟，但它看起来并没有接近完成。所以我想了想，选择确实是无穷无尽的。我从 6 个数字开始，我将第一个与其他 5 个进行比较，然后将第二个与其他 5 个进行比较，依此类推，直到我完成了 6 次(每次比较我都与每个运算符进行比较，所以又进行了 4 次)。在最初的 6 个数字的单一状态中，我现在有 5 次 6 次 4 = 120 个状态(每个状态有 5 个数字)。所有这些都必须经过相同的仪式，所以难怪要花这么长时间。
程序实在是太大了，所以我会上传给有兴趣的人: http://www.speedyshare.com/ksT43/MathGame3.jar(点击下载旁边的 MathGame3.jar 标题)
这里是对发生的事情的一般概述:
-6 integers + goal number are initialized
-I use the class StateNumbers that are acting as game states
-> in this class the remaining numbers (initially the 6 starting numbers)
are kept as well as the evaluated expressions, for printing purposes
这个方法是主要操作发生的地方:
StateNumbers stateInProcess = getStates().remove(0);
ArrayList<Integer> remainingNumbers = stateInProcess.getRemainingNumbers();
for(int j = 0; j < remainingNumbers.size(); j++){
for(int i = 0; i < remainingNumbers.size(); i++){
for(Operator op : Operator.values()){ // Looping over different operators
if(i == j) continue;
...
}
}
}
我为第一个元素评估所有可能的操作以及该状态的所有剩余数字。然后我检查自己编写的 equals 是否已经在状态数组列表中(它充当队列，但顺序并不重要)。如果它不存在，那么状态将被添加到列表中，然后我对其他元素做同样的事情。之后我丢弃状态并从不断增长的列表中选择另一个。
列表的大小在 10 分钟内增长到 80k 个状态，并且增长速度越来越慢。那是因为与我想要添加新状态时相比，有越来越多的状态可供比较。这让我想知道与其他州进行比较以防止重复是否是个好主意。
完成此计划并不是那么重要，但我希望将其视为一种学习经历。我并没有要求任何人为我编写代码，但非常感谢您就我本可以更好地处理的问题提出友好的建议。这意味着如果您有关于该计划的其他方面的内容，请提出。我不确定在这个论坛上的要求是否过高，因为大多数主题都处理程序的特定部分。虽然我的问题也很具体，但原因可能有很多。
编辑:我不是要寻找最快的单一解决方案，而是要寻找所有解决方案。因此，如果我找到解决方案，我的程序将不会停止。然而，它会尝试忽略像这样的 double :((4+5)7) 和 (7(5+4))。两者中只有一个被接受，因为加法和乘法的 equals 方法不关心操作数的位置。
最佳答案
使用递归(即深度优先搜索)编写此代码可能会更容易，因为这会简化中间状态的簿记。
如果您想保持呼吸优先的方法，请确保状态列表支持有效删除第一个元素，即使用 java.util.Queue例如java.util.ArrayDeque .我提到这个是因为最常用的 List 实现(即 java.util.ArrayList)需要复制其全部内容以删除第一个元素，这使得删除第一个元素如果列表很大，则非常昂贵。
120 states (with 5 numbers each). All of these have to undergo the same ritual, so it's no wonder it's taking so long.
实际上，它会如此令人惊讶。毕竟，2GHz CPU 每秒执行 20 亿个时钟周期。即使检查一个状态需要多达 100 个时钟周期，这仍然意味着每秒 2000 万个状态!
另一方面，如果我正确理解游戏规则，候选解决方案集由 6 个数字(其中有 6!= 720)的所有顺序给出，其中 4 个运算符中的一个中间有 5 个空格，以及定义的运算符评估顺序。也就是说，我们一共有6个! * 4^5 * 5! = 88 473 600 个候选解决方案，因此处理应在几秒钟内完成。
PS:写一个完整的解决方案可能不会很费时，所以如果你愿意，我也可以 zip - 我只是不想破坏你的学习体验。
更新:我已经写好了代码。这比我想象的要难，因为找到所有解决方案的要求意味着我们需要在不展开堆栈的情况下打印解决方案。因此，我将每个州的历史记录保存在堆中。测试后，我对性能不太满意(大约 10 秒)，所以我添加了 memoization ，即每组数字只处理一次。这样，运行时间下降到大约 3 秒。
由于 Stackoverflow 没有剧透标签，我增加了缩进，因此您必须向右滚动才能看到任何内容:-)
package katas.countdown;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
enum Operator {
plus("+", true),
minus("-", false),
multiply("*", true),
divide("/", false);
final String sign;
final boolean commutes;
Operator(String sign, boolean commutes) {
this.sign = sign;
this.commutes = commutes;
}
int apply(int left, int right) {
switch (this) {
case plus:
return left + right;
case minus:
return left - right;
case multiply:
return left * right;
case divide:
int mod = left % right;
if (mod == 0) {
return left / right;
} else {
throw new ArithmeticException();
}
}
throw new AssertionError(this);
}
@Override
public String toString() {
return sign;
}
}
class Expression implements Comparable<Expression> {
final int value;
Expression(int value) {
this.value = value;
}
@Override
public int compareTo(Expression o) {
return value - o.value;
}
@Override
public int hashCode() {
return value;
}
@Override
public boolean equals(Object obj) {
return value == ((Expression) obj).value;
}
@Override
public String toString() {
return Integer.toString(value);
}
}
class OperationExpression extends Expression {
final Expression left;
final Operator operator;
final Expression right;
OperationExpression(Expression left, Operator operator, Expression right) {
super(operator.apply(left.value, right.value));
this.left = left;
this.operator = operator;
this.right = right;
}
@Override
public String toString() {
return "(" + left + " " + operator + " " + right + ")";
}
}
class State {
final Expression[] expressions;
State(int... numbers) {
expressions = new Expression[numbers.length];
for (int i = 0; i < numbers.length; i++) {
expressions[i] = new Expression(numbers[i]);
}
}
private State(Expression[] expressions) {
this.expressions = expressions;
}
/**
* @return a new state constructed by removing indices i and j, and adding expr instead
*/
State replace(int i, int j, Expression expr) {
Expression[] exprs = Arrays.copyOf(expressions, expressions.length - 1);
if (i < exprs.length) {
exprs[i] = expr;
if (j < exprs.length) {
exprs[j] = expressions[exprs.length];
}
} else {
exprs[j] = expr;
}
Arrays.sort(exprs);
return new State(exprs);
}
@Override
public boolean equals(Object obj) {
return Arrays.equals(expressions, ((State) obj).expressions);
}
public int hashCode() {
return Arrays.hashCode(expressions);
}
}
public class Solver {
final int goal;
Set<State> visited = new HashSet<>();
public Solver(int goal) {
this.goal = goal;
}
public void solve(State s) {
if (s.expressions.length > 1 && !visited.contains(s)) {
visited.add(s);
for (int i = 0; i < s.expressions.length; i++) {
for (int j = 0; j < s.expressions.length; j++) {
if (i != j) {
Expression left = s.expressions[i];
Expression right = s.expressions[j];
for (Operator op : Operator.values()) {
if (op.commutes && i > j) {
// no need to evaluate the same branch twice
continue;
}
try {
Expression expr = new OperationExpression(left, op, right);
if (expr.value == goal) {
System.out.println(expr);
} else {
solve(s.replace(i, j, expr));
}
} catch (ArithmeticException e) {
continue;
}
}
}
}
}
}
}
public static void main(String[] args) {
new Solver(812).solve(new State(75, 50, 2, 3, 8, 7));
}
}
}
根据要求，每个解决方案仅报告一次(如果中间结果集相等，则两个解决方案被视为相等)。根据维基百科的描述，并非所有数字都需要使用。但是，存在一个小错误，即此类解决方案可能会被多次报告。
关于java - 降低程序的时间复杂度(在 Java 中)？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20734265/
25
4
0
我正在编写一个具有以下签名的 Java 方法。 void Logger(Method method, Object[] args); 如果一个方法(例如 ABC() )调用此方法 Logger，它应该
我是 Java 新手。 我的问题是我的 Java 程序找不到我试图用作的图像文件一个 JButton。 (目前这段代码什么也没做，因为我只是得到了想要的外观第一的)。这是我的主课 代码: packag
好的，今天我在接受采访，我已经编写 Java 代码多年了。采访中说“Java 垃圾收集是一个棘手的问题，我有几个 friend 一直在努力弄清楚。你在这方面做得怎么样？”。她是想骗我吗？还是我的一生都
我的 friend 给了我一个谜语让我解开。它是这样的: There are 100 people. Each one of them, in his turn, does the following
如果我将使用 Java 5 代码的应用程序编译成字节码，生成的 .class 文件是否能够在 Java 1.4 下运行？ 如果后者可以工作并且我正在尝试在我的 Java 1.4 应用程序中使用 Jav
有关于why Java doesn't support unsigned types的问题以及一些关于处理无符号类型的问题。我做了一些搜索，似乎 Scala 也不支持无符号数据类型。限制是Java和S
我只是想知道在一个 java 版本中生成的字节码是否可以在其他 java 版本上运行 最佳答案 通常，字节码无需修改即可在 较新 版本的 Java 上运行。它不会在旧版本上运行，除非您使用特殊参数 (
我有一个关于在命令提示符下执行 java 程序的基本问题。 在某些机器上我们需要指定 -cp 。 (类路径)同时执行java程序 (test为java文件名与.class文件存在于同一目录下) jav
我已经阅读 StackOverflow 有一段时间了，现在我才鼓起勇气提出问题。我今年 20 岁，目前在我的家乡(罗马尼亚克卢日-纳波卡)就读 IT 大学。足以介绍:D。 基本上，我有一家提供簿记应用
我有 public JSONObject parseXML(String xml) { JSONObject jsonObject = XML.toJSONObject(xml); r
我已经在 Java 中实现了带有动态类型的简单解释语言。不幸的是我遇到了以下问题。测试时如下代码: def main() { def ks = Map[[1, 2]].keySet()
一直提示输入 1 到 10 的数字 - 结果应将 st、rd、th 和 nd 添加到数字中。编写一个程序，提示用户输入 1 到 10 之间的任意整数，然后以序数形式显示该整数并附加后缀。 public
我有这个 DownloadFile.java 并按预期下载该文件: import java.io.*; import java.net.URL; public class DownloadFile {
我想在 GUI 上添加延迟。我放置了 2 个 for 循环，然后重新绘制了一个标签，但这 2 个 for 循环一个接一个地执行，并且标签被重新绘制到最后一个。 我能做什么？ for(int i=0;
我正在对对象 Student 的列表项进行一些测试，但是我更喜欢在 java 类对象中创建硬编码列表，然后从那里提取数据，而不是连接到数据库并在结果集中选择记录。然而，自从我这样做以来已经很长时间了，
我知道对象创建分为三个部分: 声明 实例化 初始化 classA{} classB extends classA{} classA obj = new classB(1,1); 实例化 它必须使用
我有兴趣使用 GPRS 构建车辆跟踪系统。但是，我有一些问题要问以前做过此操作的人: GPRS 是最好的技术吗？人们意识到任何问题吗？ 我计划使用 Java/Java EE - 有更好的技术吗？ 如果
我可以通过递归方法反转数组，例如:数组={1,2,3,4,5} 数组结果={5,4,3,2,1}但我的结果是相同的数组，我不知道为什么，请帮助我。 public class Recursion { p
有这样的标准方式吗？ 包括 Java源代码-测试代码- Ant 或 Maven联合单元持续集成(可能是巡航控制)ClearCase 版本控制工具部署到应用服务器 最后我希望有一个自动构建和集成环境。
我什至不知道这是否可能，我非常怀疑它是否可能，但如果可以，您能告诉我怎么做吗？我只是想知道如何从打印机打印一些文本。 有什么想法吗？ 最佳答案 这里有更简单的事情。 import javax.swin
我是一名优秀的程序员,十分优秀！