Структуры данных и алгоритмы

In[1]:= 2+2 (  Shift+Enter  )
 Out[1]= 4

 In[2]:=	FullForm[a+b c-d+1]
 Out[2]//FullForm= 	Plus[1, a, Times[b, c], Times[-1, d]]

 In[4]:=	expr = cons[1, cons[2, cons[3, nil]]];
{FullForm[{1, 2, 3}], FullForm[expr]}
 Out[5]= 	{List[1, 2, 3], cons[1, cons[2, cons[3, nil]]]}

 In[6]:=	u = RandomInteger[10];
v := RandomInteger[10]
{u, u, u, u, u}
{v, v, v, v, v}
 Out[8]= 	{1, 1, 1, 1, 1}
 Out[9]= 	{8, 3, 4, 1, 3}

Значение переменной u вычисляется и присваивается ей сразу, после этого оно не изменяется. Значение переменной v вычисляется в момент вызова.

Для определения функций применяются оба вида присваиваний. Почти всюду далее будет использоваться отсроченное присваивание. Например, функцию $$f(x) = x^2 + 1$$ можно определить следующим образом:

 In[10]:= f[x_] := x\^2 + 1
f[3]
 Out[12]= 10

Конструкции вида f[x_, y_, ...] := g[x, y, ...] называют правилами преобразования выражений. Знак подчеркивания (_) обозначает шаблонное выражение, которое может быть заменено произвольным значением. Выражение x_ обозначает шаблон с присвоенным ему именем x. Оно применяется для передачи объекта внутри функциональных конструкций. В правой части переменные используются без знака подчеркивания. Когда в коде встретится выражение, которое сопоставляется с левой частью, оно будет заменено только что вычисленным значением правой части.

Если для определения функции f используется несколько правил, то для вычисления значения выражения f[expr] применяется последнее из правил с одинаковой левой частью:

In[13]:= f[0] := 0
f[x_] := x + 1
f[x_] := x - 1
f[0] := 5
{f[2], f[1], f[0], f[-1], f[a]}
 Out[17]= {1, 0, 5, - 2, - 1 + a}

Более частное определение правила предшествует более общему. Например, ниже для вычисления g[0] используется первое правило, а не второе; если правила поменять местами, то результат не изменится:

 In[18]:= g[0] := 0
g[x_] := 1/x
{g[2], g[1], g[0], g[-1]}
 Out[20]= {1/2, 1, 0, -1}

Для условного задания функций используются встроенные функции If и Which. Например, рассмотрим функции

$$h(x)=\begin{cases} \log_2(x), x>0\\ 0 x \le 0 \end {cases}\\ sng(x)=\begin{cases} -1, x>0\\ 0, x = 0\\ 1, x > 0 \end {cases}\\$$

Функция If соответствует конструкции "если …, то …, иначе …". С ее помощью функцию h можно определить следующим образом:

 In[21]:= h[x_] := If[x > 0, Log[2, x], 0]
{h[8], h[4], h[2], h[0], h[-2]}
 Out[22]= {3, 2, 1, 0, 0}

Функция Which является обобщением функции If. Она может содержать произвольное число условных выражений. Используем ее для определения функции sgn:

In[23]:= sgn[x_] = Which[x>0, 1, x==0, 0, x<0, -1];
{sgn[-3], sgn[0], sgn[3]}
 Out[24]= {-1, 0, 1}

Отменить определение функций и очистить переменные можно с помощью функции Clear:

In[25]:=Clear[f, g];
{f[1], g[1]}
 Out[26]= {f[1], g[1]}

Рассмотрим функцию вычисления k-го члена последовательности Фибоначчи 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … Вместе с шаблоном укажем тип переменной: значение функции будет вычисляться только для целых положительных значений аргумента. Сначала определим функцию следующим образом:

 In[27]:= f[1] = f[2] = 1;
f[k_Integer?Positive] := f[k - 1] + f[k - 2]
{f[2], f[3], f[8], f[9], f[10]}
f[0]
 Out[29]= {1, 2, 21, 34, 55}
 Out[30]= f[0]

В этом случае для некоторых запросов, например f[50], система может прерывать вычисления из-за превышения временных ограничений.

Определение функции Fibonacci, которое указано ниже, приводит к существенному сокращению рекурсивных вызовов. В этом определении используется вспомогательная функция g, два последних аргумента которой хранят два соседних члена последовательности:

In[31]:= fibonacci[k_Integer?Positive] := g[k, 0, 1]
g[0, m_, _] := m
g[k_, m_, n_] := g[k - 1, n, m + n]
{fibonacci[8], fibonacci[9], fibonacci[10]}
fibonacci[144]
 Out[34]= {21, 34, 55} 
 Out[35]= 555 565 404 224 292 694 404 015 791 808

Более быстрое вычисление значений функции Фибоначчи можно получить, если использовать ее первое определение, но при этом запоминать каждое вычисленное значение:

In[36]:= fib[1] = fib[2] = 1;
fib[n_Integer?Positive]:=fib[n]=fib[n-1]+fib[n-2] 
fib[200]
 Out[38]=280 571 172 992 510 140 037 611 932 413 038 677 189 525

Более подробное введение в определение и использование функций в языке Wolfram содержится в [3, 12].

Результаты вычислений сохраняются во время работы с программой - вычислительной сессии. По умолчанию сессия начинается при открытии программы и заканчивается при ее закрытии. Можно прекратить сессию и начать другую с помощью команды меню Evaluation -> Restart Session. В этом случае все вычисления можно будет произвести заново.

Линейные структуры данных. Список

Рассмотрим модели типов данных список, стек, очередь и дек, которые представляют линейные, или одномерные структуры данных.

Для представления линейной структуры данных в виде терма будет использоваться два функциональных символа - 0-арный символ nil для обозначения пустой структуры и бинарный символ cons для обозначения непустой. Например, список [1, 2, 3] представляется в виде cons(1, cons(2, cons(3, nil))).

Откроем в облаке Wolfram новый файл и введем код:

 In[1]:= 	x = cons[1, cons[2, cons[3, nil]]];
TreeForm[x] (  Shift+Enter  )

Представление данного терма в виде дерева показано на рис. 6.2.

(рис 6.2) Представление линейной структуры данных в виде дерева

Список - это конечная последовательность элементов, которая записывается в виде [1, 2, 3] для непустого списка или [] для пустого (в языке Wolfram для списков используются фигурные скобки).

Элементы списка нумеруются с нуля, слева направо. Например, если список имеет вид ["Иванов", "Петров", "Сидоров"], то его элементом с индексом 2 является "Сидоров". Первый элемент списка называется его головой, а список последующих элементов - его хвостом. Для приведенного выше списка головой является "Иванов", а хвостом - список ["Петров", "Сидоров"].

Длиной списка называется число его элементов.

Первый аргумент h терма cons(h, t) обозначает элемент - голову списка, второй аргумент t обозначает список, который является хвостом исходного списка. Пустой список обозначается nil.

В данной лекции не будут использоваться встроенные операции над списками, которые имеются в языке Wolfram. Все операции над списками, представленными в виде описанных выше термов, моделируются в виде функций, которые определяются с помощью правил вида Elhs := rhs.

Определим следующие операции над списками: возвращение головы и хвоста списка, вычисление длины списка, возвращение элемента по индексу и индекса элемента, вставка элемента и соединение списков.

Пусть Z - множество, которому принадлежат элементы списка, и L - множество списков с элементами из Z. Операции возвращения головы списка и его хвоста определяются в виде функций head: L -> Z и tail: L -> L следующим образом:

head(cons(h, t)) = h;
tail(cons(h, t)) = t,

где $$h \in Z, t \in L$$. Областью определения обеих функций является множество непустых списков.

Пример 1. Пусть x = cons(1, cons(2, cons(3, nil))). Тогда

head(x) = 1; 
tail(x) = cons(2, cons(3, nil)).

На языке Wolfram определение этих операций имеет вид:

In[3]:=head[cons[h_, _]] := h
tail[cons[_, t_]] := t
head[x]
tail[x]
 Out[5]=1
 Out[6]= cons[2, cons[3, nil]]

Пусть $$N_0$$ - множество неотрицательных целых чисел.

Функцию вычисления длины списка $$len: L \to N_0$$ можно определить с помощью следующего рекурсивного правила: длина пустого списка равна 0, а длина непустого списка на единицу больше длины его хвоста. Определение функции len имеет вид:

len(nil) = 0;
len(cons(h, t)) = 1 + len(t),

где $$h \in Z, t \in L$$. Но практическая реализация функции len в декларативных языках программирования приводит к большому расходу памяти. Поэтому для определения операции вычисления длины списка обычно используют две функции - основную функцию length: $$L \to N_0$$ и вспомогательную $$auxlength: L \times N_0 \to N_0$$. Они определяются следующим образом:

length(p) = auxlength(p, 0);
auxlength(nil, n) = n; 
auxlength(cons(h, t), n) = auxlength(t, n + 1),

где $$h \in Z, p, t \in L, n \in N_0$$. Реализация таких функций в декларативных языках соответствует итерации в императивных языках.

Пример 2. Для списка x = cons(1, cons(2, cons(3, nil))) имеем:

length(x) = auxlength(x, 0) = auxlength(cons(2, cons(3, nil)), 1) = = auxlength(cons(3, nil), 2) = auxlength(nil, 3) = 3.

На языке Wolfram код выглядит следующим образом:

In[7]:=len[nil] := 0 
len[cons[_, t_]] := 1 + len[t] 
len[x]
 Out[9]= 3

 In[10]:= length[p_] := auxlength[p, 0]
auxlength[nil, n_] := n
auxlength[cons[_, t_], n_] := auxlength[t, n + 1]
length[x]
 Out[13]= 3

В дальнейшем для определения операций над структурами данных с помощью правил будет сразу использоваться код на языке Wolfram.

Функцию возвращения элемента по индексу nth можно определить следующим образом:

In[14]:= nth[cons[h_, _], 0] := h
nth[cons[_, t_], n_] := nth[t, n - 1]
nth[x, 2]
 Out[16]= 3

Если элемента в списке не существует, то возвращается выражение:

In[17]:= {nth[x, 4], nth[x, -1]}
 Out[17]= {nth[nil, 1], nth[nil, -4]} 

Для определения функции index возвращения индекса элемента в списке используем вспомогательную функцию auxind:

In[18]:= index[p_, a_] := auxind[p, a, 0]
auxind[cons[h_, _], h_, n_] := n
auxind[cons[_, t_], a_, n_] := auxind[t, a, n + 1]
index[x, 3]
index[x, 5]
 Out[21]= 2
 Out[22]= auxind[nil, 5, 3] 

Следующие две функции соответствуют операциям вставки элемента в список на заданную позицию n. Функция setnth заменяет элемент списка с индексом n новым элементом, функция insert "сдвигает" последующие элементы:

In[23]:= setnth[cons[_, t_], a_, 0] := cons[a, t]
setnth[cons[h_,t_],a_,n_]:=cons[h,setnth[t,a,n-1]]
setnth[x, 5, 2]
 Out[25]= cons[1, cons[2, cons[5, nil]]]

 In[26]:= insert[p_, a_, 0] := cons[a, p]
insert[cons[h_,t_],a_,n_]:=cons[h,insert[t,a,n-1]]
insert[x, 5, 2]
 Out[28]= cons[1, cons[2, cons[5, cons[3, nil]]]] 

Определение данных функций отличается первым правилом: если элемент вставляется на позицию 0, то он становится головой нового списка, а его хвостом в первом случае становится хвост старого списка, а во втором случае - сам исходный список.

Наконец, определим операцию соединения двух списков. Соединением пустого списка со вторым списком является второй список. Соединением непустого списка со вторым списком является список, голова которого совпадает с головой первого списка, а хвост является соединением хвоста первого списка со вторым списком.

Определение функции append соединения списков имеет вид:

In[29]:= 	append[nil, p_] := p
append[cons[h_, p_], q_] := cons[h, append[p, q]]
y = cons[3, cons[6, cons[5, cons[4, nil]]]];
append[x, y]
 Out[32]= cons[1, cons[2, cons[3, cons[3, cons[6, cons[5, cons[4, nil]]]]]]] 

Стек

Стек (англ. stack) - это тип данных, в котором элементы организованы по принципу "последний вошел - первый вышел" (англ. LIFO - last in - first out). В нем имеются операции добавления верхнего элемента в стек, возвращения верхнего элемента стека и удаления верхнего элемента из стека.

Иллюстрацией стека является стопка тарелок ( рис. 6.3), на которую можно положить еще одну тарелку или можно убрать верхнюю тарелку; посмотреть можно также только на верхнюю тарелку.

(рис 6.3) Стопка тарелок как иллюстрация стека

Если стек имеет вид [1, 2, 3], то в результате добавления в него элемента 5 получится стек [1, 2, 3, 5]. Если удалить из него верхний элемент, т. е. элемент 5, то опять получится стек [1, 2, 3].

Ниже определяются функция push добавления элемента в стек, функция top, которая возвращает верхний элемент стека, и функция pop возращения стека без верхнего элемента:

In[33]:= push[nil, a_] := cons[a, nil]
push[cons[h_, t_], a_] := cons[h, push[t, a]]
push[x, 5]
 Out[35]= cons[1, cons[2, cons[3, cons[5, nil]]]]

 In[36]:= top[cons[h_, nil]] := h
top[cons[_, t_]] := top[t]
top[x]
 Out[38]= 3

 In[39]:= pop[cons[_, nil]] := nil
pop[cons[h_, t_]] := cons[h, pop[t]]
pop[x]
 Out[41]= cons[1, cons[2, nil]] 

Очередь

Очередь (англ. queue) - это тип данных, в котором элементы организуются по принципу "первый пришел - первый вышел" (англ. FIFO - first in - first out). Она отличается от стека тем, что новый элемент добавляется с одной стороны - в конец очереди, а забирается с другой стороны - из начала очереди. Примером очереди является очередь на кассу в супермаркете.

Например, пусть [1, 2, 3] - очередь. Если добавить элемент 5 в конец очереди, то получится очередь [5, 1, 2, 3]. Первым элементом очереди является 3. После удаления первого элемента из очереди [5, 1, 2, 3] останется очередь [5, 1, 2].

Функция addRear добавления элемента в конец очереди определяется следующим образом:

In[42]:= addRear[p_, a_] := cons[a, p]
addRear[x, 5]
 Out[43]= cons[5, cons[1, cons[2, cons[3, nil]]]]

Первый элемент очереди возвращает функция top, а очередь без первого элемента - функция pop, которые были определены ранее.

Дек

Дек (англ. deque) - это тип данных, который отличается от очереди тем, что в нем можно добавлять элементы как в начало, так и в конец, просматривать как первый, так и последний элемент, и удалять как первый, так и последний элемент. Поэтому дек также называют двухсторонней очередью.

Например, пусть [1, 2, 3] - дек. В результате добавления элемента 5 в начало этого дека, получится дек [1, 2, 3, 5]. В результате добавления элемента 7 в конец второго дека получится дек [7, 1, 2, 3, 5].

Указанные выше операции в виде функций на языке Wolfram были определены ранее (полный список указанных функций для деков определяется также ниже в п. 6.2.4).

Иерархические структуры данных. Деревья

Иерархическая структура данных - это организация данных, в которой элементы связаны отношением частичного порядка. Если пара несовпадающих элементов принадлежит этому отношению, то один из них находится на более высоком уровне, чем другой.

Основным примером иерархической структуры данных является конечное корневое дерево - граф без циклов, один из элементов которого является корнем. Корень образует нулевой уровень дерева. Смежные с корнем вершины образуют первый уровень, они являются потомками корня. Смежные с ними и не принадлежащие предыдущему уровню - второй уровень дерева, и так далее. Вершина a называется потомком смежной с ней вершины b, если номер ее уровня на единицу больше номера уровня вершины b.

Дерево, в котором каждая вершина имеет не более двух потомков, называется бинарным. Для представления бинарного дерева используем 0-арный символ leaf, обозначающий пустое дерево и тернарный символ bin, аргументы которого соответствуют левому поддереву, корню и правому поддереву. С помощью этих символов бинарное дерево, приведенное на рис. 6.4 (a), представляется в виде терма bin(bin(leaf, 1, leaf), 2, bin(leaf, 3, leaf)).

(рис 6.4) Дерево: (a) бинарное; (b) произвольное

Произвольное дерево можно представить в виде терма с бинарным символом tree, первый аргумент которого хранит вершину дерева, а второй - список поддеревьев. Например, дереву, представленному на рис. 6.4 (b), соответствует терм tree(1, cons(tree(2, nil), cons(tree(3, nil), cons(tree(4, nil), nil)))).

Определим операции, которые возвращают корень дерева, левое и правое поддеревья для бинарных деревьев и список поддеревьев для произвольных деревьев, а также операции вычисления числа вершин дерева и списка вершин уровня n дерева.

Используем в программе дерево, приведенное на рис. 6.5 (a).

(рис 6.5) Дерево: (a) бинарное; (b) произвольное

Терм, представляющий бинарное дерево, а также функции возращения его корня и левого и правого поддеревьев определяются следующим образом:

In[44]:= z = bin[bin[leaf,1,bin[bin[leaf,7,leaf],4,leaf]], 
 2, bin[bin[leaf,5,leaf],3,bin[leaf,6,leaf]]];
rootbintree[bin[_, a_, _]] := a
lefttree[bin[l_, _, _]] := l
righttree[bin[_, _, r_]] := r
rootbintree[z]
lefttree[z]
righttree[z]
 Out[48]= 2
 Out[49]= bin[leaf, 1, bin[bin[leaf, 7, leaf], 4, leaf]]
 Out[50]= bin[bin[leaf, 5, leaf], 3, bin[leaf, 6, leaf]]

Функцию count вычисления количества вершин дерева можно определить рекурсивно в виде:

In[51]:= count[leaf] := 0
count[bin[l_, _, r_]] := count[l] + 1 + count[r]
count[z]
 Out[53]= 7

Для определения функции level, возвращающей список вершин дерева уровня n, используем функцию append (см. выше):

In[54]:= level[leaf, _] := nil
level[bin[_, a_, _], 0] := cons[a, nil]
level[bin[l_, _, r_], n_] := append[level[l, n - 1],
 level[r, n - 1]]
level[z, 0]
level[z, 1]
level[z, 2]
level[z, 3]
 Out[57]= cons[2, nil]
 Out[58]= cons[1, cons[3, nil]]
 Out[59]= cons[4, cons[5, cons[6, nil]]]
 Out[60]= cons[7, nil]

Далее определяются операции для произвольных деревьев. Используется дерево, показанное на рис. 6.5 (b).

Терм, представляющий дерево, а также функции возращения его корня и списка поддеревьев определяются следующим образом:

In[61]:= tr = tree[1, cons[tree[2, nil], cons[tree[3,
 cons[tree[5, nil], cons[tree[6, nil], nil]]],
 cons[tree[4, cons[tree[7, cons[tree[8, nil],
 nil]], nil]], nil]]]];
root[tree[a_, _]] := a
subtreelist[tree[_, tl_]] := tl
root[tr]
subtreelist[tr]
 Out[64]= 1
 Out[65]= cons[tree[2, nil], cons[tree[3, cons[tree[5, nil], cons[tree[6, nil], nil]]],
 cons[tree[4, cons[tree[7, cons[tree[8, nil], nil]], nil]], nil]]]

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

Функция number вычисления количества вершин дерева определяется в виде:

In[66]:= number[tree[_, tl_]] := 1 + numberlist[tl]
numberlist[nil] := 0
numberlist[cons[h_,t_]]:=number[h]+numberlist[t]
number[tr]
 Out[69]= 8

Аналогичным образом определяется функция leveltree построения списка элементов уровня n дерева:

In[70]:= leveltree[tree[a_, _], 0] := cons[a, nil]
leveltree[tree[_, tl_], n_] := levellist[tl, n-1]
levellist[nil, n_] := nil
levellist[cons[h_,t_],n_]:=append[leveltree[h,n],
 levellist[t, n]]
leveltree[tr, 0]
leveltree[tr, 1]
leveltree[tr, 2]
leveltree[tr, 3]
 Out[74]= cons[1, nil]
 Out[75]= cons[2, cons[3, cons[4, nil]]]
 Out[76]= cons[5, cons[6, cons[7, nil]]]
 Out[77]= cons[8, nil]

Двумерные структуры данных

В табличных структурах данных элемент имеет два индекса - номер строки и номер столбца. Примером двумерной структуры данных является матрица.

Матрицы можно моделировать в виде списка строк, которые представлены в виде списков элементов. Например, матрицу

$$\begin{pmatrix} 123\\ 456 \end{pmatrix} $$

можно представить следующим образом (см. программу ниже):

$$row_0 = cons(1, cons(2, cons(3, nil))),\\ row_1 = cons(4, cons(5, cons(6, nil))),\\ matr = cons(row_0, cons(row_1, nil)).$$

Функция get возвращения элемента матрицы с заданными индексами и функция set, которая вставляет элемент в позицию с заданными индексами, определяются следующим образом:

In[78]:= row0 := cons[1, cons[2, cons[3, nil]]]
row1 := cons[4, cons[5, cons[6, nil]]]
matrix := cons[row0, cons[row1, nil]]
get[matr_, i_, j_] := nth[nth[matr, i], j]
get[matrix, 1, 1]
 Out[82]= 5

 In[83]:= set[matr_, i_, j_, el_] := setnth[matr,
 setnth[nth[matr, i], el, j], i]
set[matrix, 1, 2, 7]
 Out[84]= cons[cons[1, cons[2, cons[3, nil]]], 
cons[cons[4, cons[5, cons[7, nil]]], nil]]

Определение функций sizeY и sizeX, которые возвращают число строк и число столбцов матрицы, соответственно, имеет вид:

In[85]:= sizeY[matr_] := length[matr]
sizeX[nil] := 0
sizeX[cons[h_, _]] := length[h]
sizeY[matrix]
sizeX[matrix]
 Out[88]= 2
 Out[89]= 3

Наконец, определим функции row и column, которые возвращают соответственно строку i и столбец j матрицы:

In[90]:= row[matr_, i_] := nth[matr, i]
column[nil, j_] := nil
column[cons[h_,t_],j_]:=cons[nth[h,j],column[t,j]]
row[matrix, 1]
column[matrix, 2]
 Out[93]= cons[4, cons[5, cons[6, nil]]]
 Out[94]= cons[3, cons[6, nil]]

Понятие алгоритма

Под алгоритмом понимается конечная система предписаний, определяющая содержание и порядок действий над исходными и промежуточными данными для получения после конечного числа шагов в качестве результата выходных данных. Алгоритм предназначен для исполнителя и описывается в его командах. Все данные, с которыми работает исполнитель, принадлежат его среде.

Алгоритмы характеризуются следующими свойствами: дискретность - действия разбиваются на конечную последовательность шагов; детерминированность - результат однозначно определяется последовательностью шагов, для одних и тех же исходных данных получается один и тот же результат; понятность - исполнитель однозначно воспринимает, а также понимает все предписания алгоритма; результативность - при точном выполнении предписаний результат получается за конечное число шагов; массовость - алгоритм правильно работает на некотором множестве исходных данных.

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

Алгоритм сортировки списка вставками

Для описаний алгоритмов используются различные способы: текстовая форма, блок-схема, псевдокод и др.

Описание алгоритма зависит от исполнителя. Например, рассмотрим алгоритм сортировки списка вставками. В императивных языках программирования сортировка одномерного массива выполняется в том же массиве. В логических языках создается и возвращается новый список, который образуют упорядоченные элементы исходного списка.

Рассмотрим алгоритм сортировки списка вставками на множестве термов, представляющих списки.

На вход алгоритма подается список элементов, на выходе возвращается упорядоченный список данных элементов.

Обозначим через $$L_k$$ и $$R_k$$ - текущие списки на шаге k алгоритма. На нулевом шаге положим: $$L_0$$ - исходный список, $$R_0$$ - пустой список. Далее шаги алгоритма нумеруются, начиная с 1.

Шаг m. Если список $$L_{m - 1}$$ пуст, то алгоритм завершается, и в качестве результата выдается список $$R_{m - 1}$$. Если список $$L_{m - 1}$$ не пуст, то в качестве списка $$R_m$$ берется список, полученный в результате вставки головы списка $$L_{m - 1}$$ в список $$R_{m - 1$$ так, чтобы полученный список был упорядоченным, а в качестве списка $$L_m$$ берется хвост списка $$L_{m - 1}$$. После этого выполняется переход к шагу m + 1.

Если выполняется сортировка по возрастанию элементов, то процедуру вставки в упорядоченный список R элемента a можно определить рекурсивно следующим образом: если элемент a больше головы h списка R, то возвращается список, головой которого является h, а хвостом - результат вставки элемента a в хвост списка R; в противном случае возвращается список с головой a и хвостом R.

Блок-схема алгоритма сортировки списка вставками представлена на рис. 6.6. В ней используются функции head и tail возвращения головы и хвоста списка, соответственно, а также функция ins вставки элемента в упорядоченный список. Через $$L_{in}$$ обозначен входной список, а через $$R_{out}$$ - выходной.

(рис 6.6) Блок-схема алгоритма сортировки вставками

Псевдокод алгоритма имеет вид:

l = [1, 2, 3], r = []
цикл пока l не пуст
r = ins(r, head(l))
l = tail(l)
конец цикла
печать r

На языке Wolfram для списков, представленных термами, алгоритм реализуется следующим образом:

In[1]:= x := cons[4,cons[2,cons[5,cons[3,cons[1,nil]]]]]
insertionsort[l_] := sort[l, nil]
sort[nil, l_] := l
sort[cons[h_, t_], l_] := sort[t, ins[h, l]]
ins[a_, nil] := cons[a, nil]
ins[a_, cons[h_, t_]] := If[a > h, 
cons[h, ins[a, t]], cons[a, cons[h, t]]]
insertionsort[x]
 Out[7]= cons[1, cons[2, cons[3, cons[4, cons[5, nil]]]]]

Быстрая сортировка

Рассмотрим реализацию алгоритма быстрой сортировки с помощью функций на множестве термов, представляющих списки. Алгоритм заключается в следующем. Если список пуст, то отсортированный список также пуст. Если список не пуст, то его хвост разбивается на два списка: список элементов, меньших головы, и список элементов, больше или равных головы. Алгоритм применяется к обоим спискам, затем два полученных упорядоченных списка соединяются в один список.

Для его реализации ниже используются функции ls и gr, которые для элемента a и списка возвращают списки элементов, меньших a и больше или равных a, соответственно. Определение функций имеет вид:

In[8]:= ls[a_, l_] := llist[a, l, nil]
llist[_, nil, l_] := l
llist[a_, cons[h_, t_], l_] := If[h < a, 
llist[a, t, cons[h, l]], llist[a, t, l]]
gr[a_, l_] := glist[a, l, nil]
glist[_, nil, g_] := g
glist[a_, cons[h_, t_], g_] := If[h >= a, 
glist[a, t, cons[h, g]], glist[a, t, g]]
ls[2, x]
gr[2, x]
 Out[14]= cons[1, nil]
 Out[15]= cons[3, cons[5, cons[2, cons[4, nil]]]]

С помощью функций ls и gr функция quicksort быстрой сортировки списка определяется следующим образом:

In[16]:= quicksort[l_] := qsort[l, nil]
qsort[nil, s_] := s
qsort[cons[h_, t_], s_] := qsort[ls[h, t],
cons[h, qsort[gr[h, t], s]]]
quicksort[x]
Out[19]= cons[1, cons[2, cons[3, cons[4, cons[5, nil]]]]]

Отметим, что операция соединения списков в данной реализации не используется.

Сортировка слиянием

Рассмотрим алгоритм сортировки списка слиянием. Его рекурсивное описание имеет вид: список разбивается на два равных по длине списка, или почти равных, если он содержит нечетное число элементов. Затем алгоритм применяется к обоим спискам. После этого выполняется операция слияния двух упорядоченных списков в один упорядоченный список.

Для того чтобы реализовать операцию разделения списка на два примерно равных по длине списка, используем функцию q, которая возвращает целую часть частного от деления длины списка на 2, а также функции take и drop, которые возвращают список, состоящий из первых n элементов, и список без первых n элементов исходного списка, соответственно. Ниже приведено определение этих функций (обычно в логических языках разделение одного списка на два реализуется проще):

In[20]:= length[l_] := len[l, 0]
len[nil, n_] := n
len[cons[_, t_], n_] := len[t, n + 1]
q[l_] := Quotient[length[l], 2]
take[_, 0] := nil
take[cons[h_, t_], c_] := cons[h, take[t, c - 1]]
drop[l_, 0] := l
drop[cons[_, t_], c_] := drop[t, c - 1]
k = q[x]
take[x, k]
drop[x, k]
 Out[28]= 2
 Out[29]= cons[4, cons[2, nil]]
 Out[30]= cons[5, cons[3, cons[1, nil]]] 

Встроенная функция Quotient от целых чисел m и n возвращает целую часть частного от деления m на n. Остаток от деления m на n возвращает встроенная функция Mod.

Функция mergesort сортировки списка слиянием определяется следующим образом:

In[31]:= mergesort[nil] := nil
mergesort[cons[a_, nil]] := cons[a, nil]
mergesort[l_] := merge[mergesort[take[l, q[l]]],
 mergesort[drop[l, q[l]]]]
merge[nil, l_] := l
merge[l_, nil] := l
merge[cons[a_, t_], cons[b_, s_]] := If[a < b,
 cons[a, merge[t, cons[b, s]]], 
 cons[b, merge[cons[a, t], s]]]
mergesort[x]
Out[37]= cons[1, cons[2, cons[3, cons[4, cons[5, nil]]]]] 

Функция merge по двум упорядоченным спискам возвращает упорядоченный список, который является их слиянием.

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

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

Дек целых чисел

На множестве термов, представляющих деки, определим функции

addFront добавления первого элемента дека;

front возвращения первого элемента дека;

removeFront возвращения дека без первого элемента;

addRear добавления последнего элемента дека;

rear возвращения последнего элемента дека;

removeRear возвращения дека без последнего элемента.

Все эти функции аналогичны функциям, определенным выше для списков, стеков и очередей.

Определим также функцию isEmpty, которая возвращает значение True, если дек пуст, и False, если не пуст.

Определение вышеперечисленных функций имеет вид:

In[1]:= x = cons[1, cons[2, cons[3, nil]]];
addFront[nil, a_] := cons[a, nil]
addFront[cons[h_,t_],a_]:=cons[h,addFront[t,a]]
front[cons[a_, nil]] := a
front[cons[_, t_]] := front[t]
removeFront[cons[a_, nil]] := nil
removeFront[cons[h_,t_]]:=cons[h,removeFront[t]]
addRear[d_, a_] := cons[a, d]
rear[cons[h_, _]] := h
removeRear[cons[_, t_]] := t
isEmpty[nil] := True
isEmpty[_] := False
{addFront[x, 5], addRear[x, 7]}
{front[x], rear[x]}
{removeFront[x], removeRear[x]}
isEmpty[x]
 Out[13]= {cons[1, cons[2, cons[3, cons[5, nil]]]], 
 cons[7, cons[1, cons[2, cons[3, nil]]]]}
 Out[14]= {3, 1}
 Out[15]= {cons[1, cons[2, nil]], cons[2, cons[3, nil]]}
 Out[16]= False

Алгоритм преобразования целой части числа из десятичного представления в p-ичное

Псевдокод алгоритма преобразования неотрицательного целого десятичного числа в p-ичное выглядит следующим образом.

n = 6, p = 2, deque = []
цикл пока n > 0
deque = addRear(deque, n mod p)
n = n div p
конец цикла

Определим функцию intToP, которая по заданному целому неотрицательному числу n и основанию системы счисления p возвращает p-ичное представление числа n в виде дека его цифр. Для этого используем вспомогательную функцию f:

$$intToP(n,p)=f(n,p,[]);\\ f(n,p,d)=\begin{cases} d, n=0\\ f(n \div p, p, addRear(d, n \mod \quad p)), \ n >0 \end{cases} $$

Пример 3. Найдем представление числа 6 в двоичной системе счисления с помощью функции intToP. Имеем:

intToP(6, 2)= f(6, 2, []) = f(3, 2, [0]) = f(1, 2, [1, 0]) = f(0, 2, [1, 1, 0]) = [1, 1, 0].

На языке Wolfram определение функций intToP и f имеет вид:

 In[17]:= intToP[0, _] := cons[0, nil]; intToP[_, 1] := nil;
intToP[n_Integer?Positive, p_Integer?Positive] :=
f[n, p, nil]
f[0, _, d_] := d
f[n_, p_, d_] := f[Quotient[n, p], p, 
addRear[d, Mod[n, p]]]
intToP[6, 2]
intToP[43000, 60]
 Out[21]= cons[1, cons[1, cons[0, nil]]]
 Out[22]= cons[11, cons[56, cons[40, nil]]] 

Алгоритм преобразования дробной части числа из десятичного представления в p-ичное

Пусть [x] и {x} - целая и дробная части действительного числа x, соответственно. Обозначим через m число знаков после запятой представления дробной части числа в системе счисления с основанием p.

Псевдокод алгоритма перевода неотрицательного десятичного числа, меньшего единицы, в систему счисления с основанием p имеет вид:

n = 0,14, p = 2, m = 5, deque = []
цикл пока n > 0 и m > 0
n = n * p
	deque = addFront(deque, [n])
	n = {n}
	m = m - 1
конец цикла
печать deque

Определим функцию fracToP, которая возвращает первые m разрядов p-ичного представления неотрицательного числа n, меньшего единицы. Как и ранее, используем вспомогательную функцию:

$$fracTop(n,p,m)=g(n,pm,[]);\\ G(n,p,m,d)=\begin{cases} d, n*m=0\\ g({np},p,m-1,addFront(d[np])), n >0, m ^gt;0 \end{cases} $$

Пример 4. Найдем первые 5 знаков после запятой двоичного представления числа 0,14 с помощью функции fracToP. Имеем:

$$fracToP(0,14, 2, 5) = g(0,14, 2, 5, []) = g(0,28, 2, 4, [0]) =\\ = g(0,56, 2, 3, [0, 0]) = g(0,12, 2, 2, [0, 0, 1])=\\ = g(0,24, 2, 1, [0, 0, 1, 0]) = g(0,48, 2, 0, [0, 0, 1, 0, 0]) = [0, 0, 1, 0, 0].$$

На языке Wolfram код выглядит следующим образом:

 In[23]:= fracToP[n_, p_Integer?Positive, m_] := If[
0<=n<1  m>=0  p>1, g[n, p, m, nil], nil]
g[0, _, _, d_] := d
g[_, _, 0, d_] := d
g[n_, p_, m_, d_] := g[FractionalPart[n p], p, 
m - 1, addFront[d, IntegerPart[n p]]]
fracToP[0.14, 2, 5]
fracToP[0.7, 3, 6]
fracToP[0.238, 16, 5]
 Out[27]= cons[0, cons[0, cons[1, cons[0, cons[0, nil]]]]]
 Out[28]= cons[2, cons[0, cons[0, cons[2, cons[2, cons[0, nil]]]]]]
 Out[29]= cons[3, cons[12, cons[14, cons[13, cons[9, nil]]]]]

Встроенные функции IntegerPart и FractionalPart возвращают соответственно целую и дробную часть действительного числа.

Функцию decimalToP преобразования представления числа из десятичной системы счисления в систему счисления с основанием p можно определить следующим образом:

In[30]:= decimalToP[n_, p_, m_] := 
append[intToP[IntegerPart[n], p], 
cons[z, fracToP[FractionalPart[n], p, m]]]
append[nil, l_] := l
append[cons[h_, t_], l_] := cons[h, append[t, l]]
decimalToP[35.85, 2, 10]
 Out[33]=cons[1, cons[0, cons[0, cons[0, cons[1, cons[1, cons[z, 
cons[1, cons[1, cons[0, cons[1, cons[1, cons[0, 
cons[0, cons[1, cons[1, cons[0, nil]]]]]]]]]]]]]]]]]

Символ z в данном списке соответствует знаку запятой.

Алгоритм преобразования целой части числа из p-ичного представления в десятичное

Псевдокод алгоритма преобразования представления целого неотрицательного числа из p-ичной системы счисления в десятичную систему имеет вид:

deque = [1, 0, 1, 1, 0, 1, 1], p = 2, n = 0
цикл пока deque $$\ne$$ []
n = n * p + rear(deque)
deque = removeRear(deque)
конец цикла 
печать n

Определение функции intToDec, которая по деку p-ичных цифр и основанию p системы счисления возвращает десятичное число, выглядит следующим образом:

$$intToDec(d,p)=h(d,p,0)\\ h(d,p,n)=\begin{cases} n,d=[]\\ h(removeRead(d), p,n*p+rear(d)),d \ne [] \end{cases}$$

Пример 5. Найдем десятичное число, двоичное представление которого равно $$110_2$$ с помощью функции intToDec. Имеем:

$$intToDec([1, 1, 0], 2)= h([1, 1, 0], 2, 0) = h([1, 0], 2, 1) = h([0], 2, 3) = h([], 2, 6) = 6.$$

Определение функции intToDec на языке Wolfram имеет вид:

In[34]:= intToDec[d_, p_Integer?Positive] := h[d, p, 0]
h[nil, _, n_] := n
h[cons[a_, t_], p_, n_] := h[t, p, n p + a]
y = cons[1, cons[1, cons[0, nil]]];
intToDec[y, 2]
 Out[38]= 6

Алгоритм преобразования дробной части числа из p-ичного представления в десятичное

Псевдокод алгоритма преобразования представления дробной части рационального числа из системы счисления с основанием p в десятичное число выглядит следующим образом:

deque = [1, 0, 1, 1, 0, 1, 1], p = 2, n = 0
цикл пока deque $$\ne$$ []
n = (n + front(deque)) / p
deque = removeFront(deque)
конец цикла 
печать n

Функция fracToDec преобразования дробной части числа из p-ичной в десятичную систему счисления определяется в виде:

$$fracToDec(d,p)=r(d,p,0);\\ r(d,p,n)=\begin{cases} n,d=[]\\ r(removeFront(d),p,(n+front(d))/p), d \ne [] \end{cases} $$

Пример 6. Найдем десятичное число, двоичное представление которого равно 0,101 с помощью функции fracToDec. Имеем:

$$fracToDec([1, 0, 1], 2) = r([1, 0, 1], 2, 0) = r([1, 0], 2, 0,5) $$

Определение функции fracToDec на языке Wolfram имеет вид:

In[39]:= fracToDec[d_, p_Integer?Positive] := r[d, p, 0]
r[nil, _, n_] := n
r[d_,p_,n_]:=r[removeFront[d],p,(n+front[d])/p]
fr = cons[1, cons[0, cons[1, nil]]];
fracToDec[fr, 2]
 Out[43]= $$\frac58$$

Функцию toDecimal, которая преобразует p-ичное представление числа в десятичное, можно определить следующим образом:

In[44]:= toDecimal[d_, p_] := intToDec[getInt[d], p] +
fracToDec[getFract[d], p]
getInt[nil] := nil
getInt[cons[z, _]] := nil
getInt[cons[a_, t_]] := cons[a, getInt[t]]
getFract[nil] := nil
getFract[cons[z, t_]] := getInt[t]
getFract[cons[_, t_]] := getFract[t]
num = append[y, cons[z, fr]]
getInt[num]
getFract[num]
toDecimal[num, 2]
N[%]
 Out[51]= cons[1, cons[1, cons[0, cons[z, cons[1, cons[0, cons[1, nil]]]]]]]
 Out[52]= cons[1, cons[1, cons[0, nil]]]
 Out[53]= cons[1, cons[0, cons[1, nil]]]
 Out[54]=  $$\frac{53}{8}$$
 Out[55]= 6.625

Функция N возвращает число в десятичном формате. Вместо знака % подставляется результат последнего вычисления.

Упражнения

Определите на языке Wolfram функцию вычисления наибольшего общего делителя двух целых чисел.

Определите на языке Wolfram для списков, представленных термами, операцию

вычисления суммы элементов списка чисел;

вычисления произведения элементов списка;

вычисления среднего арифметического элементов списка чисел;

вычисления числа вхождений заданного элемента в список;

вычисления числа четных элементов в список;

замены всех вхождений одного элемента на другой элемент;

удаления первого вхождения заданного элемента в список;

удаления всех вхождений заданного элемента в список;

удаления элемента с заданным индексом;

проверки принадлежности элемента списку;

вычисления минимального элемента списка;

вычисления максимального элемента списка;

обращения списка ($$1, 2, 3 \to 3, 2, 1$$);

возвращения списка элементов с четными индексами;

вставки после каждого элемента его удвоенного значения;

построения списка индексов всех вхождений элемента в список;

построения списка случайных чисел, не превосходящих заданной величины, который состоит из заданного числа элементов;

удаления дубликатов из списка $$(1, 2, 3, 2, 1, 2 \to 1, 2, 3)$$;

удаления подряд идущих дубликатов из списка $$(1, 2, 2, 2, 3, 3, 2, 2, 1, 1 \to 1, 2, 3, 2, 1)$$.

Определите на языке Wolfram для бинарных деревьев, представленных термами, операцию

вычисления суммы вершин дерева;

вычисления числа вершин, равных заданному элементу;

вычисления минимального элемента дерева;

замены заданного элемента на другой элемент;

удаления левого поддерева;

удаления правого поддерева;

построения списка листьев дерева;

построения по списку дерева, в котором элементы левого поддерева каждой вершины меньше этой вершины, а элементы правого поддерева больше или равны ей.

Определите на языке Wolfram для произвольных деревьев, представленных термами, операцию

вычисления суммы вершин дерева;

вычисления числа вершин, равных заданному элементу;

вычисления суммы четных вершин дерева;

вычисления максимального элемента дерева;

замены заданного элемента на другой элемент;

построения списка листьев дерева.

Определите на языке Wolfram для матриц, представленных термами, операцию

вычисления суммы элементов;

вычисления минимального элемента матрицы;

вычисления суммы элементов заданной строки;

вычисления суммы элементов заданного столбца;

сложения матриц;

транспонирования матрицы;

умножения матриц.

Реализуйте на языке Wolfram алгоритм пузырьковой сортировки для списков, представленных термами.

Реализуйте на языке Wolfram для списков, представленных термами, алгоритм перемешивания элементов списка случайным образом.

Реализуйте на языке Wolfram алгоритм построения треугольника Паскаля, используя списки, представленные термами.

Реализуйте на языке Wolfram алгоритм решения квадратного уравнения, который по списку коэффициентов уравнения возвращает список корней уравнения.

Реализуйте на языке Wolfram для многочленов, представленных списками коэффициентов по возрастанию степеней (списки представляются в виде термов), операцию

сложения многочленов;

умножения многочлена на число;

произведения многочленов;

дифференцирования многочлена;

вычисления первообразной многочлена.