Wko

Hur man skapar Thue morse sekvensen

Den Thue-Morse sekvens, eller Prouhet-Thue-Morse sekvens, är en binär sekvens vars initiala segment suppleant. Det används för att generera Koch snöflingor, en fraktal kurva av oändlig längd som innehåller ett ändligt område. Det finns andra program inom matematik och datavetenskap. Denna artikel kommer att guida dig genom de olika metoder genom vilka du kan generera denna sekvens.

Steg

Hur man skapar Thue morse sekvensen. Upprepa steg 2 för att avgöra så många siffror i sekvensen som du vill.
Hur man skapar Thue morse sekvensen. Upprepa steg 2 för att avgöra så många siffror i sekvensen som du vill.

Använda den direkta definitionen

  1. 1
    Börja med 0 som det första elementet i sekvensen (elementet t )
  2. 2
    Beräkna varje efterföljande elementet en i taget, med början från t 1. För att beräkna den n: te elementet:
    • Konvertera n till binärt format. Till exempel blir 5 101
    • Räkna antalet 1s i binärt format av n.. Till exempel har 5 2 "1": or i dess binära representation
    • Bestäm siffran i position n genom att sätta den till 1 om antalet "1" s är udda och 0 om antalet "1" s är ännu.
  3. 3
    Upprepa steg 2 för att avgöra så många siffror i sekvensen som du vill.

Använda återkommande relation

  1. 1
    Börja med t = 0
  2. 2
    Fortsätta beräkna nästa element från n = 1 ökar n med 1 varje gång. Använd följande ekvationer alternativt att beräkna de värden:
    • t 2n +1 = 1 - t 2n (ekvation 1)
    • t 2n = t n (ekvation 2)
    • Till exempel:
      • n = 0, varvid i ekv. 1: t 1 = 1 - t 0 = 1 (t 0 är 0)
      • n = 1, varvid i Ekv. 2: t 2 = t 1 = 1
      • n = 1, varvid i Ekv. 1: t 3 = 1 - t 2 = 1 - 1 = 0
      • n = 2, varvid i Ekv. 2: t 4 = t 2 = 1
      • n = 2, varvid i Ekv. 1: t 5 = 1 - t 4 = 1 - 1 = 0
      • n = 3, varvid i Ekv. 2: t 6 = t 3 = 0
      • n = 3, varvid i Ekv. 1: t 7 = 1 - t 6 = 1 - 0 i = 1

Använda bitvis negation

  1. 1
    Börja med 0
  2. 2
    Den bitvis negation av 0 är 1, så den andra delen är 1, bildar strängen "01"
  3. 3
    Den bitvis negation av "01" är "10", så det tredje elementet är 1 och den fjärde är 0, bildar strängen "0110" hittills.
  4. 4
    De första fyra elementen är 0110. Den bitvis negation av 0110 är 1001. Kombinera dessa, de första 8 element är "01101001"
  5. 5
    Upprepa denna procedur för de kommande 8 element, sedan 16 och sedan 32... etc.
  6. 6
    I korta och matematisk form, när de första 2 n element har angetts, bildar en sträng s, sedan nästa 2 n element måste bilda bitvis negation av s, som definierar de första 2 n +1 element och så vidare.
    • Till exempel:
      • T 0 = 0.
      • T 1 = 01.
      • T 2 = 0110.
      • T 3 = 01.101.001.
      • T 4 = 0110100110010110.
      • T 5 = 01101001100101101001011001101001.
      • T 6 = 0110100110010110100101100110100110010110011010010110100110010110.
      • Och så vidare.