Hemtal 3
A) Träd
Läs kapitlet
Trees i
kursboken
- Rita upp det binära sökträd vi får om vi i tur och ordning stoppar in följande tal:
24 17 20 35 28 40
- Visa vilka noder som tillhör höger delträd.
- Hur ser en postorderutskrift av trädet ut?
- Hur många jämförelser måste man som mest göra vid sökning i trädet?
- Hur många jämförelser måste man som mest göra i ett balanserat binärträd med n noder?
B) Problemträd
Läs om
breddenförstsökning (Breadth First Search) och
djupetförstsökning (Depth First Search) i kursboken.
Titta sedan på bilspelet:
rush hour
(det är samma spel i flera implementationer - välj vilken du vill).
- Rita av startpositionen för bilarna och numrera dom.
- Hur många olika sätt finns det att flytta någon bil i startläget? Skriv upp alla möjligheter (t ex "Flytta bil 1 en ruta uppåt")
- När du själv spelar bilspelet - är det breddenförstsökning eller djupetförstsökning du använder? Motivera ditt svar!
- Skriv en algoritm för ett program som löser bilspelet!
Hemtalet tas med till övning 3 och rättas där!
Den som gjort uppgiften ska skriva sitt namn
och personnummer överst till höger på alla blad.
Den som rättar ska skriva sitt namn och personnummer
längst ner till vänster på första bladet.
