Ќазаќ мемлекеттік ќыздар педагогика институты
жүктеу/скачать 1,32 Mb.
|
- Бұл бет үшін навигация:
- Рекурсия
мән := Pсоңы Көмекші алгортимді шақыру командасындағы шынайы операндаларды жазу ережесі Шынайы операндалар көмекші алгоритмнің жазылуындағы сәйкес операндалармен төмендегідей сипаттамалары бойынша сәйкес келуі тиіс: типі (нақ, бүт, нат, лит), түрі (скаляр немесе таб), міндеті (арг,нәт). Шынайы операнда да таб түрінде индекс мәні, яғни кестенің өлшемі көмекші алгоритмнің жазылуындағы кестенің өлшемімен сәйкес келуі тиіс. Енді функцияны табуляциялау мысалын қарастырайық. Есептің қойылысы: y=f(x) функциясын [a,b] аралығында h қадаммен табуляциялау. Табуляция деп функцияның мәнін есептеу кестесін айтады. Мәндер кестесі әдетте функцияның графигін тұрғызу үшін немесе басқа мақсатта функция күрделі аналитикалық өрнекпен берілген жағдайда x-тің y –тен тәуелділігін ашу үшін пайдаланылады. Табуляция қадамы h кестені тағайындауда анықталады. Табуляция алгоритмінің циклдық болатыны белгілі. Алдымен х аргументіне а мәнін меншіктеп функцияның мәнін есептейміз, одан кейін аргументті h қадамға арттырамыз. Бұл процесс аргументтің мәні кесіндінің екінші ұшындағы b –ның мәнінен артқанша жалғасады. x>b теңсіздігінің орнына x>b+h/2 теңсіздігін тексеру керек. Дөңгелектеу барысындағы қателіктің әсерін ескермеу үшін орындалады. Табуляцияның нәтижесін екі жиын арқылы көрсетеміз: x1,x2,….,xn – аргумент үшін y1,y2,….yn – функция үшін Мұндағы n – жиындағы элементтер мөлшері, формуласымен анықталады. [ ] - бүтін бөлік. Әдетте керісінше орындалады: N - кесіндідегі нүктелер мөлшері оған шектік нүктелер кіреді. Табуляция үшін табуляция қадамы формуласымен анықталады. Алгоритмнің сөзбен жазылуы Аргументтер: A,b,h Нәтижелер: N,x1,x2….xn, y1,y2,….yn Аралық шамалар: i - негізгі индекс; t – функция аргументі 1. Басы 2. 3. i:=1 4. t:=a 5. xi=t 6. yi=f(t) 7. t:=t+h 8. i:=i+1 9.егер t Енді осы мысалды функцияны пайдаланып, алгоритмін жазайық. Алг ТАБФУНК (нат n ,нақ a,b,h, нақ таб X[1:n],Y[1:n]) Арг n, a,b Нәт X,Y,h Басы Нақ t,R,E; нат i H:=(b-a)/(n-1); R:=b+h/2; i:=1; t:=a әзір t X[i]:=t Функция ( t,F) Y[i]:=F; i:=i+1 Цс Соңы Алг ФУНК (нақ x,y) Аргx Нәт y Басы Y:=(3-x)/(8+x*x) Соңы РекурсияРекурсия ұғымы. Рекурсия деп көмекші алгоритм ретінде алгоритмнің өзін-өзі тура немесе жанама түрде (басқа процедуралар арқылы) шақыруын айтамыз. Әдетте рекурсия едәуір қиын тақырыптарға жатады. Мысалы, tg(x) функциясы tg(x/2) арқылы өрнектеледі, бірақ бұл шексіз рекурсия. Функцияның рекурсивті анықталуының классикалық мысалы- факториал: алг бүт факт (бүт N) арг N нәт F басы егер N=0 онда мән:=1 әйтпесе мән:=N*F(N-1) бітті соңы Егер шақырудың орнына «команданың орнына қою» әдісін қарастыратын болсақ, онда мынадай тізбек аламыз: Ғ(3)=3*F(2)=3*(2*F(1))=3*(2*(1*F(0)))= 3*(2*(1))=3*(2)=2 Солдан оңға қарай оқимыз. Орындалу әрекеті жақшамен көрсетілген. Мұндағы қиындық көбейтуді есептеуде оң жақтағы функция көбейткішін есептегенше, кейінге қалдырылатындығында. Бұдан да айқынырақ тәсіл - ұлғаймалы параметрлі рекурсивті функциялар. Әдістің мақсаты – функцияны формуладан шығару, амалдарды кейінге қалдырудан құтылу. Бұл программалау тілдерінде алгоритмді орындауды жеңілдетеді. Сонымен, факториалды былай есептеуге болады: алг бүт ҒР (бүт N, R) басы егер N =0 онда мән:=R ! өзін шақырудың соңы әйтпесе мән:=FP(N-1,R*N) ! шақыруға дейінгі көбейту бітті соңы Енді әрекеттер кейінге қалдырылмайды (солдан оңға қарай оқимыз): Ғ(3,1) =Ғ(2,3*1) =Ғ(1,2*3) =Ғ(0,6) =6. Қорланатын параметрлер әдісінде цикл инвариантымен аса маңызды ұқсастық бар: N аргумент пен R қорлану коэффициенті сәйкес өзгереді. Рекурсия алгоритм тексіндегі тек өзін шақырумен шектеліп келді, сондықтан циклға ұқсас болып келді. Алгоритмнің өзін-өзі шақыру жүйесі бұтақты құрайтын нағызғы рекурсияны көрсетуге болады. Мұны түсіндіру үшін белгілі есепті алып, рекурсиялық жолмен шешіп көрейік. Циклды пайдаланбай, кесте элементтерінің қосындысын есептейік (цикл олимпиадалық есептерде шектелуі мүмкін). Ол үшін кестені бір элементтен қалғанша теңдей бөліктерге бөліп болғаннан кейін ғана қосу амалын орындайды. Дәлірек айтсақ, кесте теңдей екіге бөлінеді, әрқайсысы төрт элементтен; бөліктердің әрқайсысы тағы да екіге бөлінеді, әр бөлік екі элементтен тұрады; екі элементтен тұратын әр бөлікті тағы да екіге бөлеміз, әр бөлікте бір элементтен қалады; бір элементтен тұратын әр бөлік ары қарай бөлінбейді. алг нақ қосынды (нақ L, P) арг !нақ таб А[1:N] нәт !R - A[L]-дан A[Р]-ға дейінгі элементтер қосындысы басы бүт С егер L = P онда мән:= A[L]! әйтпесе С:= ІNT(L+P)/2 мән:= қосынды(L,C)+қосынды(C+1,P) бітті соңы Рекурсивті алгоритмнің құрылуын былай талқылауға болады: рекурсия шексіз болмас үшін өзін-өзі шақыру тоқталатындай шарт қажет. Келтірілген мысалдағы мұндай шарт – кесте бір ғана элементтен тұрады, оны ары қарай бөлуге келмейді. Өзін-өзі шақыру аргументтің шектік мәндерін енгізуі тиіс. жүктеу/скачать 1,32 Mb. Достарыңызбен бөлісу:
|