# Algorithmik und Arrays



## .x (27. Jan 2013)

Hallo! Ich bin gerade beim üben, anhand von alten Prüfungen und komme einfach zu keinem Ergebnis! Habe versucht es mir mit Beispielen zu erleichtern, aber bin nicht wirklich weit gekommen. 







```
int shortestRun(int[] a){
		int minrunlength = a.length; // speichert länge hier 6 elemente. minrunlength = 6
		for(int runlength = a.length; runlength >= 1; runlength--){  // runlength = 6
			boolean isrun = true;
			for(..?..){
				for(int indexinrun = 0; isrun && indexinrun < runlength; indexinrun++){
					if(a[indexinrun] != a[runstart + indexinrun]){
						isrun = false;
					}
				}
			}
			if(isrun){
				minrunlength = runlength;
			}
		}
		return minrunlength;
	}
```
Mir ist klar, man muss mit runstart arbeiten. Allerdings kann ich mir den Algorithmus in keinster Weise vorstellen... Ich hoffe jemand kann mir da einen Tipp geben.


----------



## SlaterB (28. Jan 2013)

was genau macht denn die innere Schleife, wieviel wird verglichen, wo bei den obigen Beispielen tritt das konkret auf?
offensichtlich mehrfach, an unterschiedlichen runstart, welche genau für alle Beispiele?
welcher Schleifen-Code schafft das?

b)
ist allerdings schwieriger, da will mir noch nichts ordentliches einfallen,

nachdem man mit der vollen Länge geprüft hat kann man bis zur Hälfte runtergehen, spart bis zu 50%, 
aber ist das die drastische Beschleunigung?

man könnte auch andersrum beginnen und ausrechnen, ab wann unter den größeren Runs ein bereits gefundener kleiner nicht mehr überboten werden kann,

speziell das, aber auch das erste ist nicht so ganz klar mit X zu schaffen,


----------



## Marco13 (28. Jan 2013)

Spoiler: Zu b) ein erster Gedanke



Die äußere Schleife bei 1 anfangen lassen, und ein 'break' wenn ein run gefunden wurde...?!


----------

