Wkono

Hvordan å generere Thue morse sekvens

Den Thue-Morse sekvens, eller Prouhet-Thue-Morse sekvens, er en binær sekvens som første segmenter alternativ. Den brukes til å generere Koch snøflak, en fraktal kurve av uendelig lengde som inneholder en begrenset område. Det har andre programmer i matematikk og informatikk. Denne artikkelen vil guide deg gjennom de ulike metoder som du kan generere denne sekvensen.

Trinn

Hvordan å generere Thue morse sekvens. Gjenta trinn 2 for å finne ut så mange sifrene i sekvensen som du vil.
Hvordan å generere Thue morse sekvens. Gjenta trinn 2 for å finne ut så mange sifrene i sekvensen som du vil.

Bruke direkte definisjon

  1. 1
    Begynn med 0 som det første element i sekvensen (t element )
  2. 2
    Beregn hvert påfølgende element, ett om gangen, fra t ​​1. For å beregne n th element:
    • Konverter n til binært format. For eksempel, blir 5 101
    • Tell antall 1s i det binære formatet n. For eksempel har 5 2 "1" er i sin binære representasjon
    • Bestem siffer i posisjon n ved å sette den til en hvis antall "1" s er merkelig og 0 dersom antall "1" s er enda.
  3. 3
    Gjenta trinn 2 for å finne ut så mange sifrene i sekvensen som du vil.

Bruke tilbakefall forhold

  1. 1
    Starter med t = 0
  2. 2
    Fortsette å beregne neste elementer fra n = 1 øker n med 1 hver gang. Bruk følgende ligninger alternativt å beregne verdiene:
    • t 2n +1 = 1 - t 2N (Eq. 1)
    • t 2n = t n (Eq. 2)
    • For eksempel:
      • n 0 =, erstatte i Eq. 1: t 1 = 1 - t 0 = 1 (t 0 er 0)
      • n = 1, erstatte i Eq. 2: t 2 = t 1 = 1
      • n = 1, erstatte i Eq. 1: t 3 = 1 - t 2 = 1-1 = 0
      • n 2 =, erstatte i Eq. 2: t 4 = t 2 = 1
      • n 2 =, erstatte i Eq. 1: t 5 = 1 - t 4 = 1-1 = 0
      • n 3 =, erstatte i Eq. 2: t 6 = t 3 = 0
      • n 3 =, erstatte i Eq. 1: t 7 = 1 - t 6 = 1 - 0 = 1

Ved hjelp av bitvis negasjon

  1. 1
    Begynn med 0
  2. 2
    Den bitvise negasjon av 0 er en slik at det andre elementet er 1, danner strengen "01"
  3. 3
    Bitvis negasjon av "01" er "10", så det tredje elementet er 1 og den fjerde er 0, danner strengen "0110" så langt.
  4. 4
    De første fire elementene er 0110. Bitvis negasjon av 0110 er 1001. Ved å kombinere disse, de første åtte elementene er "01101001"
  5. 5
    Gjenta denne prosedyren for de neste åtte elementer, deretter 16 så 32... osv.
  6. 6
    Kort sagt og matematisk form, når de første to n elementer har blitt spesifisert, danner en streng s, deretter neste to n elementer må danne bitvis negasjon av s, som definerer de første to n +1 elementer og så videre.
    • For eksempel:
      • T 0 = 0.
      • T 1 = 01.
      • T 2 = 0110.
      • T 3 = 01101001.
      • T 4 = 0110100110010110.
      • T 5 = 01101001100101101001011001101001.
      • T 6 = 0110100110010110100101100110100110010110011010010110100110010110.
      • Og så videre.