Sklad

Sklad

Avtor: Matija Lokar

Več o projektu...

Pravilnost oklepajev – enostavni primer

  • V izrazu bi radi preverili, če so oklepaji / (, ) / postavljeni pravilno

    • (a + b)(c + (d – a))
    • (a + b))w)(c + (d – a))
    • (a + b)(w c + d – a))

  • Ideja

    • +1 ko naletimo na predklepaj
    • - 1 ko naletimo na zaklepaj

  • Kdaj bo ok?

    • Na koncu 0
    • Ves čas + ali 0

Pravilnost oklepajev – več različnih

  • Kaj pa, če je več parov različnih oklepajev:

    • (, ), [, ], <,>, {,}
  • Dva števca?

  • Pozor na pravilno gnezdenje!

    • (a + b)[c + (d – a])
    • ([a + b])[c + [d – (a + d)]]
  • Pomembni so le oklepaji, ostali znaki nas ne zanimajo

Pravilnost oklepajev – ideja

  • Dokler oklepaj ne dobi zaklepaja, ga moramo hraniti

  • Vedno mora zaklepaj dobiti “najbolj sveži” predklepaj

    • Last In First Out
  • Predklepaje hranimo v skladu

  • Ko naletimo na zaklepaj, mora biti na vrhu sklada ustrezen predklepaj

    • Če ga ni, ... napaka!
  • Na koncu mora biti sklad prazen

Pravilnost oklepajev - algoritem

  • Pripravi sklad

  • Za vse znake v izrazu

    • Če je znak predklepaj, ga vstavi v sklad

    • Če je znak zaklepaj

      • Če je sklad prazen:

        • NAPAKA
      • Poglej vrh sklada.

      • Če je na vrhu napačen predklepaj:

        • NAPAKA
      • Odstrani vrhnji elt iz sklada (je že dobil svoj zaklepaj)

  • Če je sklad prazen

    • Oklepaji so postavljeni pravilno

Algoritem

algoritem soPravilno(izraz){
  # ali so v nizu izraz oklepaji postavljeni pravilno
  hrani = Sklad.Sklad()
  for znak in izraz # pregledamo vse znake
    if znak je predklepaj :
       hrani.vstavi(znak) # predklepaj bo počakal na svoj zaklepaj
    else :
       if znak je zaklepaj :
         if hrani.prazen() :
            return False # nihče ne čaka na ubogi zaklepaj
          if hrani.vrh() ne ustreza zaklepaju, ki je v znak :
            return False # napačno gnezdenje!
         # zaklepaj je dobil ustrezni par na skladu
         hrani.odstrani()
       # ostali znaki nas ne zanimajo
  # ce ni cakajocih zaklepajev je OK, drugace pa ne
  return hrani.prazen()

Spremljanje

  • Oglejmo si, kaj se dogaja s skladom, če podamo izraz

    • (-2)+[[6+8]*(3 – [5*2])]
    • ([(()]))
    • (([][][])
    • (a + b)[c + (d – a])
    • ([a + b])[c + [d – (a + d)]]
    • ...

Matrično množenje

  • Naj bo matrika A dimenzije k j

  • Zmnožimo jo lahko z matriko B dimenzije

    • j n

  • Za to potrebujemo

    • k * j * n množenj števil

  • Matriko velikosti a b lahko zmnožimo samo z matriko velikosti b c

    • "Za to potrebujemo a * b * c množenj

  • Pr imer:

    • A :
    • B :
    • C :
    • D :

    • Kako izračunati A B C D (rezultat bo enak, a načini, kako priti do njega so (vsaj) trije!)

      • (A B) (C D)

        • (za AB) + (za CD) + (AB je , CD ker ( ) = op

      • A ((B C) D)

        • (BC) + (množimo dobljeni produkt BC z D) + (vse skupaj še z A) = op

      • (A (B C)) D

        • (BC) + (z A) + (še z D) = op

  • Za izračun optimalnega načina množenja

    • Kasneje
    • Dinamično programiranje

Matrično množenje

  • Dane so matrike in njihove dimenzije

    • A
    • B
    • C
    • D
    • E
    • F
    • G
    • H
    • I
  • Zanima nas, koliko operacij je potrebnih za izračun matričnega izraza s samimi množenji. Vrstni red je že podan z oklepaji (ki so pravilno postavljeni!)

  • Izrazi

    • A
    • (AB)
    • (AC)
    • (A(BC))
    • ((AB)C)
    • (((((DE)F)G)H)I)
    • (D(E(F(G(HI)))))
    • ((D(EF))((GH)I))

  • Pričakovani odgovori

    • Error (dimenzije niso oK)

  • Naloga:

    • Za dani izraz izračunaj število potrebnih množenj

Kako?

  • Oklepaji "diktirajo" množenje

    • Pravzaprav so (ker so oklepaji prav) pomembni le zaklepaji

    • Ko pride do zaklepaja, se mora nekaj zmnožiti

      • Kaj? Najbolj "sveži" matriki:

        • Sklad za hranjenje

Matrično množenje - ideja

  • Sklad za hranjenje
  • ( : nič
  • A, B, C, ...: vstavi dimenzije matrike v sklad

  • ) : vzamemo dve matriki iz sklada, “izvedemo množenje”

    • Če ne gre: error

    • Če gre:

      • prištejemo število operacij
      • Vstavimo dimenzije dobljene matrike
  • Ko smo na koncu: rezultat

Algoritem

Algoritem steviloMnozenj(izraz, podatki o vel. matrik)
  matrike = Sklad.Sklad()
  stMnozenj = 0;
  for znak in izraz :
    if znak je matrika # zapomnimo si dimenzije
      matrike.vstavi((st_vrstic matrike znak, st_stolpcev matrike znak))
    elif (znak == ')') # zaklepaj – izvedemo množenje
       (v2, s2) = matrike.vrh() # podatki 2. matrike
       matrike.odstrani()
       (v1, s1) = matrike.vrh() # podatki 1. matrike
       matrike.odstrani()
       if (s1 != v2) :
          return ERROR # napačne dimenzije
       stMnozenj = stMnozenj + v1 * s1 * s2
       # dobljeno matriko (njene dimenzije) damo v sklad
       matrike.vstavi((v1,s2))
  return stMnozenj;

Spremljanje

  • Oglejmo si, kaj se dogaja, če

    • A
    • B
    • C
    • D
    • E
    • F
    • G
    • H
    • I

  • Izrazi

    • A
    • (AB)
    • (AC)
    • (A(BC))
    • ((AB)C)
    • (((((DE)F)G)H)I)
    • (D(E(F(G(HI)))))
    • ((D(EF))((GH)I))

  • Pričakovani odgovori

    • error

Težave postajenačelnika

  • Janez je postajni načelnik na železniški postaji sredi hribovite postaje. Prostora je tam tako malo, da je na postaji prostora le za slepi tir, ter vhodni in izhodni tir. Na postaji se vedno spremeni vrstni red vagonov. Če so vagoni na postajo prišli kot ABC, jih želimo npr. odposlati kot kompozicijo BCA. Janez vnaprej dobi želeno izhodno kompozicijo. Zanima, če tako preureditev vagonov lahko naredi. Če ne bo šlo, bo takoj javil v centralo, da bodo vlak poslali po drugi poti. Pomagaj mu in sestavi program, ki sprejme prihajajočo razporeditev vagonov in želeno izhodno razporeditev in pove, če je ta možna.
  • Slika postaje – glej tablo

  • Predpostavke:

    • Na slepem tiru je dovolj prostora za vse vagone.
    • Vagoni se z izhodnega tira ne vračajo na slepi tir
    • Vagoni se s slepega tira ne vračajo na vhodni tir.

Primer vlaka

  • ABC ... Želimo dobiti BCA
  • Vagon A zapelje na slepi tir
  • Vagon B zapelje na slepi tir
  • Vagon B se iz slepega tira premakne na izhodnega
  • Vagon C zapelje na slepi tir
  • Vagon C se iz slepega tira premakne na izhodnega
  • Vagon A se iz slepega tira premakne na izhodnega

Primer vlaka

  • ABC ... Želimo dobiti CAB
  • Ne gre!
  • Sestavi algoritem, ki ugotovi, če je iz ene razporeditve mogoče dobiti drugo!

Preureditev vlaka

  • Ideja:

    • Vagoni na vhodnem tiru: sklad (prvi vagon je na vrhu)
    • Vagoni na slepem tiru: sklad
    • Željena kompozicija: sklad, kjer je oznaka prvega vagona nove kompozicije na vrhu

  • Simulacija dogajanj

    • Če je na slepem tiru enak vagon, kot ga potrebujemo na izhodnem tiru, ga s slepega tira pošljemo na izhodni tir in na spisku z želeno kompozicijo odstranimo ta vagon
    • Če na slepem tiru ni ustreznega vagona, z vhodnega tira pripeljemo nov vagon na vhodni tir.
    • rekurzija
0%
0%