NumiSum

Programmere en enkel matematisk algoritme

En algoritme kan skrives som PSEUDOKODE – en presis, steg-for-steg beskrivelse som ligner ekte kode, men uten å følge et bestemt programmeringsspråks regler. F.eks.: «SETT rest = tallet MODULO 2. HVIS rest er 0: tallet er et partall. ELLERS: tallet er et oddetall.»

Tips

  • Bruk presise ord i pseudokoden din: SETT (for å lagre en verdi), HVIS/ELLERS (for valg), FOR HVERT (for løkker) – flere av disse kjenner du igjen fra Algoritmer på 6./7. trinn.
  • Test alltid pseudokoden din for hånd med et konkret tall FØR du stoler på at den er riktig – akkurat som i forrige undertema.

Eksempel: Sjekke om et tall er delelig med 3

Skriv en algoritme (pseudokode) som sjekker om et tall er delelig med 3, og test den på tallet 15.

Teste algoritmen på 15
StegVerdi
Tallet15
rest = 15 mod 30
Konklusjondelelig med 3
Løsning:
  1. Algoritmen: «SETT rest = tallet MODULO 3. HVIS rest er 0: tallet er delelig med 3. ELLERS: tallet er ikke delelig med 3.»
  2. test på 15: 15mod  3=015 \mod 3 = 0 (siden 15=3⋅515 = 3 \cdot 5 uten rest). Svaret er 15 er delelig med 3.
Alternativ forklaring/metode: Trekk fra 3 gjentatte ganger i stedet for modulo

Alternativ metode – innenfor pensum, men ikke hovedmetoden her

Gjenta subtraksjon

Hvis MODULO-operasjonen er uvant, kan algoritmen skrives om: «SETT tall = 15. SÅ LENGE tallet er 3 eller mer: trekk fra 3. HVIS tallet til slutt er 0: opprinnelig tall var delelig med 3.» For 15: 15→12→9→6→3→015 \to 12 \to 9 \to 6 \to 3 \to 0 – ender på 0, samme konklusjon som modulo-metoden.

StegVerdi
15 - 312
12 - 39
9 - 36
6 - 33
3 - 30, delelig med 3

Oppgaver

Prøv minst én oppgave på hvert nivå.

Lett(3)

L-21Bruk algoritmen «SETT rest = tallet MODULO 2. HVIS rest er 0: partall» på tallet 8. Er 8 et partall?

Vis fasit
StegVerdi
8 mod 20
KonklusjonJa, partall
  1. 8 mod 2 = 0
  2. ja, partall

L-22Bruk samme algoritme på tallet 13. Er 13 et partall?

Vis fasit
StegVerdi
13 mod 21
KonklusjonNei, oddetall
  1. 13 mod 2 = 1 (ikke 0)
  2. nei, oddetall

L-23Bruk algoritmen «SETT rest = tallet MODULO 5. HVIS rest er 0: delelig med 5» på tallet 20.

Vis fasit
StegVerdi
20 mod 50
KonklusjonJa, delelig med 5
  1. 20 mod 5 = 0
  2. ja, delelig med 5
Middels(3)

M-21Skriv en algoritme (pseudokode) som sjekker om et tall er delelig med 4, og test den på tallet 18.

Vis fasit
StegVerdi
18 mod 42
KonklusjonIkke delelig med 4
  1. 18 mod 4 = 2 (ikke 0)
  2. ikke delelig med 4

M-22En algoritme skal doble et tall og deretter legge til 3. Skriv pseudokoden, og test den på tallet 5.

Vis fasit
StegVerdi
5 * 210
+ 313
  1. SETT resultat = tallet * 2 + 3
  2. 5*2+3 = 13

M-23En algoritme skal sjekke om et tall er et kvadrattall ved å teste om tallet\sqrt{\text{tallet}} er et helt tall. Test den på tallet 49.

Vis fasit
StegVerdi
Kvadratrot av 497
KonklusjonJa, kvadrattall
  1. 49\sqrt{49} = 7, et helt tall
  2. ja, kvadrattall
Vanskelig(3)

V-21Skriv en algoritme (pseudokode) som avgjør om et tall er et primtall ved å teste delelighet med alle tall fra 2 opp til tallet minus 1. Test den på tallet 7.

Vis fasit
StegVerdi
7 mod 2 til 7 mod 6alle ≠ 0
Konklusjon7 er et primtall
  1. 7 mod 2, 7 mod 3, ..., 7 mod 6 er alle ulik 0
  2. 7 er et primtall

V-22En algoritme for å finne primtall (forrige oppgave) tester ALLE tall fra 2 til tallet minus 1. For tallet 97 er dette 95 tester. Hvorfor kan man stoppe testingen ved 97≈9,8\sqrt{97} \approx 9,8 i stedet (altså etter tallet 9)?

Vis fasit
StegVerdi
Full test95 tester (2 til 96)
Forbedret teststopp ved kvadratroten av 97 (ca. 9,8)
  1. Hvis 97 hadde en faktor over 97\sqrt{97}, måtte den tilhørende faktoren være under 97\sqrt{97} og allerede vært funnet
  2. testing kan stoppe ved kvadratroten, en STOR forbedring av algoritmen

V-23Skriv en algoritme som regner ut summen av alle partall fra 1 til et gitt tall nn. Test den for n=10n = 10.

Vis fasit
StegVerdi
2+4+6+8+1030

2+4+6+8+10 = 30