Tävlingsprogrammering/Uppgifter/Hageltal

Hageltal

Tänk dig att du skriver upp alla positiva heltal på ett oändligt stort papper. Från varje tal n>1 ritar du nu en pil till talet

• n/2 om n är jämnt.
• 3n+1 om n är udda.

Ett avsnitt ur den graf som bildas visas i den här serierutan. De talföljder man får genom att följa pilarna kallas ibland för hageltal eftersom de likt hagelkorn driver upp och ner längs tallinjen innan de slutligen faller ner till marken (talet 1). Det intressanta är att det fortfarande inte har bevisats att man verkligen alltid når talet 1, men det har verifierats för alla tal upp till 1019 så man förmodar det, vilket brukar kallas Collatz förmodan (conjecture).

Skriv ett program som, givet två olika heltal beräknar hur långt ifrån varandra (antal pilar, oavsett riktning) de är i grafen.

Indata

En rad med två olika heltal A och B, där 1≤A,B≤1000.

Utdata

En rad med ett heltal, antal steg mellan A och B i grafen.

Fem körningsexempel

3 20      ger 2

24 10      ger 4

1 5         ger 5

22 32     ger 12

702 703    ger 236

Lösning

Eftersom vi vet att det inte finns några cykler i grafen kan uppgiften kan omformuleras på följande sätt:

• Generera hageltalföljden från A till 1.
• Generera hageltalföljden från B till 1.
• Hitta det första talet C i den ena talföljden som förekommer i den andra.
• Positionen (indexet) för C i vardera sekvensen beskriver avståndet mellan A och C respektive B och C. Avståndet mellan A och B ges därför av summan av dessa index.

Genom att köra igenom de möjliga startvärdena ser man att inga sekvenser blir mer än 200 steg långa, så det mest tidskrävande steget (att kolla om varje tal från den ena sekvensen finns i den andra), kan göras nästan hur naivt som helst. I ett högnivåspråk som Python blir denna algoritm extra enkel att skriva.

import sys
 
def seq(n):    #Rekursiv funktion som genererar sekvensen
    if n==1:        return [n]                  # n=1: avsluta sekvensen
    elif n%2==0:    return [n]+seq(n/2)         # n är jämnt
    else:           return [n]+seq(n*3+1)       # n är udda
 
tokens=sys.stdin.readline().split()
s1=seq(int(tokens[0]))   #Generera sekvens från A
s2=seq(int(tokens[1]))   #Generera sekvens från B
 
for a in s1:     # För varje tal i ena sekvensen
    if a in s2:        # Kolla om det förekommer i den andra sekvensen
        print s1.index(a) + s2.index(a)    #Skriv ut avståndet
        break

Och en lösning i Haskell (av Anton Fors Hurdén):

hageltal 1 = [1]
hageltal n = n : hageltal (if odd n then 3*n+1 else quot n 2)

main = do
	line <- getLine
	let [s1, s2] = map (hageltal . read) $ words line
	print $ sum [1 | n <- s1 ++ s2, elem n s1 /= elem n s2]