Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
gf_informatik:suchen_und_sortieren [2024-02-04 09:18] – [Aufgabe A1 - 079] hofgf_informatik:suchen_und_sortieren [2025-02-17 10:15] (aktuell) – [Aufgabe A3: Zäh Millione Kombinatione] hof
Zeile 22: Zeile 22:
  
 Der Sänger von _079_ will die Telefonnummer der Angebeteten unter allen möglichen Schweizer Mobilfunknummern (10-stellig) mit dem Präfix `079` herausfinden. Dafür probiert er sämtliche Nummern von `079 000 00 00` bis `079 999 99 99` durch, was natürlich ziemlich lange dauert... Der Sänger von _079_ will die Telefonnummer der Angebeteten unter allen möglichen Schweizer Mobilfunknummern (10-stellig) mit dem Präfix `079` herausfinden. Dafür probiert er sämtliche Nummern von `079 000 00 00` bis `079 999 99 99` durch, was natürlich ziemlich lange dauert...
- 
 #### Aufgabe A1 - 079 #### Aufgabe A1 - 079
  
Zeile 33: Zeile 32:
 1. Wie lange dauerte die Suche, wenn wir nicht einmal die Vorwahl kennen würden (aber wüssten, dass alle Nummern mit `0` beginnen)? 1. Wie lange dauerte die Suche, wenn wir nicht einmal die Vorwahl kennen würden (aber wüssten, dass alle Nummern mit `0` beginnen)?
  
-<nodisp 2>+<nodisp 1>
 ++++Lösung| ++++Lösung|
  
Zeile 55: Zeile 54:
 === Aufgabe A2: Lineare Suche in Python === === Aufgabe A2: Lineare Suche in Python ===
  
-Betrachte folgenden Datensatz mit Namen und Telefonnummern. Wir haben zwei parallele Listen, die erste mit Namen, die zweite mit den dazugehörigen Telefonnummern.+Betrachte folgenden Datensatz mit Namen und Telefonnummern. Wir haben zwei parallele Listen, die erste mit Namen, die zweite mit den dazugehörigen Telefonnummern. Am gleichen Index ist in der ersten Liste der Name, in der zweiten die Telefonnummer gespeichert.
  
-Zum Beispiel ist die Telefonnummer von Anela 0790000001.+Zum Beispiel finden für den Index `1` Anela in `names[1]` und ihre Nummer 0790000001 in `numbers[1]`.
  
 <code python lineare_suche.py> <code python lineare_suche.py>
Zeile 76: Zeile 75:
  
 ++++Tipps (zuerst ohne Tipps versuchen!)| ++++Tipps (zuerst ohne Tipps versuchen!)|
-  - Gehe IN der Funktion die Liste alle möglichen Indices (Positionen) durch. +  - Gehe IN der Funktion die Liste `l` alle möglichen Indices (Positionen) durch. 
-  - Vergleiche das Element an jedem Index mit dem gesuchten Wert. +  - Vergleiche das Element an jedem Index mit dem gesuchten Wert `v`. 
-  - Wenn es gleich ist: Gebe den Index zurück.+  - Wenn es gleich ist: Gib den Index zurück.
   - Ausserhalb der Funktion: Lese nun aus der **anderen** Liste das Element mit dem eben ermittelten Index aus.   - Ausserhalb der Funktion: Lese nun aus der **anderen** Liste das Element mit dem eben ermittelten Index aus.
 ++++ ++++
Zeile 101: Zeile 100:
 Für das kleine Telefonbuch oben ist es nicht so wichtig, wie schnell der Such-Algorithmus ist. Was aber, wenn wir wirklich alle 10 Millionen Kombinationen durchprobieren? Für das kleine Telefonbuch oben ist es nicht so wichtig, wie schnell der Such-Algorithmus ist. Was aber, wenn wir wirklich alle 10 Millionen Kombinationen durchprobieren?
  
-Lade die Datei [[https://kantonsschuleromanshorn.sharepoint.com/:u:/s/FSInformatik/EQpO02ZUBldHmbYjEgKka_YBeaBaTHf1IUd-lrtYrdZJkA?download=1|null79.py]] herunter und speichere sie im selben Verzeichnis wie dein Code.+Für diese Aufgabe benötigst du zusätzlich eine weitere Python-Datei, `null79.py`, die wir in unserem selbstgeschriebenen Code importieren. Dazu verwenden wir ähnlich wie zu Turtle-Zeiten das Schlüsselwort `import`:
  
-Du kannst das Telefonbuch wie folgt importieren und den Namen für eine Telefonnummer herausfinden. Der Code muss im gleichen Ordner wie `null79.py` abgespeichert werden (**funktioniert nur in TigerJython, aber nicht in WebTigerJython**)!+<code python> 
 +from null79 import names, numbers 
 +</code> 
 + 
 +Damit das funktioniert, muss die Datei `null79.py` im gleichen Ordner gespeichert sein, wie unser selbstgeschriebener Code. 
 + 
 +== Mit WebtigerPython == 
 +Am einfachsten geht das mit [[https://webtigerpython.ethz.ch/?code=NobwRAdghgtgpmAXGGUCWEB0AHAnmAGjABMoAXKJMAMwCcB7GAAggFcAbdgdgE4m0Y2erTItYcAM4EWrGACM4tCQB0IqjMTgAPJgF4mAFgBMq6PD1j4E4Bu0BdVWTjsItC23mLrtrQ4jZaDDIACmUwABE0OCYAFWc4anoID3g3ADckpjCmAGpLaLzstAlRbLynF1oASjAAXwJwMwRkNk5eHHwiUgoqAGIAQgB6VglaQbkMQbwyAAsk1V6mAFoAKiWmAGN6YgwAc0QmVjJqAA5ltfVBYVEyAThpEsCIXelUWdVVDfYoCQkmAGVsFAlHAAApzCBwABC9HoAGtglVEKomKismAwmEAIJMCRAkFMdjFG4zchMWhwMisWgQP6zaIUtJeODEfiaCC3Mi4JiJNxQJi7NBMiD8CCaLTSAIJNBaFlMADuaHeIrRaP5UuoMswmIxGJVqM01CYAH1jRglabghJnNRJRTNVpdGEAAy8MJIlGqtHW9jUTDG9hwZ6zCwARmdEcjzs9XtxNv9GplFkTWg--qYhpNAaDlp91A96dVFKpNLjvv9geDMzTqszpt2lKVcBguZt0jQBdjqLQRq52DgwQ7_D-EHooiCyMLXdo6GtTAAkmLtABRWgMWihMCLtJQImsnwHMq4sgbjtVGNenv8JgAHiYzsnXcvuX0latNvPU-7Rudt_0aFvQkg3fX1OyfNFi2pEU8wTe0kzyXk3mCN88yqZYmFDdC0GkF0j0eQcOWCN4Zkwdh6F2cNkOA1Cqlo3J0TUMBPyfGdimiRdxVXddNw47QmHoI5-KNGdnjgQ8wHo_CzzTL4fj-QFgWtAAZYlEUfNEdWxXF8WtaRd2wUkFFuDZd3YbkJGuOUiRKJhZjJTQnFoGBzRKNATM4blIJpP4oAvNEmh5YQmDgKANhmAUhSDUVxWkbQNjgbBRF5Jh-WtDZiyYOE4FwQYd3YVhoiBNBaG1XVMXTOszQgC1jRA20gKrB44HSyljSy3AmpashjTygrpE0b5cF0Z0wNjGDjQGqBuX0SbcD87142zKsLErXZlSfca0uLNrsosLbWva-bUU25rtt66J9H27rzqOss_R6-h5WcP59AAcigOA0AE17bvGrZaSSKAORephgDCwK3HBjBjyeXZMB-DY0DQANHsUEy5yvcHR3HaDFoyJ72AkPwNsW4gBLkQMQdeuRiGoXZ2BgfwlDIH6vzu_1Ek4VGlD2yziDq_18eeyTSfJynPwvSrK1bUD1NjLzcfLJa1urdNJYSE1IS0br9MMyk6ukb4SlGr0jdEV8fjIUjucRW6rzN4AllDOxRXZh6CYkOXwIVt3_os6Bgbto03zNtC7yML2WMpKC3aFwmg8JS3HaMF3ob-pJ_aBshPduoto9Lca45UNmffGzmyKepQL3Vo1jQbSEZycY0mgN_gTdVTSIkpRRnOq1z3LMgUg0UchonpfIUpx8VrzoRhbJmaIoB3NBvgpxf2AMqAjKYBReWiK6et3ArSs0tQ2avADdEuxaD_ayPp3zxX7oPm7z6NAC7xOrqdtwe-xooEQFhoxs1VEGVk18la32yrnNUG89bmxhnseGEhEbI1YNgfstB0ZwGAA-R4SCEZI2NOgzB2DMA-AFsaF-R8cHOjsFUYm4FUTsBWsBXWW9KTMS7M9MSMDjoAIQV_ba7V6Khj4cFMUrCIB1S4Uw9h29LongISgohJC0Y_Bwfg54yDUHEIweo605ClxaEodQ_KtD6E5FDIgRhTCAJLAgc_U6B1dp5DEWfJ8ixARElEMAEowIyCIDAanDk9BCTBQAI6sF3EsCQaAABecogiKDyn8egRp-SrRDOklKcgBI40cnlQY7BbosNfGwuBHCyCyK9OApgxFMDxRXsEYIYD0L-JEGhQYhIamqh8BYIIg4mCDG6cQXp_lxAWHkZSGwxjbHPn_EwAApBmGsXZ5QzBXtEVkAA-DCf8vTTMEYtLWOtKlGWCE0cZsYykNWCEc65tSLANKaewYIrJunsEeX04xAzCIARGRmb5EzzA5H0Ec2Z4p5lPkvteFZxBbo-yaGsg0Gt6yNicC2WqeZ2ztzRLceAmAJCBgSpQ2ajyrx9gHEOYoLAxyikCeI1ic5eJaC4sIHiEA8poH3MY8SkkTyDlognD-94Dl9JfHc1CIq9COP9FA3-TLH5uzMQVRFyrxr1xHk3FuHY0weAUDzfQCkQTgiSNCWECIXRuiYqYcQIMTXKVUuGKMEZpAAGYeAAFZ3UnGMNIV6SlcBA2gK9GotQ7BAA&vanilla_python=true|diesem WebtigerPython-Link]] - die Datei ist hier bereits hinterlegt. 
 + 
 +== Mit TigerPython == 
 +Lade die Datei [[https://kantonsschuleromanshorn.sharepoint.com/:u:/s/FSInformatik/EQpO02ZUBldHmbYjEgKka_YBeaBaTHf1IUd-lrtYrdZJkA?download=1|null79.py]] herunter und speichere sie im selben Ordner wie dein Code. 
 + 
 +Du kannst das Telefonbuch wie folgt importieren und den Namen für eine Telefonnummer herausfinden. Der Code muss im gleichen Ordner wie `null79.py` abgespeichert werden!
  
 <code python> <code python>
Zeile 113: Zeile 124:
 print("Die Telefonnummer von " + name + " ist " + telnr) print("Die Telefonnummer von " + name + " ist " + telnr)
 </code> </code>
 +
 +== Aufgabe ==
  
 Verwende deine `linear_search()` Funktion, um die richtige Telefonnummer von Lyanna herauszufinden. Wie lange dauert die Suche? Verwende deine `linear_search()` Funktion, um die richtige Telefonnummer von Lyanna herauszufinden. Wie lange dauert die Suche?
  
-<nodisp 2>+<nodisp 1>
 ++++Lösung mit Code| ++++Lösung mit Code|
 <code python Aufgabe A3.py> <code python Aufgabe A3.py>
Zeile 135: Zeile 148:
     print("Die Telefonnummer von " + name + " ist " + tel)     print("Die Telefonnummer von " + name + " ist " + tel)
     print("144 hei si gseit!")     print("144 hei si gseit!")
-    print("Wie isch das nume passiert, hei si seit.") +    print("Wie isch das nume passiert, hei si gseit.") 
-    print("Hueresiech, hei si seit, ey")+    print("Hueresiech, hei si gseit, ey")
 </code> </code>
  
Zeile 152: Zeile 165:
 # do something # do something
 elapsed = time.time() - start elapsed = time.time() - start
-print("do something took {0}s".format(elapsed))+print("do something took " + str(elapsed) + "s")
 </code> </code>
  
-<nodisp 2>+<nodisp 1>
 ++++Lösung| ++++Lösung|
 <code python time_algos.py> <code python time_algos.py>
Zeile 186: Zeile 199:
 ++++ ++++
  
-<nodisp 2>+<nodisp 1>
 ++++Code| ++++Code|
 <code python> <code python>
Zeile 195: Zeile 208:
 </nodisp> </nodisp>
  
-=== Aufgabe A5: Verbesserte lineare Suche (optional) ===+=== Aufgabe A6: Verbesserte lineare Suche (optional) ===
  
 Wenn wir nach einem Namen suchen, der gar nicht in der Liste vorkommt, z.B. `Alaska`, so dauert die Suche lange, weil die ganze Liste durchsucht wird. Wenn wir nach einem Namen suchen, der gar nicht in der Liste vorkommt, z.B. `Alaska`, so dauert die Suche lange, weil die ganze Liste durchsucht wird.
Zeile 215: Zeile 228:
   * Ist die Liste sortiert, soll die Suche abbrechen, wenn wir im Alphabet bereits weiter sind als der gesuchte Wert.   * Ist die Liste sortiert, soll die Suche abbrechen, wenn wir im Alphabet bereits weiter sind als der gesuchte Wert.
  
-<nodisp 2>+<nodisp 1>
 ++++Lösung| ++++Lösung|
 <code python> <code python>
Zeile 229: Zeile 242:
 </nodisp> </nodisp>
  
-=== Aufgabe A6: Besserer Algorithmus? (optional) ===+=== Aufgabe A7: Besserer Algorithmus? (optional) ===
  
 Hast du eine Idee für einen besseren, sprich effizienteren Suchalgorithmus einer bereits sortierten Liste? Bespreche mit der Lehrperson und implementiere danach in Python. Hast du eine Idee für einen besseren, sprich effizienteren Suchalgorithmus einer bereits sortierten Liste? Bespreche mit der Lehrperson und implementiere danach in Python.
  • gf_informatik/suchen_und_sortieren.1707038322.txt.gz
  • Zuletzt geändert: 2024-02-04 09:18
  • von hof