Ханойдың магниттік мұнарасы - Magnetic Tower of Hanoi

Ханойдың магниттік мұнарасы (MToH) жұмбақ

The Ханойдың магниттік мұнарасы (MToH) жұмбақ - классиканың вариациясы Ханой мұнарасы басқатырғыш (ToH), мұнда әр дисктің екі жағы болады, мысалы, «қызыл» және «көк» түрлі-түсті. MToH басқатырғышының ережелері түпнұсқа басқатырғышының ережелерімен бірдей, оған қоса әр диск қозғалған кезде аударылады және егер олардың жанасатын жақтары бірдей түсті болса, екі дискіні бір-біріне қоюға болмайды. . Әр дискінің солтүстік және оңтүстік полюстері бар, ұқсас полюстер бір-бірін репеляциялайды және қарама-қарсы полюстер бір-бірін қызықтырады.Әр дискінің ішіндегі магниттер физикалық тұрғыдан заңсыз әрекеттерді болдырмайды.^[1]

Магниттіліктің иллюстрациясы: Дискілер магниттік әсер етеді, егер олардың жанасатын жақтары бірдей түсті болса

ToH классикалық басқатырғышының таңқаларлық ерекшеліктерінің бірі оның 2-негізге қатынасы: басқатырғышты шешуге қажетті жалпы жүрістердің минималды саны - 2ⁿ - 1 (қайда n - бұл дискілердің саны), ал дискінің ең аз қозғалу саны к 2.^к − 1 (дискілер төменнен жоғарыға қарай нөмірленген к = 1 ең үлкен диск, және к = n ең кішкентай болу). Төменде түпнұсқа ToH басқатырғышының 2-негізге қатысты болатындығы сияқты, MToH-дің 3-негізге де қатысты екендігі, бірақ одан да күрделі болады.^[2]

Шығу тегі

MToH белгілі бір вариацияларына математикалық эквивалентті жұмбақтар біраз уақыттан бері белгілі. Мысалы, біреуіне балама басқатырғыш түрлі-түсті вариациялар MToH пайда болады Бетонды математика.^[3] Бұл басқатырғышта жылжуға тек белгілі бір посттар арасында ғана рұқсат етіледі, бұл посттарға тұрақты түстерді тағайындауға тең (мысалы, егер екі постта оларға бекітілген бірдей түсті болса, онда екі пост арасында тікелей қозғалуға жол берілмейді).

Ақысыз (түсті емес) MToH алғаш рет интернетте пайда болды^[4] шамамен 2000 жылы («Домино Ханой» деген атпен) математик Фред Луннонның Ханой мұнарасының түпнұсқа басқатырғыштарының әр түрлі вариацияларын егжей-тегжейлі шолу шеңберінде.

MToH-ді физик Ури Леви 1984 жылдың жазында өздігінен ойлап тапты, ол сонымен бірге магнетизмге ұқсастық пен атауды ұсынды.^{[түсіндіру қажет ][5]} Кейінірек доктор Леви бірқатар мақалаларын жариялады ^[1][6][7] MToH математикалық аспектілерімен айналысады.

Сөзжұмбақтың сипаттамасы

Жұмбақтың бастапқы орны

MToH басқатырғышы дерек көзі (S), тағайындалатын жер (D) және аралық (I) деп белгіленген үш посттан және стекадан тұрады. n Қызыл немесе Көк түстерінің әр түрлі түсі бар дискінің әр жағымен әр түрлі өлшемді дискілер. Сөзжұмбақтың басында дискілер көлемінің кішіреюіне қарай S тіреуіне қойылады (яғни ең үлкен диск төменгі жағында), және барлық дискілерде қызыл жағы жоғары қаратылған болады. Сөзжұмбақтың мақсаты (оның «негізгі» нұсқасында) бүкіл стекті, бір-бірден дискіні D постына жылжыту, тәртіпті ең үлкенінен ең кішісіне, бірақ көк жақтарын жоғары қаратып ұстау.

Жұмбақтың соңғы орны

Дискілердің қозғалысын реттейтін ережелер:

• Үлкенірек дискіні кіші дисктің үстіне қою мүмкін емес (бастапқы ToH-дағыдай)
• Дискіні жылжытқанда, оны аударады, яғни жоғары қараған түс төмен қарайды
• Түсі бірдей әр түрлі дискілердің екі жағы бір-біріне тиіп кетпеуі мүмкін (мысалы, Көк жағы төмен қараған дискіні Көк жағы жоғары қараған дисктің үстіне қоюға болмайды).

Жұмбақ шешімі n = 2 және n = 3

MToH ережелерін иллюстрациялау және жалпы шешімге жету жолын көрсету үшін мысалдар арқылы жұмыс жасаған пайдалы n = 2 және n = 3. жағдай үшін n =, Үш қадаммен салыстырғанда, ілеспе суретте көрсетілгендей төрт қадам қажет n = ToH-нің 2 жағдайы. Қосымша қадам қажет, себебі екінші қадамнан кейін кішігірім дискіні I постынан D постына тікелей жылжыту мүмкін емес, өйткені бұл оның көк жағы төмен қаратылғанын білдіреді. Осылайша, кішкене дискінің түсін аудару үшін оны D тіреуіне Көк жағын жоғары қаратып қоюға болатын қосымша қадам қажет.

Шешімі n = 2 жұмбақ

Үшін n = 3 жағдай, шешім келесі қадамдарды қамтиды:

• Дискілерді 1-ден 3-ке дейін ең үлкенінен кішісіне қарай нөмірлеу, алдымен 2 және 3 дискілерді S постынан I постына ауыстырады (төрт жүріс)

Бұл бірінші кезең келесіге ұқсас n = Жоғарыда сипатталған 2 жұмбақ, ол төрт жүрісті алады, мұнда D мен I посттары ауыстырылады. Алайда, бұл ұқсас емес n = S постында үлкен дисктің болуына байланысты 2 жұмбақ, оны қызыл түске бояйды. Бұл дегеніміз, дискіні осы постқа тек қызыл жағын жоғары қаратып қоюға болады.

• 1-дискіні S-ден D-ге ауыстыру (бір қозғалыс)

Осы кезеңде біреуін қайтадан пайдалануға азғырылуы мүмкін n = 2 басқатырғышты, және 2 және 3 дискілерді I-ден D-ге 4 жүріске ауыстыруға тырысыңыз. Алайда, мұнда тағы да қамқорлық қажет. D дискісінде 1 болғандықтан, D енді «түсті» Көк түске ие, яғни басқа диск оған Көк жағы жоғары қараған жағдайда ғана орналастырылуы мүмкін. Сонымен бірге n = 2 басқатырғыштар дискілердің қызыл жағын бастапқы күйінде жоғары қаратады, ал мұнда олардың көк жақтарын жоғары қаратады. Осылайша, бұл аралық конфигурация n = 2 MToH. Оның орнына біз келесідей әрекет етеміз:

• 3-дискіні I арқылы D-ге S арқылы жылжытыңыз (2 қозғалыс)
• 2-дискіні I-ден S-ге ауыстыру (1 жылжыту)
• 3-дискіні D-ден I-ге ауыстыру (1 жылжыту)
• 2-дискіні S-ден D-ге ауыстыру (1 жылжыту)
• 3-дискіні I-ден D-ге ауыстыру (1 жылжыту)

Осылайша, шешім 11 қадамды қажет етеді. Жаңа көрсетілгендей, қолдануға тырысу табиғи нәрсе n = Бөліктерін шешуге арналған 2 шешім n = А-да 3 жұмбақ рекурсивті классикалық ToH басқатырғыштарын шешу үшін қолданылатын тәсіл. Алайда, классикалық ToH-тен айырмашылығы, мұнда n = 2 ерітінді посттар мен дискілердің түсіне байланысты соқыр түрде қолданыла алмайды. Бұл тармақ жалпыға ортақ шешімге қол жеткізуге болатындығын көрсетеді n-disk MToH басқатырғыштары, посттар алдын ала боялған (көк немесе қызыл) басқатырғыштардың нұсқаларын қарастыру қажет. Осы нұсқаларды қарастыра отырып, MToH басқатырғышына толық рекурсивті қатынастарды дамытып, осылайша жалпы шешім табуға болады.

MToH басқатырғышының түрлі-түсті нұсқалары

MToH «апа жұмбақтарының» түрлі-түсті вариациялары

MToH басқатырғышының жоғарыдағы сипаттамасы дискілердің өзі түсті болғанымен, тіректер бейтарап деп болжайды. Бұл дегеніміз, бос пост дискіні Қызыл жағы немесе Көк жағы жоғары қаратып қабылдай алады. MToH-дің бұл негізгі нұсқасы «ақысыз» MToH деп аталады.

MToH басқатырғышының басқа нұсқалары болуы мүмкін, олардың көмегімен тірек суретте көрсетілгендей посттардың өзі боялған. Егер пост алдын ала Қызыл / Көк түске боялған болса, онда бұл алдын ала боялған постқа тек Қызыл / Көк жағы жоғары қаратылған дискілерді қоюға болады. MToH әр түрлі вариацияларын 3 әріптен тұратын «SID» белгісімен атауға болады, мұнда S, ID сәйкесінше Source, Intermediate және Destination посттарының түсін білдіреді және R (Red), B (Blue) мәндерін қабылдай алады. , немесе N (Бейтарап - түс жоқ). Сонымен, «NNN» басқатырғышы бос MToH туралы айтады, ал «RBB» басқатырғышы S посты алдын ала қызыл түске боялған вариацияны білдіреді, ал I және D посттары алдын ала көк түске боялған.

MToH вариациялары өз бетінше жұмбақтар болғанымен, олар еркін MToH шешуде де маңызды рөл атқарады. Жоғарыда көрсетілгендей, бос MToH аралық күйлерін түрлі-түсті вариациялар деп санауға болады, өйткені онда дискі бар пост дисктің тиісті түсін қабылдайды (яғни тірекке тек сол түсті жоғары қараған дискіні қоюға болады) ).

Мысалы, тегін n = Жоғарыда сипатталған 3 MToH басқатырғышы, 5 қозғалудан кейін үлкен дискі D постында орналасқан аралық күйге жетеді. Осы сәттен бастап D бағанасы Көк түске боялған болып саналады, ал басқатырғыш «NNB» басқатырғышына тең болады. Егер шешім белгілі болса n = 2 «NNB» сөзжұмбақ, оны бірден орындау үшін қолдануға болады n = 3 тегін басқатырғыш.

Симметрия қатынастары

Түрлі-түсті вариациялардың барлығы бірдей емес, басқатырғыштар симметрия басқатырғыштармен алдын ала боялған басқатырғыштардың вариациялары бірдей болатындығын білдіреді. Мысалы, егер біз RBB басқатырғышын артқа шешетін болсақ, онда бұл RRB басқатырғышын кәдімгі алға бағытта шешумен бірдей (ескерту: басқатырғыштың басында барлық дискілер бар деген ережені сақтау үшін көк және қызыл түстер ауыстырылды) олар қызыл жағын жоғары қаратып, постта болуы керек). Сонымен, RBB және RRB басқатырғыштары а уақытты өзгерту симметриясы жұп. Бұл дегеніміз, олар қажет болатын оңтайлы қозғалыстар санына қатысты бірдей сипаттамаларға ие, дегенмен әр жұмбақ оны шешу үшін нақты алгоритмді қажет етеді. Шындығында, уақыттың кері симметриялы жұбын құрайтын басқатырғыштардың бір-біріне тәуелді болатындығы төменде көрсетілген, өйткені біреуінің шешу алгоритмі екіншісінің шешу алгоритмін пайдаланады.

Шешімдер

Классикалық TOH басқатырғыштарындағы сияқты, MToH шешудің қарапайым және нұсқаулық әдістерінің бірі қолдану болып табылады рекурсивті алгоритмдер. Мұндай алгоритмдер басқатырғыштың таңдалған вариациялары үшін төменде келтірілген және шешімдердің оңтайлылығы дәлелденген. Осы алгоритмдерді пайдалану арқылы рекурсивті қатынастар және кейіннен жабық формалық өрнектер басқатырғышты шешуге қажетті жалпы қозғалыстардың саны және шешім кезінде әр дискінің қанша жүрісі болатындығы туралы білуге ​​болады.

Рекурсивті қатынастарды сонымен бірге a көмегімен ұсынуға және талдауға болады Марков типтік талдау, ол да талқыланады.

Рекурсивті шешу алгоритмдері және олардың оңтайлылығын дәлелдеу

Алдымен RBB және RRB басқатырғыштарының уақытты өзгерту симметриясының жұбын қарастырған жөн. Көрсетілгендей, бұл екі жұмбақтың шешімі қарапайым, өйткені олардың рекурсивті алгоритмдері басқатырғыштың басқа вариацияларына емес, біреуіне ғана тәуелді.

Керісінше, жартылай түсті вариацияларға арналған шешімдер (бір немесе бірнеше пост бейтарап жерде) және толық еркін вариация күрделі рекурсиялық қатынастармен шешіледі. RBB (n) және RRB (n) жұмбақтарын келесі жұптың көмегімен шешуге болады. оңтайлы алгоритмдер:

RBB (n) үшін:

• Жылжыту n - RBB көмегімен S-ден I-ге дейінгі ең кішкентай 1 диск (n - 1) алгоритм
• 1-дискіні S-ден D-ге ауыстырыңыз
• Жылжыту n - RRB көмегімен I-ден S-ге дейінгі 1 диск (n - 1) алгоритм
• Жылжыту n - RBB көмегімен S-ден D-ге дейінгі 1 диск (n - 1) алгоритм

RRB (n) үшін:

• Жылжыту n - RRB көмегімен S-ден D-ге дейінгі ең кішкентай 1 диск (n - 1) алгоритм
• Жылжыту n - RBB көмегімен D-ден I-ге дейінгі дискілер (n - 1) алгоритм
• 1-дискіні S-ден D-ге ауыстырыңыз
• Жылжыту n - RRB көмегімен I-ден D-ге дейін 1 диск (n - 1) алгоритм

Осы алгоритмдердің оңтайлылығы арқылы дәлелденеді индукция, келесідей (бұл дәлел алгоритмдердің толық түсіндірмесін құрайды):

Үшін n = 1 алгоритмдердің оңтайлы екендігі анық, өйткені бір ғана қозғалыс бар. Әрі қарай, алгоритмдер оңтайлы болып саналады n - 1, және осы болжамды қолдана отырып, олардың оңтайлы екендігі көрсетілгенn.

RBB бастап (n) алгоритмі, 1-дискіні D постына орналастырмас бұрын, алдымен S постында болуы керек (бұл жалғыз қызыл түске боялған пост), ал қалған дискілер I постында болуы керек. Сонымен, шешім осы аралық күйден өтуі керек, ал болжам бойынша, осы аралық күйге жетудің оңтайлы әдісі RBB (n - 1) D және I жазбаларымен алгоритм ауыстырылды.

Әрі қарай, 1 дискіні S-ден D-ге ауыстыру керек, өйткені оны кем дегенде бір рет жылжыту керек.

Әрі қарай, осы күйден соңғы шешімге тек барлық жерде болатын аралық күй арқылы қол жеткізуге болатындығы көрсетілген n - S дискісінде 1 диск бар. 2-дискіні D постына орналастыру үшін ол алдымен S постында (жалғыз Қызыл постта), ал екіншісі болуы керек n - Мен постта 2 диск болуы керек. Дегенмен, 3-дискіні I постына орналастырмас бұрын, ол алдымен дискінің 2-індегі S постында болуы керек. Бұл пайымдау барлық дискілерде жүруі мүмкін, олардың әрқайсысы алдымен S постында болуы керек. Мен хабарлама жіберемін, осылайша шешім барлық жерде болатын аралық күйден өтуі керек n - S дискісінде 1 диск бар.

Осы аралық күйге жету үшін трансферт беретін оңтайлы алгоритмді қолдану қажет n - Blue I постынан Red S постына Blue D посты арқылы 1 диск, яғни оңтайлы BBR (n - 1) RRB-ге балама алгоритм (n - 1) алгоритм (түстер жай ауыстырылған).

Соңында, аудару қажет n - I посты арқылы S-ден D постына дейін ең кішкентай 1 диск. Бұл, әрине, тек RBB (n - 1) алгоритм.

Жоғарыда келтірілген RRB (n) алгоритмінің оңтайлы екендігін көрсету үшін осыған ұқсас пайымдауларды қолдануға болады. Шешімді алгоритмдерді жазуға және олардың оңтайлылығын дәлелдеуге болады, басқаша жұмбақтардың уақытты кері айналдыру жұптары үшін, атап айтқанда:

• RBN және NRB жұбы
• RNB және BNR жұбы
• RNN және NNB жұбы

Бұл алгоритмдер, әдетте, күрделі және жоғарыда сипатталған толық RBB және RRB алгоритмдерін қолданады. Осы алгоритмдердің толық мәліметтерін және олардың оңтайлылығының дәлелдерін табуға болады.^[7]

Осы бөлімді аяқтау үшін NNN толықтай басқатырғышты шешу алгоритмі келтірілген. Оңтайлылықтың дәлелі де табуға болады.^[7]

• Ең кішісін жылжытыңыз n - SN-ден D-ге дейін 1 диск, RNN қолдана отырып (n - 1) алгоритм
• 1-дискіні S-ден D-ге ауыстырыңыз.
• Ең кішісін жылжытыңыз n - RRB көмегімен I-ден S-ге дейін 2 диск (n - 2) алгоритм (бұл BBR (n-2) алгоритміне балама)
• Ең кішісін жылжытыңыз n - RBB көмегімен S-ден I-ге дейінгі 2 диск (n - 2) алгоритм
• 2-дискіні I-ден S-ге ауыстырыңыз
• Ең кішісін жылжытыңыз n - D-ден I-ге дейін SB арқылы 2 диск, RBN (n - 2) алгоритм (бұл BRN-ге баламалы (n - 2) алгоритм)
• 2-дискіні S-ден D-ге ауыстырыңыз
• Ең кішісін жылжытыңыз n - NNB алгоритмін қолдана отырып S-ден I-ге дейін 2 диск

Қайталану қатынастары және оларды шешу жолдары

Шешім алгоритмдері табылғаннан кейін оларды шығару үшін қолдануға болады қайталанатын қатынастар алгоритмді орындау кезінде жүргізілген қозғалыстардың жалпы саны үшін, сондай-ақ әр диск жасаған қозғалыстар саны үшін.

RBB және RRB басқатырғыштарының оңтайлы алгоритмдері бойынша жалпы жүрістер санын белгілеу ${ displaystyle S_ {RBB} (n)}$ және ${ displaystyle S_ {RRB} (n)}$, содан кейін жоғарыда келтірілген шешу алгоритміне сілтеме жасай отырып, келесі қайталану қатынастарының болатындығын көрсету оңай:

${ displaystyle S_ {RBB} (n + 1) = 2S_ {RBB} (n) + S_ {RRB} (n) + 1 = 3S_ {RBB} (n) +1}$

мұнда RBB және RRB басқатырғыштары уақыттың кері симметрия жұбын құрайтындығы және осылайша қолданылған ${ displaystyle S_ {RBB} (n) = S_ {RRB} (n)}$.

Сондай-ақ, k дискісі арқылы жасалынған қозғалыстардың жалпы санына арналған рекурсиялық қатынасты тізімдеуге болады ${ displaystyle P_ {RBB} (k)}$ және ${ displaystyle P_ {RRB} (k)}$ сәйкесінше RBB және RRB алгоритмдері үшін (ескеріңіз ${ displaystyle P (k)}$ дискілердің жалпы санынан тәуелсіз n басқатырғышта). Тағы да алгоритмдер арқылы жұмыс жасау және теңдікті қолдану ${ displaystyle P_ {RBB} (k) = P_ {RRB} (k)}$, мұны көрсету қарапайым

${ displaystyle P_ {RBB} (k + 1) = 2P_ {RBB} (k) + P_ {RRB} (k) = 3P_ {RBB} (k)}$

Осы рекурсивті қатынастардан тұйық формалы өрнектерді алу өте қарапайым ${ displaystyle S_ {RBB} (n)}$ және ${ displaystyle P_ {RBB} (k)}$арқылы беріледі

${ displaystyle S_ {RBB} (n) = S_ {RRB} (n) = { tfrac {1} {2}} 3 ^ {n} - { tfrac {1} {2}}}$

${ displaystyle P_ {RBB} (k) = P_ {RRB} (k) = 3 ^ {k-1}}$

Көріп отырғанымыздай, бұл шамалар 3-ке теңⁿ, 2-ге тең келетін классикалық ToH басқатырғышынан айырмашылығыⁿ. Шын мәнінде, көрсетілгендей,^[7] MToH басқатырғышының барлық нұсқалары асимптотикалық қатынастарды қанағаттандырады

${ displaystyle lim _ {n to infty} S (n) = s3 ^ {n}}$

${ displaystyle lim _ {k to infty} P (k) = p3 ^ {k-1}}$

факторлармен с, б келесі кесте арқылы берілген:

Ақырында, ал бүтін тізбектер үшін өрнек тудырады ${ displaystyle S_ {RRB} (n)}$ және ${ displaystyle P_ {RRB} (k)}$ Интернеттегі бүтін тізбектер энциклопедиясында (OEIS) белгілі және^[8] басқатырғыштардың вариациялары тудырған бүтін тізбектер онша маңызды емес және MToH талдауға дейін OEIS-те табылған жоқ. Олардың саны 15-тен тұратын бұл жаңа тізбектер қазір тізімге енгізілді.

Марков типіндегі шешім

Фред Луннон ұсынған және мұнара жұмбақтарының вариацияларын шолуда ұсынылған MToH басқатырғыштарын (және басқа да басқатырғыштарды) талдаудың күшті әдісі,^[4] матрицалық әдіс.

Бұл әдісте әртүрлі жұмбақтарды шешудің алгоритмдері бір-біріне тәуелді болатын тәуелсіз топтарға бөлуге күш салынбайды. Оның орнына шешу алгоритмдері барлық басқатырғыштар алгоритмдері өзара тәуелді болатындай етіп, тура жолмен жазылады. Мұны жасағаннан кейін, жүрістердің жалпы саны ${ displaystyle S_ {SID} (n)}$ (S, I, D R, B, N-ге тең) әр басқатырғыштың вариациясы үшін келесідей жазуға болады:

${ displaystyle S_ {NNN (n)} = S_ {RNN (n-1)} + 1 + S_ {NNR (n-1)}}$

${ displaystyle S_ {RNN (n)} = S_ {RNN (n-1)} + 1 + S_ {NBR (n-1)}}$

${ displaystyle S_ {NNR (n)} = 2 cdot S_ {RRB (n-1)} + 1 + S_ {RBN (n-1)} + 1 + S_ {RNN (n-1)}}$

${ displaystyle S_ {NBR (n)} = 2 cdot S_ {RRB (n-1)} + 1 + S_ {RBN (n-1)} + 1 + S_ {RBN (n-1)}}$

${ displaystyle S_ {RNB (n)} = S_ {RBN (n-1)} + 1 + S_ {NBR (n-1)}}$

${ displaystyle S_ {RBN (n)} = S_ {RNB (n-1)} + 2 cdot S_ {RRB (n-1)} + 1}$

${ displaystyle S_ {RRB (n)} = 2 cdot S_ {RRB (n-1)} + 1 + S_ {RRB (n-1)}}$

Басқа вариациялардан және жалпы ережеден айырмашылығы, MToH вариациялары NNR және NBR дискілердің қызыл жақтарын жоғары қаратып аяқтайды. Бұл тағайындалған посттың қызыл түске боялуының табиғи салдары.

Егер қазір векторды анықтайтын болсақ

${ displaystyle { vec {S}} (n) = { begin {bmatrix} S_ {NNN} (n) S_ {RNN} (n) S_ {NNR} (n) S_ {NBR } (n) S_ {RNB} (n) S_ {RBN} (n) S_ {RRB} (n) 1 end {bmatrix}}}$

Содан кейін

${ displaystyle { vec {S}} (1) = { begin {bmatrix} 1 1 2 2 1 1 1 1 end {bmatrix}},}$

және рекурсиялық қатынастарды келесі матрица түрінде жазуға болады

${ displaystyle { vec {S}} (n) = M { vec {S}} (n-1),}$

онда Марков матрицасы ${ displaystyle M}$ арқылы анықталады

MToH басқатырғышының әр түрлі вариациясының оңтайлы шешімдері үшін қажет болатын қозғалыс саны

${ Displaystyle М экв { {bmatrix} 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 0 & 1 & 0 & 0 & 0 & 1 & 2 & 2 0 & 0 & 0 & 0 & 0 & 2 & 2 & 2 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 0 & 0 & 0 & 0 & 1 & 0 & 2 & 1 0 & 0 & 0 & 0 & 0 & 0 & 3 & 1 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 басталады түпкі {bmatrix}}}$

Үшін теңдеу ${ displaystyle { vec {S}} (n)}$ енді ретінде жазуға болады

${ displaystyle { vec {S}} (n) = M ^ {n-1} { vec {S}} (1).}$

The тән көпмүшелік туралы ${ displaystyle M}$ арқылы беріледі

${ displaystyle (K-3) (K ^ {3} -K-2) (K-1) ^ {2} K ^ {2},}$

келесі сегіз тамырға ие

${ displaystyle {K_ {1}, нүктелер, K_ {8}} = {3,1.52183, -0.7607 + 0.8579i, -0.7607-0.8579i, 1,1,0,0},}$

және сегіз жеке вектор ${ displaystyle { vec { xi}} _ {j}}$ осындай

${ displaystyle M { vec { xi}} _ {j} = K_ {j} { vec { xi}} _ {j}.}$

Біз енді білдіре аламыз ${ displaystyle { vec {S}} (1)}$ сегіз жеке векторды қолдана отырып

${ displaystyle { vec {S}} (1) = sum _ {j = 1} ^ {8} b_ {j} K_ {j} { vec { xi}} _ {j},}$

сондай-ақ

${ displaystyle { vec {S}} (n) = sum _ {j = 1} ^ {8} b_ {j} K_ {j} ^ {n} { vec { xi}} _ {j} .}$

Енді, содан бері ${ displaystyle | K_ {1} |> | K_ {j} |}$ барлығына ${ displaystyle j> 1}$, бұл анық

${ displaystyle lim _ {n to infty} { vec {S}} (n) = b_ {1} K_ {1} ^ {n} { vec { xi}} _ {1} = b_ {1} 3 ^ {n} { vec { xi}} _ {1}.}$

Осылайша, біз басқадай басқатырғыштар үшін келесі асимптотикалық қатынасты алдық

${ displaystyle lim _ {n to infty} S_ {SID} (n) = s3 ^ {n}}$

фактормен с келесі кесте арқылы берілген:

Әдебиеттер тізімі