КАТЕГОРИЯ:


Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Военное дело- (14632) Высокие технологии- (1363) География- (913) Геология- (1438) Государство- (451) Демография- (1065) Дом- (47672) Журналистика и СМИ- (912) Изобретательство- (14524) Иностранные языки- (4268) Информатика- (17799) Искусство- (1338) История- (13644) Компьютеры- (11121) Косметика- (55) Кулинария- (373) Культура- (8427) Лингвистика- (374) Литература- (1642) Маркетинг- (23702) Математика- (16968) Машиностроение- (1700) Медицина- (12668) Менеджмент- (24684) Механика- (15423) Науковедение- (506) Образование- (11852) Охрана труда- (3308) Педагогика- (5571) Полиграфия- (1312) Политика- (7869) Право- (5454) Приборостроение- (1369) Программирование- (2801) Производство- (97182) Промышленность- (8706) Психология- (18388) Религия- (3217) Связь- (10668) Сельское хозяйство- (299) Социология- (6455) Спорт- (42831) Строительство- (4793) Торговля- (5050) Транспорт- (2929) Туризм- (1568) Физика- (3942) Философия- (17015) Финансы- (26596) Химия- (22929) Экология- (12095) Экономика- (9961) Электроника- (8441) Электротехника- (4623) Энергетика- (12629) Юриспруденция- (1492) Ядерная техника- (1748) Arhitektura- (3434) Astronomiya- (809) Biologiya- (7483) Biotehnologii- (1457) Военни бизнесмен (14632) Висока technologies- (1363) Geografiya- (913) Geologiya- (1438) на държавата (451) Demografiya- ( 1065) Къща- (47672) журналистика и смирен (912) Izobretatelstvo- (14524) външен >(4268) Informatika- (17799) Iskusstvo- (1338) историята е (13644) Компютри- (11,121) Kosmetika- (55) Kulinariya- (373) културата е (8427) Lingvistika- (374) Literatura- (1642) маркетинг-(23702) математиците на (16968) Механична инженерно (1700) медицина-(12668) Management- (24684) Mehanika- (15423) Naukovedenie- (506) образователна (11852) truda- сигурност (3308) Pedagogika- (5571) Poligrafiya- (1312) Politika- (7869) Лево- (5454) Priborostroenie- (1369) Programmirovanie- (2801) производствено (97 182 ) индустрия- (8706) Psihologiya- (18388) Religiya- (3217) Svyaz (10668) Agriculture- (299) Sotsiologiya- (6455) на (42831) спортист строително (4793) Torgovlya- (5050) транспорт ( 2929) Turizm- (1568) физик (3942) Filosofiya- (17015) Finansy- (26596) химия (22929) Ekologiya- (12095) Ekonomika- (9961) Electronics- (8441) Elektrotehnika- (4623) Мощност инженерно ( 12629) Yurisprudentsiya- (1492) ядрена technics- (1748)

рекурсия

Семантични модели Prologue

В Prolog, обикновено се използват два семантичен модел: декларативна и процедурно. Семантични модели са проектирани, за да обясни смисъла на програмата.

В декларативен модел обсъжда връзката е определено в програмата. Не е важно на този модел предлага програма за последователност и условия в това правило.

Процедурно модел счита правилото като поредица от стъпки, които трябва да бъдат успешно завършени, за да съответства на съотношението дадено в правилата за колекторни.

Много от предложенията, с предиката заглавието със същото име и същия брой аргументи, се третират като процедура. За процедурно модел е важна последователността, в която писмени оферти и условия в изречения.

Когато пишете програма в Prolog изглежда логично първо да се разгледа декларативни семантиката, обаче, и по процесуално един не трябва да се забравя, особено когато програмата не работи или не работи съвсем както се очаква.

Имайте предвид, че в някои случаи използването на подрязване може да се промени декларативен смисъл.

За разлика от традиционните езици за програмиране, в която основното средство за организиране на повтарящи се действия са цикли в пролога на тази процедура за търсене се използват, за да се върне (намаление на цените) и рекурсия. Намаление на цените ви позволява да получите много решения в същия брой на програмата, и позволява използването на рекурсия в дефиницията на предикат от него. В проучването на рекурсия често напомня на случая на Барон Мюнхаузен, който се дръпна за косата от блатото. За натиск говорим повече в шестата лекция, и това трябва да се проучи рекурсията. Имайте предвид, че рекурсия се използва не само в Prolog, но в конвенционалните императивни езици за програмиране. Но за Prolog, за разлика от императивни езици, рекурсия е основен техники за програмиране. Нещо повече, Prolog ви позволява да определите рекурсивни структури от данни. Работата с тях ще бъде посветена на серия от лекции на този курс.

За да започне изучаването на рекурсия в пролога на класически пример. Нека приемем, че на базата от знания е съвкупност от факти, описващи родство на хора чрез връзката ", за да бъде майка." родител на предикат има два аргумента. Посоченият името на родителя, като втори по първия си аргумент - името на детето. Ние искаме да създадем една връзка ", за да бъде предшественик на" използване на предикатното родител.

За един човек е бил предшественик на другия човек, че е необходимо, че е било негов родител или е майка на още един от неговите предци.



Пишем тази идея:

прародител (Ancestor, потомък): -

Родител (Ancestor, потомък).

/ * * Ancestor е родител /

прародител (Ancestor, потомък): -

Родител (Ancestor, Person)

прародител (Лице, потомък).

/ * Ancestor е прародител на родител * /

Отношението е прародител на преходен затварянето на връзката родител, това означава, че е най-малко отношение, включително и нагласите на родителите и като собственост на преходност. Припомнете си, че връзката е преходен ако за всички двойки (А, В) и (В, С), в това отношение, двойката (А, С) е в това отношение. Очевидно е, че прародител на съотношение съдържа съотношение на родителя. Това следва от първото изречение, което казва, че всеки родител е предшественик. Второто изречение предвижда преходен.

По аналогия с математическа индукция, която е малко като рекурсия, всяко рекурсивно процедура трябва да включва основа и стъпка на рекурсия.

Основа рекурсия - предложение, което определя определена първоначална ситуация или ситуацията към момента на прекратяване. Като правило, в това изречение, написано прост случай, при който отговорът е прав, дори и без използването на рекурсия. Така че, в горната процедура, описваща предикат прародител основа на рекурсия е първото правило, което определя, че непосредствените предци на човека са неговите родители. Това изречение често съдържа състоянието, при което излиза от рекурсията или изрезка.

Стъпка рекурсия - това обикновено е в тялото, което е необходимо да съдържа, като под, определено повикване предикат един. Ако искаме да избегнем примка дефиниран предикат не трябва да се използва от същите параметри, които са определени в правилата за хедър. Параметрите трябва да се променят, защото при всяка стъпка, така че в крайна сметка на база натоварване рекурсия или състояние от рекурсия, поставени в това правило. По принцип правилото, че изпълнява стъпка на рекурсия ще изглежда така:

<Наименование дефиниран предикат>: -

[<Sub>]

[<Exit състояние на рекурсия>]

[<Sub>]

<Наименование дефиниран предикат>

[<Sub>].

В някои ситуации, предложения за прилагане на база рекурсия и изречения, описващи стъпка рекурсия, може да има няколко. Това обикновено се случва в сложни случаи, като например, когато се извършва в процеса на изпълнение на стъпка рекурсия действия зависят от изпълнението или неизпълнението на някои условия. Тези задачи ще ни срещнат в следващите глави, когато ние се занимават с обработката на рекурсивни структури от данни. В същата глава, ние ще се занимава основно с случаи на проста рекурсия, когато рекурсивно процедура има една база и една стъпка рекурсия.

Пример. Създаване на предикат, който ще се изчислява на броя на естествената си факторен. Тази задача позволява рекурсивно решение на много езици за програмиране, както и рекурсивно математическо описание:

1! = 1 / * факторен е равна на единица * /

N! = (N-1)! * N / *, за да се изчисли факториел

определен брой, че е необходимо да се изчисли

факторен на един по-малко

и го умножете по оригиналния номер * /

Нека се опитаме да напише еквивалент на изпълнение предикат с математическия определението на предиката:

Всъщност (1,1). / * Факториел е равна на единица * /

Всъщност (N, F): -

N1 = N-1,

Всъщност (N1, F1), / * F1 е равен на броя на факториален

един по-малко от оригинала

номер * /

F = F1 * N. / * Факториел е равен на първоначалния брой

продукт на F1 на огромния брой * /

За съжаление, когато се опитате да се изчисли факториела на всяко положително цяло число от описаните по-горе факт предикат ще стека преливане ( "Stack преливане"). Опитайте се да разберете причината. Например, помислете какво би станало, ако се опитаме да изчислим факториела на три.

Съответният въпрос може да се запише, както следва:

Всъщност (3, X).

Пролог система се опитва да се обедини с гол с глава на първата присъда (факта, (1,1)). Тя не успя, защото числото три не е равно на единство. С цел уеднаквяване с титлата на второ изречение (факта, (N, F)) променливата п е посочено числото три, а променливата X се свързва с променлива F. Това е последвано от опит да се изпълни под, разположен в тялото на правила от ляво на дясно. N1 първи вариабилен означаващ броя една по-малка от стойността на променливата N, след това има две. Задействане на следните под (факт (N1, F1)) води до рекурсивни повикване на предиката, че изчислява факториела, със стойността на променливата N1, равно на две.

Точно както е в случая, че първият аргумент е равен на три, не се случи обединението с главата на първото изречение (уредът не е равно на две). Сравнение с главата на второто правило успява. След това всичко е почти същата, както за променлива N, равно на три. Ние изчисляваме новата N1 стойност, равна на две, без единство, т.е. единство. Пролог отново се опитва да изчисли подцел факта (N1, F1) (обаче, стойността на променливата N1, равна на единство).

По това време, там е сравнение на обективна (факт (1, F1)) със заглавието на първото изречение, и променливата F1 е посочено единица. Пролог система най-накрая успя да се изчисли втората подцел на второто правило, и той отива при изчисляването на третия подводницата (F = F1 * N). Индексът п е равно на две, променливата F1 - единство и продуктът от две единици е две, и следователно, променливата F е посочено две.

Започва обратни рекурсия. След като изчислява факториела на две, системата Prolog е готов да се изчисли факториела на три. За да направите това, се размножават факториела на 02:58. Променливата F е конкретизирана номер шест. Ние имам отговор на въпроса за трите факториелите.

Въпреки това, изчисленията не свършват дотук. Пролог система установи, че обективния факт (1, F1) може да се сравнява не само с титлата от първото изречение, но също така и с правилата на титлата (факт (N, F)). Индексът п е определена единица, и променлива F1 е свързан с променлива, променливата F. След N1 означаващ броя една по-малка от стойността на променливата N, който е нула. Prolog система се опитва да изчисли цел факт (0, F1). Със заглавието на първото изречение (факта, (1,1)), за да съответства на тази цел не може да бъде, защото нула не е равен на една. Но с титлата на второ изречение (факта, (N, F)) има успешно единна цел. Частично N1 става равна на минус един. След това се прави опит да се изчисли като целта на факт (-1, F1) .... След това на факта (-2, F1), фактът, (-3, F1), фактът, (-4, F1), фактът (-5, F1). ...

Този процес ще продължи дотогава, докато притежаването на паметта, запазена за стека. След това програмата ще спре със съобщение, че топчето е пълен.

Защо се случи това? Какво сме направили грешен? Причината е, че първоначалното определение на факториел, който ние използвахме, беше прието, че правилото работи само за естествените числа, която е за положителни числа. Ние също така са настъпили в изхода на програмата в негативната част на цяло число, което е предоставено от формулата, на която е установена процедура ни.

Как мога да се коригира грешката? Имаме две възможности за процедури за корекция.

Можете да проверите броя, за които се прилага правилото е по-голям от един. За устройството ще остане факт, като посочва, че устройството ще бъде факторен единица. Виж, този вариант ще бъде, както следва:

Всъщност (1,1). / * Факториел е равна на единица * /

Всъщност (N, F): -

N> 1, / * Уверете се, че броят им е по-голям от един * /

N1 = N-1,

Всъщност (N1, F1), / * F1 е равен на броя факторните,

един по-малко от оригинала

номер * /

F = F1 * N. / * Факториел е равен на първоначалния брой

продукт на F1 на огромния брой * /

В този случай, цели, въпреки че тя ще предоговаряне факт (1, F1) от заглавната част, и променлива N е конкретизирана единица F и променливата, свързана с променлива F1, първото правило subgoal (N> 1) е невярна. В този процес завършва. Опитите да се изчисли факториела на не-положителни числа, не се случи, процедурата ще работи точно както искахме.

Второто решение на проблема - да се добавят в първото изречение на процедура ампутация. Спомнете си, че се обади прекъсване на захранването води до факта, че процедурата предлага намира под тази, от която е наречена, тя не се счита. И, съответно, след известно цел да бъде в съответствие със заглавието на първото изречение, резитба работата и опит да се обедини мишената с второто изречение на титлата няма да бъде направено. в този случай процедурата ще изглежда така:

Всъщност (1,1): -. / * Stop състояние рекурсия * /

Всъщност (N, F): -

N1 = N-1,

Всъщност (N1, F1), / * F1 е равен на броя факторните,

един по-малко от оригинала

номер * /

F = F1 * N. / * Факториел е равен на първоначалния брой

продукт на F1 на огромния брой * /

Разбира се, от една страна, методът на рекурсия има предимства пред метода на повторение се използва за императивно програмиране езици по-често. Рекурсивни алгоритми обикновено са много по-лесни от логическа гледна точка, отколкото на итерация. Някои алгоритми са удобни, за да го напише рекурсивно.

От друга страна, рекурсия е голям недостатък: тя е най-общо казано, може да не е достатъчно за стека. Всяка рекурсивна покана на предиката в специална стека рамка съхранява всички встъпили променливи, които могат да бъдат необходими. Максималният размер на стека, когато работи MS DOS операционна система само 64 KB. Това е достатъчно, за да се настанят около три до четири хиляди стека рамки (в зависимост от броя и размера на междинните променливи). За по-големи стойности на входа стека не може да бъде достатъчно.

Има, обаче, едно изпълнение на рекурсия, която използва почти толкова RAM като итерация на императивни програмни езици. Този така наречен опашка рекурсия или надясно. За нейното изпълнение рекурсивно дефинирани повикване предикат трябва да бъде последната подцел в тялото на рекурсивно правило, и по време на рекурсивни повикването не трябва да остане листенца (неизпитани алтернативи). Това означава, че под-цели, разположени от лявата страна на рекурсивно дефинирани повикване предикат не трябва да остават никакви неизпитани възможности и процедури, които не трябва да бъдат изречения под рекурсивно правило. Turbo Prolog, върху които ще се съсредоточи в нашия курс, признават опашка рекурсия и елиминира свързаните с това допълнителни разходи. Този процес се нарича опашка-рекурсия оптимизация, или оптимизация на последния разговор.

Пример. Нека се опитаме да приложат факторен изчисление с помощта на опашката рекурсия. За да направите това, вие ще трябва да добавите два допълнителни параметри, които ще бъдат използвани от нас за съхраняване на междинните резултати. Третият параметър е необходима, за да съхраните текущия природен броя, за който се изчислява факториела, четвъртия вариант - да факторен броя съхранява в третия параметър.

Стартирайте факториел, ние ще в първия параметър е равен на броя, за който искате да се изчисли факториела. Третият и четвъртият аргументи са равни на единство. Вторият аргумент след рекурсивни изчисления трябва да бъдат поставени факторен брой съхраняват в първия параметър. Всяка стъпка ще се увеличи с една трета аргумент, на втория аргумент се умножава по новата стойност на третия аргумент. Рекурсия ще трябва да се спре, когато третият аргумент равен на първия и четвъртия аргумент е необходимо натрупаната факториел, който може да бъде поставен в отговор на втория аргумент.

Цялата процедура ще бъде както следва:

fact2 (N, F, Н, F): -. / * Спрете рекурсията, когато третият

аргументът е първият * /

fact2 (N, F, N1, F1): -

N2 = N1 + 1, / * N2 - следващото цяло число

след няколко N1 * /

F2 = F1 * N2, / * F2 - факторен на N2 * /

fact2 (N, F, N2, F2).

/ * Рекурсивен разговор с нов естествен

номер N2 и съответните

Брой факторен F2 * /

Спрете рекурсия може, използвайки прекъсване в основата на рекурсия, както беше направено по-горе, или чрез прибавяне към началото на второто изречение на сравнение N1 с N.

Ако решим, че причина предиката за четири аргументи неудобно, можете да въведете допълнителен две аргумент предикат, който ще се проведе на оригиналния предиката:

factM (N, F): -

fact2 (N, F, 1,1). / * Обадете се на предиката е вече

Началната

стойности * /

Пример. В предишната лекция записахме аналог наложително разклонения с помощта на прекъсване на захранването. Сега пишем с помощта на рекурсия и подрязване, цикъл на изпълнение с предварително условие. Обикновено, този цикъл изглежда така: докато <условие> направя P. Това съответства на описанието на текст ", докато е налице <условие>, за да изпълнява P". В Prolog такава структура може да бъде написано, както следва:

w: -

<Състояние>, р, w

w: -!.

Пример. Друг класически проблем, който има рекурсивно решение е свързано с изчисляването на така наречените числата на Фибоначи. Числата на Фибоначи могат да се определят, както следва: първа и втора цифрите са равни на един, и всеки следващ брой е сумата от предходните две. Съответно, трета номер Фибоначи е равно на две, четвъртият три (сумата на втория брой (един) и третата номер (две)), петият - пет (сума от третата и четвъртата цифри, т.е., две или три), на 6 - осем (сумата от четвъртата и пето, три и пет), и т.н.

Бази рекурсия в този случай две. Първият е да се твърди, че първата Фибоначи брой е равен на една. Втората основа - подобно твърдение за втори номер Фибоначи. Стъпка рекурсия е необичайно, тъй като ще се основава на изчисляването на следващия брой на Фибоначи не само от броя предхождащия го, но по време на предишния предишния брой. Това ще бъде посочено, че за изчисляването на числата на Фибоначи с номер N първо място е необходимо да се изчисли и да добавите до броя на Фибоначи номера N-1 и N-2.

Запишете тези съображения, можете да:

ПИБ (1,1): -!. / * Първо Фибоначи брой е равен на една * /

ПИБ (2,1): -!. / * Второ Фибоначи брой е равен на една * /

ПИБ (N, F): -

N1 = N-1, ПИБ (N1, F1), / * F1 е N-1-ия ден

Фибоначи * /

N2 = N-2, ПИБ (N2, F2), / * F2 е N-2-ти номер

Фибоначи * /

F = F1 + F2. / * N-ти брой на Фибоначи е сумата от

N-1 и N-2-те номера Фибоначи * /

Имайте предвид, стреляйки първите две изречения. Той се използва за спиране на рекурсията, да живеят с по време на рекурсията не се случи от областта на естествените числа (числата на Фибоначи) в границите на отрицателни числа, какъвто беше случаят в нашата първа версия на предиката, която изчислява факториела.

Вместо двете примки на равнината на рязане може да се елиминира чрез добавяне на върха на правилата за изпълнение на етапа на рекурсия, проверка на стойността, която е в първи параметър предикат (N> 2). Тази разпоредба изрично се посочва, че рекурсивно правило се използва за изчисляване на числата на Фибоначи, като се започне с една трета.

Но трябва да кажа, че въпреки че нашето решение беше ясна и прозрачна, доста точно отговаря на определението на числата на Фибоначи, то е, обаче, много неефективно. При изчисляването на Фибоначи номера N-1-ия F1 изчислява всички предишни номера Фибоначи, по-специално, N-2 -Е F2 Фибоначи номер. След това повторно изчислява започвайки 2 N-ти брой на Фибоначи вече е изчислен. Освен това, всички предишни числа на Фибоначи се изчисляват отново. Оказва се, че за изчисляването на числата на Фибоначи, използвайки номера на рекурсивни повиквания ПИБ предикат равен на необходимия брой на Фибоначи.

Да се ​​опитаме да се подобри ефективността на изчисление на числата на Фибоначи. Ние се търси само два Числата на Фибоначи: този, който ние трябва да намерим, и да го следва. Съответно, предиката ще има трети допълнителен аргумент, и в който на следващия брой ще бъде поставен. Основа на рекурсия на двете предложения в един свие, като твърди, че първите две Числата на Фибоначи са равни на един.

Това ще изглежда така предикат:

fib_fast (1,1,1): -!. / * Първите две Числата на Фибоначи са равни

единица * /

fib_fast (N, FN, fn1): -

N1 = N-1, fib_fast (N1, FN_1, FN),

/ * FN_1 е N-1-ия ден

Фибоначи, FN е

N-ти брой на Фибоначи * /

Fn1 = FN + FN_1. / * Fn1 е N + 1-то число на Фибоначи * /

Въпреки fib_fast предикат, който е, за разлика от ПИБ предикатното, Фибоначи номер не е един, а два, той използва много по-малко пространство и стак работи много пъти по-бързо. За да се изчисли броят на Фибоначи N (и заедно с N брой + 1-ия Фибоначи) се нуждаят само N рекурсивни повиквания fib_fast предикат.

Ако ние не се нуждаем от следващия брой на Фибоначи, можете да направите последния аргумент анонимен променлива или да добавите два аргумента предикат е описано по-долу:

fib_fast (N, FN): -

fib_fast (N, FN, _).

Моля, имайте предвид, че ако второто правило на процедура, която описва предикат прародител, с които започнахме запознаване с рекурсия, промяна на реда на подцели, с декларативен гледна точка, по смисъла остава същата:

predok2 (Ancestor, потомък): -

Родител (Ancestor, потомък). / * Ancestor

* Майка /

predok2 (Ancestor, потомък): -

predok2 (мъж дете), / * е прародител

прародител майка * /

Родител (Ancestor, Person).

Процедурата обаче ще бъде променен, за да работа не е така. Ако предикат predok2 на кауза, като се посочват като аргументи имената на хора, един от които е прародител на друг, той успешно се потвърди, че първият човек - прародител на другия. Във всички други случаи (един от аргументите е свободен, човек, чието име е посочено като първи аргумент, не е човешко предшественик, чието име се появява като втори аргумент) всички няма да се случи, както би трябвало. След това предикат ще даде същите отговори като оригиналния прародител на предиката, тя ще премине и в резултат ще покаже, че топчето е пълен.

С оригиналната предикат прародител, че не се случи, тъй като във втория си правило, първата подцел е предизвикателство към суб-майка. В резултат на този под-променлива лице получава като име на стойността на един човек. Ето защо, по време на втората подгрупа повикване прародител (Лице, потомък) променлива човек е вече обвързана. В новата версия на второто правило предикатното започва с под повикване predok2 (мъж дете), с променлива човек в него е безплатно. След като всички алтернативи са изчерпани за значимостта, на свободните променливи от първото изречение на процедурата, в съответствие с целта да бъде обединена с титлата на второто изречение. Free Man променлива ще бъде свързан с променлива прародител и потомък на променлива под - променливи правила потомък удар с глава. Когато се опитате да тече първата подцел правило всичко отново. Този процес ще продължи дотогава, докато не се изчерпва цялото свободно пространство на стека.

Този вид на рекурсия, когато тялото започва да владее рекурсивни разговор определено предикат се нарича левостранна рекурсия. Левостранен рекурсия често се случват описаните проблеми. Ето защо, трябва да се опитате, ако е възможно, да се избегне използването на левостранна рекурсия, в контраст с десностранна или опашка рекурсията.

<== Предишна лекция | На следващата лекция ==>
| рекурсия

; Дата: 05.01.2014; ; Прегледи: 271; Нарушаването на авторските права? ;


Ние ценим Вашето мнение! Беше ли полезна публикуван материал? Да | не



ТЪРСЕНЕ:


Вижте също:



ailback.ru - Edu Doc (2013 - 2017) на година. Тя не е автор на материали, и дава на студентите с безплатно образование и използва!
Page генерирана за: 0.053 сек.