PDF-лекции (1121253), страница 7
Текст из файла (страница 7)
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). w^ASTNOSTI 'i (i) = f (i) I ZNA^IT OPREDELENO. dOPUSTIM, ^TO ti(i) 6 T (i).tOGDA PO OPREDELENI@ f (x) POLU^AEM: ESLI 'i (i) = 0, TO f (i) = 1, A ESLI'i(i) =6 0, TO f (i) = 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
