Oplossingen · hoofdstuk 34Algoritmen en complexiteit
Een correct programma wordt pas bruikbaar als zijn werk binnen het budget past
Uitgewerkte oplossingen bij de 9 opdrachten van het werkboek. Voor de leerkracht, en voor wie zichzelf wil verbeteren nadat hij het eerst zelf probeerde.
De snelste route op een kaart is alleen bruikbaar als elke verbinding werkelijk berijdbaar is.
Voor de leerkrachtDeze pagina bevat de antwoorden. Druk het werkboek af zonder deze pagina.
Oefenen
Oefenen
één stap, direct toepassen
34.1
Halveren zonder randfout
Oefenen6Analyseren25 min
De geordende array is [2, 4, 7, 9, 13, 18, 25, 31]. Gebruik [l,r).
a
Volg binair zoeken naar 13 en naar 8. Geef l, r en m na elke stap.
13: (0,8,m=4) vindt direct 13. Voor 8: (0,8,m=4:13) → [0,4); m=2:7 → [3,4); m=3:9 → [3,3), leeg. Index 4 voor 13; None voor 8. Geen toegang tot index 8 is nodig.
b
Formuleer de invariant en verklaar waarom m+1 nodig is in de rechterhelft.
Als de sleutel aanwezig is, ligt een mogelijke positie in [l,r). De middelste waarde is al uitgesloten wanneer de sleutel groter is; m+1 verwijdert haar. Alleen l=m kan bij een interval van één element dezelfde m blijven geven en dus niet eindigen.
34.2
Groeiklasse kiezen
Oefenen6Begrijpen25 min
Een programma doet 8n+20 stappen; een ander n2+3n.
a
Geef de scherpste O-klasse en leg uit waarom één tijdmeting de klasse niet bewijst.
De hoogste groeiende termen geven O(n) en O(n2). De constanten verdwijnen alleen in de asymptotische grens. Eén invoergrootte kan niet tonen hoe de tijd bij grotere n schaalt; ook caches en I/O kunnen de tijd vertekenen.
34.3
Verschuivingen tellen
Oefenen6Rekenen25 min
Invoegsorteren krijgt 1000 records in omgekeerde volgorde.
a
Bereken het aantal verschuivingen en de verhouding tot 2000 records.
1000⋅999/2=499500; voor 2000: 2000⋅1999/2=1999000. De verhouding is 4,002: bij verdubbeling ongeveer viermaal werk.
Toepassen
Toepassen
meerdere stappen, in een context
34.4
Een zoekfunctie schrijven
Toepassen7Programmeren25 min
Schrijf zelf binair zoeken; de uitvoer is de eerste index bij dubbele sleutels.
a
Geef code of precieze pseudocode en tests voor lege lijst, één element, afwezig en [2,2,2].
Bewaar een kandidaat bij gelijkheid en zoek links verder: lo=0, hi=len(a); while lo<hi: m=(lo+hi)//2; als a[m]<x: lo=m+1; anders hi=m. Na de lus: return lo als lo<len(a) en a[lo]==x, anders None. Tests: []→None; [2],2→0; [2],3→None; [2,2,2],2→0. Het halfopen interval wordt altijd kleiner.
34.5
Een recursie herstellen
Toepassen7Programmeren25 min
Faculteit wordt recursief gedefinieerd met alleen n == 1 als basisgeval.
a
Toon waarom n = 0 faalt; herstel het contract en beschrijf tijd en geheugen.
0 roept −1, −2 enzovoort aan tot de Python-recursiegrens een fout geeft. Valideer dat n een niet-negatief geheel getal is; gebruik if n==0: return 1, anders n*fac(n-1). Tijd O(n), stapel O(n). Een iteratieve productlus bewaart constant veel variabelen.
34.6
Een blokkade in de kaart
Toepassen7Analyseren25 min
Gebruik de volledige graaf uit het handboek. De kant C–D is geblokkeerd.
Kanten zijn berijdbare verbindingen; getallen zijn modelafstanden in meter, geen schaaltekening van de gang.
a
Bereken de nieuwe route Laad–E en rijtijd bij 0,20 m/s. Leg uit waarom een groot gewicht minder goed is dan verwijderen.
Afstanden: A2, B3, C5, D8 via B, E9 via C. Route Laad–A–B–C–E, 9 m, 45 s. Via D zou het 10 m zijn. Verwijderen maakt de blokkade absoluut; een eindige straf kan toch gekozen worden als andere routes duurder zijn.
Uitdagen
Uitdagen
transfer, open problemen, leerlijnen combineren
34.7
Een eerlijke tijdmeting
Uitdagen9Onderzoeken40 min
Je vergelijkt twee sorteerders op een laptop.
a
Ontwerp een meetprotocol dat invoervorm, n, herhalingen en geheugen omvat. Geef een analyse die toevallige ruis van groei onderscheidt.
Gebruik dezelfde kopieën van random, geordende en omgekeerde data; n bijvoorbeeld 1000, 2000, 4000, 8000. Doe opwarming en minstens meerdere herhalingen per geval, rapporteer mediaan en spreiding. Meet alleen het sorteren, maar rapporteer ook de totale pipeline afzonderlijk. Verdubbelingsverhoudingen rond 2 wijzen op lineair, rond 4 op kwadratisch; n log n ligt ertussen. Meet piekgeheugen en noteer interpreter en machine. Dit ondersteunt een model, het bewijst geen worst-case bovengrens.
Zo wordt dit beoordeeld
reproduceerbaarheid
Vaste invoer, omgeving, ruwe tijden en script.
interpretatie
Groei en spreiding afzonderlijk besproken.
34.8
Een routeplanner met terugweg
Uitdagen9Habitat60 min
De voorbeeldgraaf heeft meetpunten A, C en E. De robot moet terug naar Laad. Elke meting kost 5 s; een beurt mag 120 s duren.
Kanten zijn berijdbare verbindingen; getallen zijn modelafstanden in meter, geen schaaltekening van de gang.
a
Bereken een korte ronde en totaalduur; ontwerp het contract tussen Pi-planner en robot en de reactie op obstakels of netwerkuitval.
Dijkstra-afstanden geven ronde Laad–A–C–E–Laad van 2+3+3+8=16 m (A–C via B, C–E via D), dus 80 s rijden +15 s meten=95 s. Het budget heeft 25 s marge. Contract: kaartversie, route-ID, knopen, limiet, opdrachtverval en ontvangstbevestiging. De Uno stopt lokaal bij obstakel, meldt welke kant blokkeert en vraagt herplanning; bij verloren verbinding eindigt hij veilig zijn actuele beweging of stopt volgens de vooraf geteste modus, nooit blind een nieuwe route. De 16 m is een modelronde, niet de fysieke i33-lus.
Zo wordt dit beoordeeld
berekening
Afstand, meettijd en reserve gescheiden.
correctheid
Alle meetpunten en terugweg gecontroleerd.
veilig gedrag
Actuele blokkades en communicatieverlies begrensd.
34.9
Een negatieve energiekant
Uitdagen9Ontwerpen25 min
Bij afdalen zou een robot energie terugwinnen. Iemand voert negatieve kantgewichten in Dijkstra in.
a
Verklaar het probleem en geef twee bruikbare alternatieven, inclusief een beperking.
Dijkstra kan een afstand definitief verklaren vóór een later negatief segment die verkleint. Gebruik Bellman–Ford met detectie van negatieve cycli, of optimaliseer reistijd met niet-negatieve gewichten en evalueer de energie afzonderlijk. Een fysisch energiemodel moet SoC, verliezen en regeneratiebegrenzing bevatten: een negatieve cyclus betekent geen onbeperkte echte energiewinst. Alleen alle gewichten met dezelfde constante verhogen verandert het aantal gebruikte kanten en behoudt dus niet algemeen het optimale pad.
