Navigasjonsproblem
Problem
Kor mange forskjellige vegar frå S til T er det som ikkje går gjennom U og V meir enn éin gong?
- Kan du lage ein algoritme som stiller to spørsmål: Kor mange gonger må ein gjere eit vegval? Kor mange vegar kan ein velje frå eitt punkt til eit anna?
- Kan du lage algoritmen slik at han reknar ut antal forskjellige vegar frå start til slutt, ut frå svara på dei to spørsmåla?
- Kan du programmere algoritmen?
Løysing
Her går det an å tenkje på fleire måtar. Ein av dei er slik:
Det er 3 vegar frå S til U og 2 vegar frå U til V. Antalet vegar frå S til V er difor \(3\cdot2=6\). Kvar av dei kan etterfølgjast av 3 forskjellige vegar frå V til T, som gjer at det blir \(6\cdot3=18\) vegar totalt.
Ressursen er utviklet av NRICH