Hur man skapar Thue Morse-sekvensen?
Thue-Morse-sekvensen, eller Prouhet-Thue-Morse-sekvensen, är en binär sekvens vars initiala segment alternerar.
Thue-Morse-sekvensen, eller Prouhet-Thue-Morse-sekvensen, är en binär sekvens vars initiala segment alternerar. Det används för att generera Koch-snöflingor, en fraktalkurva med oändlig längd som innehåller ett ändligt område. Det har andra tillämpningar inom matematik och datavetenskap. Den här artikeln guidar dig genom de olika metoderna med vilka du kan skapa denna sekvens.
Metod 1 av 3: använda den direkta definitionen
- 1Börja med 0 som det första elementet i sekvensen (element t)
- 2Beräkna varje efterföljande element en i taget, med start från t 1. Så här beräknar du det n: te elementet:
- Konvertera n till binärt format. Till exempel blir 5 101
- Räkna antalet 1s i det binära formatet av n. Till exempel har 5 2" 1" i sin binära representation
- Bestäm siffran vid position n genom att ställa in den på 1 om antalet "1" s är udda och 0 om antalet "1" är jämnt.
- 3Upprepa steg 2 för att bestämma så många siffror i sekvensen som du vill.
Metod 2 av 3: använder återfallssamband
- 1Börja med t = 0
- 2Fortsätt beräkna nästa element från n = 1 och öka n med 1 varje gång. Använd följande ekvationer alternativt för att beräkna värdena:
- t 2n + 1 = 1 - t 2n (ekv. 1)
- t 2n = t n (ekv. 2)
- Till exempel:
- n = 0, ersätter ekv. 1: t 1 = 1 - t 0 = 1 (t 0 är 0)
- n = 1, ersätter i ekv. 2: t 2 = t 1 = 1
- n = 1, ersätter i ekv. 1: t 3 = 1 - t 2 = 1 - 1 = 0
- n = 2, ersätter i ekv. 2: t 4 = t 2 = 1
- n = 2, ersätter i ekv. 1: t 5 = 1 - t 4 = 1 - 1 = 0
- n = 3, ersätter i ekv. 2: t 6 = t 3 = 0
- n = 3, ersätter i ekv. 1: t 7 = 1 - t 6 = 1 - 0 = 1
Börja med 0 som det första elementet i sekvensen (element t).
Metod 3 av 3: Använd bitvis negation
- 1Börja med 0
- 2Den bitvisa negationen av 0 är 1 så det andra elementet är 1 och bildar strängen "01"
- 3Den bitvisa negationen av "01" är "10", så det tredje elementet är 1 och det fjärde är 0, och bildar strängen "0110" hittills.
- 4De första 4 elementen är "0110". Den bitvisa negationen av 0110 är 1001. Genom att kombinera dessa är de första 8 elementen "01101001"
- 5Upprepa proceduren för de kommande åtta elementen, sedan 16 och sedan 32... etc.
- 6I kort och matematisk form, när de första 2 n- elementen har specificerats och bildar en sträng s, måste de nästa 2 n- elementen bilda den bitvisa negationen av s, som definierar de första 2 n + 1- elementen och så vidare.
- Till exempel:
- T 0 = 0.
- T 1 = 01.
- T 2 = 0110.
- T 3 = 01101001.
- T 4 = 0110100110010110.
- T 5 = 01101001100101101001011001101001.
- T 6 = 0110100110010110100101100110100110010110011010010110100110010110.
- Och så vidare.
- Till exempel:
Läs också: Hur man beräknar fördubblingstid?
