Tiltų planavimas
Taškai: 9
Senelis bebras bijo vandens. Jis nori lankyti giminaičius iš savo gyvenvietės eidamas tiltais. Bebriukas labai myli senelį ir nori tiltais sujungti visas gyvenvietes. Tiltus jis tiesia laikydamasis šių dviejų taisyklių:
• senelis bebras iš savo gyvenvietės bet kurią kitą gyvenvietę pasiekia ne daugiau kaip dviem tiltais;
• bet kurioje gyvenvietėje turi prasidėti ne daugiau kaip du nauji tiltai.
Bebriukas pradeda planuoti. Gyvenvietes pažymi skrituliais. Senelio gyvenvietę pažymi raudonai, iš jos nutiesia pirmąjį tiltą. O kas toliau? Padėkite bebriukui.
Yra daug teisingų sprendimų. Bet kuriuo atveju reikės nutiesti dar penkis tiltus. Spustelėkite gyvenvietę ir tempkite tiltą link kitos gyvenvietės – tarp jų atsiras tiltas. Jei norite pašalinti tiltą, spustelėkite jį.
Informatikoje daugelio algoritmų, realizuojančių medžio veiksmus, sudėtingumas priklauso nuo to medžio aukščio, todėl siekiame, kad didėjant medžio viršūnių skaičiui jo aukštis didėtų kiek galima lėčiau. Vadinasi, reikia derinti medžio kairįjį ir dešinįjį pomedžius.
Dvejetainis medis, kurio kiekvieno elemento kairiojo ir dešiniojo pomedžių elementų skaičiai skiriasi ne daugiau kaip vienetu, vadinamas visiškai subalansuotu medžiu.
https://lt.wikipedia.org/wiki/Medis_(duomen%C5%B3_strukt%C5%ABra)
Reikšminiai žodžiai: medis, dvejetainis subalansuotas medis, pomedis.
Galimi du sprendimo būdai.
Šis sprendimas atitinka dvi sąlygas: iš raudonai pažymėtos gyvenvietės kitą gyvenvietę galima pasiekti ne daugiau kaip dviem tiltais ir bet kurioje gyvenvietėje yra du nauji tiltai.
Tokias sąlygas atitinka ir šis planas: