Mikroschema

Taškai: 12

Mikroschema sudaryta iš tinkleliu išdėstytų lizdų (žymimų taškais). Kai kurie iš jų jau sujungti jungtimis (žymimomis geltonomis linijomis). Jungiami tik horizontaliai arba vertikaliai gretimi lizdai.

Reikia sujungti S ir R lizdus ištisine jungčių seka neliečiant jau esamų jungčių.

Keliais skirtingais būdais galima sujungti S ir R naudojant mažiausiai jungčių?

Paaiškinimas

Mikroschemos sukėlė revoliuciją elektronikos pasaulyje ir šiuo metu yra gausiai naudojamos. Mikroschema gali būti labai maža (dažnai vadinama lustu). Pavyzdžiui, keletas bilijonų tranzistorių ir kitų komponenčių gali sutilpti ant nago dydžio ploto.

Mikroschemose ryšių linijos turi būti išdėstomos labai tankiai, tiesiog raizgalynė, todėl mikroschemų projektavimas nėra lengva užduotis. Informatikai sukūrė daug išmaniųjų algoritmų tokiam projektavimui. Ieškant dviejų komponentų optimalaus išdėstymo, kelių tarp jų skaičius gali būti itin svarbus, kadangi norint vėliau pridėti trečią komponentą, reikia įvertinti tai, jog jis gali užtverti dalį esamų kelių.

Trumpiausio kelio suradimas yra dažna užduotis informatikoje.  Aprašytas procesas – taip paieška į plotį.  Čia ji pritaikyta tam, kad surastumėme trumpiausią kelią. Mes neturėjome patikrinti visų įmanomų kelių, kadangi nuo pat pradžios ėjome sistemiškai. Toks metodas vadinamas dinaminiu programavimu.

Atsakymas

Teisingas atsakymas – 15.

Nėra sunku rasti trumpiausią kelią – jungčių seką. Galima įsivaizduoti bangą, kuri prasideda taške S ir plinta iki taško R. Kai banga pasiekia kontaktą, akivaizdu, jog ji pasirinks trumpiausią kelią (jungčių seką).

Lentelėje parodytas bangos sklidimas, pasiekus maždaug pusiaukelę. Skaičiai rodo eiliškumą, kuriuo banga pasiekia kontaktus, o juodi langeliai – pradžioje esamas jungtis, kurias turime aplenkti. Skaičiai taip pat nusako ir trumpiausią atstumą iki tam tikro kontakto. Didžiausia reikšmė – bangos krašte.

Jeigu bandysime rasti visus trumpiausius kelius – lengvai pasiklysime. Tačiau to ir nereikia, kadangi užduoties tikslas yra nustatyti tokių kelių skaičių. Taigi, kaip šį uždavinį suskaidyti į mažesnes dalis?
Svarbu suprasti, jog trumpiausias kelias iki bet kurio kontakto turi eiti per viena iš gretimų kontaktų, kuris yra arčiau pradžios. Jeigu tokių kontaktų yra daugiau negu vienas – jie visi gali būti panaudoti. Norint rasti galimybių skaičių, reikia žingsnis po žingsnio sumuoti galimybes judant link iki artimiausio kontakto. Taigi trumpiausių kelių skaičius yra visų artimiausių gretimų kontaktų, kurie yra žingsniu arčiau starto, suma.
Tai leidžia sukurti procesą, vykdant kurį užtikrintai gausime trumpiausių kelių skaičių. Pradėti galima nuo bangos aprašymo lentelės sudarymo. Pradėkime nuo S – artimiausias kontaktas gali būti pasiektas tik viena kryptimi. Toliau pridėkime kontaktus, kurie yra bangos krašte ir sudėkime kaimynų numerius iš ankstesnio žingsnio.
Pateikiame galutinę lentelę. Mes parodėme šios lentelės užpildymo eigą – dešinėje pavaizduota anksčiau minėta trumpiausių kelių lentelė, kuri yra visa užpildyta.

Kaip matome, gavome teisingą atsakymą –15.

Interaktyvi užduotis

 

 
Informacija atnaujinta 2015-12-03 07:50:57