Algoritmen for å legge sammen tall

Hvordan kan kalkulatoren din legge sammen tall raskt? Det trengs det en algoritme for addisjon (pluss), slik som du ville ha gjort det for hånd. Klart definerte steg som vil føre frem til et riktig svar. Dette er ikke problemløsning og algoritmisk tenkning, men det er fint å reflektere over algoritmer du kjenner. Det kan være en stund siden du selv har gjort det for hånd, så som en liten utfordring:

På barneskolen lærte du å legge sammen hele tall med mer enn et siffer. Skriv ned en beskrivelse av algoritmen.

Tallsystemet gjør algoritmen enkel

Slik jeg lærte det på 80-tallet, brukte vi en del tid på å legge sammen ensifrede tall til det ble automatisert og vi husket hva de summene ble: 8+5 = 13 osv. Kanskje synger du en sang om «tiervenner» inne i deg eller teller diskret på fingrene, det går helt fint. Denne typen pugging gir «tabellkunnskap» og er viktig for å regne effektivt for hånd. Algoritmen for addisjon utnytter at du kan legge sammen ensifrede tall og lar deg ved hjelp av det legge sammen heltall av ubegrenset størrelse. Dette er helt avhengig av tallsystemet vi bruker, det indo-arabiske titallsystemet hvor sifferne representerer ulike tierpotenser. Å legge sammen romertall for hånd er derimot ganske vanskelig, hva blir for eksempel CCXCIV + DCCCXLVII? Dette var en av grunnene til at matematikk ikke gjorde fremskritt i romerriket og at de brukte greske tall om de skulle regne. Vår tids datamaskiner bruker totallsystemet, hvor det er mye mindre å huske: 0+0 = 0, 0+1 = 1 og 1+1 blir 0 med 1 i mente. Titallsystemet fungerer veldig godt for mennesker, siden vi stort sett har ti fingre til hjelp i tellingen.

Beskrivelse av algoritmen

Jeg lærte å sette tallene under hverandre, med like posisjoner over hverandre og streker for å skille ut svaret. For 27 + 65 får vi:

  27
+ 65
 ---
=
 ===

Algoritmen starter på enerplassen, helt til høyre, og legger sammen de to sifrene: 7+5 = 12. Resultatet på enerplassen skrives i svaret der, og tierverdien overføres til tierkolonnen i «mente» («i tankene» på latin).

  ¹
  27
+ 65
 ---
=  2
 ===

Så blir prosessen gjentatt for sifferet til venstre, på tierplassen. Sifferet i «mente» må også legges til: 1+2+6 = 9. Du er ferdig når dette er gjort for alle siffer.

  ¹
  27
+ 65
 ---
= 92
 ===

Modellering med programmering

Dette er en greit formulert algoritme, som er en fin utfordring å implementere i python. Det er noen utfordringer:

Du må håndtere et og et siffer om gangen, for eksempel ved å gjøre om tallet til en tekststreng eller liste av tall og lese en og en verdi.
Du må lese tallene «bakfra» for å starte med den minste verdien. Nummereringen i python starter fra venstre, som for oss blir sifferet med størst verdi.
Om summen i en kolonne blir større enn 9, må du lagre «mente»-verdien til neste kolonne.
Dersom tallene har ulikt antall siffer, som 42 + 386, må du passe på å legge sammen like sifferposisjoner.
Svaret, og mente-verdiene, kan ha en verdi i en posisjon som de opprinnelige tallene ikke har en. For eksempel blir 59 + 83 = 142.
Kan du få programmet til å skrive det ut som du ville ha stilt det opp med blyant på et ruteark?

Eksempel på addisjon i python

I eksempelet under lar jeg verdiene av tallene som skal legges sammen være representert ved tekststrenger. Det gjør det enklere å håndtere et og et siffer, og å skrive de ut til slutt. Ulempen er at det blir en del konvertering med str()og int(). Python lar deg ikke endre en tekststreng, så variablene mente og svar er lister hvor hvert element er et siffer.

Jeg bruker også et par innebygde funksjoner for python-strenger: i linje 5 og 6 en for å gjøre alle like lange og fylle fra venstre med 0: a = a.rjust(lengde, "0") og i linje 17 for å slå sammen listen til en tekststreng med ingen mellomrom mellom: svar = int("".join(svar)). Du kan gjerne lage din egen funksjon for disse.

def pluss(a, b):
    a = str(a)                    # Gjør om til tekst
    b = str(b)
    lengde = max(len(a), len(b))  # Fyller med 0 så de blir like lange
    a = a.rjust(lengde, "0")
    b = b.rjust(lengde, "0")
    
    svar = [" "]*(lengde+1)       # Setter opp lister som skal holde 
    mente = ["0"]*(lengde+1)      # svaret og mente
    
    for i in range(lengde-1, -1, -1):  # Løkke som går baklengs
        resultat = str(int(a[i]) + int(b[i]) + int(mente[i+1]))
        if len(resultat) == 2:    # Hvis vi må ha mente, tosifret delsvar
            mente[i] = "1"
        svar[i+1] = resultat[-1]  # Lagrer et siffer i svaret
    svar[0] = mente[0]            # Hvis svaret har et siffer mer enn argumentene
    svar = int("".join(svar))     # Tilbake til heltall
    return svar

For å til slutt kunne skrive ut regnestykket satt opp som du ville ha gjort for hånd, kan du erstatte den siste linjen return svar med koden under som setter inn en del print()-kommandoer. For å fjerne innledende 0, blir tekststrengen først gjort om til hetall. "0058" blir da til 58. Så gjøres det tilbake til en teksttreng med gitt lengde og mellomrom først. Husk å ha korrekt innrykk fra venstre om du kopierer inn koden under.

    # Gjør om mente til blanke felt og små ettall.
    mente = " "+"".join(mente)
    mente = mente.replace("0", " ")
    mente = mente.replace("1", "¹")
    # Fjerner eventuelle 0 som står først i tallene
    a = int(a)
    a = str(a).rjust(lengde, " ")
    b = int(b)
    b = str(b).rjust(lengde, " ")
    svar = str(svar).rjust(lengde+1, " ")
    
    # Skriver ut svaret
    print("" ,mente)
    print("  ", a)
    print("+ ", b)
    print(" ", "-"*(lengde+1))
    print("=", svar)
    print(" ", "="*(lengde+1))

Det gir dette resultatet, hvis du tester det for litt store tall:

>>> pluss(7578962, 94701342)
  ¹¹¹ ¹¹¹  
    7578962
+  94701342
  ---------
= 102280304
  =========

Utvidelser

Kan du få den til å legge sammen desimaltall?
Hva om det er flere enn to tall som skal legges sammen?
Er det juks å bruke pythons innebygde + for å legge sammen verdiene av to siffer pluss eventuell mente? Hvordan kan du unngå det?
Algoritmen gjentar det samme med et litt mindre problem i hvert steg, kan du omformulere den til en rekursiv algoritme?
Kanskje har du lært å legge sammen tall med en annen algoritme, kan du programmere den?
Kan du programmere subtraksjon, eller minus?
Kan du legge sammen romertall? Enten ved å konvertere de til titallsystemet eller ikke.
Oppsettet blir tegnet med vanlige bindestreker og likhetstegn for å lage skillestrekene. Finn spesialtegn som kan lage sammenhengende streker.

Relatert

11. juli 2024