Ist das Verfahren allgemeingültig?
-
Moin, kurze Frage an unsere Algorithmiker.
Folgendes Problem kann mit folgendem Verfahren gelöst werden:
import java.util.*; public class Dyn { public static void main(String[] args) { customBreadthFirstSearch(); } public static void customBreadthFirstSearch() { int n = 5; Deque<int[]> solutions = new ArrayDeque<>(); int[] first = new int[n]; //Arrays.fill(first, 11); solutions.addLast(first); int[] best = checkSolution(first); while (!solutions.isEmpty()) { int[] solution1 = solutions.removeFirst(); int[] check = checkSolution(solution1); System.out.println(Arrays.toString(solution1) + " " + Arrays.toString(check) + " (was " + Arrays.toString(best) + ")"); if (containsOnlyZero(check)) { System.out.printf(" %d %n", 86); System.out.printf(" %d %d %n", 47, 39); System.out.printf(" %d %d %d %n", solution1[0], solution1[1], solution1[2]); System.out.printf(" %d %d %d %d %n", 12, solution1[3], solution1[4], 5); System.out.println("numberOfCheckCalls = " + numberOfCheckCalls); return; } if (Arrays.compare(check, best) > 0) { continue; } if (Arrays.compare(check, best) < 0) { best = check; } int[] solution2 = new int[n]; System.arraycopy(solution1, 0, solution2, 0, n); for (int i = 0; i < n; i++) { solution2[i]++; int[] solution3 = new int[n]; System.arraycopy(solution2, 0, solution3, 0, n); solutions.addLast(solution3); } } } private static int numberOfCheckCalls = 0; private static int[] checkSolution(int[] a) { numberOfCheckCalls++; int[] b = { 86, 47, 39, a[0], a[1], a[2], 12, a[3], a[4], 5 }; int[] result = { b[3] + b[4] - b[1], b[4] + b[5] - b[2], b[6] + b[7] - b[3], b[7] + b[8] - b[4], b[8] + b[9] - b[5], }; for (int i = 0; i < result.length; i++) { result[i] = Math.abs(result[i]); } return result; } private static boolean containsOnlyZero(int[] a) { for (int i : a) { if (i != 0) { return false; } } return true; } }Nun frage ich mich, ob das Verfahren allgemeingültig ist, also für alle Probleme, die auch eine Lösung haben, eine Lösung finden würde. Meine Vermutung geht eher Richtung Nein.
Eigentlich müsste man doch "nur" 12 und 5 durch etwas anderes austauschen, womit das Verfahren keine Lösung findet, oder irre ich?
-
Vorweg, ich werde jetzt nicht auf deinen Code im Speziellen eingehen.
Es geht scheinbar um eine Pyramide mit konstant 4 Ebenen, bei denen immer genau diese Parameter bekannt sind. Intuitiv würde ich behaupten, dass ist eine Variante des Pascalschen Dreickes.
Für deine konkrete Aufgabenstellung gilt also ausgeschrieben:b = d + e c = e + f d = g + h e = h + i f = i + jMit ein wenig Substituieren kommen wir also zu
b = g + h + h + i = g + 2h + i c = h + i + i + j = h + 2i + jDa
b,c,gundjbekannt sind, gilt es jetzt also nur noch passende Parameter fürhundizu finden.
Bringen wir also alles Konstanten auf die eine und alle Parameter auf die andere Seite:2h + i = b - g h + 2i = c - jMit
Z1 - 2*Z2(mit anschließendem Zeilentausch) folgt dann entsprechend:h + 2i = c - j 0h - 3i = b - g - 2(c - j) <=> 3i = g - b + 2(c -j)Also:
i = (g - b + 2(c -j)) / 3 h = c - j - 2iDie Frage, die nun also zu klären wäre: Hält dein Verfahren strikt diese Bedingungen ein?
-
@DNKpp Danke. Ich probiere es nachher mal aus, bin gerade in der Mittagspause...
-
@DNKpp sagte in Ist das Verfahren allgemeingültig?:
Also:
i = (g - b + 2(c -j)) / 3
h = c - j - 2iDanke, aber die Formeln sind nutzlos.
So ... für:
int[] b = { 160, 55, 105, a[0], a[1], a[2], 0, a[3], a[4], 10 };also
160 55 105 5 50 55 0 5 45 10funktioniert es nicht mehr. Auch nicht, wenn ich das
continueauskommetiere -> dann läuft der Heap-Space voll.Also ist das Verfahren nicht allgemeingültig (Beweis durch Gegenbeispiel). Mehr wollte ich gar nicht wissen.
-
Also die Quelle für diese Meisterleistung an Java Software kommt aus dem Computer Base Forum:
https://www.computerbase.de/forum/threads/bin-zu-doof-mathe-3-klasse.2212978/page-4#post-29969370
Da es sich dabei um einen bekannten Forentroll handelt, würde ich das „Programm“ nicht weiter betrachten.
Habe es auch nicht gelesen oder versucht zu verstehen was da passiert. Würde es ignorieren und meine Zeit in sinnvolle Aktivitäten packen wie eine Mittagspause.
-
@oxide
Danke für deinen Hinweis. Es bestätigt meine Vermutung.Apropos, die Reinkarnationen scheinen auch wieder in Aktion zu sein:
https://www.c-plusplus.net/forum/topic/355138/private-nachrichten-verschicken
-
@oxide sagte in Ist das Verfahren allgemeingültig?:
Also die Quelle für diese Meisterleistung an Java Software kommt aus dem Computer Base Forum:
https://www.computerbase.de/forum/threads/bin-zu-doof-mathe-3-klasse.2212978/page-4#post-29969370
Da es sich dabei um einen bekannten Forentroll handelt, würde ich das „Programm“ nicht weiter betrachten.
Habe es auch nicht gelesen oder versucht zu verstehen was da passiert. Würde es ignorieren und meine Zeit in sinnvolle Aktivitäten packen wie eine Mittagspause.
Verstehe ich das richtig? @ShredderButtonOn ist besagter Troll?
-
-
Ich fände es gut, wenn ihr dieses Thema nicht durch Off-topic zweckentfremden würdet.
-
@oxide sagte in Ist das Verfahren allgemeingültig?:
Würde es ignorieren und meine Zeit in sinnvolle Aktivitäten packen wie eine Mittagspause.
Das ist schön und gut. Ich war aber ehrlich und habe gesagt, dass ich eine lange Mittagspause gemacht habe. Andere sind da nicht so ehrlich, und verschweigen dies oder schwurbeln halt herum. Mir sind aufrichtige Menschen immer lieber, als solche, die das nur vorgeben. Darin unterscheiden wir uns auch, ich kann mir Blabla nicht erlauben.
-
Könnte hier jemand "schnell" einen Blick rauf werfen, weshalb das Verfahren immer noch nicht anhält?
import java.util.*; public class Dyn { public static void main(String[] args) { customBreadthFirstSearch(); } private record PossibleSolution(int[] solution, int[] check) implements Comparable<PossibleSolution> { @Override public boolean equals(Object o) { if (this == o) return true; if (!(o instanceof PossibleSolution that)) return false; return Objects.deepEquals(solution, that.solution); } @Override public int hashCode() { return Arrays.hashCode(solution); } @Override public int compareTo(PossibleSolution o) { return Integer.compare(Arrays.stream(check()).sum(), Arrays.stream(o.check()).sum()); } @Override public String toString() { return "PossibleSolution{" + "solution=" + Arrays.toString(solution) + ", check=" + Arrays.toString(check) + '}'; } } public static void customBreadthFirstSearch() { int n = 5; Set<PossibleSolution> seen = new HashSet<>(); // hashCode and equals Queue<PossibleSolution> solutions = new PriorityQueue<>(); // only compareTo int[] first = new int[n]; //Arrays.fill(first, 11); solutions.add(new PossibleSolution(first, checkSolution(first))); while (!solutions.isEmpty()) { PossibleSolution solution1 = solutions.remove(); if (containsOnlyZero(solution1.check())) { System.out.printf(" %d %n", 160); System.out.printf(" %d %d %n", 55, 105); System.out.printf(" %d %d %d %n", solution1.solution()[0], solution1.solution()[1], solution1.solution()[2]); System.out.printf(" %d %d %d %d %n", 0, solution1.solution()[3], solution1.solution()[4], 10); System.out.println("numberOfCheckCalls = " + numberOfCheckCalls); return; } int[] solution2 = new int[n]; System.arraycopy(solution1.solution(), 0, solution2, 0, n); for (int i = 0; i < n; i++) { solution2[i]++; int[] solution3 = new int[n]; System.arraycopy(solution2, 0, solution3, 0, n); PossibleSolution possibleSolution = new PossibleSolution(solution3, checkSolution(solution3)); if (seen.contains(possibleSolution)) { // System.out.println("Duplicate: " + possibleSolution); } else { seen.add(possibleSolution); solutions.add(possibleSolution); } solution2[i]--; } } } private static int numberOfCheckCalls = 0; private static int[] checkSolution(int[] a) { numberOfCheckCalls++; int[] b = { 160, 55, 105, a[0], a[1], a[2], 0, a[3], a[4], 10 }; int[] result = { b[3] + b[4] - b[1], b[4] + b[5] - b[2], b[6] + b[7] - b[3], b[7] + b[8] - b[4], b[8] + b[9] - b[5], }; for (int i = 0; i < result.length; i++) { result[i] = Math.abs(result[i]); } return result; } private static boolean containsOnlyZero(int[] a) { for (int i : a) { if (i != 0) { return false; } } return true; } }Es ist jetzt leider doch komplizierter geworden, und ich weiß leider nicht, wie das Verfahren genau heißt ... also diese spezielle Breitensuche.
-
Das hat keinen Namen. Weder löst es irgend ein Problem noch ist es ein Algorithmus. Es ist nix. Niemand programmiert so. Wenn ich dem Ding einen Namen geben würde, würde der hier im Forum rausgefiltert werden.
Allein schon die Prämisse ist falsch, man müsste beim gegebenen Problem irgendwas raten. Man kann es durch simple Äquivalenz Umformung lösen. Das ist sowohl hier als auch meine ich im CB Forum bereits gesagt worden.
Es ist auch nicht allgemeingültig, um diese Frage auch zu beantworten.
—-
Frag doch deinen Professor Chef, was er davon hält.
PRO Tipp: Einfach im CB Forum bleiben. Da kannst du doch super mit den Leuten über sowas diskutieren. Alle freuen sich die Anzahl der Beiträge mit Diskussionen über Mäuse, dritte Klasse Probleme oder welche Musik man gerade hört in die Höhe zu bekommen.
Das hast du ja super drauf. Bleib dabei. Mehr Erfolg wirst du nicht erhalten.
-
@oxide sagte in Ist das Verfahren allgemeingültig?:
Man kann es durch simple Äquivalenz Umformung lösen
Was ich aber nicht will. Bitte sorgfältiger lesen und Beleidigungen unterlassen. Merci.
-
@ Mods : Ich möchte https://www.c-plusplus.net/forum/post/2623046 bitte als unangemessen melden (alles bis auf den von mir zitierten Satz). Ich kann leider noch nicht weder downvoten noch melden.
-
Dieser Beitrag wurde gelöscht!
-
Der erfolgreichste Run seit langem, aber jetzt fängt er wieder an, zu cyborgbetatisieren.
-
Dieser Beitrag wurde gelöscht!
