Prüfen ob Array alternierend sortiert ist?

[Perpetuum]

Hi,

wir haben eine Aufgabe bekommen in der wir drei rekursive Methoden schreiben sollen, die ein mit zufälligen natürlichen Zahlen belegtes Array überprüfen ob die Elemente aufsteigend, absteigend oder alternierend geordnet sind.

Aufsteigend oder Absteigend ist ja kein Problem... aber bei alternierned habe ich eine nicht ganz so optimale Lösung gefunden (alternierend wäre z.B. 1 2 1 1 1 1 2):

public static boolean alt(int[] a, int laenge, int i){


		// Basisfall

		if(laenge == 0){

			System.out.print("|   JA   ");

			return true;

		}


		if(i == 1){

		// Rekursionsfall 1

		if(a[laenge-1] <= a[laenge]){

			return alt(a, laenge-1, 0);

		}

		}else{

		// Rekursionsfall 2

		if(a[laenge-1] >= a[laenge]){

			return alt(a, laenge-1, 1);

		}

		}

		System.out.print("|   -    ");

		return false;

	}[/PHP]

Die Methode funktioniert auch, nur muss ich extern bestimmen ob das letzte Array Element "<=" oder ">=" dem vorletzten Element ist umso die Richtung zu bestimmen.

Allerdings sollte die Methode "selbstständig" arbeiten und nicht von außen auf ein zusätzliches Script angewiesen sein. Hat jemand eine Idee wie man das Problem lösen kann? Vieleicht euch einen ganz anderen [b]rekursiven[/b] Vorschlag?

[geloescht_Newlukai]

Was wäre denn ein Beispiel für nicht alternierend? Ich blick' noch nicht ganz durch...

Hmm. Vielleicht 012?

[BenjieAul]

was ist altinierend überhaupt????

[Klotzkopp]

Eigentlich würde es hier bedeuten, dass die Zahlen abwechselnd größer und wieder kleiner werden. Möglicherweise mein Perpetuum mit "alternierend" aber auch nur weder aufsteigend noch absteigend. Eine Klärung wäre hilfreich...

[Perpetuum]

Hi,

was alternierend genau bedeutet weis ich auch nicht genau. Doch ich habe eine Definition im Internet gefunden die lautet:

Zur Erklärung: ein Array soll dann aufsteigend sortiert sein, wenn keines seiner Elemente kleiner als sein Vorgänger ist. Absteigend sortiert soll es sein, wenn keines seiner Elemente größer als sein Vorgänger ist. Wird die Folge der Elemente abwechselnd größer und kleiner, ist es alternierend sortiert

Ausserdem muss ein alternierendes Array mindestens 3 Elemente haben.

Nach dieser Definition sind dann folgende Array alternierend:

1 2 1

2 1 2

und folgende nicht

2 1 1

1 2 2

Hab das ganze dann so rekursiv gelöst:

	

	/**

	 * Hilfsmethode zur Methode 'altmain()'. Prüft letztes und vorletztes

	 * Element ob >= oder <= und gibt so den Startwert für die Alternierung

	 * vor. 

	 * @param a : Array

	 * @return boolean  : true falls Elemente alternierend sortiert sind

	 */

	public static boolean alt(int[] a, int laenge){


		// Nur dann wenn Array mindestens drei Elemente enthält.

		if(laenge > 1 && a[laenge] > a[laenge-1]){

			altmain(a, laenge, 1);

	  	}else if(laenge > 1){

	  		altmain(a, laenge, 0);

	  	}


		System.out.print("|   -    ");

	  	return false;


	}



	/**

	 * Methode prüft ob Elemente (vom Typ int) in einem Array alternierend

	 * sortiert sind.

	 * @param a, laenge, i : Array und Länge vom Array, Startwert

	 * @return boolean     : true falls Elemente alternierend sortiert sind

	 */

	public static boolean altmain(int[] a, int laenge, int i){


		// Basisfall

		if(laenge == 0){

			System.out.print("|   JA   ");

			return true;

		}


		if(i == 1){

		// Rekursionsfall 1

		if(a[laenge-1] < a[laenge]){

			return altmain(a, laenge-1, 0);

		}

		}else{

		// Rekursionsfall 2

		if(a[laenge-1] > a[laenge]){

			return altmain(a, laenge-1, 1);

		}

		}

		System.out.print("|   -    ");

		return false;

	}[/PHP]

[speedi]

Kannst du bei der Beschreibung deines nächsten Problems bitte etwas weniger Fachbegriffe verwenden?

Wenn ich dich richtig verstanden hab ist alternierend im Prinzip nichts anderes wie durcheinander.

In dem Fall würde ich einfach schauen ob der Array weder aufasteigend noch absteigend sortiert ist: daraus folgt dann: alternierend sortiert

[geloescht_Newlukai]

Wenn ich dich richtig verstanden hab ist alternierend im Prinzip nichts anderes wie durcheinander.

Er hat's doch ganz genau beschrieben:

Wird die Folge der Elemente abwechselnd größer und kleiner, ist es alternierend sortiert

Also wäre die Liste

5,2,4,3,1

zwar unsortiert (durcheinander), aber nicht alternierend. Das wäre sie, wenn sie so aussähe:

5,3,4,1,2

D.h. der Vergleich wechselt mit jedem Element (mal >, das nächste Mal <)

Aber wie man das geschickt rekursiv löst, ist mir auch noch nciht eingefallen (hab' mich ja auch noch nicht wirklich mit der Frage beschäftigt )

[speedi]

eine gute Lösung könnte man mit einem boolean erreichen das würde in etwa so aussenhen(ACHTUNG: hatte noch keine Zeit das zu testen!):

boolean check;

boolean nichtalt=false;

if(array[0]<array[1]){

    check = false;

}else{

    if(array[0]>array[1]){

        check=true;

    }else{

        nichtalt=true;

    }

}

for(int a = 2;a<(array.length-1);a++){

    if(nichtalt==false){

        if(check==true){

            check=false;

            if(array[a-1]<array[a]){

            }else{

                nichtalt=true;

            }

        }else{

            check=true;

            if(array[a-1]>array[a]){

            }else{

                nichtalt=true;

            }

        }

    }

}

if(nichtalt==true){

    System.out.println("Alternierend sortiert");

}else{

    System.out.println("Nicht alternierend sortiert");   

}

Ich denke das das funktionieren müsste. Für den Fall das zwei gleich größe aufeinander folgen habe ich jetzt festgelegt das es dann nicht alternierend ist(weis nicht ob das stimmt) musst halt dann noch ergänzen.

[geloescht_Newlukai]

wir haben eine Aufgabe bekommen in der wir drei rekursive Methoden schreiben sollen, die ein mit zufälligen natürlichen Zahlen belegtes Array überprüfen ob die Elemente aufsteigend, absteigend oder alternierend geordnet sind.

Das zu Deinem Vorschlag speedi

@perpetuum: Ich hab' mal einen unserer Diplomanden um Hilfe gebeten. Er hatte auch keine Lösung parat, bei der man nur das Array übergeben könnte. Dies könnte man höchstens mit globalen Variablen umgehen, aber ist ja Jacke wie Hose...