Navigasjonsproblem
Problem
Hvor mange forskjellige veier er det fra S til T, som ikke går gjennom U og V mer enn én gang?
- Kan du lage en algoritme som stiller to spørsmål: hvor mange ganger det må foretas et veivalg, og hvor mange veier som kan velges fra et punkt til et annet?
- Kan du lage algoritmen slik at den regner ut antall forskjellige veier fra start til slutt, ut fra svarene på de to spørsmålene?
- Kan du programmere algoritmen?
Løsning
Her går det an å tenke på mange måter, her er en måte:
Det er 3 veier fra S til U og 2 fra U til V. Antall veier fra S til V er derfor \(3\cdot2=6\). Hver av dem kan etterfølges av 3 forskjellige veier fra V til T, som gjør at det blir \(6\cdot3=18\) veier totalt.
Ressursen er utviklet av NRICH