Пәндердің оқу-әдістемелік кешенінің тізімдемесі
жүктеу/скачать 2.35 Mb.
|
| Практикалық сабақ №8
Тақырыбы: Рекурсия Объекттердiң арасындағы қатынаста тек қана өзара байланыстарын қолдана отырып анықтауға болатын көптеген есептер бар. Мұндай жағдайда пайда болатын ереже, есiңiзде болса рекурсия деп аталады Рекурсияны бiрнеше бағдарламалар мысалдарымен сипаттау арқылы Пролог-Д жүйесімен логикалық та есептеп те құрастыруға мысал келтiремiз. Бiрiншi мысалмен екi сандардың ең үлкен ортақ бөлгiшi (Нод - наибольший общий делитель) есептеу үлгiсі болады. Орындалатын предикат: егер табылган екі саннын (Нод) нод және үш аргумент атымен аталса, a, b сандары және НОД мәні – с болады. Нодтың есептеуiнiң сипаттамалары үшiн төмендегі пiкiрлер қолданылады. Бiрiншiден, егер а=b болса, онда c=a=b, онда Егер b болса, екiншiден, онда b және a-bнiң сандары үшiн Нод есептеуге керек үшiншiден, егер a b болса, онда a және b-aдiң сандары үшiн Нод есептеуге керек. Бұл үш бекiтулер Пролог - Д нодта кәдiмгiдей жазып ала алады; (, b, c) нод - (, b) көбiрек, (b, a-b, c) нод; (, b, c) нод - (b) көбiрек, (a, b-a, c) нод; Егер осыған бiлiм базасына сұрақты берiлсе ?(10, 25, x) нод; Пролог-Д жүйесiнiң жауабы: x=5 Басқа шешiм жоқ Екiншi мысал ретінде тiзбектiң элементтерiнiң есептеуi туралы есепте қаралады: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...... , фибоначчи тiзбегі сияқты белгiлi. Оның әрбiр элементі келесi ережелермен анықталады: f0=0, f1=1, fn=fn-1+fn-2 Бiрiншi формула тiзбектiң нөлдiк элементiнiң мәнi нөлге тең туралы бекiтуге сәйкес келедi. Мұны айғақты түрде жазып алуға болады: (0, 0) Фиб;. Екiншi жол бекiтуге сәйкес келедi: бiрiншi элемент 1 ге тең. Пролог - Д мұны былай жазуға болады: (1, 1) Фиб;. үшiншi жол рекурсия байланысының жазуы болады: (N, X) Фиб - (N-2, Y) Фиб, (N-1, Z) Фиб (Y, Z, X) қосу; Осы ұсыныстар тiзбектiң элементтерiнiң мәнiн есептелуге мүмкiндiк беретiн Пролог-Д жүйесінің деректер қорлары болады. ?(10, X) Фиб; деген сұраққа Пролог-Д жүйесiнiң жауабы: x=55 Басқа шешiм жоқ Есептi осылайша шешiм жолын маңдай алды шешім жолы деп айтуға болмайды. Fn-2 есептеулерiнен кейiн, fn-1 есептеуiнде де алдыңғы элементті жаңадан есептеуге тура келедi, әйтпесе, оның осы қәзiр есептеліп қойылуы, еш жерде қолданылмайды. N+1 деген Фибоначчи сандарының табылулары үшiн (N+1 ) 2* деген рекурсия айналымы қажет болады. Демек, егер "Фиб" аты бар предикатына үш аргумент мәні өзiне дәлел ретiнде N қосатын болатын трехарный сияқты анықталған және N-1 басқа бiлiм базасына тiзбектiң элементтерi өтсе, алайда, бұдан құтылуға болады. Мұндай бiлiм базалары Пролог-Д аудармасының нәтижесiнде пайда болады. 1. тiзбектiң 0-шi элементi бұл 0, ал элемент (-1) анықталмаған. (0, x, 0) Фиб;. Екiншi дәлел x-пен белгiленген. X мәні осы жағдайда қай-қайсысы да бола алады. 2. тiзбектiң 1-шi элементi бұл қашан да 1-шi, ал нөлдiк - 0. (1, 0, 1) Фиб;. 3. фибоначчи тiзбектiң мүшесiнің N-шы тiзбектiң элементi, (N-1 ) арқылы анықталады. (N, F, f) Фиб - (N-1, Ф, F) Фиб, (Ф, F, f) қосу;. Осы бiлiм базасына жүгінсек: ?(10, F, f) Фиб;. Пролог-Д жүйесiнiң жауабы: F=55, f=34 Басқа шешiм жоқ Бұл білім базасымен жұмыс жасау кезінде, Фибоначчидың N-шы санын есептеу үшiн бар болғаны N рекурсия айналымдары керек. Пролог-Д жүйелері үшiн рекурсия бағдарламаларымен жұмыс iстегенде байқалатын ерекшелiктер тән. Бұл жағдайда, ұсыныстардың бiлiм базасындағы реттік мәнi болмайды. Алайда бұл төменде айтылған мысалда дәл осылай емес (X ) ата-ана - (Y ) ата-ана, (Y, Z) әке; (жара ) ата-ана; (жара, Петя) әке; (Петя ) ата-ана;. Бiрiншi ұсыныстың басы мақсаттардың бiрінiң "Родитель" атауын иемденеді. Бұл бiлiм базасында жауаптың iздестiруiнің процессiнде бiрiншi тұрған және бiрiншi қолданылатын сөйлем - тереңдетіле iздестiрiлетін белгiлi бір қағида бойынша ереже қолданылады. Бұл жүйе бiлiм базасының тек қана бiрiншi сөйлеміне жүгінеді де және сұраққа жауап ? (Петя ) ата-ана; ешқашан табылмайды. Сонымен бiрге, бiлiм базасының аздаған өзгерiсi, екi сөйлемдегі орындардың орын ауыстыруы, шешiмнiң сәттi iздестiрілуiне алып келедi: (жара ) ата-ана; (X ) ата-ана - (Y ) ата-ана, (Y, X) әке; (жара, Петя) әке; ?(Петя ) ата-ана;. Сөйлемге шектеусіз – қайталап жүгіну төмендегі мысалда шыққандай жақсы тығылғандай болады () жоғары - () төменде; () төменде - () жоғары; (жара, Петя) жоғары; ?(жара Петя) төменде;. Мұндай ахуал топса деп аталады. егер үшiншi ұсыныс бiрiншi орында тұрса, онда қайтадан жүгіну болмайды да жауап табылады. Фибоначчи тiзбектер элементтердiң есептелу шексiз топса бағдарламасы орындалуы көрiнеді. Шындығында, егер сұрақ: ?(0, x, y) Фиб;, онда бiрiншi нәтиже төмендегідей болуы мүмкiн x=_0, y=1 Бұдан әрi келесi шешiмдi iздеуде шексiз топса пайда болса, өйткенi есеп бойынша табылады: (x, y) Фиб, Фиб ......) ...... . Бұл тәрiзді жағдайды бақылау үшiн бiлiм базасының түрлендiрілуi қажет: (N, F, f) Фиб - (N, 1) көбiрек, (N-1, Ф, F) Фиб, (Ф, F, f) қосу;. сонда баламалы шешiмдi iздестiруде сұраққа жауап алғаннан кейiн: ?(0, x, y) Фиб; x=_0, y=1 нәтижесi алынады: Басқа шешiм жоқ. Және тағы бір таза эстетикалық ұсыныс. Егер бiрдей аттары бар ұсыныс бiр жерде орналастырса Пролог-Д бiлiм базасында анық көрiнедi. Салыстырулар үшiн екi бiлiм базасы төменде мысалға келтіріледі: 1. 2. (Таня, Надь) ана; (Таня, Надь) ана; (X, Y) әже - (X, Z) ана, (домалай Надь) ана; (Z, Y) ана, (X, Y) әже - (X, Z) ана, (домалай Надь) ана; (Z, Y) ана;. жүктеу/скачать 2.35 Mb. Достарыңызбен бөлісу:
|