Wkonl

Hoe de Thue morse volgorde genereren

De Thue-Morse sequence, of Prouhet-Thue-Morse reeks, is een binaire reeks waarvan het eerste segmenten afwisselen. Het wordt gebruikt zijn Koch sneeuwvlokken, een fractal curve van oneindige lengte met een eindig gebied. Het heeft andere toepassingen in wiskunde en informatica. Dit artikel leidt u door de verschillende manieren waarop u kunt deze sequentie te genereren.

Stappen

Hoe de Thue morse volgorde genereren. Herhaal stap 2 om te bepalen zoveel cijfers van de volgorde zoals je wilt.
Hoe de Thue morse volgorde genereren. Herhaal stap 2 om te bepalen zoveel cijfers van de volgorde zoals je wilt.

Volgens de directe definitie

  1. 1
    Begin met 0 als het eerste element van de reeks (element t )
  2. 2
    Bereken elke volgende elementen een voor een, vanaf t1. Om de n element te berekenen:
    • Omzetten n om de binair formaat. Zo 5 wordt 101
    • Tel het aantal 1s in de binaire indeling van n. Zo 5 heeft 2 "1" s in de binaire representatie
    • Bepaal het cijfer op positie n door deze op 1 als het aantal "1" s is 0 en oneven als het aantal "1" s is gelijk.
  3. 3
    Herhaal stap 2 om te bepalen zoveel cijfers van de volgorde zoals je wilt.

Met behulp van de recurrente betrekking

  1. 1
    Beginnen met t = 0
  2. 2
    Verdere berekeningen van de volgende elementen van n = 1 toenemende n door 1 telkens. Gebruik de volgende vergelijkingen alternatief om de waarden te berekenen:
    • t 2n +1 = 1 - t 2n (Vgl. 1)
    • t 2n = t n (Vgl. 2)
    • Bijvoorbeeld:
      • n = 0, vervangen in Eq. 1: t 1 = 1 - t = 0 1 (t 0 is 0)
      • n = 1, substitueren in vgl.. 2: t = 2 t = 1 1
      • n = 1, substitueren in vgl.. 1: t 3 = 1 - t 2 = 1-1 = 0
      • n = 2, substitueren in vgl.. 2: t = 4 t = 2 1
      • n = 2, substitueren in vgl.. 1: 5 t = 1 - 4 t = 1-1 = 0
      • n = 3, substitueren in vgl.. 2: t = 6 t = 3 0
      • n = 3, substitueren in vgl.. 1: 7 t = 1 - 6 t = 1-0 = 1

Met behulp van bitwise negatie

  1. 1
    Begin met 0
  2. 2
    De bitsgewijze negatie van 0 is 1, zodat het tweede element is 1, die de string "01"
  3. 3
    De bitsgewijze negatie van "01" is "10", dus de derde element is 1 en de vierde is 0, de vorming van de string "0110" tot nu toe.
  4. 4
    De eerste 4 elementen zijn 0110. De bitsgewijze negatie van 0110 is 1001. De combinatie van deze, de eerste 8 elementen zijn "01101001"
  5. 5
    Herhaal deze procedure voor de volgende 8 elementen, dan 16 dan 32... etc.
  6. 6
    In het kort en wiskundige vorm, zodra de eerste 2 n elementen zijn gespecificeerd, de vorming van een string s, dan is de volgende 2 n elementen moeten de bitsgewijze negatie van s, waarvan de eerste 2 n +1 elementen enzovoort definieert vormen.
    • Bijvoorbeeld:
      • T 0 = 0.
      • T 1 = 01.
      • T 2 = 0110.
      • T3 = 01101001.
      • T 4 = 0110100110010110.
      • T 5 = 01101001100101101001011001101001.
      • T6 = 0110100110010110100101100110100110010110011010010110100110010110.
      • En ga zo maar door.