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
redigeraEftersom 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]