В.Б. Алекссев - Сложные алгоритмы (1132790), страница 7
Текст из файла (страница 7)
tAK, W ZADA^AH SORTIROWKI I POISKA MY NE OBSUVDALI SPOSOBPREDSTAWLENIQ \LEMENTOW ai I NE RAZRE[ALI IZU^ATX I PREOBRAZOWYWATX OTDELXNYE ^ASTI \TIH PREDSTAWLENIJ. eSLI MY HOTIM POLU^ATXUTWERVDENIQ TIPA "DLQ L@BYH ALGORITMOW" WOOB]E, TO MY DOLVNYPRINQTX KAKU@-NIBUDX UNIWERSALXNU@ MODELX ALGORITMOW.
oDNOJ IZTAKIH MODELEJ QWLQETSQ MA[INA tX@RINGAmA[INA tX@RINGA M IMEET POTENCIALXNO BESKONE^NU@ LENTU,RAZDELENNU@ NA Q^EJKI, I GOLOWKU, KOTORAQ W KAVDYJ (DISKRETNYJ)MOMENT WREMENI t = 0; 1; 2; : : : OBOZREWAET ROWNO ODNU Q^EJKU. zADANONEKOTOROE KONE^NOE MNOVESTWO SOSTOQNIJ Q = fq0; q1; : : : ; ql g, I MA[INAW KAVDYJ MOMENT WREMENI NAHODITSQ ROWNO W 1 IZ \TIH SOSTOQNIJ.zADAN KONE^NYJ LENTO^NYJ (RABO^IJ) ALFAWIT C = fc0; c1; : : : ; cm g, GDEc0 = | PUSTOJ SIMWOL, I W KAVDYJ MOMENT WREMENI W KAVDOJ Q^EJKENAHODITSQ ROWNO 1 SIMWOL IZ ALFAWITA C , PRI^EM BUDEM S^ITATX, ^TOSIMWOLY, OTLI^NYE OT , NAHODQTSQ LI[X W KONE^NOM ^ISLE Q^EEK. mA[INA M HARAKTERIZUETSQ EE PROGRAMMOJ, KOTORAQ PREDSTAWLQET SOBOJKONE^NYJ NABOR KOMAND WIDA: ciqj ! ck qr T , GDE ci 2 C , ck 2 C , qj 2 Q,qr 2 Q, T 2 L; R; S .
nA KAVDOM TAKTE MA[INA M RABOTAET SLEDU@]IMOBRAZOM. eSLI GOLOWKA OBOZREWAET Q^EJKU, W KOTOROJ NAHODITSQ SIMWOLcj , M NAHODITSQ W SOSTOQNII qj I W PROGRAMME MA[INY M ESTX KOMANDAciqj ! ck qr T , TO SIMWOL W OBOZREWAEMOJ Q^EJKE ZAMENQETSQ NA ck ,MA[INA PEREHODIT W SOSTOQNIE qr I GOLOWKA OSTAETSQ NA MESTE, ESLIT = S , ILI SDWIGAETSQ NA 1 Q^EJKU WPRAWO ILI WLEWO, ESLI T = R ILIT = L. dALEE MA[INA PEREHODIT K SLEDU@]EMU TAKTU I POWTORQET \TOTPROCESS.
eSLI VE W PROGRAMME MA[INY NET KOMANDY, W LEWOJ ^ASTIKOTOROJ STOIT PARA ciqj , TO MA[INA OSTANAWLIWAETSQ.mY BUDEM RASSMATRIWATX TOLXKO DETERMINIROWANNYE MA[INYtX@RINGA, TO ESTX TAKIE, U KOTORYH W PROGRAMME KAVDAQ PARA ci qjWSTRE^AETSQ W LEWYH ^ASTQH KOMAND NE BOLEE ODNOGO RAZA. w \TOM SLU^AEKAVDYJ [AG MA[INY OPREDELQETSQ ODNOZNA^NO.oPREDELENIE. eSLI A - ALFAWIT, TO ^EREZ A BUDEM OBOZNA^ATXMNOVESTWO WSEH (KONE^NYH) SLOW W ALFAWITE A.
pUSTX C - LENTO^NYJALFAWIT MA[INY M , C0 = C n fg I PUSTX ZADAN NEKOTORYJ WHODNOJ ALFAWIT A, TAKOJ, ^TO A C0. tOGDA MY BUDEM S^ITATX, ^TOMA[INA M OSU]ESTWLQET PREOBRAZOWANIE 'M : A ! C0 [ fg, KOTOROE OPREDELQETSQ SLEDU@]IM OBRAZOM (ZDESX W fg TRAKTUETSQ KAKNEOPREDELENNOSTX). pUSTX ZADANO NEKOTOROE SLOWO a = a1a2 : : : an 2 A..35rAZMESTIM SIMWOLY \TOGO SLOWA W POSLEDOWATELXNYE Q^EJKI LENTY, A WOSTALXNYE Q^EJKI POMESTIM , POMESTIM GOLOWKU NA Q^EJKU, W KOTOROJSTOIT a1, USTANOWIM MA[INU W NA^ALXNOE SOSTOQNIE q1 I NA^NEM RABOTUMA[INY. eSLI POSLE \TOGO MA[INA M BUDET RABOTATX BESKONE^NO DOLGO, TO S^ITAEM, ^TO 'M (a1a2 : : : an) = .
eSLI MA[INA M OSTANOWITSQI GOLOWKA BUDET OBOZREWATX , TO TAKVE S^ITAEM, ^TO 'M (a) = .eSLI VE M OSTANOWITSQ I OBOZREWAEMYJ SIMWOL OTLI^EN OT , TORASSMOTRIM MAKSIMALXNU@ SWQZNU@ (SOSTOQ]U@ IZ POSLEDOWATELXNYHQ^EEK) OBLASTX LENTY, KOTORAQ SODERVIT OBOZREWAEMU@ Q^EJKU I NESODERVIT . pUSTX W Q^EJKAH \TOJ OBLASTI ZAPISANO SLOWO b = b1b2 : : : bk(\TA OBLASTX, O^EWIDNO, KONE^NA). tOGDA S^ITAEM, ^TO 'M (a) = b.tEZIStX@RINGA. dLQ L@BOGO ALGORITMI^ESKOGO PREOBRAZOWANIQ ' : A ! C0 [ fg SU]ESTWUET MA[INA tX@RINGA M OSU]ESTWLQ@]AQ PREOBRAZOWANIE 'rASPOZNAWANIE SIMMETRIIpUSTX A = f0; 1g I SLOWO a = a1a2 : : : an 2 A. bUDEM GOWORITX,^TO SLOWO a SIMMETRI^NO, ESLI a1 = an; a2 = an;1 I T.D. pUSTX MA[INAtX@RINGA M IMEET LENTO^NYJ ALFAWIT C I MNOVESTWO SOSTOQNIJ Q,PRI^EM A C I q0 2 Q, q00 2 Q. bUDEM GOWORITX, ^TO M RASPOZNAETSIMMETRI@, ESLI DLQ L@BOGO WHODNOGO SLOWA a 2 A MA[INA M WSEGDAOSTANAWLIWAETSQ I PRI \TOM NAHODITSQ W SOSTOQNII q0 , ESLI a SIMMETRI^NO, ILI q00, ESLI a NE SIMMETRI^NO.uTWERVDENIE.
sU]ESTWUET MA[INA tX@RINGA M KOTORAQRASPOZNAET SIMMETRI@ I DELAET PRI L@BOM WHODNOM SLOWE DLINY nNE BOLEE cn2 [AGOW GDE c NEKOTORAQ KONSTANTAdOKAZATELXSTWO dOSTATO^NO POSTROITX MA[INU M , KOTORAQ ZAPOMINAET I STIRAET PERWYJ SIMWOL, PEREGONQET GOLOWKU W KONEC SLOWAI SRAWNIWAET SIMWOL W PAMQTI S POSLEDNIM SIMWOLOM SLOWA. eSLIONI NE SOWPADA@T, TO M PEREHODIT W SOSTOQNIE q00 I OSTANAWLIWAETSQ.eSLI SOWPADA@T, TO ONA STIRAET POSLEDNIJ SIMWOL, WOZWRA]AETSQ WNA^ALO SLOWA I POWTORQET PROCESS. eSLI SLOWO POLNOSTX@ STERTO, TOM PEREHODIT W SOSTOQNIE q0 I OSTANAWLIWAETSQ. pRI \TOM GOLOWKA NEBOLEE n RAZ PROBEGAET PO SLOWU DLINY NE BOLEE n. pO\TOMU OB]EE ^ISLO[AGOW ESTX O(n2).-,-.,,-..36oB]IE UTWERVDENIQ O SLOVNOSTI ZADA^rASSMOTRIM WSE MA[INY tX@RINGA, IME@]IE W LENTO^NOM ALFAWITE SIMWOLY I j. pUSTX Z + = f0g[ N , GDE N - MNOVESTWO NATURALXNYH ^ISEL.
bUDEM PREDSTAWLQTX ^ISLO k 2 Z + NA LENTE MA[INY W WIDEKODA jj : : : j , GDE KOLI^ESTWO j RAWNO k + 1 (OSTALXNYE SIMWOLYNA LENTE ). nABOR (k1; k2; : : : ; kn ) BUDEM PREDSTAWLQTX W WIDE KODA jj : : : j jj : : : j : : : jj : : : j ,GDE W PERWOM MASSIWE k1 +1 SIMWOLOW j,WO WTOROM k2 + 1 I T.D. pRIMENQQ MA[INU M K KODU ^ISLA ILI NABORA,BUDEM POME]ATX GOLOWKU NA SAMYJ PERWYJ SIMWOL j I USTANAWLIWATXMA[INU M W EE NA^ALXNOE SOSTOQNIE q1.oPREDELENIE. dLQ L@BOJ MA[INY tX@RINGA M I L@BOGO NATURALXNOGO ^ISLA n BUDEM S^ITATX, ^TO MA[INA M WY^ISLQET FUNKCI@f (x1; x2; : : : ; xn) : (Z + )n ! Z + [ fg KOTORAQ OPREDELQETSQ SLEDU@]IMOBRAZOM.
pRIMENIM MA[INU M K KODU NABORA (a1; a2; : : : ; an). eSLI MOSTANOWITSQ I POSLE OSTANOWKI NA LENTE BUDET TOLXKO KOD NEKOTOROGO^ISLA b 2 Z + , TO f (a1; a2; : : : ; an) = b. wO WSEH OSTALXNYH SLU^AQHf (a1; a2; : : : ; an) = (NEOPREDELENNOSTX).oPREDELENIE. fUNKCIQ f (x1; x2; : : : ; xn) : (Z +)n ! Z + [ fg NAZYWAETSQ WY^ISLIMOJ, ESLI SU]ESTWUET MA[INA tX@RINGA M , KOTORAQEE WY^ISLQET.oPREDELENIE. gOWORQT, ^TO MA[INA M PRAWILXNO WY^ISLQET FUNKCI@ f (x1; x2; : : : ; xn), ESLI NA^INAQ RABOTU S KODA NABORA(a1; : : : ; an) MA[INA M W TOM SLU^AE, KOGDA f (a1; a2; : : : ; an) NE OPREDELENO, OBQZATELXNO RABOTAET BESKONE^NO DOLGO, A W TOM SLU^AE, KOGDAf (a1; a2; : : : ; an) = b, MA[INA OSTANAWLIWAETSQ, NA LENTE OSTAETSQ KOD bI GOLOWKA MA[INY OBOZREWAET SAMYJ LEWYJ SIMWOL j.uTWERVDENIE. eSLI f (x1; x2; : : : ; xn) WY^ISLIMA TO SU]ESTWUET MA[INA tX@RINGA M KOTORAQ EE WY^ISLQET PRAWILXNOdOKAZATELXSTWO SM., NAPRIMER, W [ ].oPREDELENIE.
wS@DU OPREDELENNYE WY^ISLIMYE FUNKCII MYBUDEM NAZYWATX OB]EREKURSIWNYMI FUNKCIQMI. (oBY^NO OB]EREKURSIWNYE FUNKCII OPREDELQ@T INA^E, NO DANNOE OPREDELENIE \KWIWALENTNO OBY^NOMU; SM., NAPRIMER, [ ]).fUNKCIQ, WY^ISLQEMAQ MA[INOJ M , NE IZMENITSQ, ESLI PROIZWOLXNO PEREIMENOWATX WSE SIMWOLY LENTO^NOGO ALFAWITA, KROME Ij, I WSE SOSTOQNIQ, OSTAWLQQ NA^ALXNOE SOSTOQNIE NA^ALXNYM (KONE^NO, RAZNYE SIMWOLY DOLVNY PEREIMENOWYWATXSQ W RAZNYE). pO\TOMUMY BUDEM S^ITATX, ^TO ESTX BESKONE^NYJ FIKSIROWANNYJ ALFAWITfc1 = ; c2 =j; c3; c4; : : : g, IZ KOTOROGO BERETSQ LENTO^NYJ ALFAWIT,,-.37MA[INY M , I BESKONE^NYJ FIKSIROWANNYJ ALFAWIT fq1; q2; : : : g, IZKOTOROGO BERUTSQ SOSTOQNIQ MA[INY M . bUDEM ZAPISYWATX INDEKSYW STROKU POSLE c ILI q, PREDSTAWLQQ IH W DWOI^NOJ SISTEME S^ISLENIQ(NAPRIMER, c6 = c110).
pROGRAMMU MA[INY M BUDEM ZAPISYWATX W WIDEPOSLEDOWATELXNOSTI WSEH EE KOMAND ciqj ;! ck qr T , RAZDELENNYH TO^KOJS ZAPQTOJ. tOGDA PROGRAMMA L@BOJ MA[INY BUDET PREDSTAWLQTX SOBOJSLOWO W ALFAWITE D = f; j; c; q; 0; 1; ;!; R; L; S; ; g.tEOREMA. sU]ESTWUET ALGORITM NUMERACII WSEH MA[IN tX@RINGA IZ UKAZANNOGO WY[E SEMEJSTWA TAKOJ ^TO DLQ WOSSTANOWLENIQPROGRAMMY PO EE NOMERU TAKVE SU]ESTWUET ALGORITMdOKAZATELXSTWO bUDEM S^ITATX, ^TO SIMWOLY ALFAWITA D UPORQDO^ENY (NAPRIMER, TAK, KAK \TO SDELANO WY[E).
tOGDA WSE SLOWAODNOJ DLINY k MOVNO UPORQDO^ITX LEKSIGRAFI^ESKI (KAK W SLOWARE).bUDEM TEPERX PROSMATRIWATX WSE SLOWA W ALFAWITE D W SOOTWETSTWII SIH DLINOJ: SNA^ALA DLINY 1, ZATEM DLINY 2 I T.D. sLOWA ODNOJ DLINY kPROSMATRIWAEM W LEKSIKOGRAFI^ESKOM PORQDKE. dLQ KAVDOGO SLOWA PRIMENQEM ALGORITM, KOTORYJ PROWERQET, QWLQETSQ LI \TO SLOWO PRAWILXNO POSTROENNOJ PROGRAMMOJ NEKOTOROJ DETERMINIROWANNOJ MA[INYtX@RINGA.
eSLI DA, TO PRIPISYWAEM \TOJ PROGRAMME O^EREDNOJ NOMER(NA^INAQ S 0). pRI \TOM L@BOJ MA[INE tX@RINGA (IZ RASSMATRIWAEMOGO SEMEJSTWA) PO EE PROGRAMME BUDET (ALGORITMI^NO) SOPOSTAWLQTXSQNEKOTORYJ NOMER. tOT VE PEREBOR OSU]ESTWLQEM, ESLI ZADAN NOMER ITREBUETSQ NAJTI SOOTWETSTWU@]U@ \TOMU NOMERU PROGRAMMU.zAFIKSIRUEM DALEE NEKOTORU@ NUMERACI@ MA[IN tX@RINGAi ! Mi, UDOWLETWORQ@]U@ TEOREME. tAK KAK MA[INA Mi WY^ISLQETNEKOTORU@ FUNKCI@ f (x), TO MY POLU^AEM TAKVE NEKOTORU@ NUMERACI@ WSEH WY^ISLIMYH FUNKCIJ ODNOJ PEREMENNOJ i ;! 'i(x). zAMETIM,^TO PRI \TOM MOVET BYTX 'i(x) 'j (x) PRI i =6 j , POSKOLXKU RAZNYEMA[INY tX@RINGA MOGUT WY^ISLQTX ODNU I TU VE FUNKCI@ f (x).dOKAVEM TEPERX TEOREMY O TOM, ^TO SU]ESTWU@T SKOLX UGODNOSLOVNO WY^ISLIMYE FUNKCII.tEOREMA. dLQ L@BOJ OB]EREKURSIWNOJ FUNKCII T (x) SU]ESTWUET OB]EREKURSIWNAQ FUNKCIQ f (x) PRINIMA@]AQ TOLXKO ZNA^ENIQI I TAKAQ ^TO DLQ L@BOJ MA[INY tX@RINGA Mi WY^ISLQ@]EJ f (x)HOTQ BY PRI ODNOM x WYPOLNQETSQ NERAWENSTWO ti(x) > T (x) GDE ti (x)WREMQ RABOTY MA[INY Mi NA WHODE x TO^NEE NA KODE ^ISLA xzAME^ANIE.
oTMETIM, ^TO FUNKCIQ T (x) MOVET RASTI O^ENXBYSTRO. nAPRIMER, FUNKCII g1(n) = n, g2(n) = nn, g3(n) = ng2(n),: : : , gm+1 (n) = ngm(n) , : : : OB]EREKURSIWNY. tAKVE OB]EREKURSIWNA I-,..-,12,0,,,|(38,).FUNKCIQ h(n) = gn(n), KOTORAQ RASTET S ASTRONOMI^ESKOJ SKOROSTX@.dOKAZATELXSTWO dLQ WSEH i 2 Z + I x 2 Z + PUSTX ti(x) OBOZNA^AETWREMQ RABOTY MA[INY S NOMEROM i, ESLI WHODOM QWLQETSQ KOD ^ISLA x(ti(x) MOVET BYTX I BESKONE^NYM), I PUSTX 'i(x) OBOZNA^AET FUNKCI@,WY^ISLQEMU@ MA[INOJ Mi. oPREDELIM FUNKCI@ f (x) SLEDU@]IM OBRAZOM:(f (x) = 1; ESLI tx(x) 6 T (x) I 'x (x) = 0;(12)0; INA^E:uTWERVDENIE. fUNKCIQ f (x) WY^ISLIMAQ A SLEDOWATELXNO OB]EREKURSIWNAQdOKAZATELXSTWO oPI[EM ALGORITM WY^ISLENIQ f (x).
pO ZADANNOMU x 2 Z + NAHODIM PROGRAMMU MA[INY Mx (SM. TEOREMU). wY^ISLQEM T (x) (TAK KAK T (x) - OB]EREKURSIWNA, TO DLQ \TOGO SU]ESTWUETALGORITM). iMEQ PROGRAMMU MA[INY Mx, MODELIRUEM EE RABOTU W TE^ENIE T (x) TAKTOW, WZQW W KA^ESTWE WHODNOGO SLOWA KOD ^ISLA x. eSLI ZAT (x) TAKTOW MA[INA OSTANOWITSQ I REZULXTATOM BUDET KOD ^ISLA 0, TOWYDAEM OTWET 1, INA^E WYDAEM OTWET 0. mODELIRUQ RABOTU MA[INY, MYMOVEM RABOTATX TOLXKO S TOJ ^ASTX@ LENTY, NA KOTOROJ ZAPISYWAETSQWHODNOE SLOWO, A TAKVE KOTORAQ POSE]AETSQ GOLOWKOJ WO WREMQ RABOTY.tOGDA NA KAVDOM [AGE NAM DOSTATO^NO HRANITX LI[X KONE^NYJ KUSOKLENTY, ^TO POZWOLQET OPREDELITX SODERVIMOE LENTY I POSLE OSTANOWAMA[INY. sLEDOWATELXNO, WESX PROCESS WY^ISLENIQ f (x) ALGORITMI^EN.w SOOTWETSTWII S TEZISOM tX@RINGA SU]ESTWUET MA[INA tX@RINGA,KOTORAQ WY^ISLQET f (x). mY PRIMEM ZDESX \TO UTWERVDENIE, HOTQ DLQOPISANNOJ FUNKCII f (x) MOVNO I QWNO POSTROITX WY^ISLQ@]U@ EEMA[INU tX@RINGA (PRAWDA, DOLGO I GROMOZDKO).pUSTX MA[INA Mi WY^ISLQET f (x), TO ESTX f (x) = 'i(x).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
