Post on 01-Jan-2016
description
transcript
WS 09/10
Einführung in die Informatik: Programmierung und Software-
Entwicklung
Zentralübung 6: Lösung Aufgabe 5-4, Tipps zu Blatt 6, Einfache Klassen
Christian Kroiß
25.11.2009
http://www.pst.ifi.lmu.de/Lehre/wise-09-10/infoeinf/
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Aufgabe 5-4
Zunächst: Entschuldigung! Die Aufgabe doch etwas sehr schwer. Aber: bei der Korrektur wird auf die Grundideen Wert gelegt statt auf
die genaue Rechnung. Wir werden versuchen, das nächste Bonus-Blatt einfacher zu machen!
2
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Aufgabe 5-4 a/c)
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
3
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a ungleich b, ungleiche Länge
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
4
a =
b =
true
Ergebnis: FALSEErgebnis: FALSE
1 2 3
1 2 3 4
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a ungleich b, a[0] nicht in b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
5
1 2 3a =
b = 4 2 3
VERGLEICHE = 0
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a ungleich b, a[0] nicht in b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
6
a =
b =
i = 01 2 3
4 2 3
VERGLEICHE = 1
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a ungleich b, a[0] nicht in b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
7
a =
b =
i = 0j = 0
1 2 3
4 2 3
VERGLEICHE = 2
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a ungleich b, a[0] nicht in b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
8
a =
b =
i = 0j = 0
true
true
1 2 3
4 2 3
VERGLEICHE = 2
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a ungleich b, a[0] nicht in b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
9
a =
b =
i = 0j = 0
1 2 3
4 2 3
VERGLEICHE = 4
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a ungleich b, a[0] nicht in b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
10
a =
b =
i = 0j = 1
true
true
1 2 3
4 2 3
VERGLEICHE = 4
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a ungleich b, a[0] nicht in b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
11
a =
b =
i = 0j = 1
1 2 3
4 2 3
VERGLEICHE = 6
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a ungleich b, a[0] nicht in b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
12
a =
b =
i = 0j = 2
true
true
1 2 3
4 2 3
VERGLEICHE = 6
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a ungleich b, a[0] nicht in b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
13
a =
b =
i = 0j = 2
1 2 3
4 2 3
VERGLEICHE = 8
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a ungleich b, a[0] nicht in b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
14
a =
b =
i = 0j = 3
false
1 2 3
4 2 3
VERGLEICHE = 8
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a ungleich b, a[0] nicht in b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
15
a =
b =
i = 0j = 3
true
1 2 3
4 2 3
VERGLEICHE = 9
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a ungleich b, a[0] nicht in b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
16
a =
b =
i = 0j = 3
1 2 3
4 2 3
VERGLEICHE = 10
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a ungleich b, a[0] nicht in b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
17
a =
b =
i = 0j = 3
1 2 3
4 2 3
Ergebnis: FALSEVergleiche:
1 + 1 + 2n + 1 + 1= 4 + 2n
= 10
Ergebnis: FALSEVergleiche:
1 + 1 + 2n + 1 + 1= 4 + 2n
= 10
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
18
1 2 3a =
b = 1 2 3
VERGLEICHE = 0
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
19
a =
b =
i = 01 2 3
1 2 3
VERGLEICHE = 1
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
20
a =
b =
i = 0j = 0
1 2 3
1 2 3
VERGLEICHE = 2
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
21
a =
b =
i = 0j = 0
true
false
1 2 3
1 2 3
0 Durchläufe der WHILE-Schleife für i == 0
Aber: 2 Vergleiche
0 Durchläufe der WHILE-Schleife für i == 0
Aber: 2 Vergleiche
VERGLEICHE = 2
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
22
a =
b =
i = 0j = 0
1 2 3
1 2 3
falseVERGLEICHE = 4
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
23
a =
b =
i = 1j = 0
true
1 2 3
1 2 3
VERGLEICHE = 5
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
24
a =
b =
i = 1j = 0
1 2 3
1 2 3
VERGLEICHE = 6
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
25
a =
b =
i = 1j = 0
true
1 2 3
1 2 3
VERGLEICHE = 6
true
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
26
a =
b =
i = 1j = 0
1 2 3
1 2 3
VERGLEICHE = 8
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
27
a =
b =
i = 1j = 1
true
1 2 3
1 2 3
VERGLEICHE = 8
false
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
28
a =
b =
i = 1j = 1
true
1 2 3
1 2 3
VERGLEICHE = 8
false
1 Durchlauf der WHILE-Schleife für i == 1
Aber: 4 Vergleiche
1 Durchlauf der WHILE-Schleife für i == 1
Aber: 4 Vergleiche
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
29
a =
b =
i = 1j = 1
1 2 3
1 2 3
VERGLEICHE = 10false
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
30
a =
b =
i = 2j = 0
true
1 2 3
1 2 3
VERGLEICHE = 11
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
31
a =
b =
i = 2j = 0
1 2 3
1 2 3
VERGLEICHE = 12
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
32
a =
b =
i = 2j = 0
true
1 2 3
1 2 3
VERGLEICHE = 12
true
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
33
a =
b =
i = 2j = 0
1 2 3
1 2 3
VERGLEICHE = 14
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
34
a =
b =
i = 2j = 1
true
1 2 3
1 2 3
VERGLEICHE = 14
true
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
35
a =
b =
i = 2j = 1
1 2 3
1 2 3
VERGLEICHE = 16
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
36
a =
b =
i = 2j = 2
true
1 2 3
1 2 3
VERGLEICHE = 16
false
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
37
a =
b =
i = 2j = 2
true
1 2 3
1 2 3
VERGLEICHE = 16
false
2 Durchläufe der WHILE-Schleife für i == 2
Aber: 6 Vergleiche
2 Durchläufe der WHILE-Schleife für i == 2
Aber: 6 Vergleiche
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
38
a =
b =
i = 2j = 2
1 2 3
1 2 3
VERGLEICHE = 18false
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
39
a =
b =
i = 3j = 0
false
1 2 3
1 2 3
VERGLEICHE = 19
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
40
a =
b =
i = 3j = 0
1 2 3
1 2 3
VERGLEICHE = 20
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Simulation a gleich b
static boolean compareSets(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
int j = 0;
while (j < b.length && b[j] != a[i])
j++;
if (j == b.length)
return false;
}
return true;
}
41
a =
b =
i = 3j = 0
1 2 3
1 2 3
VERGLEICHE = 20
Ergebnis: TRUEVergleiche:
n2 + 3n + 2 = 20
Ergebnis: TRUEVergleiche:
n2 + 3n + 2 = 20
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Ergebnis
Bester Fall für ungleiche Längen: 1 Bester Fall für gleiche Längen: a[0] nicht in b TB = 4 + 2n Schlechtester Fall: Mengen sind gleich
Da jedes Element nur einmal vorkommt braucht man unabhängig von der Reihenfolge
• 1 x keinen Durchlauf der WHILE-Schleife für i == i0• 1 x 1 Durchlauf der WHILE-Schleife für i == i1• 1 x 2 Durchläufe der WHILE-Schleife für i == i2• etc.
Insgesamt (inklusive Schleifen-Abbrüche):n2 + 3n + 2
42
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Herleitung TW
43
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Herleitung TW
44
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Herleitung TW
45
GaußscheSummen-formel
GaußscheSummen-formel
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Tipps für Blatt 6
Aufgabe 6-1 Noch mal genau die Definition der O-Notation im Skript lesen Insbesondere muss die <= - Beziehung erst ab einem gewissen n0 gelten Bei j)
• Polynomdivision mit Rest
• Grenzwerte für n ∞ anschauen
• Bedenken: in einer Summe entscheidet der Summand mit dem schnellsten Wachstum
Aufgabe 6-2 b) Man kann so tun, als ob es tatsächlich n, log n, etc. viele Operationen gebe Für jeweils eine Operation denkt man sich eine Zeitkonstante Top , die
natürlich unabhängig von n ist.
46
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Tipps für Blatt 6
Aufgabe 6-2 c) Im Taschenrechner mit großen Zahlen für n ausprobieren Wenn f(n) langsamer wächst als g(n), dann gilt:
Graphen zeichnen lassen
• Online auf http://www.wolframalpha.com
• Sehr interessante und mächtige Such-/Informationsmaschine mit Mathe-Funktionen von Mathematica.
• Relativ kompliziert, Dokumentation für Mathe-Funktionen unter http://reference.wolfram.com/mathematica/guide/Mathematica.html
• GeoGebra (http://www.geogebra.org)
• Sehr leicht zu benutzen
47
Einführung in die Informatik: Programmierung und Software-Entwicklung, WS 09/10
Zentralübung 5
Einige einfache Klassen
48