(H) Verkostomarkkinointia¶

Tavoite: Harjoittelen sopivan STL-säiliön valitsemista ja rekursiivisen algoritmin toteuttamista.

Ohjeita: Hae ohjelmakoodipohja: templates/06/network/ -> student/06/network/.

Veikko Verkostomarkkinoijalla on ongelma (verkostomarkkinoinnin lisäksi). Verkostomarkkinointiverkoston idea on, että jokainen markkinoija on värvännyt mukaan markkinointiin uusia henkilöitä. Missään ei kuitenkaan ole tallella tietoa koko markkinointiverkoston rakenteesta. Tiedossa on vain kuka markkinoijista on värvännyt ketäkin muita markkinointiin mukaan. Auta Veikkoa selvittämään verkoston rakenne kirjoittamalla ohjelma, joka tulostaa verkoston rakenteen puumaisena kuviona ja osaa myös laskea aliverkostojen syvyyksiä ja kokoja.

Ohjelmakoodipohjassa on valmiina toteutettu pääohjelma, joka lukee ja jäsentelee käyttäjän syötteet. Jos muutat komentotulkin ohjelmakoodia, pidä huolta, että se toimii samalla tavoin kuin alkuperäinen komentotulkki.

Tehtävänä on valita sopiva tietorakenne tietojen tallentamiseen ja toteuttaa komentojen toiminta seuraavasti:

• S (eli store, tallenna) saa parametrinaan kahden henkilön tunnisteet (esim. nimet tai id-numerot tms), jotka ovat merkkijonoja. Ensimmäisenä on sen henkilön tunniste, joka on värvännyt mukaan markkinointiin henkilön, jolla on toisena oleva tunniste. Eli toisin sanottuna ensimmäiseksi mainittu henkilö on verkostossa ylempänä kuin toiseksi mainittu henkilö. Kukin henkilö voi olla värvännyt mukaan kuinka monta henkilöä tahansa. Tässä tehtävässä voit olettaa, että henkilöiden tunnisteet eivät muodosta silmukoita, eli alempana oleva tunniste ei koskaan ole mitään kautta värvääjäänsä ylempänä.
• P (eli print, tulosta) saa parametrinaan yhden tunnisteen. Ohjelma tulostaa sen henkilön aliverkoston, jonka tunniste on kyseessä. Ensimmäiseksi tulostetaan kysytyn henkilön tunniste. Hänen alapuolelleen 2 pistemerkillä sisennettynä tulostetaan niiden henkilöiden tunnisteet, jotka hän on värvännyt mukaan markkinointiin ja heidän alapuolelleen samalla tavoin enemmän sisennettynä heidän värväämänsä henkilöt. Henkilöt tulostetaan siinä järjestyksessä, missä heidät on kirjattu värvätyiksi. Jos henkilölle ei ole kirjattu värvättyjä tai henkilöä ei ole kirjattu ollenkaan, tulostetaan vain hänen tunnisteensa.
• C (eli count, lukumäärä) saa parametrinaan yhden tunnisteen. Ohjelma tulostaa kyseisen henkilön aliverkoston suuruuden, eli toisin sanoen hänen värväämiensä henkilöiden muodostaman aliverkon jäsenten määrän.
• D (eli depth, syvyys) saa parametrinaan yhden tunnisteen. Ohjelma tulostaa annetun henkilön aliverkon syvyyden, eli toisin sanoen pisimmän värväysketjun pituuden hänestä lähtien.

Esimerkki henkilöiden lisäämisen ja verkon tulostamisen toiminnasta:

> S Hugo Laura
> S Hugo Jasper
> S Laura Helena
> S Jasper Maria
> S Laura Elias
> S Helena Sofia
> P Hugo
Hugo
..Laura
....Helena
......Sofia
....Elias
..Jasper
....Maria
> P Laura
Laura
..Helena
....Sofia
..Elias
> Q

Alla on esimerkki aliverkoston suuruuden laskemisesta:

> S Hugo Laura
> S Hugo Jasper
> S Laura Helena
> S Jasper Maria
> S Laura Elias
> S Helena Sofia
> C Hugo
6
> C Laura
3
> C Helena
1
> C Sofia
0
> C Jasper
1
> Q

Alla on esimerkki aliverkon syvyyden laskemisesta:

> S Hugo Laura
> S Hugo Jasper
> S Laura Helena
> S Jasper Maria
> S Laura Elias
> S Helena Sofia
> D Hugo
4
> D Laura
3
> D Helena
2
> D Sofia
1
> D Jasper
2
> Q

Vinkkejä tehtävän tekemiseen:

• Tietorakenteen ei tarvitse olla rekursiivinen, vaikka sen sisältö olisikin tulkittavissa rekursiivisesti. Tämän tehtävän saa yksinkertaisimmin ratkaistua käyttämällä tietorakennetta, joka on hyvin samantyylinen kuin edellisen kierroksen tehtävissä käytetyt tietorakenteet.
• Tietorakennetta käsittelevät algoritmit (komentojen P, C ja D toteutukset) taas saa helpoiten tehtyä rekursiivisesti. Malliratkaisussa jokainen komennoista on toteutettu alle kymmenellä ohjelmakoodirivillä. Jos ratkaisusi on kasvamassa huomattavasti tätä pidemmäksi, kannattaa todennäköisesti miettiä muitakin vaihtoehtoisia ratkaisuja.