Spegilstrengir

Spegilstrengir (e. palindrome)

Þetta verkefni gengur út á að skrifa fall sem ...

• tekur inn streng (e. string),

• athugar hvort hann sé spegilstrengur (e. palindrome),

• og skilar annað hvort True eða False

Í þessu verkefni koma fyrir eftirfarandi þættir:

• Strengir

• tvíundabreytur

• for-lykkjur

• heiltölur

• kommutölur

• tagskipti

• innbyggð föll

Hvað er spegilstrengur?

Þegar við segjum að strengur eða orð sé spegilstrengur þá þýðir það að við getum lesið hann aftur á bak eða áfram og hann hljómar alltaf eins. Dæmi um það gætu verið orðin amma og radar eða talan 1234321.

Hvernig á forritið að virka?

Á myndinni hér fyrir neðan sjáum við dæmi um strenginn radar. Eins og við sjáum á myndinni, þá fær hver stafur í strengnum einskonar sætistölu sem við köllum vísi (e. index). Þessir vísar munu reynast gagnlegir í lausninni á þessu verkefni.

Það getur verið gott að prófa fyrst að prenta gildin sem við viljum nota, áður en við gerum eitthvað flóknara við þau. Prófum að skrifa pínulítið fall sem prentar alla stafi í streng ásamt vísi hvers stafs. Til þess að gera það legg ég til að við notum for-lykkju . Ásamt henni væri hægt að nota innbyggt fall sem heitir range(). Fallið range() tekur inn heiltölu sem tilgreinir hversu oft for-lykkjan muni keyra. Við viljum prenta hvern staf í strengnum og því notum við lengd strengsins til þess að tilgreina hversu oft lykkjan á að keyra. Við getum notað fallið len() til þess að finna lengd strengs :

def palin_test(st_inn):
    lengd = len(st_inn)
    for s in range(lengd):
        print(s, ' ', st_inn[s])

>>> palin_test('radar')
0   r
1   a
2   d
3   a
4   r

Í dæminu hér að ofan færum við inntakið undir breytuna st_inn (eins og strengur sem við tökum inn) og við skulum fylgja honum gegnum forritið. Þegar for-lykkjan byrjar að keyra fær breytan s (s eins og stafur) heiltölugildi og við notum það til þess að prenta hvern staf út frá sæti stafsins.

Eins og við sjáum á myndinni hérna á undan, þá getum við notað vísinn [0] til þess að sækja fyrsta stakið og [4] til að sækja síðasta stakið. En við getum líka notað [-1] og fáum þá alltaf síðasta stakið úr safninu (þetta virkar fyrir fleiri tög en bara strengi og þess vegna nefni ég stak og safn) og þá skiptir engu máli hversu stórt það er. Vegna þess að síðasta stakið hefur vísinn -1, þá hefur næst-síðasta stakið vísinn -2 og svo framvegis.

Þá er spurning hvernig best sé að leysa verkefnið?

Við þurfum að finna leið til að bera saman fyrsta og síðasta stafinn, næst-fyrsta og næst-síðasta stafinn og svo koll af kolli eins og taflan hér fyrir neðan sýnir.

Fyrra stak	Seinna stak
0	-1
1	-2
2	-3

Fyrsta spurningin er hversu oft þarf for-lykkjan að keyra í þessu verkefni?

Í hverju skrefi munum við bera saman fyrsta og síðasta staf strengsins og þar af leiðandi þarf fjöldi skrefa ekki að vera meiri en sem nemur hálfri lengd strengsins. Það væri því óþarfi fyrir for-lykkjuna að fara í gegnum allan strenginn heldur nægir okkur að fara í gegnum hálfa lengd strenginn.

>>> strengur = 'amma'
>>> len(strengur)
4
>>> (len(strengur)/2)
2.0

Þar sem við ætlum að nota fallið range() þá þurfum við að hafa í huga að það tekur einungis við heiltölu. Hefðbundin deiling í Python skilar alltaf kommutölu (e. float). Því höfum við tvo möguleika; annars vegar að skipta um tag (e. type conversion) með int() og hins vegar að nota heiltöludeilingu. Heiltöludeiling er framkvæmd með // virkjanum og kosturinn við hana (í þessu tilfelli) er að þá þurfum við ekki að huga sérstaklega að tagskiptum ásamt því að kóðinn verður aðeins læsilegri.

>>> int(len(strengur)/2)
2
>>> len(strengur)//2
2

Þá getum við notað þessa heiltölu (len(strengur)//2) sem inntak fyrir range(). Við getum einnig tekið eitt auka skref og skilgreint þessa tölu (hálfu lengdina) sem breytu. Við gætum til dæmis kallað hana lengd:

lengd = len(strengur)//2

Setningin gæti þá litið svona út:

for s in range(lengd):

Spurningin núna er þá, hvernig getum við látið -1 færast "niður" á móti s ?

Það eru nokkrar leiðir til að leysa þetta vandamál en við skulum skoða þá leið sem er fremur einföld og auðvelt að átta sig á. Eins og við vitum þá getur vísirinn verið bæði tala (meira að segja neikvæð) og einnig breyta. Vísirinn þarf einungis að uppfylla tvö skilyrði; hann verður að vera heiltala og hann verður að passa við einhvern vísi í safninu (við getum ekki sótt stak númer 40 ef það eru bara 39 stök í safninu). Vísirinn mætti þess vegna vera útreikningur sem þýðir að við getum reiknað seinni vísirinn þegar við viljum sækja hann. Við þurfum þá að finna formúlu fyrir seinna stakið út frá því sem við vitum um fyrra stakið.

Í töflunni fyrir ofan sáum við að þegar við erum með fyrsta stakið [0] þá þarf seinna stakið að vera [-1], þegar talan er [1] þá þarf seinna stakið að vera [-2] og svo framvegis. Sem sagt, seinna stakið lækkar alltaf um einn þegar fyrra stakið hækkar um einn. Ef við drögum gildi s frá -1 fyrir seinna stakið, þá fáum við alltaf vísi sem færist jafnt niður á við samhliða s.

Notum prentforritið okkar nema núna skuluð við prenta fyrsta og síðasta stakið í einu, svo annað og næst-síðasta stakið og svo koll af kolli.

def palin_test(st_inn):
    lengd = len(st_inn)//2
    for s in range(lengd):
        print(st_inn[s],'==', st_inn[-1 - s])

>>> palin_test('amma')
a == a
m == m

Núna erum við komin með grunninn að forritinu okkar að því leyti að við erum komin með for-lykkju sem keyrir rétt og sækir rétt stök úr strengnum okkar. Næst þurfum við því að kanna hvort að stökin sem við erum að sækja séu þau sömu. Til þess að gera það getum við notað samanburðarvirkjann ==. Samanburður á tveimur stökum skilar ýmist satt (e. True) eða ósatt (e. False). Ef að við fáum satt þá viljum við skoða næsta stak annars viljum við hætta strax þar sem orðið er augljóslega ekki spegilstrengur. Við þurfum því að nota if-else setningu eins og þessa hér að neðan.

if st_inn[s] == st_inn[-1 - s]:       
        continue                            
    else:                                  
        return False

Stingum þessu inn í forritið okkar og gerum nokkrar tilraunir :

def palin_test(st_inn):
    lengd = len(st_inn)//2                         

    for s in range(lengd):
        print(st_inn[s],'==', st_inn[-1 - s])  

        if st_inn[s] == st_inn[-1 - s]:       
          continue
        else:                                  
            return False                   

>>> palin_test('amma')
a == a
m == m
>>> palin_test('halló')
h == ó
False

Núna er forritið okkar farið að virka vel ef orðið sem við erum með er ekki spegilstrengur en við þurfum líka að geta sagt notandanum ef orðið er spegilstrengur. Líkt og við setjum inn return False í lokin á if-else setningunni til þess að gefa til kynna að orðið sé ekki spegilstrengur þá ættum við að gera return True ef við komumst í gegnum if-else lykkjuna. Við þurfum bara að passa okkur að setja return True á eftir lykkjunni en ekki inn í hana.

def palin_test(st_inn):
    lengd = len(st_inn)//2

    for s in range(lengd):
        print(st_inn[s],'==', st_inn[-1 - s])

        if st_inn[s] == st_inn[-1 - s]:
            continue
        else:
            return False
    return True

>>> palin_test('amma')
a == a
m == m
True
>>> palin_test('halló')
h == ó
False