Jag funderade lite på ett problem när jag slog in portkoden häromdagen. Antag att man vill pröva alla fyrsiffriga portkoder. då måste man ju prova 10000 kombinationer. De flesta kortläsare testar dock de senast fyra inslagna siffrorna, så om man provar 1111 och sedan 2222 så har man automatiskt provat 1112, 1122 och 1222 också. Det ledde mig till en fundering:
1)
finns det en sekvens så att man bara behöver slå in 10003 siffror för
att ha provat alla koder?
2)
vilken sekvens är den optimala med avseende på antal knapptryckningar
för att ha provat alla?
3)
hur hittar man den sekvensen?
exempel:
med en tvåsiffrig kod med siffror 0 och 1 fås kombinationerna
00,01,10,11
som kan slås in med fem knapptryckningar
00110
i detta fall finns ingen lösning med fyra knapptryckningar.
2 kommentarer:
Hej!
En deBruijn-följd löser ditt problem.
http://mathworld.wolfram.com/deBruijnSequence.html
//
Christian
Tack för det!
Jag tittade vidare, det fanns en förklaring på wikipedia: De_Bruijn_sequence
Det står att det finns (minst) en sekvens med längd k^n för varje längd på kod n och antal knappar k. För fallet med knappar 0-9 och fyrsiffrig kod (ett vanligt fall!) behövs alltså 10^4 knapptryckningar (samt tre till eftersom man måste börja någonstans också).
Tack Christian!
Skicka en kommentar