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 [2025-10-29 14:11] – gragf_informatik:suchen_und_sortieren [2026-04-04 20:02] (aktuell) – hof
Zeile 1: Zeile 1:
 ====== Suchen und Sortieren ====== ====== Suchen und Sortieren ======
 +<html><script type="module" src="https://bottom.ch/editor/stable/bottom-editor.js"></script></html>
  
 Weiter zu [[gf_informatik:suchen_und_sortieren:binaersuche|Binäre Suche]] Weiter zu [[gf_informatik:suchen_und_sortieren:binaersuche|Binäre Suche]]
Zeile 7: Zeile 8:
 ++++Lernziele lineare und binäre Suche:| ++++Lernziele lineare und binäre Suche:|
    * Ich kann erklären, wie die lineare Suche und wie die binäre Suche funktioniert.    * Ich kann erklären, wie die lineare Suche und wie die binäre Suche funktioniert.
-   * Ich kann die beiden Such-Algorithmen (linar und binär) miteinander vergleichen, d.h. Unterschiede, Vor- und Nachteile/Voraussetzungen erklären.  +   * Ich kann die beiden Such-Algorithmen (linear und binär) miteinander vergleichen, d.h. Unterschiede, Vor- und Nachteile/Voraussetzungen erklären.  
-   * Ich kann für eine gegebene Anzahl Einträge (Listen-Länge) die maximale Anzahl Suchanfragen für beide Such-Algorithmen berechnen.+   * Ich kann für eine gegebene Anzahl Einträge (Listen-Länge) die maximale Anzahl Abfragen für beide Such-Algorithmen berechnen.
    * Ich kann eine Funktion ''linear\_search(list, value)'' definieren, die nach der linearen Suche die **Position** von ''value'' in ''list'' zurückgibt.     * Ich kann eine Funktion ''linear\_search(list, value)'' definieren, die nach der linearen Suche die **Position** von ''value'' in ''list'' zurückgibt. 
    * Ich kann eine Funktion ''binary\_search(list, value)'' definieren, die nach der binären Suche die **Position** von ''value'' in ''list'' zurückgibt.    * Ich kann eine Funktion ''binary\_search(list, value)'' definieren, die nach der binären Suche die **Position** von ''value'' in ''list'' zurückgibt.
 +   * Ich kann Suchfunktionen (linear und binär) verwenden, um in mehreren zusammenpassenden Listen zusammengehörende Elemente zu finden – Beispiel: Ausgehend vom Namen über dessen Index in der Namensliste die entsprechende Nummer aus der Nummernliste ermitteln.
 ++++ ++++
  
Zeile 31: Zeile 33:
  
 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 41: Zeile 44:
 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 65: Zeile 68:
 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. 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 finden für den Index `1` Anela in `names[1]` und ihre Nummer 0790000001 in `numbers[1]`.+Zum Beispiel finden wir für den Index `1` Anela in `names[1]` und ihre Nummer 0790000001 in `numbers[1]`.
  
-<code python lineare_suche.py>+<html><bottom-editor autorun>
 names = ['Aja', 'Anela', 'Arwen', 'Isra', names = ['Aja', 'Anela', 'Arwen', 'Isra',
          'Juno', 'Kaida', 'Loelia', 'Luna',          'Juno', 'Kaida', 'Loelia', 'Luna',
Zeile 76: Zeile 79:
            '0790000008', '0790000009', '0790000010', '0790000011',            '0790000008', '0790000009', '0790000010', '0790000011',
            '0790000012', '0790000013', '0790000014', '0790000015']            '0790000012', '0790000013', '0790000014', '0790000015']
-</code>+</bottom-editor></html> 
   - Schreibe eine Python-Funktion `linear_search(l, v)`. Die Funktion soll in der Liste ''l'' nach dem Wert ''v'' suchen. Falls er gefunden wird, soll __die Position (Index)__ des Elements in der Liste //zurückgegeben// werden (*nicht* geprintet!).    - Schreibe eine Python-Funktion `linear_search(l, v)`. Die Funktion soll in der Liste ''l'' nach dem Wert ''v'' suchen. Falls er gefunden wird, soll __die Position (Index)__ des Elements in der Liste //zurückgegeben// werden (*nicht* geprintet!). 
   - Test: Der Funktionsaufruf `print(linear_search(names, 'Anela'))` soll $1$ ausgeben.   - Test: Der Funktionsaufruf `print(linear_search(names, 'Anela'))` soll $1$ ausgeben.
Zeile 84: Zeile 88:
  
 ++++Tipps (zuerst ohne Tipps versuchen!)| ++++Tipps (zuerst ohne Tipps versuchen!)|
-  - Gehe IN der Funktion die Liste `l` alle möglichen Indices (Positionen) durch. +  - Gehe IN der Funktion die Liste `l` alle möglichen Indices (Positionen) durch ([[gf_informatik:programmieren_iii#indirekte_for-schleife|indirekte for-Schleife]]). 
-  - Vergleiche das Element an jedem Index mit dem gesuchten Wert `v`.+  - Vergleiche das Element an jedem Index (also `l[index]`) mit dem gesuchten Wert `v`.
   - Wenn es gleich ist: Gib 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 91: Zeile 95:
  
  
-<nodisp 2>+<nodisp 1>
 ++++Lösung| ++++Lösung|
-<code python>+<html><bottom-editor>
 def linear_search(l, v): def linear_search(l, v):
     for i in range(len(l)):     for i in range(len(l)):
Zeile 102: Zeile 106:
 index = linear_search(names, 'Lyanna') index = linear_search(names, 'Lyanna')
 print(numbers[index]) print(numbers[index])
-</code>+</bottom-editor></html>
 ++++ ++++
 </nodisp> </nodisp>
Zeile 109: Zeile 113:
 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?
  
-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`:+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`.
  
-<code python>+Verwende deine `linear_search()` Funktion, um die richtige Telefonnummer von Lyanna herauszufinden. Wie lange dauert die Suche? 
 + 
 +<html><bottom-editor timeout="180" zip="https://sca.ksr.ch/lib/exe/fetch.php?media=gf_informatik:programmieren_i:null79.py.zip" session="10m">
 from null79 import names, numbers from null79 import names, numbers
-</code> 
  
-Damit das funktioniert, muss die Datei `null79.py` im gleichen Ordner gespeichert sein, wie unser selbstgeschriebener Code.+index = 42  # TODO: Suche den Index von Lyanna! 
 +name = names[index] 
 +tel = numbers[index] 
 +print(f'Die Telefonnummer von {name} ist {tel}') 
 +</bottom-editor></html> 
 + 
 +Oben ist die Datei `null79.py` bereits im gleichen Ordner hinterlegt - wenn du den Code in TigerJython oder VisualStudioCode ausführst, muss die Datei ebenfalls dort abgespeichert werden.
  
-== Mit WebtigerPython == +== Mit WebTigerPython == 
-Am einfachsten geht das mit [[https://wtp.ethz.ch/#?layout=%5B%22Editor%22%2C%20%22Console%22%5D&code=NobwRAdghgtgpmAXGANgezQBwHSYJ5gA0YAJlAC5RJgCMADAEyE00AszLzdAnIQMxMW7FgHYOdcVxod2ArgFYuvFoM5COANn6C6Y-ovoAOLse6LueusaOEzm23poHdHRXPpdLz61dvnLPqYGNFoWrp7hrBKsNGAAvoTg0PDUMFAAlhC4BMRklNQAZgBOaDAABBAArigoItxl6TCYaEXkFbBwAM6EFZUwAEZwRZ0AOhBlY5kkcAAeZQC8ZawMY8lwC-3wncBTswC6Y-RwKBBFG1UDQ9u7MwcQmEWZ5AAUI2AAIunrACrHcAVoCAXeBnABugImYDKAGpNutYW8Gp02ojYUcTkUAJTxRKQDrUKo1OrZIikChUZAAYgAhAB6SqdIq0_qZWn4cgAC0BY0pZQAtAAqPllADGaBImQA5ogypVyAVDPyhZMmi02uRGnAesjHhBJT00pyxmMRSgoJ1OmUAMqYKDDOAABS5EDgACEMABrZ6YxBjMr-yFvN4AQTKnVt9rKKHSyLKnIoZSKcHIlSKEEtnPWSdBVzgJAa0wgGvIeDKALOUDKkvSOfGNx6D3-6RmebKAHd0kbxgGA5XGwVm9gg2Ag93_dMCmUAPpTzKdmfPTrHAoNpMDmbzN66bhvH1-nsBpcoArYKcoOB6zkbeh0W93_cHsPL0_95sbV8zY1jsoT6dni8LkeBR7t-PZJimaZPsep7npeHJfj2v4zpKyadnAMCAcuPTpCBj7-ukk4lpgcDPDhSIVGgbRPL6oF4UUGRLmUACSEDTDMACiRQlEUrxgCxoJQNG-Y3DKqJhuQPE4ZiD4HgRDRlAAPGUdA0XhskwossGLsu0m0fhk50IpizpIpUYXtpx64WpAbgam4xAS-a5vrC5aGs8WlAZi_JlDQ3npD0W5iTqpFFs8hoctg6CSvQ7nmZ5mIJTCkIQLuMlgQx6wsWxnHcbxWWzGUaByoVk70XqcCiVCsLBVJX6mualo2naS4ADIxi8Vn-sOIZhhGS49IJmAclAgwaiKgkoKWnRqq20axvGbTTEcRQwHOyLpONNSlrZaaWlAaX-msZYtGUcBQCKHJVjWF4NKxsw9LMIpwJgbTlmUlZLiK4FlB6cB4LSAkoJU6y2ukRRDiOkMyUhs4QPOU4WSuZlwdqcBfcmU6_XgqPo-QU6A8DPTTGaeDzHQnUHg5U7E1ApaLDTeAHf6VOwZKV6aRebPwXpUEnlOn3gZjf0bALGNY0zvOnqLeME-sizS_jgnAxLVPgm2xyWosADkUBwOkRVayrz5TmK6aAlARaa2UwAXcdZy25k4m6pK2DmiK6TpGeaDq0U42MXJtsQJRt2S_j3sa3calUyQRX9OeVta_0JAFJKKAwPcwzkIbPNUwCNTh8MIszSQiOnmrGtJdHsfx7p0P_H-sGYZZql0cmdmh6zXY9nXk5Ti6Mx44Nw2jYjPRmsiFM9uPbSaea5CRQX3oS3J0_AHyNB7CHqvhygnQt9ZiZt5BVOm9N0CW8vk5adPXlKQw-_WTt9nG-Xu-X1Gc9rwwm-OyfgJnxbcge8JZgSPs_aCYd1Zvx5k_UOed0A-1GN-Hu04UIunokcPuHRR4NEngGbqHxkxDFWnDdam1JpVgvEMCg6xMxwnelRO6cwTLFFKHGDk6woACXSGaOOnCUBDRGsmMogxyzrAVrLCG3UUo8zkiZeY8tjYKyxg_NSsCqYSKVnAd-JklIaLRoLFRIDDyUFaBsOgxj_QXnzIoiByi_qWPegI4ewj5YSSlK7To7tPaVEwMRX25o4DABUjqDxbsPZTl8f4v2cBsA3FLvzAxGNZbBL2JiSOB8owbC0kPIR5BdJqQ1hVRxyI7Qz1DvY0ssIaCOOsdkuKOlHG5NGiLdxepPHeMiX4oYMTgChPaeEnx3SAlLjiUwhJmigZBLoGk6ENBEAZIPiZPkti-aVKSjUmRaleQ2mjG0PppjyCIGsT_IsaAslwAAI6VEEnyTo6QABerYnhDEBpaNAk5Kyd0uh896_QiqMOWoDWkKAJYoHqRAZ4zTkwFLwjYso4VsBPR4c8Z4dThSlNaF5WkUZYWPhuBsJ4pEyi0hxSQPFB4jqLGheQHYTDFnqWMmUAApD-BCeE2wch4esfMAA-Hyqi8I0pFsbfug9nF5OeGsClalwUc0hTSmVcKNiIuRSgZ4-YcUoCVfiphhLQomVJT-HVlKOgaScYI0adK2IMrUvI-SrKSAS1gWsdl4567IVQkcDCCMgLYTwf6DU8BsCdHPM9BJDMTVySIiRMiMYKKAsFY-eiMZMpMJyi0PKEBAbpGEkwyqlcJKkQSjo0yKlHEmWhPKxGUbJzyNWVLJJeMjE81ARBcBaym2Kymc6sBoc0HUMwWsYtX4LiDELosJq9onSAjdJ6Xi25UpAg6FbKdrV2rPBvHeW8PQ-BmD4IYZYPQtYtTwBbaAWtsRxD2EAA|diesem WebtigerPython-Link]] - die Datei ist hier bereits hinterlegt.+Am einfachsten geht das mit [[https://wtp.ethz.ch/#?code=NobwRAdghgtgpmAXGANgezQBwHSYJ5gA0YAJlAC5RJgCMADAEyE00AszLzdAnIQMxMW7FgHYOdcVxod2ArgFYuvFoM5COANn6C6Y-ovoAOLse6LueusaOEzm23poHdHRXPpdLz61dvnLPqYGNFoWrp7hrBKsNGAAvoTg0PDUMFAAlhC4BMRklNQAZgBOaDAABBAArigoItxl6TCYaEXkFbBwAM6EFZUwAEZwRZ0AOhBlY5kkcAAeZQC8ZawMZWUAxGUAKgDyACLbiGUAypUAxgAWcGXT4wCSENNzAG5o4wAyeFAQ0ACEY8lXRYAzrAKazAC6Y3IcBQECKC16AyGILBM0hEEwRUy5AAFAUAOS7dJXTYwuAFV5VGDweEvcYgAFxBqdNogaGwopxfEASniiUgHWoVRqdWyRFIFCoyDWPwA9JVOkVZf1MrL8ORzq8xhsALQAKh1ZVOaBImQA5odKuQCoYyvqdZMmi02uRGnAeiysRAzT00hqxmNTigoJ1OsdMFBhnAAAqaiBwABCGAA1jjuYgxqtViMwDmcwBBMqdCNRsoodIssoaihlIpwciVIoQMMaq51p7IuAkBo3V3kPBlCnwqBlM3pDvjVE9THk9IzLtlADu6X94yzWZHM4Kc-wedzubXq2mBTKAH1T5kV-ecZ0YQVp3XtzN5jndNwc-nM-us7eUAVsKeKBwN6GoIvQdAQZBX7fkWd4AVuc4IghMwBoe1zkmegHAdev4FJ-aHrnWDZNrBf4AUBIHnKh67HphZr1iucAwDhd49Ok-Ewas6Qnv2mBwDi7HMhUaBtNiGYEZxRQZLeZT3I8ACiRQlEUOI5vcTxQOW3aoocOZlAA1EW5Aqex3LQd-3ENGUAA8ZR0OJnEWQZiwUTed5mRJXEnnQNmLOkNllsBbl_hxjlZkRjbjLh8GPohhlDn6OKubh3J2mUNBpekPSvnphmegJEC4n65zYOgZr0ElQUpdyNUGRMkAfuZhHSVccmzIpymqWAbVzGgVplGgJ5Sd6cC6WAdX5aZqFBiGYZHCWt5vBWuKhdm-4FkWC3umUmmYOcUCDK6pyaSgA6dM6C7lpW1ZtNM0JFDAl4sukx01AOEVNmGUBNasAKDi0ZRwFAFyjuOwENA8sw9LMpxwJgbRDjtsGnERZTJnAeCyhpKCVFcEbpEUu7rQeNEYeel7kCxf49BRZoah6cAo_Wp7o3gDNM5T2O4z00zBng8x0Kt37RaevNQAOixi3gP2rCLtOgS5wF01Rnmkf-p63hzLMYwimtEdr0uqyLevM1zgLI_rZsy2rAEvIuMJhos-JQHA6R9fi1si8azavF85CO2UwAg4jIOZEZXpmtgIanOk6SAWg9tFMdMmWSDEAiRDNunnbDvoo5IskH1_RAQH-L9CQBRmigMAYsM5Ae0bcGnhSNQJ8iusXSQwXqznKBhnlTeF5UxddB55m0eeFFU3hDmSfWkVZ_LKvruPZPxjMlO7fth3dzTIbkEL67BpWLn76VbcqR5jmWcf5DADqNDgpnIu950s9hbW88kV7rzndAhWjFVjfIKt9Uq2QYO_MKH0opN1ftbG--974MCfmHH-Pt_7-0gY5aBWc4GqxwSLFu6BE6AJXmhCe9F4xSWhKeAEu8GiHyzHuHMux6xDEehAZaL0ToDkoUMCgVxWztHgDtUSkM5j-WKKUKslwdoaXSMGEeO0UB7QOvWMogwhxXBNpzTSuMibMIgPAk8_l5iLGNozfWrMsFz2IjAsiGtLGmz0XAYxVlbIWK1tY6264WSRjaIsOgPiszAW7OYpuOiDbBNWFvNRATw7mijp0GOcdKiYD4knEMcBgD2U9Ik6OsdTxpIycnOA2BUTdwApEs2OTwTcjzh_MsCJXKxMOlfTiDtRrRKMv43WESnGU1ZnVGg3TQnNKqu5bprT1HmOMvk5JhTilDFKcAPJ3okkpKKek5ZWTyniMqY4rWNS6B1P0jQRADSP7-R1OEhxkShmGRGUY1WGx5rljaKsygrREChJQYVNATS4AAEdKiaR1J0dIAAvBc2IhjYzDINJGS8BongOn1MR91sayhQNbFA4yIA4mmQfa2YSyjFWwLDBROIcRjMNH41oqVZRlnaTBVECJsQCTKLKJlJAWXfj-osIloJxGXKcn5MoABSa41FOKLnOAoq43YAB86UbEwSJX0hx69N4qO3vWHEAI-WOTxYrAlRKjWcVJeSylKAcTdiZSgC1rLxHssKpy7l1wnX8o6M5ZRqjDrCseKK6-7LJXSvwV_cYAIZVHjJqeeifYmLTzYow1Yrp4DYE6EBOGBypZessrxfigkKzCQxWq78UkKytXER1FoXV1KaXSNpcRY0JrGQEjVNx_lbL2W6f5fSpru75pMQsW56t7kY3LYRSNWdqkuOtgQpufDqFwFoR0DtqEqSDGGAieakZbyxleImFMXU3yNW-B0AOe6oxLRZDicCkEII9D4GYPghhlg9HxB8L40AeTxHBEAA|diesem WebtigerPython-Link]] - die Datei ist hier bereits hinterlegt.
  
-++++ Mit TigerPython :|+++++ Mit TigerPython / VisualStudioCode :|
 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. 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.
  
Zeile 128: Zeile 139:
 from null79 import names, numbers from null79 import names, numbers
  
-index = 42+index = 42  # TODO: Suche den Index von Lyanna!
 name = names[index] name = names[index]
-telnr = numbers[index] +tel = numbers[index] 
-print("Die Telefonnummer von " + name + " ist " + telnr)+print(f'Die Telefonnummer von {name} ist {tel}')
 </code> </code>
 ++++ ++++
 == Aufgabe == == Aufgabe ==
  
-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>+<html><bottom-editor timeout="180" zip="https://sca.ksr.ch/lib/exe/fetch.php?media=gf_informatik:programmieren_i:null79.py.zip" session="10m">
 from null79 import names, numbers from null79 import names, numbers
  
Zeile 150: Zeile 160:
  
 name = 'Lyanna' name = 'Lyanna'
-idx = linear_search(names, name) +index = linear_search(names, name) 
-if idx == None:+if index == None:
     print("Du weisch immer no nüt het si gseit")     print("Du weisch immer no nüt het si gseit")
 else: else:
-    tel = numbers[idx] +    tel = numbers[index] 
-    print("Die Telefonnummer von " + name + " ist " + tel)+    print(f'Die Telefonnummer von {name} ist {tel}')
     print("144 hei si gseit!")     print("144 hei si gseit!")
     print("Wie isch das nume passiert, hei si gseit.")     print("Wie isch das nume passiert, hei si gseit.")
     print("Hueresiech, hei si gseit, ey")     print("Hueresiech, hei si gseit, ey")
-</code>+</bottom-editor></html>
  
 ++++ ++++
Zeile 167: Zeile 177:
 Wir möchten genau wissen, wie lange die Suche dauert, auch wenn es hoffentlich nicht 6.5 Jahre sind. Wir möchten genau wissen, wie lange die Suche dauert, auch wenn es hoffentlich nicht 6.5 Jahre sind.
  
-Um in Python die Zeit zu stoppen, kannst du das `time` Modul verwenden. Wie lange dauert die Suche für die `Lyanna`? Wie lange für `Annina`? Weshalb der Unterschied?+Um in Python die Zeit zu stoppen, kannst du das `time` Modul verwenden. Wie lange dauert die Suche für die `Lyanna`? Wie lange für `Annina` oder `Zoraya`? Weshalb der Unterschied?
  
-<code python>+<html><bottom-editor timeout="180" zip="https://sca.ksr.ch/lib/exe/fetch.php?media=gf_informatik:programmieren_i:null79.py.zip" session="10m">
 import time import time
 +# Startzeitpunkt bestimmen
 start = time.time() start = time.time()
-# do something+ 
 +# TODO: Hier muss die Suche passieren 
 + 
 +# Endzeitpunkt bestimmen und Differenz zum Start berechnen
 elapsed = time.time() - start elapsed = time.time() - start
-print("do something took " + str(elapsed) + "s") +# Ausgabe - das ':1f' bewirkt die Darstellung mit einer Nachkommastelle 
-</code>+print(f'Vergangene Zeit: {elapsed:1f}s') 
 +</bottom-editor></html>
  
-<nodisp 2>+<nodisp 1>
 ++++Lösung| ++++Lösung|
-<code python time_algos.py>+<html><bottom-editor timeout="180" zip="https://sca.ksr.ch/lib/exe/fetch.php?media=gf_informatik:programmieren_i:null79.py.zip" session="10m">
 from null79 import names, numbers from null79 import names, numbers
 import time import time
 + 
 def linear_search(l, v): def linear_search(l, v):
     for i in range(len(l)):     for i in range(len(l)):
Zeile 188: Zeile 203:
             return i             return i
     return None     return None
 + 
 def stopwatch(name): def stopwatch(name):
     start = time.time()     start = time.time()
     index = linear_search(names, name)     index = linear_search(names, name)
     elapsed = time.time() - start     elapsed = time.time() - start
-    print("Lineare Suche für {0} dauerte {1:.1f}s".format(name, elapsed)) +    print(f'Lineare Suche für {name} dauerte {elapsed:.1f}s') 
 +  
 +stopwatch('Annina')
 stopwatch('Lyanna') stopwatch('Lyanna')
-stopwatch('Annina') +stopwatch('Zoraya') 
-</code>+</bottom-editor></html>
 ++++ ++++
 </nodisp> </nodisp>
Zeile 208: Zeile 224:
 ++++ ++++
  
-<nodisp 2>+<nodisp 1>
 ++++Code| ++++Code|
-<code python>+<html><bottom-editor zip="https://sca.ksr.ch/lib/exe/fetch.php?media=gf_informatik:programmieren_i:null79.py.zip" session="10m">
 idx = linear_search(numbers, '0791234567') idx = linear_search(numbers, '0791234567')
 print(names[idx]) print(names[idx])
-</code>+</bottom-editor></html>
 ++++ ++++
 </nodisp> </nodisp>
Zeile 223: Zeile 239:
 Nun sind die Namen in `null79.names` *alphabetisch sortiert*. Sobald wir einen Namen antreffen, der alphabetisch nach dem gesuchten Wert liegt, können wir die Suche abbrechen. Strings können in Python mit den `>` und `<` Operatoren verglichen werden: Nun sind die Namen in `null79.names` *alphabetisch sortiert*. Sobald wir einen Namen antreffen, der alphabetisch nach dem gesuchten Wert liegt, können wir die Suche abbrechen. Strings können in Python mit den `>` und `<` Operatoren verglichen werden:
  
-<code python>+<html><bottom-editor>
 s1 = 'Alaska' s1 = 'Alaska'
 s2 = 'Alberta' s2 = 'Alberta'
Zeile 230: Zeile 246:
 else: else:
     print(s1 + ' liegt im Alphabet nach ' + s2)     print(s1 + ' liegt im Alphabet nach ' + s2)
-</code>+</bottom-editor></html>
  
 Erweitere deine Funktion `linear_search()` wie folgt: Erweitere deine Funktion `linear_search()` wie folgt:
Zeile 237: Zeile 253:
   * 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>
  • gf_informatik/suchen_und_sortieren.1761747108.txt.gz
  • Zuletzt geändert: 2025-10-29 14:11
  • von gra