Session activities¶
Harjoitukset kurssiaiheeseen 9¶
Tehtävä 1 - Polut¶
Tehtävänä on koota joukko, joka sisältää kaikki harjoituksessa 1 annetut polut. Sinulla on pääsy juurisolmuun, ja sinun tulee käyttää kaikkia solmuja lehtiin asti, aloittaen juurisolmusta. Kootut polut tulee kuitenkin alkaa jokaisesta solmusta ja ulottua juurisolmuun asti, kuten harjoituksessa 1.
Kirjoita pseudokoodi tai C++-koodi, joka kokoaa polut jokaisesta solmusta juureen. (Huom: koska kokoat joukon, polkujen järjestys joukossa ei ole tärkeä.)
Pseudokoodi¶
Voidaan olettaa, että jokaisella puun solmulla on datatyyppi Node, jolla on seuraavat attribuutit:
- Node.key = solmun avain
- Node.parent = pointteri Node:n vanhempaan tai NIL, jos juuri
- Node.children = Node:n kaikki lapset
Voidaan tehdä seuraavat oletukset:
- Node.children on joku säiliö, joka sisältää kaikki Node:n lapset.
- Node.children.length() Noden:n lapsien lukumäärä.
- Root on Node, joka sisältää puun juurisolmun.
C++¶
Vastaavasti kuin pseudokoodissa, voit käyttää seuraavaa C++ structia ja vakioita tehtävässäsi, joka kokoaa polut annetussa tehtävässä 1.
Kaikki solmut käyttävät seuraavan näköistä structia:
struct Node {
int key=NO_KEY;
Node* parent = NO_NODE;
std::unordered_set<Node*> children = {};
}
Jossa vakiot ovat seuraavat:
int NO_KEY = -1;
Node* NO_NODE = nullptr;
Voit käyttää C++-pohjakoodia, joka on saatavilla: zip-pakkauksena.
Koodi sisältää jo Node-rakenteen ja yllä esitetyt vakiot.
Se myös luo yllä esitetyn esimerkkipuun.
Sinun tarvitsee kirjoittaa vain funktio, joka kokoaa polut.
Tehtävä 2a - Mediaani¶
Anna seuraavat tiedot jokaisen alkion lisäyksen jälkeen syötesekvenssistä: 5, 6, 7, 4, 2, 1, 11, 12, 13, 14, 15:
- Lisätyn alkion arvo.
- Onko lisätty arvo pienempi vai suurempi kuin vanha mediaaniarvo.
- Uusi mediaaniarvo lisäyksen jälkeen.
Tehtävä 2b - Mediaani - implementaatio¶
Kirjoita pseudokoodi tai C++-koodi, joka ylläpitää tietoa syötesekvenssin mediaanista käyttämällä kahta kekoa. Ratkaisun tulisi toimia tehokkaasti tilanteessa, jossa mediaania pyydetään usein, ja uutta tietoa lisätään mediaanipyyntöjen välissä.
Voit käyttää C++-pohjakoodia, joka on saatavilla: zip .
Seuraavat funktiot saattavat olla hyödyllisiä:
A+ esittää tässä kohdassa tehtävän palautuslomakkeen.