Лекции по информатике (984119), страница 4
Текст из файла (страница 4)
Можно было бы помещать элемент и в конец, по пришлось бы или заводить еще одну переменную-указатель на хвост массива, или вообще ттроходить его от начала до конца,, тем самым нивелировав вс:с преимущества отказа от стандартного распрс",делителя ~а~~~~. Мы ~~д~~. ~сто дстступ к с;писку с~об~д~~~ элсмснтов отрантт тстн и фактически реализует дисциплину стека: все свободные элеметггы равноценны и одинаково пригодны для хранения элементов списка.
Стек свободных элементов позволяет вернуть память так жс быстро, как и получить ее, и к тому же обойтись без лтппних указателей (на конец списка). Таким образом в одном буферном массиве мы организовали эффективный симбиоз различных структур. ,'/ Освобождение занлтпого элемента буфера 1 — >вос1е — >пех1 == 1 — >1,ор; ( Прсдостпастление свободного элеменпта массивп, для очередной компонснгпы списка, (а 1а ттето()) ) гев .
пос1е: — 1. $ор: 1т'(гез.пос1с п1Ц СЬеп 1пзегг: 1.авг Я е1ве Ьеи1п 1.1о1з: 1. то1з .пех1; гез.пос1е .с1а1а: — т; гез.вос1е .пехт: — 1.пос1е; гез . ттос1е".ргеч: — 1.пос1е .ргет'1 гез.ттос)е".ргеч".тзех1: гег.пос1е; 1. пос1е".ргеъ. -- гез.ттос1е; 1. з1хе:-= 1. з1хе + 1; 1взег1:=- гез; ( Возврат итератора на добавленный элемент 3 ГппсС1оп 1Эс1е1е(тсаг 1; 1 1вг, тсаг 1 1гега1от ): !гегагог; айаг гез: 11егаСог; Ьеи1п гез: — 1 азу(1); 1Г(Ес1па1(1, гез)) ФЬеп Бе1ете: — гез е1ве Ьеи1п гез,пос1е с тлюс1е .пех1; гез.пос1е .ргеч: =- т.пос1е .рта; 1.ргет ".вех1:-- гез.вос1е; 1.
з1хе: =- 1. з1хе — 1: злеметипа массива, для очередной кос гпонентпы списка (а 1а гпа11ос()) л 1сега1ог гез ( 1 — >1ор ); Ы (! гез.пос1е) геФпгп 1.аз1(1); 1 — >гор 1 — >гор — >вех$; гев. пос1е — >с1ттга тб гез. пос1е — >ттехг - - 1 — >пос1е; гез.пос1е — >ргег - 1 — >пос1е — =ргеъ-, гез.пос1е — >ргег — >пехт - гез.пос1е; 1 — >пос1е — >ргет - гез.вос1е; 1 — >з1хе-. '1-; ге$пгп гез; 1тсгатог Гуе!ете11.1з1* 1, 1гегатог * т) 1тегатог гез -- 1.азт(1); 1т'1Ес1па111, лхгез)) ге1пгп гез; гез.пос1е -- 1 — >вос1е — >ттехт; гез,вос1е — >ргеч -- 1 — >тюс1е — >ргех; т — >ргет — >пех1 — гез.пос1е; 1 — ' з1хе — —. 1' Осообооюдение занятого элелента буфера ~ >.пос1е".псхс г- 1лор: 1.
1ор: - > . пос1е; ! — >сор . > — >пос1с; > — >пос1е -- 0; геФпгп геа; 1. пос1е: Ш1: Пе1сСс;: Гс>а; епс1; епс1; Функция с>езй'оуО не возвращает память ОС, т. к. массив статический и заранее и навсегда выделен компилятором.
Во избежание повторного ошисючного использования списка все его служебные указатели устанавливаются в п1. Итак, мы перешли от списков на динамических структурах к списками на массиве, переписав всего четыре функции из 11! Исправления коснулись лишь кода, осуществляющего управление памятью. Этот факт наталкивает на мысль, что функцию Сгеа1е(1 можно дополнительно параметризовать распределителем памяти.
В частности, в ВТЕ С вЂ”,+ осе контейнеры (векторы, деки, списки) в качестве аргумента по умолчанию принимают с;тандартный роснределитс.ль памяти, 1аНоса1ог), который, при необходимости, можно всегда заменить. '1 ак аМз11аг по умолчанию является динамическим списком, но его легко превратить в список на массиве при помощи собственного распределителя., например, аналогичного только что описанному. 5.7 Списки общего вида В монографии 163~ рассматриваются нелинейные непоследовательные списки, ортоспис- ки, суперсписки и другие обобщения списковых структур, Интересной разновиднос>тьн> сложных структур данных являются разреженные матрицы 1511. 5.8 Понятие о рекурсии Рекурсивным называется объект, частично состоящий или определяемый с помощью самого себя 1511 Рекурсия встречается не только в математике, но и в реальной жизни. Если встать между двумя зеркалами.
то можно увиде и бесконечную последовательность уменьшающихся отражений исходной картинки 147~. Другой способ получить рекурсивное изооражепие направить видеокамеру на телемонитор, па который приходит картинка 255 ргосес1иге Р>езсгоу(айаг 1: Ь~зс); Ьен1п 1. Ьеас1:=-- ш1; 1. з1ие: - 0; 1.1ор:=- п11; епс1; >соЫ Г>езсгоу(ЕМ~ Ц ( 1 — >Ьеас1 — О; 1 — >з1яе -- О; 1 — >сор ==- 0; с этой камеры. Лучше всех сказал о рекурсии немецкий поэт-сатирик Иоахим Рингель- нац [1]: ...
дар' дгелст Киггп ип И'йгтегп ай, 1ге глго1егит ап Угйггпегп 1гПсп. Рекурсивные (рекуррентные) определения представляют собой мощный математический аппарат [20]. Например, натуральные числа определяются следующим соотношением: ° 0 есть натуральное число (по Бурбаки); ° число, следующее по порядку за натуральным, есть натуральное число. Другой известный пример - - функция факториал п| (и > 0): ° О!=1:, ° п ) 0: п1= п(п — 1)!.
Мощь рекурсивного определения заключается в возможности конструкгпивпо определить (породить) бесконечное множество объектов с помощью небольшого количества правил. 1'1рогра,ммы, как и функции, тоже могут быть описаны рскурсивно. Явных повторений (итераций) рекурсивная программа не содержит. В общем виде рекурсивная программа Р есть некоторая композиция 'Р из множества операторов о', не содержащих Р и самой Р: Р = Р [б', .Р]. Не существует иного способа программной рекурсии, кроме как вызов подпрограммой самой себя по имени.
Такая рекурсия называется прямой. Если программа Р вызывает себя посредством другой ь,, то рекурсия косвсппав. Многоуровневая косвенная рекурсия тоже возможна, но часто неочевидна по тексту программы. Существует более сложная классификация рекурсий: линейная, повторная (концевая, хвостовая), каскадная, удаленная, взаимная [20]. Выполнение рекурсивных вызовов процедур производится аналогично вызову одной процедуры из другой.
Просто здесь все вызываемые процедуры одинаковы. Тем не менее при каждой рекурсивной активации блока процедуры порождается (и распределяется в стеке данных) новый экземпляр множества локальных переменных, включая формальные параметры. Предыдущие одноименные локальные переменные (и формальные параметры) откладываются в стек и тем самым экранируются.
То есть рекурсия это углубляющееся многократное самоприменение, своеобразное повторение, аналогичное циклу. Поскольку мы прибегаем к рекурсии, чтобы постепенно автоматически свести задачу к более простой и даже тривиальной, этот процесс, как и цикл, должен заканчиваться. Для этого внутри рекурсивно-итсрируемого тела Р должно находится некое условие заверпзения рекурсии Л, которое под влиянием операторов тела рано или поздно становится истинным, Поэтому можно представить схему рекурсивных алгоритмов в одной из следующих форм: «...
а этот глист страдал глистами, что мучались глистами сами» (ием,). Перевод Л. Макаровой Р = Ы В СЬеп Р[Я, Р) епс1 Р =— 'Р[Я, 11' В СЬеп Р епс1 ) Завершимость рекурсивного или итерационного процесса обычно имеет место, если он реализует функцию, монотонно убывающую с каждым повторением цикла на конечную величину, так что при достижении функцией некоторого барьерного (порогового) значения условие окончания рекурсии или цикла становится истинным (- В). Конечность декремснта и начального значения функции гарантирует, что повторение закончится за конечное число шагов. При рекурсивном вызове процедур удобно ввести формальный параметр персчислимого типа, по которому и будет отслеживаться и завершаты я рекурсия.
Уменьшая этот параметр арифметически и: — и — 1 или персчислительно ъч; ргсс1(ч ), .мы постепенно редуцируем задачу, снижая ее размерность. Если в качестве условия завершения В использовать п, > О, то окончание по достижении О гарантировано. Наши схемы рекурсии могут быть расписаны следующим образом: 1' Концевая или гавостовая рекурсия?' Р(и) = 1Г п > О СЬеп Р~[с'., Р(п — 1)) епс1 Р(и) = Р[Я, 11' и > О СЬеп Р(и — 1) епс1) Как нас учит практическая теория алгоритмов и вычислимости, надо добиваться не только конечной, но и небольшой повторяемости рекурсивных вычислений.
В противном случае накладные расходы на обслуживание рекурсивных вызовов превысят выигрыш от простого и красивого программирования. Рассмотрим достоинства и недостатки рекурсии на примере вычисления факториала. ФоРмУла 7', с — — (1+ 1) ~с содеРжит инкРемент и индУктивное Умножение. Схема вычисления факториала в наших обозначениях такова: Р ив з 11' В СЬеп Я; Р епс1 где .5' =Ьерп 1:-- 1 + 1: 1: -- 1 * 1 епс1. а В = г' < и,. Сводя вычисление факториала к вычислению факториала предыдущего числа, мы можем соответствующий декремент аргумента вписать прямо в фактические параметры рекурсивной цроцедуры-функции, возвращаемое значение которой заменит нам локальную переменную 1 итеративного варианта.
257 ГппсС1оп 1(1: шСенег): шСенег; 1' г' — 4орма льный параметр, передаваемый по значению, локальный объект процедурьь размесцаемый во временнбм, стеке у Ьенш 11 1 >ОСЬеп 1: — 1 * 1(1 — 1) е1ве 1:-1 епс1; шС 1(шС 1),'~ 1 — формальный паралселпр, иередаваемьис ио значению, локальный объект процедуры, размеисаемый во времесисбм стеке ~ У геСпгп (~ > О) ? 1 * 1(1 — 1): 1: Для того, чтобы проиллюстрировать выполнение, рекурсивной программы вычисления факториала, снабдим ее код сплогппой трассировкой выполнения. Е!иже приведен текст и протокол работы подобной программы для 64-битного целого типа на ЭВМ 1)ЕС Л!р!ъа: ргоигаш Еасг20(!прпС, .опгрш); Суре шСеиег — !пСеиег64; ъаг и: шСеиег: КппсСЕоп Е(1: шСеиег): шСеиег; ъаг геа: шСеиег; ойаеС: шСедег; : шСеиег; Ьеиш ойаеС г:- 2 э (и — !); ъътЬСе1п(' ': ойае$, 'Еппсг!оп Е(', 1: 1, '): Еп1еи г; '); ъъ г1Се1п(' ': ойае1, 'Ьеи!ц'); 1Е ! > О СЬеп Ьер;ш ъът1Се1п(' ': оЕЕаеС, ' !Е ', !: 1, ' > О С!ъеп'); ъът1Се1п(' ': оЕЕаеС, ' Е: - ', 1: 1, ' э Е(', ! — 1: 1, геа г- ! а Е(! — 1); юг!Се(' ': ойаеС, Ког )': — ! с1оъъпСо 1 г1о юг!Се(): 1, ъът1Се1п('1 — '„геа: 1); епс1 е1ее Ьефп жг1Се1п(' ': о(Еае1, ' е!ае'); ъът1Се1пГ„': ойаеС, '„„„Е: -„1'); геа : 1; епс1; геа; ъът1Се1п(' ': ойаег, 'епй ); епг1; Е' Е3 Ьеи1п геас11п(п); Е(п); епс1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
