Aufgabe 6.3

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Aufgabe 6.3
Bei der Skyline-Aufgabe tritt beim Aufruf

merge(new int[]{1,11,5}, new int[]{2,6,7});

z. B. in der main- oder conquer-Methode eine ArrayIndexOutOfBoundsException in der Zeile 21,

add(internalRep, left[l], Math.max(left[l + 1], rHeight));

auf. Liegt es daran, dass die Felder falsch gewählt sind oder warum tritt sie auf?

edit: hat sich erledigt, das liegt daran, dass die letzte Höhe 0 ist.

3

Dein Aufruf ist falsch. :wink:

Was du dort merge übergibst ist sicher keine skyline. :wink:

4

Danke. Ich frage mich trotzdem, warum das dann funktioniert, wenn die letzte Höhe 0 ist, aber wahrscheinlich liegt es daran, dass die while-Schleife abgebrochen wird. Mein Main-Testfall gibt jedenfalls Folgendes aus:

189 [1, 11, 3, 13, 10, 0] [[1, 11, 5]] [[2, 6, 7], [3, 13, 19]] [[1, 11, 5], [2, 6, 7]] [[14, 3, 25], [19, 18, 22], [23, 13, 29], [24, 4, 28]] [1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0] 272

und ein weiterer guter Testfall - ich weiß nicht, ob das schon im main-Testfall drin ist - wäre aus meiner Sicht noch int[][] buildings = {{1,11,5}, {2,3,4}};, denn so kann man testen, ob ein Teil der Skyline komplett durch ein einziges Kästchen absorbiert wird.

5

Du warst zu schnell ;). Es geht in dem Fall nicht wirklich um die 0, sondern um das Format:
x_Koordinate_1, Höhe_1, x_Koordinate_2, Höhe_2, …, x_Koordinate_n, Höhe_n

edit: Typos

6

Bin gerade über dasselbe Problem gestolpert. An solchen Stellen wünscht man sich Objektorientierung :-).

7

*edit
Fehler selber gesehn

8

erstens: kein Code posten! Bitte entfern ihn wieder, wenn nicht du (und andere) ein Plagiat bekommen sollen. Das ist fast die komplette Essenz der Aufgabe.

9

Lies mal deinen Post durch, dann die Definition einer Skyline und das, was pug oben schrieb. Dann faellt dir der Fehler selbst auf.

10

hey kurz ne frage
zu zwei testcases von mir:

int[][] buildings2 = new int[][] { {1,11,5},{1,10,5}}; // see 5-44
		System.out.println(Arrays.toString(conquer(buildings2)));
		System.out.println(area(conquer(buildings2)));
		System.out.println(Arrays.deepToString(divide(buildings2, 0, true)));
		
		
		int[][] buildings3 = new int[][] { {1,11,5},{1,10,6}}; // see 5-44
		System.out.println(Arrays.toString(conquer(buildings3)));
		System.out.println(area(conquer(buildings3)));
		System.out.println(Arrays.deepToString(divide(buildings3, 2, false)));

Result:

[1, 10, 1, 11, 5, 0] // zu dem Fall gibts glaube ich scho einen Thread left==right (Inhaltscheck, kein Identitätscheck)-> return left; [in merge]
44
[]
[1, 10, 1, 11, 5, 10, 6, 0] //Skyline passt, könnte aber optimiert werden, bzw. soll ich da noch was in meiner conquer methode optimieren, was das Ergebnis von merge optimiert?
54
[]

Ist des normal, dass die merge-Method non-optimized Skylines herausgibt?

lg knotenpunkt

11

Ja - es kommen „leere“ Abschnitte bei raus wie bei deinem Testfall. Das ist kein Grund zur Beunruhigung.

1 Like
12

ok ich steht immerncoh voll aufm schlauch, wie kann es sein das eine ganze skyline (in unserem fall ja aus 8 Gebäuden initial bestehende) nur ca. 80 m² größer ist als ein einzelnes gebäude? (ich nehm jetzt einfach mal m² ;))
da müsste doch wesentlich mehr rauskommen.

ich komm atm auf diesen schlontz:

189
[1, 11, 3, 13, 10, 0]
[[1, 11]]
[[2, 6], [3, 13]]
[[1, 11], [0, 0]]
[[14, 3], [19, 18], [23, 13], [24, 4]]
[1, 11, 3, 13, 3, 0, 14, 3, 19, 18, 23, 13]
733