Kaprekars rutine for firesifrede tall
Lov på eksamen
- Datamaskin med programmeringsverktøy
- Lærebok, dokumentasjon og egne notater og programmer
Ikke åpent internett (bare noen utvalgte nettressurser), kommunikasjon med andre eller kunstig intelligens.
Kan den løses uten PC?
1 av 2 deloppgaver kan løses uten PC.
Fra 2027 er det bare kalkulator og skriftlige hjelpemidler på del 2. Vurderingen er gjort med KI og kan inneholde feil.
Pseudokoden nedenfor beskriver en algoritme som behandler et positivt firesifret heltall, der det første sifferet ikke er 0:
FUNCTION tallspill(tall)
REPEAT
SET stigendeTall TO sortAscending(sifrene i tall)
SET synkendeTall TO sortDescending(sifrene i tall)
SET nyttTall TO synkendeTall - stigendeTall
DISPLAY tall, "->", synkendeTall, "-", stigendeTall, "=" og nyttTall
SET tall TO nyttTall
UNTIL tall er det samme som i forrige runde
RETURN tall
ENDFUNCTIONForklaring
sortAscending(sifrene i tall): sorterer sifrene i tallet fra minste til størstesortDescending(sifrene i tall): sorterer sifrene i tallet fra største til minste
Eksempel
3142 -> 4321 - 1234 = 3087
3087 -> 8730 - 0378 = 8352
8352 -> 8532 - 2358 = 6174
6174 -> 7641 - 1467 = 6174Forklar med egne ord hva algoritmen gjør. Beskriv hvordan algoritmen endrer tallet for hvert steg, og hvordan algoritmen fortsetter til et tall gjentas. Du skal fokusere på hva som skjer i algoritmen som helhet, ikke forklare hver linje i pseudokoden.
Implementer algoritmen i ditt programmeringsspråk. Programmet skal ta inn et heltall fra brukeren, for eksempel tallet 3142, og vise hvert steg i algoritmen slik pseudokoden beskriver, helt til tallet ikke endrer seg lenger.
Fasit
I hvert steg sorteres sifrene i tallet synkende og stigende, og det minste tallet trekkes fra det største. Differansen blir det nye tallet. Dette gjentas til differansen blir den samme som tallet vi startet steget med. For firesifrede tall der ikke alle sifrene er like, ender algoritmen alltid på 6174 (Kaprekars konstant), fordi .
LøsningsforslagKI-generert
Algoritmen tar et firesifret tall og lager to nye tall av de samme sifrene: det største tallet (sifrene sortert synkende) og det minste tallet (sifrene sortert stigende). Så trekker den det minste fra det største. Differansen er det nye tallet, og hele prosessen starter på nytt med det. Hvert steg vises på skjermen.
Løkken fortsetter så lenge tallet endrer seg. Når differansen blir lik tallet den ble regnet ut fra, vil alle senere steg gi det samme tallet. Da stopper algoritmen og returnerer tallet.
Med startverdien 3142 blir stegene:
| Steg | Tall | Synkende | Stigende | Differanse |
|---|---|---|---|---|
| 1 | 3142 | 4321 | 1234 | 3087 |
| 2 | 3087 | 8730 | 0378 | 8352 |
| 3 | 8352 | 8532 | 2358 | 6174 |
| 4 | 6174 | 7641 | 1467 | 6174 |
I steg 4 gir 6174 seg selv igjen, og algoritmen stopper. Tallet 6174 kalles Kaprekars konstant. Alle firesifrede tall der ikke alle sifrene er like, ender på 6174 etter høyst sju steg.
To ting er verdt å merke seg:
- Sifrene må regnes som fire. Differansen kan få færre enn fire sifre, for eksempel . Da må tallet regnes som 0999, med en null foran, ellers virker ikke algoritmen. Det er derfor stigende sortering av 3087 blir 0378 i eksempelet.
- Tall med fire like sifre. For 1111, 2222 og så videre er det største og det minste tallet like, så differansen blir 0. Da gir neste steg også 0, og algoritmen stopper på 0 i stedet for 6174. Oppgaven sier ikke at sifrene må være ulike, så et program bør ta høyde for dette.