Kirjautuminen

Haku

Tehtävät

Putkaposti: Hyppykeppi

Kirjoittaja: Antti Laaksonen

Tohtori Sykerön hyppykeppi on epäkunnossa: se vie Sykeröä satunnaisesti joko askeleen eteenpäin tai askeleen taaksepäin. Sykerö lähtee liikkeelle vesilammikon luota ja yrittää päästä aikakoneeseen, joka on tietyn askelmäärän päässä. Kuinka todennäköisesti Sykerö pääsee lopulta aikakoneeseen eikä molskahda lammikkoon?

Tehtävä

Hyppykeppi vie Sykeröä askeleen eteenpäin todennäköisyydellä p ja askeleen taaksepäin todennäköisyydellä 1 - p. Aikakoneeseen on matkaa n askelta. Heti askel Sykerön aloituskohdasta taaksepäin on vesilammikko, johon hyppääminen keskeyttää Sykerön matkanteon.

Tarkastellaan tilannetta, jossa Sykerö hyppää eteenpäin todennäköisyydellä 4/5 ja aikakoneeseen on matkaa 3 askelta (eli p on 4/5 ja n on 3). Nyt mahdollisia hyppysarjoja ovat esimerkiksi seuraavat:

  1. eteen, eteen, taakse, eteen, eteen
  2. eteen, taakse, taakse
  3. eteen, eteen, taakse, taakse, eteen, taakse, eteen, eteen, eteen
  4. eteen, eteen, taakse, eteen, taakse, taakse, taakse

Hyppysarjat 1 ja 3 johtavat aikakoneeseen, kun taas hyppysarjat 2 ja 4 johtavat vesilammikkoon. Erilaisia hyppysarjoja on ääretön määrä, koska Sykerö voi pomppia edestakaisin samoissa kohdissa. Tässä tapauksessa todennäköisyys, että Sykerö pääsee aikakoneeseen, on 64/85 ≈ 0,75294.

Tiedostossa hkeppi.txt on joka rivillä yksi p:n ja n:n arvo. Tehtävänä on laskea kussakin tapauksessa todennäköisyys, että Sykerö pääsee aikakoneeseen.

Vastausohje

Vastauksen jokaiselle riville tulee yksi todennäköisyys loppuun asti sievennetyssä murtolukumuodossa. Todennäköisyydet voi ilmoittaa missä tahansa järjestyksessä, ja jokainen todennäköisyys on yli 0 ja alle 1.

Vastaus voisi näyttää seuraavalta:

64/85

Tämä on esimerkin oikea vastaus, mutta tätä tapausta ei ole tiedostossa hkeppi.txt.

Vastaukset

31 henkilöllä on tulos. Suluissa oleva luku tarkoittaa ratkaistujen testitapausten määrää.

Sisuaski (20), os (20), jlaire (20), Jaska (20), Metabolix (20), SirDayBat (20), Konvehti (20), Laitinen (20), Jepso (20), msdos464 (20), lukujenVihaaja (20), Anaatti (20), L2-K2 (20), Torgo (20), Legu (20), Jhuunhym (20), TapaniS (20), symbols (20), membolic (20), isashkar (20), Chiman (15), johku90 (10), osku91 (6), regnessem (6), öppis (4), Grez (3), Laakeri (3), Juice (1), FooBat (1), tkok (1), heisti (1)

Kirjaudu sisään Ohjelmointiputkaan, niin voit lähettää vastauksen tehtävään.

Keskustelu

Katso myös Putkaposti 33: Hyppykeppi.

Tietoa sivustosta