Пәндердің оқу-әдістемелік кешенінің тізімдемесі
Тақырып №9: Пролог жүйесінде есептеулер жүргізу. Рекурсия
жүктеу/скачать 2.35 Mb.
|
| Тақырып №9: Пролог жүйесінде есептеулер жүргізу. Рекурсия.
Рекурсия негізінде циклді ұйымдастыру. Факториалды есептеу. Басқа программалау тілінде қайталанбалы әрекеттер цикл көмегімен орындалса, Пролог тілінде қайтарымы бар іздеу процедурасы (откат) және рекурсия арқылы жүзеге асырылады. Откат программаға қойылған бір сұраққа көптеген шешімдер алуға мүмкіндік береді. Ал, рекурсия анықтау, жауап іздеу процесінде предикаттың өзін қолданады. Мысалы, барон Мюнхаузеннің өзін-өзі шашынан тартып батпақтан шығаруы рекурсияға мысал бола алады. Сонымен қатар, Пролог мәліметтердің рекурсивтік құрылымын анықтауға мүмкідік береді. Ата-ана қатынасы арқылы туысқандықты көрсететін программада ата-ана предикаты 2 аргументтен тұрады: 1. ата-ана аты; 2. баласының аты Ата-ана предикатын қолданып, ата-бабасы, арғы атасы қатынасын алу керек болсын. Бір адам екінші адамның ата-бабасы болуы үшін, ол оның ата-анасы болуы немесе ата-анасының ата-анасы болуы шарт. Сонда программа мына түрде жазылады: Ата_баба (ата_баба, ұрпақ);-ата_ана (ата_баба, ұрпақ) Ата_ана (ата_баба, ұрпақ): - Ата_баба (адам_ ұрпақ) Кез-келген рекурсивті процедурада құрамына базис пен рекурсия қадамы кіреді. Рекурсия базисі қайсыбір алғашқы жағдайды не аяқталған мерзімдегі жағдайды анықтайтын сөйлем. Бұл сөйлемде жауабы рекурсияны қолданбай-ақ, бірден алынатын қайсыбір қарапайым жағдай жазылады. Ата-баба предикаты сипатталған рекурсия базисі бірінші ереже болады. Мұнда адамның ең жақын ата-бабасы – оның ата-анасы болатындығы анықталған. Мұндай ережелер әдетте процесс орындалған соң рекурсиядан шығу және қиып тастауды (тоқтатуды) қамтамасыз ететін шарттан тұрады. Рекурсия қадамы программа денесінде міндетті түрде болатын ереже. Ол ереже негізгі мақсатқа жету жолында қолданылатын ішкі мақсат болады. Ол нақты бір предикатты шақырады. Цикл үздіксіз, шексіз болмауы үшін анықталған ереже тақырыбында, яғни басында сипатталған параметрлерден болмауы керек. Параметрлер әрбір қадамда өзгеріп отыруы тиіс. Бұл рекурсия базисінің нәтижелік қадамда жұмыс істеуіне не рекурсиядан шығуына мүмкіндік береді.Рекурсия қадамын анықтайтын ереже жалпы түрде мына түрде болады: <анықталған предикат аты>: - [<ішкі мақсаттар>], [<рекурсиядан шығу шарты>], [<ішкі мақсаттар>], <анықталатын предикаттар аты>; [<ішкі мақсаттар>] Кейбір жағдайларда рекурсия базисін жүзеге асыратын сөйлемдермен рекурсия қадамы сипатталатын сөйлемдер бірнеше болуы мүмкін. Бір рекурсия базисінен және бір рекурсия қадамынан тұратын программа қарастырайық.. Натурал санның факториалын анықтау керек.Факториалдың математикалық сиапттамасы мына түрде беріледі. 1!=1, n!=(n-1)!+n 1 вариант: Fact (1, 1). /*1-ң факториалы 1-ге тең*/ Fact (N, F):- N1=N-1 fact (N1, F1) /*Ғ1 алдыңғы кіші санның факториалына тең*/ F=F1*N /*алынатын санның факториалы Ғ1-ге сол санның өзін көбейткенге тең*/ МЫСАЛ. 3! Есептеп көрейік. Программаға қойылатын сұрақ Fact (3, х). түрінде болады. Программада сұрақ бірінші сөйлеммен (Fact (1, 1).) салыстырылады, ол нәтиже бермейді, себебі 3 саны 1-ге тең емес. Екінші Fact (N, F) сөйлемінде п айнымалысына 3 саны сәйкес келеді, ал Ғ х айнымалысымен байланыстырылады. Әрі қарай ішкі мақсаттарды орындау әрекеті жүргізіледі.п1 айнымалысы п айнымалысының мәнінен 1-ге кем санға теңестіріледі, яғни 2-ге тең болады. fact (N1, F1) мақсаты орындалып, п1=2 болғандағы факториал есептелінеді, предикат рекурсивті түрде қайта шақырылады. Алғашқы сөйлем 3 санымен салыстырылғандай қайта тексеріледі. 1 саны 2-ге тең болмағандықтан сөйлем басы жүзеге асырылмайды да, екінші сөйлем сәтті орындалады. Әрі қарай әрекет қайталанады, п1 мәнін 1-ге кемітеді, яғни 1-ге тең болады да жаңа факториал мәні есептелінеді. Келесі қадамда fact (1, F1) сәйкес болады. Пролог прпограмма екінші ереженің екінші ішкі мақсатын жүзеге асырған соң F=F1*N үшінші ішкі мақсатын орындауға кіріседі. N айнымалысы 2-ге тең, Ғ1 айнымалысы 1-ге тең, олардың көбейтіндісі 2-ге, яғни Ғ айнымалысы 2-ге тең болады. Содан соң рекурсияның кері қадамы басталады. 2!-ды есептеген соң 3!-ды есептейді, ол үшін 2! Мәнін 3-ке көбейту керек, Ғ айнымалысы 6-ға тең болады. Сонымен 3! Анықталады. Бірақ программа тоқтап қалмайды, есептеу жалғаса береді. Программа fact (1, F1) мақсаты бірінші сөйлем басымен ғана емес Fact (N, F) ережесінің басымен де салыстырылатынын анықтап N=1, ал Ғ1 Ғ айнымалысымен байланысады. Осындан кейін N1 N-нен кем санға теңестіріледі, яғни 0 болады. Енді fact (0, F1) есептелінеді, бірінші сөйлем орындалмайды, екінші сөйлем жүзеге асырылады. N1 1-ге кем санға меншіктеледі, әрі қарай fact (-1, F1), fact (-2, F1), fact (-3, F1), fact (-4, F1) ...процестері жүргізіледі. Бұл процесс стектегі оперативтік жады таусылғанша жүргізіле береді де стек толғандығы жайлы хабарлама шыққан соң программа жұмысын тоқтатады. Программа қатесі қайда? Неліктен 3!-ды анықтағаннан кейін программа орындалуын тоқтатпады? Программа тек нақты оң сандарға ғана жүргізілуі тиіс, сондықтан шарт енгізуіміз қажет, яғни тексерілеті сан 1-ден үлкен болу керек. Осыған орай программаға өзгеріс енгіземіз. 2 вариант: Fact (1, 1). /*1-ң факториалы 1-ге тең*/ Fact (N, F):- N>1, N1=N-1 fact (N1, F1) /*Ғ1 алдыңғы кіші санның факториалына тең*/ F=F1*N /*алынатын санның факториалы Ғ1-ге сол санның өзін көбейткенге тең*/ Екінші вариантта бірінші сөйлемге қиып алу процедурасын кірістіру қажет. Бұл жағдайда қиып алу әрекетінен кейінгі орналасқан сөйлем орындалмайды, сондықтан алдыңғы сөйлем басының орындалу процесінде қиып тастау орындалса, екінші сөйлем басымен салыстыру, сәйкестендірілу жүзеге асырылмайды. Бұл жағдайдағы программа мына түрде жазылады: Fact (1, 1): - !. Fact (N, F): - N1=N-1, Fact(N1, F1), F=F1*N. Бақылау сұрақтары Пролог жүйесінде есептеулер жүргізу қалай ұйымдастырылады? Рекурсия деген не? Мысал келтіріңіз. Рекурсия базисі мен қадамы деген не? Неліктен Пролог программасының аяқталуы стекке тәуелді? Қарастырылған факториалды анықтау мысалдарының қандай айырмашылығы бар? жүктеу/скачать 2.35 Mb. Достарыңызбен бөлісу:
|