Ќазаќ мемлекеттік ќыздар педагогика институты
жүктеу/скачать 1,32 Mb.
|
аза стан Республикасыны Білім ж не ылым министрлігі аза мем
| Рекурентті тізбектерді өңдеу
U(1), …, U(K) тізбегінің алғашқы К-сыншы мүшелері берілген болса, онда U(1), U(2), …,U(N) тізбегінің элементтері К ретті рекурентті тізбекті құрайды делінеді, ал N>К үшін U(N)=F(U(N-1),…,U(N-K)) теңдеуi орындалады. Мұндағы Ғ – К аргументтің қандай да бір функциясы. Екінші ретті пекуррентті тізбекті белгілі мысалы Фибоначчи сан тізбегі болып табылады., оның U(1)=U(2)=1, ал N>2 үшін U(N)=U(N-1)+U(N-2). Бірінші ретті рекуррентті тізбектің мысалы – а санынан квадрат түбірді Ньютон әдісі бойынша есептеуге арналған тізбек: U(1)=a+1, ал N>1 үшін U(N)=0.5*(U(N-1)+a/U(N-1)). Рекурентті тізбектерге қатысты төмендегідей есептер қойылады. Тізбектің N-ші элементін есептеу. Берілген G(U(N), U(N-),…,U(N-K)) логикалық функциясының ең кіші нөмірлі элементін есептеу. Бұл екі есепті шығару үшін тізбектің К+1 элементін жадыда сақтау қажет. К1=К+1. Онда К+1 элементті жадыға сақтауға арналған массив былай сипатталады: VAR T:ARRAY[1..k1] OF <тізбектегі элементтер типі> тізбектегі есептелген элементтердің соңғысы T[K+1] элементінде сақталады. Екі есепті шығаруда екі негізгі кезеңге бөлінеді:бастапқы шар және тізбек бойынша орындау. Бастапқы шартты төмендегідей жазуға болады: T[2]:=U(1);…;T[K+1]:=U(K); Ал тізбек болйынша бір элементке алға қарай орындауда: FOR I:=1 TO K DO T[I]:=T[I+1]; T[K+1]:=F(T[K],…,T[1]); Т массивінің әрбір элементі біріншісінен бастап, мәнді келесі элменттен бастап алады. Соңғы элементтен мәнін алғаннан кейін, F рекурренттік формуласын қолдана отырып, жаңа мән қабылдайды. Келесі есептеуге әсер етпейтіндіктен T[1]-дің ескі мәні қажет болмай қалады. 1 және 2-есептер тізбек бойынша болатын орын ауыстырулар қаншалықты орындалатынымен ажыратылады. 1-есепте жылжу N-K-ға тең, өйткені T[K+1] алғашқы шарттан кейін тізбектің К-элементін сақтайды, бірақ N-элементті алу керек. Жылжуды қайталау үшін FOR қайталануын пайдаланған ыңғайлы: FOR J:=K+1 TO N DO BEGIN FOR I:=1 TO K DO T[I]:=T[I+1]; T[K+1]:=F(T[K],…,T[1]); {T[K+1]:=U(J)} END; {T[K+1]:=U(N)} 2-есепте G функциясының мәні ақиқат болған мезеттежылжуды аяқтау қажет. Бұл жағдайда жылжуды қайталау үшін REPEAT-UNTIL қайталануын пайдаланған ыңғайлы: REPEAT FOR I:=1 TO K DO T[I]:=T[I+1]; T[K+1]:=F(T[K],…,T[1]); UNTIL G(T[K+1],…,T[1]); 1-есепті шығаруға мысал ретінде N-Фибоначчи санын есептеу функциясын қарастырайық: Function FIBONACHI_SANY (N:integer):integer; { N – ізделінді элементтің нөмірі, ол N>0 деп есептелінеді} Var I,J:integer; T:ARRAY[1..3] OF INTEGER; Begin {бастапқы шарт} T2:=1; T3:=1 {жылжуды қайталау} FOR J:=3 TO N DO Begin FOR I:=1 TO 2 DO T[I]:=T[I+1]; T[3]:=T[2]+T[1]; END; FIBONACHI_SANY:=T[3]; END; Рекурентті тізбек айтарлықтай үлкен болмаса, массивті пайдаланбай-ақ, тізбек элементтері сақталған айнымалыларды жеке атаулармен бөліп көрсетуге болады. Бұл жағдайда тізбек бойынша жылжуда FOR қайталануы К меншіктеулермен алмастырылады. 2-есепті шығару мысалы ретінде А санынан берілген дәлдікпен квадрат түбірді есептейтін функциянвы қарастырайық. ТЕК айнымалысы түбірге ағымдағы жуықтатылған мәнді, ал АР айнымалысы алдыңғы мәнді сақтау үшін пайдаланылсын. ABS(U(N)-U(N-1)) Function KVADRAT_TUBIR (A,KATE:REAL):REAL; { A – Түбір алынатын сан, KATE- қажеттті жуықтау дәлдігі} Var TEK,AP:REAL; {ТЕК – квадрат түбірге жуықтатылатын ағымдағы мән, АР – алдыңғы жуықтау} Begin {бастапқы шарт} TEK:=A+1; {жылжуды қайталау} REPEAT AP:=TEK; TEK:=0.5*(AP+A/AP) UNTIL ABS(TEK-AP) END; Рекуррентті тізбекті анықтаубіршама жалпылауға мүмкіндік береді, егер элементтерді нөмірлесе, оны 1-ден бастау міндет емес, F функциясының N-нен тәуелділігін алуға болады. Мұндай тізбектермен жұмыс істеуде бастапқы нөмір меншіктелетін бастапқы шартты қосу керек және әрбір жылжуда тізбек бойынша нөмірді 1-ге арттырып отыру қажет. Мұндай жалпылаудан тек 2-цикл ғана аздапкүрделенеді. Сол нөмірлі элементті есептеуде FOR циклы бәрін орындайтындықтан 1-цикл өзгермейді. Енді осы айтылғанды мысалмен түсіндірейік. Кейбір есептер рекуррентті тізбектерді өңдеуге келтіріледі. С коэффициентпен берілген массивтегі М дәрежелі көпмүшеліктің мәнін есептеу қажет болсын: VAR C:ARRAY[0..M] OF REAL; X айнымалысының мәнін берілген деп есептейміз. Көпмүшеліктің мәнін есептеу үшін Горнер схемасы пайдаланылатыны белгілі. Көпмүшелікті мына түрде жазуға болады: (…(C[0]·X+C[1]) ·X+…+C[M-1]) ·X+C[M]. U(N) бірінші ретті рекуррентті тізбекті төмендегідей анықтайық: U(0)=C[0], U(N)=U(N-1) ·X+ C[N], 1≤N≤M (бұл жағдайда тізбек элементтерін 0-ден бастап нөмірлеген ыңғайлы). U(M) көпмүшеліктің мәні екенін көрсету қиын емес. Жоғарыда келтірілген әдістемені U(M)-ді табу үшін қолданамыз. Бұл тізбек элементтерін нөмірі бойынша есептеу есебі. Егер жалпы схема бойынша қарастырсақ, SAP және STEK екі айнымалыларын енгізу керек және жылжуды төмендегідей жүргіземіз: FOR J:=1 TOM DO BEGIN SAP:=STEK; STEK:=SAP*X+C[J]; END; Мұнда SAP айнымалысының қажет емес екені көрінеді, өйткені STEK айнымалысының жаңа мәнін есептеуде осы айнымалының алдыңғы мәнін пайдалануға болады. Сөйтіп, элемент нөмірі бойынша бірінші ретті рекуррентті тізбекті есептеуде бір айнымалыны пайдалану жеткілікті, нәтиже сол айнымалыға меншіктеліп отырады. Берілген шартты қанағаттандыратын тізбектің элементін есептеу есебі үшін де ақиқат болып табылады, егер G функциясы тек U(N)-нен тәуелді болатын болса. Сондай-ақ, циклдың алдындағы бастапқы шартты тізбектің бірінші элементі басқаларымен тең есептелінетіндей етіп, ұйымдастыруға болады. Нәтижесінде төмендегідей функцияны аламыз: CONST M=…, TYPE KOEF=ARRAY[0..M] OF REAL; … Function GORNER (VAR C:KOEF; X:REAL):REAL; { С коэффициентті массивпен, Х айнымалысының мәні берілген, бір айнымалыдан тәуелді көпмүшеліктің мәнін Горнер схемасы бойынша есептейтін функция} Var S:REAL; J:INTEGER; { S айнымалысына көпмүшеліктің мәні есептеледі} Begin S:=0; FOR J:=1 TO M DO S:=S*X+C[J]; GORNER:=S; END; Рекуррентті қатынастармен жұмыс істеу техникасы сондай-ақ, тізбектерді өңдеу программаларын құруда, әсіресе, жалпы формула бойынша әрбір мүшені есептемей, алдыңғының мәнін біле отырып, кезекті элементті алуда тиімді. Қатардың қосындысын табу есебін қарастырайық. 1+1/1!+1/2!+…+1/N!+… (бұл е санын есептеуге арналған қатар). Қосындыны табуды кезекті қосылғыш алдын-ала берілген КАТЕ шамасынан кіші болғанша жүргізу керек. Әрине, әрбір N үшін N!-ды қайтадан есептеу керек. Қосындыны табу уақыты C1m2 өрнегімен беріледі, мұндағы m - қатардың қосынды табылған мүшелерінің саны. Егер N!=N·(N-1)! қатынасын пайдалансақ, есептеуді жеделдетуге болады. Қатардың қосылғыштарын бірінші ретті рекуррентті тізбектің көмегімен анықтауға болады: U(0)=1, U(N)=U(N-1)/N,N>0. Енді U(N) Function CHISLO_E (KATE:REAL):REAL; Var N:INTEGER; U,S:REAL; { N – қосылғыш нөмірі; U – кезекті қосылғыш; S – алғашқы N элементтің қосындысы} Begin N:=0; U:=1; S:=U; REPEAT N:=N+1; U:=U/N; {U:=1/N!} S:=S+U; {S=1+1/1!+…+1/N!} UNTIL U END; Қосынды берілген шартты қанағаттандыратын рекурентті тізбектің элементін есептеумен бірге жүргізіледі. Сонымен, уақыттың көп бөлігін машина циклды, алдыңғы кезекте ішкі циклды орындауға жұмсайды. Берілген қайталану саны бойынша циклды орындау уақыты циклға кіретін әрекеттер санына тәуелді. Цикл қаншалықты қарапайым болса, яғни әрекеттер саны қанша аз болса, соншалықты программа жылдам орындалады. Сондықтан, программаның ішкі циклын жеңілдету шараларын қолдану қажет. Сонымен қатар, программаның жұмыс уақытына негізгі әсер ететін таңдалған алгоритм болып табылады. Алдымен, есепті шығарудың мүмкін болатын алгоритмдерін талдау қажет, оның ішінен ең жылдам орындалатын алгоритмін таңдап, ондағы ішкі циклды анықтап, ішкі циклды жеңілдетуге әрекет жасау қажет. Әдебиеттер: Негізгі әдебиеттер: 8 [189-214], 3 [60-75] Қосымша әдебиеттер: 3[52-58] – б, 6[64-69] – б. Бақылау сұрақтары Алгоритмдегі циклдың дұрыстығын қалай тексеруге болады? Қосынды алгоритмінде қандай жағдайда келесі қосылғышты есептеу үшін реккурентті формуланы пайдаланған жөн? Қосындының алгоритмін сипаттаған кезде қосылғыштарды жалпы формуламен есептеуге бола ма? Рекурентті тізбектерге қатысты қандай есептер қойылады? Алгоритмдегі циклдың дұрыстығын қалай тексеруге болады? жүктеу/скачать 1,32 Mb. Достарыңызбен бөлісу:
|