1と7の間の数字はどれくらいですか？複数の質問を解決するプログラムを作成するにはどうすればよいですか？
ことを考えると - D = G
ルールは、次のとおり
あなたは順列は、このルールに適合した、Javaコードに適切な方法でルールを定義し、{1,2,3,4,5,6,7}の有効なすべての順列を作成し、チェックする必要があります。私は他の順列の問題のために、ここですでにこれを行っている：あなたのルールに適応How to write an "all these numbers are different" condition in Java?
、コードは次のようになります。
import java.util.Arrays;
class Graph26 {
private static final int A = 0;
private static final int B = 1;
private static final int C = 2;
private static final int D = 3;
private static final int E = 4;
private static final int F = 5;
private static final int G = 6;
private final static boolean rule1(final int[] n) {
return n[A] != 2;
}
private final static boolean rule2(final int[] n) {
return n[A] + n[B] == n[F];
}
private final static boolean rule3(final int[] n) {
return n[C] - n[D] == n[G];
}
private final static boolean rule4(final int[] n) {
return n[D] + n[E] == 2*n[F];
}
private final static boolean rule5(final int[] n) {
return n[E] + n[G] == n[F];
}
private final static boolean isValid(final int[] nodes) {
return rule1(nodes) && rule2(nodes) && rule3(nodes) && rule4(nodes)
&& rule5(nodes);
}
class Permutation {
private final int[] o;
private boolean perms = true;
public boolean hasPerms() {
return perms;
}
Permutation(final int[] obj) {
o = obj.clone();
}
private int[] nextPerm() {
int temp;
int j = o.length - 2;
while (o[j] > o[j + 1]) {
j--;
if (j < 0) {
perms = false;
break;
}
}
if (perms) {
int k = o.length - 1;
while (o[j] > o[k]) {
k--;
}
temp = o[k];
o[k] = o[j];
o[j] = temp;
int r = o.length - 1;
int s = j + 1;
while (r > s) {
temp = o[s];
o[s] = o[r];
o[r] = temp;
r--;
s++;
}
}
return o.clone();
}
}
public static void main(final String[] args) {
int[] nodes = new int[] { 1, 2, 3, 4, 5, 6, 7};
final Graph26 graph = new Graph26();
final Permutation p = graph.new Permutation(nodes);
int i = 0;
while (p.hasPerms()) {
if (isValid(nodes)) {
System.out.println(Arrays.toString(nodes));
}
i++;
nodes = p.nextPerm();
}
System.out.println(i);
}
}
これは質問で定義されたルールに関するrules1..5を定義します{1,2,3,4,5,6,7}のすべての！7 = 5040の順列のチェックを実行します。あなたはここにこの動作を確認することができますhttps://ideone.com/wwxG0になり
（A、B、C、D、E、F、G）：Apacheのコモンズ数学ライブラリで、あなたがすべき良い解決策のためのために [3, 2, 7, 6, 4, 5, 1]
私は手でそれを行うことはできますか？ – toy
@toy：どういう意味ですか？手で何をしたいですか？ –
太い持ち上げを行うには、線形プログラミングライブラリを選択することをお勧めします。試してみてください。そこ
7！それほど多くない数字を整理する方法は、強引な力を使い、おそらく十分に速いでしょう。置換を生成したくない場合でも、7つのネストされたforループを使用することができ、それは7^7回の反復になります。最初のforループでA!=2をチェックし、Fを3番目のレベルに移動すると、レベル3でA+B=F、レベル5でD+E=2Fをチェックすることができます。これは繰り返しをカットします。
宿題やインタビューでは適切な答えではありませんが、答えが必要な場合は、ブルートフォースでもっと速くなります。 Mathematicaで
：
Reduce[ a != 2 && f == a + b && g == c - d && f == (d + e)/2 && f == e + g &&
First[And @@@ {0 < # < 8 & /@ {a, b, c, d, e, f, g}}],
{a, b, c, d, e, f, g}, Integers]
ソリューション：
(a == 1 && b == 1 && c == 4 && d == 3 && e == 1 && f == 2 && g == 1) ||
(a == 1 && b == 2 && c == 5 && d == 4 && e == 2 && f == 3 && g == 1) ||
(a == 1 && b == 2 && c == 7 && d == 5 && e == 1 && f == 3 && g == 2) ||
(a == 1 && b == 3 && c == 6 && d == 5 && e == 3 && f == 4 && g == 1) ||
(a == 1 && b == 4 && c == 7 && d == 6 && e == 4 && f == 5 && g == 1) ||
(a == 3 && b == 1 && c == 6 && d == 5 && e == 3 && f == 4 && g == 1) ||
(a == 3 && b == 2 && c == 7 && d == 6 && e == 4 && f == 5 && g == 1) ||
(a == 4 && b == 1 && c == 7 && d == 6 && e == 4 && f == 5 && g == 1)
そしてそう7つの異なる値を持つ唯一の解決策は次のとおりです。
(a == 3 && b == 2 && c == 7 && d == 6 && e == 4 && f == 5 && g == 1)
編集
「すべての値が違う」という条件は、通常書き留めるのがひどいため、Mathematicaから直接答えを出したい場合はもう少し作業が必要です。ここでは、次のとおりです。
k = {a, b, c, d, e, f, g};
Reduce[
a != 2 && f == a + b && g == c - d && f == (d + e)/2 && f == e + g &&
First[And @@@ {0 < # < 8 & /@ k}] &&
[email protected](Sequence @@ (Subsets[k, {2}] /. {x_, y_} -> (x - y))) != 0, k, Integers]
結果
(a == 3 && b == 2 && c == 7 && d == 6 && e == 4 && f == 5 && g == 1)
はWolframAlphaがあまりにもこれを行うことができます[チェックマークsign'を押して ']があれば、より良いあなたの問題を解決する答えを受け入れることを覚えていますか？ –
@ThorbjørnAFAIKではありません。 Reduce []はCPU集約型関数であり、それらの多くはWAlphaでは禁止されています。 –
@Thorbjørn：いいえ、少なくとも上記の入力はありません。 http://goo.gl/T0zB8 – miku
最も簡単な方法は、7つのネストされたループさせることです。
for(int a = 1; a < 8 ; a++) {
for(int b = 1; b < 8; b++) {
same for c, d, e, f, g
....
see if all conditions hold, and if yes, print out all values.
}
}
がそれを覚えて、すべての変数が異なる値を持っている状態です。
方程式系を解く。 シンプルな解決策のために、ブルートフォースが仕事をします。あなたはすべての可能な値のリストを使用して、単純にこれをpermutateすることができ、パフォーマンスを向上させるために
public class Test {
private static Value A = new Value("A");
private static Value B = new Value("B");
private static Value C = new Value("C");
private static Value D = new Value("D");
private static Value E = new Value("E");
private static Value F = new Value("F");
private static Value G = new Value("G");
private static List<Value> VALUES = new ArrayList<Value>(Arrays.asList(
A,B,C,D,E,F,G
));
private static Rule RESULT = new CombinedRule(
new Rule(){
public boolean isValid() {
return A.getValue() != 2;
};
},
new Rule(){
public boolean isValid() {
return A.getValue() + B.getValue() == F.getValue();
}
},
new Rule(){
public boolean isValid() {
return C.getValue() - D.getValue() == G.getValue();
}
},
new Rule(){
public boolean isValid() {
return D.getValue() + E.getValue() == 2 * F.getValue();
}
},
new Rule(){
public boolean isValid() {
return E.getValue() + G.getValue() == F.getValue();
}
},
new Rule(){
public boolean isValid() {
return A.getValue() != B.getValue()
&& A.getValue() != C.getValue()
&& A.getValue() != D.getValue()
&& A.getValue() != E.getValue()
&& A.getValue() != F.getValue()
&& A.getValue() != G.getValue()
&& B.getValue() != C.getValue()
&& B.getValue() != D.getValue()
&& B.getValue() != E.getValue()
&& B.getValue() != F.getValue()
&& B.getValue() != G.getValue()
&& C.getValue() != D.getValue()
&& C.getValue() != E.getValue()
&& C.getValue() != F.getValue()
&& C.getValue() != G.getValue()
&& D.getValue() != E.getValue()
&& D.getValue() != F.getValue()
&& D.getValue() != G.getValue()
&& E.getValue() != F.getValue()
&& E.getValue() != G.getValue()
&& F.getValue() != G.getValue();
}
}
);
public static void main(String[] args) {
long start = System.currentTimeMillis();
iterateOn(0);
System.out.println(System.currentTimeMillis()-start+" millis.");
}
private static void iterateOn(int valueNo){
if(valueNo < VALUES.size()){
Value v = VALUES.get(valueNo);
for(int value = 1; value < 8; value++){
v.setValue(value);
if(RESULT.isValid()) System.out.println(VALUES);
iterateOn(valueNo+1);
}
}
}
}
：鉱山はこのようになります。 これは、ループの総量を約960000から約13000に減らしますが、リスト作成コストをいくらか導入します。コードの変更は次のとおりです。
public static void main(String[] args) {
List<Integer> possibleValues = new ArrayList<Integer>();
for(int value = 1; value < 8; value++){
possibleValues.add(Integer.valueOf(value));
}
long start = System.currentTimeMillis();
iterateOn(0, possibleValues);
System.out.println((System.currentTimeMillis()-start)+" millis.");
}
private static void iterateOn(int valueIndex, List<Integer> possibleValues){
Value v = VALUES.get(valueIndex);
for(int i = 0; i < possibleValues.size(); i++){
Integer currentValue = possibleValues.get(i);
v.setValue(currentValue);
if(RESULT.isValid()) System.out.println(VALUES);
if(possibleValues.size() > 1){
List<Integer> remainingValues = new ArrayList<Integer>(possibleValues);
remainingValues.remove(currentValue);
iterateOn(valueIndex+1, remainingValues);
}
}
}
この宿題はありますか？ –
一般的かつ迅速に行う方法は、これを線形行列方程式として表現し、それを解くことです。 – sinelaw
答えが必要な場合は、最速の方法は無差別な力です。 7つのネストされたループは、7^7を点滅します。 – Rogach