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

8,9