Differences

This shows you the differences between two versions of the page.

--- lehrkraefte:blc:informatik:ffprg1-2020:arrays [2020/02/10 17:51]
Ivo Blöchliger [Aufgaben]
+++ lehrkraefte:blc:informatik:ffprg1-2020:arrays [2022/05/05 12:58] (current)
Ivo Blöchliger [Pascal-Dreieck]
@@ Line 1: / Line 1: @@
-====== Listen und Arrays ======
+====== Arrays und Tuples ======
-  * Liste: Wird mit runden Klammern geschrieben, Liste und direkter Inhalt können nicht verändert werden.
+  * Tuples: Wird mit runden Klammern geschrieben, Liste und direkter Inhalt können nicht verändert werden.
-  * Array: Wird mit eckigen Klammern geschrieben. Kann verändert werden (Länge und Inhalt).
+  * Array/Liste: Wird mit eckigen Klammern geschrieben. Kann verändert werden (Länge und Inhalt).
   * Zugriff bei beiden via eckige Klammern, z.B. a[4], Index von 0 bis Anzahl Elemente minus 1.
-Wo möglich, mit Listen arbeiten. Ist in vielen Fällen effizienter (Zeit und Speicher).
+Wo möglich, mit Tuples arbeiten. Ist in vielen Fällen effizienter (Zeit und Speicher).
 <code python>
-a = (1,4,9,16)
+a = (1,4,9,16)  # Tuple
-b = [1,4,9,16]
+b = [1,4,9,16]  # Array/Liste
 print(a[2])  # Liefert 9
 b[2]=8       # Eintrag kann verändert werden
 print(b)
-a[2]=8       # Fehler bei der Ausführung, Liste kann nicht verändert werden.
+a[2]=8       # Fehler bei der Ausführung, Tuple kann nicht verändert werden.
 </code>
 ==== Wichtige Funktionen und Methoden ====
-  * len: Anzahl Element einer Liste/Array
+  * ''len'': Anzahl Element einer Liste/Array, z.B. ''len(a)'' wenn a ein Array enthält.
-  * Negative Indizies: a[-1] -> a[len(a)-1] (letztes Element), a[-2] ist zweitleztes Element etc.
+  * Negative Indexe: ''a[-1]'' -> ''a[len(a)-1]'' (letztes Element), ''a[-2]'' ist zweitletztes Element etc.
-  * Unterliste/Array mit a[2:4] -> Liste/Array mit den Elementen a[2] und a[3]
+  * Unterliste/Array mit ''a[2:4]'' -> Liste/Array mit den Elementen ''a[2]'' und ''a[3]''  (gleiche Logik wie bei range)
-  * Anfang  a[:3] -> a[0:3], Ende a[5:] -> a[5:len(a)]
+  * Unterliste/Array mit ''a[2:10:2]'' -> Liste/Array mit den Elementen der Indizies 2,4,6 und 8. ''a[Untergrenze:Obergrenze:Schrittweite]''.
+  * Array/Liste «umdrehen»: ''a[::-1]'' (Letztes Element an erster Stelle etc.)
+  * Anfang  ''a[:3]'' -> ''a[0:3]'', Ende ''a[5:]'' -> ''a[5:len(a)]''
 Nur für Arrays:
-  * a.append(5) -> zusätzliches Element hinten anfügen
+  * ''a.append(5)'' -> zusätzliches Element hinten anfügen
+  * ''tuple(a)'' -> Konvertiert ein Array in ein Tuple
 Weitere nützliche Methoden: https://www.w3schools.com/python/python_ref_list.asp
@@ Line 40: / Line 43: @@
 feld = [ [x*y for y in range(1,4)] for x in range(1,4) ]
 print(feld)
+</code>
+==== Loop über Arrays ====
+<code python>
+quadrate = [i**2 for i in range(1,9)]
+# Loop über alle Elemente
+for q in quadrate:
+  print("%d ist eine Quadratzahl" % q)
+# Loop mit Index über alle Elemente
+for i,q in enumerate(quadrate):
+  print("quadrate[%d]=%d" % (i,q))
 </code>
 ====== Aufgaben ======
+===== Array-Rätsel =====
+Geben ist folgendes Array:
+<code python array.py>
+a = [58, 64, 2, 79, 92, 46, 80, 54, 50, 86, 72, 50, 84, 37, 76, 84, 14, 60, 99, 65, 66, 47, 28, 48, 38, 51, 17, 51, 6, 73, 20, 5, 83, 15, 43, 76, 93, 53, 65, 15, 91, 64, 86, 1, 63, 82, 96, 96, 35, 62, 37, 55, 51, 39, 96, 5, 24, 31, 23, 45, 75, 100, 81, 57, 67, 1, 55, 21, 80, 77, 89, 13, 75, 7, 49, 28, 31, 30, 41, 1, 57, 58, 75, 42, 14, 47, 64, 59, 9, 95, 59, 68, 74, 60, 99, 93, 39, 38, 65, 24]
+</code>
+Gesucht sind folgende Dinge (wenn es mehrere Lösungen geben sollte, ist immer nur die erste auszugeben)
+  * Position und Wert des kleinsten und grössten Elements
+  * Position und Länge der längsten Sequenz strikt aufsteigender Zahlen
+  * Position und Länge der längsten Sequenz ungerader Zahlen
+<code>
+Minimum 1 bei Index 43
+Maximum 100 bei Index 61
+Aufsteigende Sequenz mit Länge 4, Start bei 33, Sequenz [15, 43, 76, 93]
+Ungerade Sequenz mit Länge 6, Start bei 62, Sequenz [81, 57, 67, 1, 55, 21]
+</code>
+<hidden Lösungsvorschläge>
+<code python arraysuche.py>
+a = [58, 64, 2, 79, 92, 46, 80, 54, 50, 86, 72, 50, 84, 37, 76, 84, 14, 60, 99, 65, 66, 47, 28, 48, 38, 51, 17, 51, 6, 73, 20, 5, 83, 15, 43, 76, 93, 53, 65, 15, 91, 64, 86, 1, 63, 82, 96, 96, 35, 62, 37, 55, 51, 39, 96, 5, 24, 31, 23, 45, 75, 100, 81, 57, 67, 1, 55, 21, 80, 77, 89, 13, 75, 7, 49, 28, 31, 30, 41, 1, 57, 58, 75, 42, 14, 47, 64, 59, 9, 95, 59, 68, 74, 60, 99, 93, 39, 38, 65, 24]
+minimum = a[0]  # Kleinster Wert
+minpos=0        # Index vom kleinstem Wert
+maximum = a[0]  # Grösster Wert
+maxpos=0        # Index vom grössten Wert
+maxlen = 1      # Maximale Länge aufsteigender Sequenz
+inclen = 1      # Aktuelle Länge der Sequenz
+incpos = 0      # Startposition der längsten Sequenz
+oddlen = 0      # Aktuelle Länge ungerader Sequenz
+oddpos = 0      # Startposition der längsten Sequenz
+maxodd = 0      # Maximale Länge der Sequenz, die bis jetzt gefunden wurde.
+for i in range(len(a)):
+    if a[i]<minimum:  # kleineres Element?
+        minimum=a[i]
+        minpos = i
+    if a[i]>maximum:  # grösseres Element?
+        maximum=a[i]
+        maxpos = i
+    if i>0 and a[i]>a[i-1]:  # Aufsteigend?
+        inclen+=1
+        if (inclen>maxlen):  # Besser als bereits gefunden?
+            maxlen=inclen
+            incpos = i-maxlen+1
+    else:
+        inclen=1       # Nicht aufsteigend, Beginn neuer Sequenz
+    if a[i]%2==1:      # Ungerade?
+        oddlen+=1
+        if oddlen>maxodd:
+            maxodd=oddlen
+            oddpos = i-maxodd+1
+    else:              # Gerade
+        oddlen=0
+print("Minimum %d bei Index %d" % (minimum, minpos))
+print("Maximum %d bei Index %d" % (maximum, maxpos))
+print("Aufsteigende Sequenz mit Länge %d, Start bei %d, Sequenz %s" % (maxlen, incpos, str(a[incpos:(incpos+maxlen)])))
+print("Ungerade Sequenz mit Länge %d, Start bei %d, Sequenz %s" % (maxodd, oddpos, str(a[oddpos:(oddpos+maxodd)])))
+</code>
+</hidden>
+===== Fibbonacci-Zahlen =====
   * Erzeugen Sie ein Array mit gegebener Länge mit den Fibbonacci-Zahlen: [0,1,1,2,3,5,8,13,21,34,...]
   * Bilden Sie auf dem Array mit den Fibbonacci-Zahlen ein Array mit den Quotienten zweier aufeinanderfolgenen Fibbonacci-Zahlen
-  * Erzeugen Sie ein zweidimensionales Array mit dem Pascal-Dreieck und geben Sie dieses "schön" aus.
-  * Gegeben ist ein String mit lauter unterschiedlichen Buchstaben, z.B. "ABCD". Erzeugen Sie ein Array mit allen möglichen Permutationen der Buchstaben (d.h. alle möglichen Wörter mit genau diesen 4 Buchstaben). Für "ABC" erhält man dann ["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"].
+<hidden Lösungsvorschläge>
-    * **Challenge**: Gegeben ist ein String mit lauter unterschiedlichen Buchstaben, z.B. "BCAED". Berechnen Sie die lexikographisch nächste Permutation, in diesem Fall "BCDAE".
+<code python fib.py>
+n=20  # 20 Fibbonacci-Zahlen
+fib = [0,1]
+for i in range(n-2):
+    fib.append(fib[-1]+fib[-2])
+print(fib)
+quotient = [fib[i]/fib[i+1] for i in range(n-1)]
+print(quotient)
+</code>
+</hidden>
+===== Pascal-Dreieck =====
+  * Erzeugen Sie ein zweidimensionales Array mit dem Pascal-Dreieck.
+  * **Challenge**: Geben Sie dieses "schön" aus (wie unten):
+<code>
+[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1], [1, 6, 15, 20, 15, 6, 1], [1, 7, 21, 35, 35, 21, 7, 1], [1, 8, 28, 56, 70, 56, 28, 8, 1], [1, 9, 36, 84, 126, 126, 84, 36, 9, 1], [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1]]
+
+   1
+   2   1
+   3   3   1
+   4   6   4   1
+   5  10  10   5   1
+   6  15  20  15   6   1
+   7  21  35  35  21   7   1
+   8  28  56  70  56  28   8   1
+   9  36  84 126 126  84  36   9   1
+  10  45 120 210 252 210 120  45  10   1
+</code>
+<hidden Lösungsvorschläge>
+Erzeugung des Dreiecks:
+<code python>
+n = 10
+p = [[1]]
+for zeile in range(n):
+    neu = [1]  # Neue Zeile mit einem 1 beginnen
+    for index in range(zeile):  # So viele Zahlen der neuen Zeile hinzufügen
+        # Aus der letzten Zeile p[-1] benachbarte Einträge zusammenzählen
+        neu.append(p[-1][index] + p[-1][index+1])
+    neu.append(1)   # Neue Zeile mit 1 beenden
+    p.append(neu)   # Neue Zeile dem Resultat hinzufügen
+print(p)
+</code>
+Folgende Lösung ist keine schöne Lösung, schon eher eine Aufgabe in sich, den Code zu verstehen.
+<code python pascaldreieck.py>
+n=10  # Anzahl Zeilen
+space = 4
+p = [[1]]
+for i in range(n):
+    p.append([1]+[p[-1][j]+p[-1][j+1] for j in range(i)]+[1])
+for i in range(n+1):
+    print((" "*((n-i)*space//2)+("%"+str(space)+"d")*(i+1))%tuple(p[i]))
+</code>
+</hidden>