Dein Ansatz hat ein paar Probleme.
Du erzeugst sehr viele Objekte. Bei 1000 Münzen, 1000 Instanzen, bei 1 Mrd. Münzen 1 Mrd. Instanzen.
Das hat Elementare Nachteile, wenn so etwas tatsächlich mal eingesetzt werden sollte.
Bei deinem Ansatz wird der User gefragt, was nun schwerer wiegt. Würde man dies umstellen und den Rechner die Gewichte aufsummieren lassen, um den schwereren Haufen zu finden, dann würde er bei 1 Mrd. Objekte sehr viel aufsummieren müssen um dann einen Vergleich zu ziehen.
Es gibt Fälle in denen dies nötig oder unvermeidlich ist. Hier ist das allerdings nicht der Fall.
Meiner Meinung nach kann man aber dennoch etwas Objektorientierung sinnvoll hineinbringen.
public class Scale {
public enum Result {
A_HEAVIER, B_HEAVIER, EQUAL, ERROR;
}
private final int target;
public Scale(int target) {
this.target = target;
}
public Result weigh(int minA, int maxA, int minB, int maxB, boolean rest) {
System.out.printf("Comparing [%d - %d], [%d - %d]%s%n",minA,maxA, minB,maxB, (rest)? " and Rest "+(maxB+1):"");
int a = maxA - minA;
int b = maxB - minB;
if (a != b) {
System.out.println("Unequal Number of Elements");
return Result.ERROR;
} else if (minA <= target && target <= maxA) {
System.out.printf("Set A [%d - %d] is heavier%n", minA, maxA);
return Result.A_HEAVIER;
} else if (minB <= target && target <= maxB) {
System.out.printf("Set B [%d - %d] is heavier%n", minB, maxB);
return Result.B_HEAVIER;
} else {
System.out.println("Sets weight equal!");
return Result.EQUAL;
}
}
}
Eine Waage, die die lästigen Benutzereingaben ersetzt.
Hierbei bekommt die Waage die Info, in welcher Schale sich die schwerere Münze befindet.
Zum Wiegen werden zwei Bereiche übergeben. Sowie die Info, ob es noch eine zusätzliche Münze gibt (Für eine passende Ausgabe).
Man kann sich auch vorstellen in dieser Waage die Nutzereingaben zu kapseln.
public enum CoinAlgorithms {
ITERATIV {
@Override
public int search(int minX, int maxX, Scale scale) {
int min = minX;
int max = maxX;
while (min != max) {
int size = max - min + 1;
int half = size / 2;
int minA = min;
int maxA = minA + half - 1;
int minB = maxA + 1;
int maxB = minB + half - 1;
boolean rest = maxB < max;
Scale.Result weighResult = scale.weigh(minA, maxA, minB, maxB, rest);
switch (weighResult) {
case A_HEAVIER:
max = maxA;
break;
case B_HEAVIER:
min = minB;
max = maxB;
break;
case EQUAL:
min = max;
break;
case ERROR:
default:
return -1;
}
}
return max;
}
}, REKURSIV {
@Override
public int search(int min, int max, Scale scale) {
if (min == max) {
return min;
}
int size = max - min + 1;
int half = size / 2;
int minA = min;
int maxA = minA + half - 1;
int minB = maxA + 1;
int maxB = minB + half - 1;
Scale.Result weighResult = scale.weigh(minA, maxA, minB, maxB, maxB < max);
switch (weighResult) {
case A_HEAVIER:
return search(minA, maxA, scale);
case B_HEAVIER:
return search(minB, maxB, scale);
case EQUAL:
return maxB + 1;
case ERROR:
default:
return -1;
}
}
};
public abstract int search(int min, int max, Scale scale);
}
Nun kann man ein (Strategy-Pattern?) anwenden, dass die Algorithmen bereithält. Einmal Rekursiv und einmal Iterativ. Wobei es doch sehr schwer wird hier einen Stackoverflow zu erhalten.
import java.util.Random;
public class Coins {
private final Scale scale;
private final int nrCoins;
private final CoinAlgorithms algorithm;
public Coins(Scale scale, int nrCoins, CoinAlgorithms algorithm) {
this.scale = scale;
this.nrCoins = nrCoins;
this.algorithm = algorithm;
}
public int search() {
return algorithm.search(1, nrCoins, scale);
}
public static void main(String[] args) {
int nrCoins = 1000;
int target = new Random().nextInt(nrCoins + 1);
System.out.printf("Target is %d %n", target);
Scale scale = new Scale(target);
for(CoinAlgorithms algorithm : CoinAlgorithms.values()){
System.out.println(algorithm);
Coins coins = new Coins(scale, nrCoins, algorithm);
int result = coins.search();
System.out.println("Found false coin " + result);
}
}
}```
Das Programm Coins bekommt im Konstruktor eine Waage die die Münze "erkennt", sowie die maximale Anzahl an Münzen übergeben und einen Algorithmus nachdem es vorgehen soll.
Danach wird einer der beiden Algorithmen mit den anfänglichen Grenzen aufgerufen.
Das könnte man sich nun auch mit den entsprechenden Interfacen und Factories ausstatten, sowie ausreichend dokumentieren
@Timothy_Truckle ausserdem sorgt, deine Objektorientierte Version durch das Nutzen von subList in Verbindung mit dem Remove für eine ConcurrentModification Exception.
Exception in thread “main” java.util.ConcurrentModificationException
at java.util.ArrayList$SubList.checkForComodification(ArrayList.java:1129)
at java.util.ArrayList$SubList.listIterator(ArrayList.java:1009)
at java.util.AbstractList.listIterator(AbstractList.java:299)
at java.util.ArrayList$SubList.iterator(ArrayList.java:1005)
at java.util.AbstractCollection.toString(AbstractCollection.java:442)
at MuenzeFindenTest.findLeichtereMenge(MuenzeFindenTest.java:22)
at MuenzeFindenTest.leichtereSuchen(MuenzeFindenTest.java:11)
at MuenzeFindenTest.main(MuenzeFindenTest.java:44)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:606)
at com.intellij.rt.execution.application.AppMain.main(AppMain.java:120)
). Die Collections entsprechend zu verwenden hat sicher was , aber echt objektorientiert® wäre eher sowas wie