Tietorakenteet ja algoritmit syksy 2020
Polut verkossa
Tarkastellaan verkkoa, jossa solmut on numeroitu 1, 2, 3, jne. ja solmusta
i
on suunnatut kaaret solmuihin
i
+1 ja
i
+2 (eli esimerkiksi solmusta 3 pääsee kaarella solmuihin 4 ja 5).
Solmusta 1 solmuun 5 on yhteensä 5 erilaista polkua:
1 → 2 → 3 → 4 → 5
1 → 2 → 3 → 5
1 → 2 → 4 → 5
1 → 3 → 4 → 5
1 → 3 → 5
Laske dynaamisella ohjelmoinnilla, montako erilaista polkua on solmusta 1 solmuun 50.
Vastaus
Polkujen määrä on
.
Algoritmin toteutus
Kirjoita tähän toteuttamasi algoritmin koodi:
The deadline for this task has passed
Return to task list