Рекурсивные программы работы со списками

Списки и операции над ними

Большинство рекурсивных алгоритмов связано с работой со списками в силу рекурсивного определения самих структур данных - списков. Для описания этих алгоритмов введем следующую нотацию.

Список – это набор объектов, отделенных друг от друга пробелами и заключенных в квадратные скобки []. Объектами, входящими в такие списки, являются атомы (неделимые элементы) или другие списки.

Атом – это строка буквенно-цифровых символов, не содержащая пробелы.

Для того чтобы отличать атомы от переменных, будем считать, что переменные записываются строчными буквами, а атомы – прописными. Например, [А В С] – список из трех элементов, каждый из которых является атомом. [А [В А [С]]D] – список, в котором на верхнем уровне три элемента: второй элемент сам является списком из трех элементов, в котором третий элемент – это список из одного элемента С.

Для пустого списка, т.е. списка, не содержащего одного элемента, выделяется специальное имя nil.

Наиболее распространенными операциями над списками и атомами являются следующие.

1. Проверка на равенство:

[А В] = [А В] выдает true ,

[А В] = [В А] и во всех других случаях - false.

2. Проверка аtom(х) - применима к любым объектам: атомам или спискам. Выдает true, если х является атомом или пустым списком.

3. Саr(l) применима к любому непустому списку. В качестве результата выдается первый на верхнем уровне элемент этого списка:

Саr([А В С])=А;

Саr([[А В]С D])=[А В];

Саr(nil) и Саr (А) – не определены.

4. Cdr( l) – применима к любому непустому списку l; результатом является список, полученный из списка l путем исключения первого элемента: Cdr([А В С]) = [В С].

5. Соns(х,l) - объединяет элемент х со списком l:

Соns(А, [D E]) = [А D Е];

Соns([А В], [D E]) = [[А В] D E].

Примеры программ работы со списками

1. Программа, определяющая является ли х элементом списка l на верхнем уровне.

member (x,l) =

            if l=nil then false

            else if x=car (l) then true

                  else member (x,cdr (l))

2. Программа, присоединяющая список l₂ в конец списка l₁.

append (l₁, l₂) =

       if l₁ = nil then l₂

       else cons (car (l₁), append (cdr (l₁), l₂))

6.3. Примеры доказательства правильности рекурсивных программ

Для доказательства правильности рекурсивных программ может быть использован метод обобщенной индукции.

Пример 1. Докажем, что функция Аккермана (см. 6.1) конечна.

В качестве множества х выберем множество пар натуральных чисел, упорядоченных в лексикографическом порядке, т.е. (х,у) < ( ), если х < , иначе, когда х = , то должен быть у< . Очевидно, минимальным элементом этого множества будет элемент (0,0).

Для доказательства конечности функции Аккермана необходимо доказать:

1. А(0,0) – конечна.

Действительно, А(0,0) = 1 - конечна.

2. Доказать, что если А(х,y) конечна , то функция А конечна и для .

Докажем это. Для этого предположим, что  конечна  (гипотеза индукции).

Тогда получим:

а) если , то очевидно, что  конечна;

б) если , то  конечна, т.к. ;

в) если , то , где   конечна, т.к. . Следовательно, и  конечна, т.к. .

Пример 2. Рассмотрим рекурсивную программу, вычисляющую пересечение двух упорядоченных списков l₁ и l₂.

Intord (l₁,l₂) =

if l₁=nil then nil

else if l₂=nil then nil

  else if car(l₁) < car(l₂) then intord(cdr (l₁),l₂)

         else if car (l₂) < car (l₁) then intord(l₁, cdr(l₂))

               else cons (car(l₁), intord (cdr(l₁), cdr(l₂)))

Доказательство правильности будем проводить по парам возможных длин списков.

Пусть d₁ = length (l₁), d₂ = length (l₂).

Для доказательства правильности покажем, что:

1. функция работает правильно для наименьшей пары длин, т.е. для ( d₁, d₂)=(0,0). Очевидно, что списки с длинами (0,0) – есть пустые списки, поэтому intord (nil,nil) = nil .

2. покажем, что если  функция работает правильно, то она работает правильно для .

Возможны следующие варианты.

а) l₁ =nil или l₂ =nil. Здесь intord( l₁, l₂)= nil – функция работает правильно.

б) car(l₁)<car(l₂). Здесь intord( l₁, l₂)= intord( cdr( l₁), l₂)), но , т.е. для  функция работает правильно.

в) car ( l₂) < car ( l₁), доказывается аналогично варианту б).

г) car(l₁)=car(l₂). Здесь  выдает объединение элемента, присутствующего в списках l₁ и l₂, с пересечением со списками меньшей длины, для которых функция работает правильно. Следовательно, функция в целом работает правильно.

Тема 7. Отладка программ

⇐ Предыдущая45678910111213Следующая ⇒

Поделиться: