Hallo zusammen.
Ich bräuchte Hilfe bei der Entwicklung eines Algorithmus, welcher nach bestimmten "Muster" in einem boolean Array sucht. Der Algorithmus erhällt Arrays, welche mit true und false Werte gefüllt ist. Dabei stehen im Normalfall mehrere true-Werte hintereinander. Der Algorithmus soll den Index finden, welche dem mittleren Wert der Indizes alles True-Werte entspricht. Hier ein Beispiel:
In diesem Fall soll der Algorithmus den Wert 4 ausgeben, da der niedrixte Index mit true 3 und der höchste Index 5 ist. Bei solch einem Beispiel ist das einfach zu realisieren mit folgendem code:
Im Falle das gar kein Index gefunden wird, sprich wenn im Array nur false-Werte stehen, gibt der Algorithmus als Index 0 zurück, was auch so gewollt ist. Dass bei der bestimmung des Mittelwertes manchmal gerundet wird spielt ebenfals keine Rolle.
Nun zum eigentlichen Problem. Der Algorithmus soll auch berücksichtigen können, dass eine bestimmte Anzahl von True-Werten hintereinander stehen muss damit der index "gültig" ist.
Hier ein weiteres Beispiel bei dem wir anehmen, dass die Minimalanzahl 3 beträgt:
In diesem Fall müsste der Algorithmus den Wert 12 zurückgeben, da bei Index 3 nicht genügend True-Werte hintereinander stehen.
Als letztes der komplizierteste Fall:
Nehmen wir auch hier an die Minimalanzahl an true-Werten wäre 3. In diesem Beispiel wäre dass von Index 2 - 4 und Index 9 - 12 erfüllt. In diesem Fall sollte sich der Algorithmus für einer der beiden True-Folgen entscheiden und entweder 3 oder 10 zurückgeben. Dabei spielt es keine Rolle für Welchen Wert er sich entscheidet, es ist nur wichtig dass sich der Algorithmus immer gleich entscheidet.
Die Erkennung der minimal Benötigten True-Folge habe ich so gelöst:
Der StartIndex wird dabei mit der Methode getLowestIndex bestimmt. Im Falle dass die Methode checkMinWidth false zurückgibt, wird der startIndex um 1 erhöht und der Vorgang widerholt. Sobald der Startindex grösser als die Differenz der Arraylänge-minWidth ist, was bedeutet dass der Algorithmus bis fast ans Ende gelaufen ist und nicht genügend true-Folgen gefunden wurden, wird der Vorgang abgebrochen und als Index wird dann wieder 0 zurückgegeben.
Ich scheitere am letzten Punkt bei dem der Algorithmus sowohl die minimale Anzahl an true-Folgen sowie den "Abstand" zwischen mehreren Folgen im gleichen Array berücksichtigen soll.
Sollte jemand eine Lösung haben wäre ich sehr Dankbar.
Hier noch ein paar Beispiele von Arrays und den Werten, welche der Algorithmus liefern sollte:
Minimalwert: 2
Ausgabe = 0 (keine Übereinstimmung gefunden)
Minimalwert: 3
Ausgabe = 0 (keine Übereinstimmung gefunden)
Minimalwert: 3
Ausgabe = 3 oder 13
Ich bräuchte Hilfe bei der Entwicklung eines Algorithmus, welcher nach bestimmten "Muster" in einem boolean Array sucht. Der Algorithmus erhällt Arrays, welche mit true und false Werte gefüllt ist. Dabei stehen im Normalfall mehrere true-Werte hintereinander. Der Algorithmus soll den Index finden, welche dem mittleren Wert der Indizes alles True-Werte entspricht. Hier ein Beispiel:
Code:
boolean array1 = {false, false, false, true, true, true, false, false, false, false, false, false, false, false}In diesem Fall soll der Algorithmus den Wert 4 ausgeben, da der niedrixte Index mit true 3 und der höchste Index 5 ist. Bei solch einem Beispiel ist das einfach zu realisieren mit folgendem code:
Code:
public int getMiddleTrueIndex(boolean array){
int minIndex = getLowestTrueIndex(array);
int maxIndex = getHighestTrueIndex(array);
return (minIndex+maxIndex)/2;
}
private int getLowestIndex(boolean[] array) {
int index = 0;
for(int i = 0; i < array.length;i++){
if(array[i]==true){
index = i;
return index;
}
}
return index;
}
private int getHighestIndex(boolean[] array){
int index = 0;
for(int i = array.length-1; i > -1 ;i--){
if(array[i]==true){
index = i;
return index;
}
}
return index;
}Im Falle das gar kein Index gefunden wird, sprich wenn im Array nur false-Werte stehen, gibt der Algorithmus als Index 0 zurück, was auch so gewollt ist. Dass bei der bestimmung des Mittelwertes manchmal gerundet wird spielt ebenfals keine Rolle.
Nun zum eigentlichen Problem. Der Algorithmus soll auch berücksichtigen können, dass eine bestimmte Anzahl von True-Werten hintereinander stehen muss damit der index "gültig" ist.
Hier ein weiteres Beispiel bei dem wir anehmen, dass die Minimalanzahl 3 beträgt:
Code:
boolean array2 = {false, false, false, true, true, false, false, false, false, false, false, true, true, true}Als letztes der komplizierteste Fall:
Code:
boolean array2 = {false, false, true, true, true, false, false, false, false, true, true, true, true, false}Die Erkennung der minimal Benötigten True-Folge habe ich so gelöst:
Code:
public boolean checkMinWidth(boolean[] array, int startIndex, int minWidth){
boolean check = true;
for(int i = 0; i < minWidth; i++){
if(array[startIndex+i] == false){
check = false;
}
}
return check;
}Der StartIndex wird dabei mit der Methode getLowestIndex bestimmt. Im Falle dass die Methode checkMinWidth false zurückgibt, wird der startIndex um 1 erhöht und der Vorgang widerholt. Sobald der Startindex grösser als die Differenz der Arraylänge-minWidth ist, was bedeutet dass der Algorithmus bis fast ans Ende gelaufen ist und nicht genügend true-Folgen gefunden wurden, wird der Vorgang abgebrochen und als Index wird dann wieder 0 zurückgegeben.
Ich scheitere am letzten Punkt bei dem der Algorithmus sowohl die minimale Anzahl an true-Folgen sowie den "Abstand" zwischen mehreren Folgen im gleichen Array berücksichtigen soll.
Sollte jemand eine Lösung haben wäre ich sehr Dankbar.
Hier noch ein paar Beispiele von Arrays und den Werten, welche der Algorithmus liefern sollte:
Minimalwert: 2
Code:
boolean array3 = {false, true, false, true, false, true, false, true, false, true, false, true, false, true}Minimalwert: 3
Code:
boolean array4 = {false, true, true, false, true, true, false, false, false, false, false, false, false,false ,false }Minimalwert: 3
Code:
boolean array5 = {false, true, true, true, true, true, false, false, false, true, false, false, true,true,true}
