Приемы программирования и избранные задачи
Введение

Предлагаемый в этом разделе материал можно условно разделить на две части.

В первой части рассматриваются примеры, демонстрирующие преимущества Лиспа над другими языками программирования. Большая часть приведенных задач взяты из литературы, но есть и задачи, придуманые автором. Назначение первой части - показать на реальных примерах основные идеи Лиспа.

Во второй части приводятся решения достаточно традиционных задач. Здесь, наряду с сугубо лисповскими подходами используется и привычное процедурное программирование. Назначение второй части - привести лисповские решения задач, которые обычно решаются на практикумах по программированию. Можно убедиться, что при желании можно программировать на Лиспе, как, например, на Паскале.

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

Некоторые примеры рекурсивных программ
Построение списка целых

Наверное, одной из первых задач, которую предлагают студенту или школьнику при изучении Паскаля, является задача заполнения массива последовательными целыми числами от единицы до заданного N. Напомним решение этой задачи:

- заводим массив M;

- заводим целую переменную i;

- в цикле по i от единицы до N i-му элементу массива величину i (M[i]:=i).

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

Будем рассуждать так:

- Очевидно, что если N=0, то результирующий список должен быть пустым списком (список из нуля элементов);

- Пусть у нас уже построен список из N-1-го числа (обозначим его Ln-1). Тогда очевидно, что список из N чисел получается из списка Ln-1 простым добавлением в хвост числа N:    Ln = Ln-1 + ( N ).

Как можно убедиться, приведенные выше рассуждения в точности повторяют выкладки метода математической индукции. Теперь осталось воплотить эти выкладки в программу на Лиспе. Объединение списков выполняет функция append, а построить список из одного элемента можно с помощью функции list. Собирая все вместе, получаем:


(defun alist (n) (cond ((= n 0) Nil)
                        (T (append (alist (- N 1)) (list N)))
                 )
)


==> alist

(alist 100)

==> (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
     23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
     42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
     61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
     80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
     99 100)

Функция вполне работоспособна. Теперь немного усложним задачу. Предположим, что требуется построить список не всех чисел от единицы до заданного N, а список всех чисел из интервала N1 - N2. Повторим наши рассуждения, применительно к новой задаче:

- Очевидно, что если N1 = N2, то результирующий список должен быть списком из одного элемента (неважно, какого N1 или N2);

- Пусть у нас уже построен список чисел из диапазона N1 - (N2-1). Тогда очевидно, что искомый список получается из последнего просто добавлением в хвост числа N2.

Этот подход реализуется на Лиспе вполне очевидным образом:


(defun clist (n1 n2) (cond ((= n1 n2) (list n1))
                        (T (append (clist N1 (- N2 1)) (list N2)))
                 )
)

==> clist

(clist 5 55)

==> (5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
      27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
      47 48 49 50 51 52 53 54 55)

Решение получилось изящным и лаконичным.

Чередование элементов двух списков ("два гребня")

Пусть даны два произвольных списка. Обозначим элементы этих списков Ai и Bi соответственно. Длины списков могут различаться. Требуется построить новый список в котором элементы исходных списков чередовались бы следующим образом: A1 , B1 , A2 , B2 ... и т.д. до исчерпания более короткого списка. Допуская вольность, можно представить себе результат, как два два гребня, вставленных один в другой.

Рассмотрим лисповское (функциональное) решение этой задачи. Назовем функцию, которая будет строить список-результат grb. У этой функции будет два параметра (исходные списки); обозначим их a и b. Представляется очевидным, что результирующий список будет совпадать со списком a, если список b пуст. Соответственно, если пуст список a, то результат будет совпадать со списком b. Если же оба исходных списка не пусты, то результат можно представить как объединение следующих двух списков:

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

- результата применения функции grb к хвостам списков a и b.

В Лиспе это выглядит следующим образом:


(defun grb (a b) (cond ((null a) b)
                       ((null b) a)
                       (T (append (list (car a) (car b)) (grb (cdr a) (cdr b))))
                 )
)

==> grb

(grb '(1 2 3 4 5 6) '(a b c d e f g h))

==> (1 a 2 b 3 c 4 d 5 e 6 f g h)

Определяющее выражение функции получается дословным переводом на Лисп приведенных выше математических рассуждений (что является большим преимуществом рекурсивного функционального подхода).

Получение n-го элемента списка

Встроенные в Лисп функции CAR и CDR позволяют "разобрать" произвольный список на составные части. Однако, в стандартный набор функций Лиспа не входит функция, позволяющая получить элемент списка по его номеру. Попробуем заполнить этот пробел.

Построим функцию n-th, имеющую два параметра: список и номер извлекаемого элемента. Очевидно, что если входной список пуст, то функция должна возбудить состояние ошибки (у пустого списка нет элементов). Далее, если запрошен первый элемент непустого списка, то он просто равен голове этого списка. И, наконец, если запрошен n-й элемент непустого списка, то он в точности равен (n-1)-му элементу хвоста исходного списка.

Воплощаем все сказанное в Лиспе:


(defun n-th (x n) (cond ((null x) (raiseError "n-th: список пуст(исчерпан)")) 
                        ((= n 1) (car x))  
                        (T (n-th (cdr x) (- n 1)))
                  )
)

==> n-th

(n-th '(1 2 3) 5)

n-th: список пуст(исчерпан)
==> ERRSTATE

(n-th '(q w e r t y) 4)

==> r

(n-th '(q w e r t y) -4)

n-th: список пуст(исчерпан)
==> ERRSTATE

Использованная выше функция RAISEERROR позволяет установить состояние ошибки и задать текст разъясняющего сообщения. Приведенное сообщение может возникнуть в двух случаях: когда явно запрашивается элемент пустого списка или когда запрашиваемый элемент списка не существует (у трехэлементного списка запрошен, например, пятый элемент).

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

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


(defun n-th (x n) (cond ((<= n 0) (raiseError "n-th: аргумент неположителен"))
                        ((null x) (raiseError "n-th: список пуст(исчерпан)")) 
                        ((= n 1) (car x))  
                        (T (n-th (cdr x) (- n 1)))
                  )
)

==> n-th

(n-th '(q w e r t y) 4)

==> r

(n-th '(q w e r t y) -4)

n-th: аргумент неположителен
==> ERRSTATE

Теперь наша функция приобрела необходимую завершенность.

Арифметика неограниченной разрядности

Действия с целыми числами высокой разрядности всегда доставляли определенные трудности. Дело в том, что стандартные целые, которые обрабатывает компьютер, имеют достаточно большую, но все же ограниченную разрядность. Так, для популярных интеловских 32-х битных процессоров максимальная величина целого составляет 231 = 2 147 483 648. Если попробовать вычислить, например, величину 50!=1*2*3*...*49*50, то переполнение неминуемо.

Хорошим тоном при реализации Лиспа считается обеспечение арифметики неограниченной разрядности. Долгое время (примерно, до середины 90-х годов прошлого века) только Лисп и позволял вычислить, например, все значащие цифры 100!. Сейчас с появлением языков новых поколений (таких, как Haskell или Python) ситуация изменилась. Тем не менее, арифметика неограниченной разрядности остается привлекательной строной Лиспа. В данном разделе будет разобрано две задачи, в которых арифметика высокой разрядности играет главную роль.

Проблема 3n+1

Эта математическая проблема, суть которой сообщил автору П.Л. Бахрах, состоит в следующем:

Берется произвольное целое число N. Из него получается число M по следующему алгоритму:

Если N - четное, то M полагается равным N\2;

Если N - нечетное, то M полагается равным 3*N+1;

Далее полагается N = M и процесс повторяется. При этом оказывается, что какое бы исходное число N ни было бы взято, процесс рано или поздно сойдется к единице. Строгого математического доказательства этого факта (на момент написания этих строк) пока не найдено. Удивительно здесь то, что число или уменьшается вдвое или увеличивается втрое. Казалось бы, увеличение должно "перевесить", и число должно бесконечно возрастать. Но этого не происходит!

Вот простая Лисповская программа, реализующая приведенный выше алгоритм:


(defun 3n+1 (n) (prog nil 
                      (printline n)
                      (cond ((= n 1) (return 'OK))
                            ((= (% n 2) 0) (return (3n+1 (\ n 2))))
                            (T (return (3n+1 (+ (* n 3) 1))))
                      )
                )        
)

==> 3n+1

Функция снова получена простым переводом на Лисп алгоритма "3n+1". Единственное отличие заключается в том, что тело функции оформлена как PROG-конструкция. При входе в функцию сначала выполняется печать значения аргумента. Это позволяет проследить, какие числа получаются в процессе работы программы.

А вот и результат вызова:


(3n+1 10000)

10000
5000
2500
1250
625
1876
938
469
1408
704
352
176
88
44
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

==> OK

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


(defun 3n+1 (n k) (cond ((= n 1) k)
                        ((= (% n 2) 0) (3n+1 (\ n 2) (+ k 1)))
                        (T  (3n+1 (+ (* n 3) 1) (+ k 1)))
                  )        
)

==> 3n+1

Здесь функции добавлен второй параметр k. При рекурсивном обращении функции к самой себе к значению параметра прибавляется единица. При терминировании рекурсии накопленное значение параметра k возвращается в качестве результата. Легко видеть, что это и будет в точности количество выполненных циклов. Подобный прием использования параметра в рекурсивном программировании имеет специальное название - накапливающий параметр.

Единственным неудобством новой редакции функции 3n+1 является то, что вызывать ее нужно с двумя параметрами - исследуемым числом и нулем:


(3n+1 10000 0)

==> 29

(3n+1 (fact 50) 0)

==> 1295

Впрочем, это неудобство легко преодолеть: достаточно погрузить функцию 3n+1 в функцию-облочку:


(defun *3n+1 (n) (3n+1 n 0))

==> *3n+1

(*3n+1 10000)

==> 29

Накапливающий параметр теперь скрыт в оболочке.

Численный перебор

В книге И. Сафронова "Visual Basic в задачах и примерах" Санкт-Петербург, 2006. автор этих строк нашел замечательную задачу. Вот ее формулировка:

Сколько существует натуральных чисел n, меньших 1000, для которых 2n-n делится на 7?

Решение ее кажется простым: завести цикл по i от единицы до 1000 и для каждого i проверить остаток от деления 2i-i на 7. Да вот незадача: Visual Basic не позволит вычислить 2i при i большем 31... А в Лиспе такой проблемы нет! Вот простая программа решения задачи И. Сафронова "в лоб":


(prog (i n)
      (setq n 0)
      (setq i 1)
   @1 (cond ((= (% (- (^ 2 i) i) 7) 0) (setq n (+ 1 n))))
      (setq i (+ 1 i))
      (cond ((<= i 1000) (go @1)))
      (return n)
)

==> 142

PROG-конструкция использует две локальные переменные i и n. Для очередного i вычисляется остаток от деления на 7 величины 2i-i. Если остаток оказывается нулевым, значение переменной n увеличивается на единицу. Далее величина i увеличивается на единицу и проверяется, не превысила ли величина i граничного значения (1000). Если нет - вычисления повторяются. Когда i получает значение, большее 1000, цикл разрывается и оператор return возвращает количество чисел, удовлетворяющих заданному условию.

Используя макро for этот же алгоритм можно реализовать короче:


(prog (i n)
      (setq n 0)
      (for i 1 1000  
         ( (cond ((= (% (- (^ 2 i) i) 7) 0) (setq n (+ 1 n)))) )
      )
      (return n)
)

==> 142

Обе программы дают верный результат, но работают ощутимо долго - около минуты. Производительность программы может быть повышена почти в 10 раз, если оптимизировать приведенный код. Легко видеть, что "узким местом" является вычисление степени двойки. Предположим, на j-м витке цикла вычислена величина 2j. На следующем витке будет вычислятся величина 2j+1 с помощью встроенной функции EXPT(^), хотя для вычисления 2j+1 достаточно умножить уже вычисленную ранее величину 2j на 2! Если не перевычислять степень двойки на каждом витке, а завести рабочую переменную, значение которой просто умножать на 2, тот производительность программы возрастет более, чем в 9 раз:


(prog (i n m)
      (setq n 0)
      (setq m 2)
      (for i 1 1000  
         ( (cond ((= (% (- m i) 7) 0) (setq n (+ 1 n)))) (setq m (* 2 m)) )
      )
      (return n)
)

==> 142

Результат получается не за минуту, а за 7.5 сек! А если мы хотим не просто подсчитать, а увидеть числа n, для которых 2n-n делится на 7 без остатка? Нет проблем:


(prog (i n m)
      (setq n 0)
      (setq m 2)
      (for i 1 1000  
         ( (cond ((= (% (- m i) 7) 0) (prog nil (printline i) (setq n (+ 1 n)))))
           (setq m (* 2 m))
         )
      )
      (return n)
)

11
15
16
32
36
37
53
57
58
74
78
79
95
99
...
960
961
977
981
982
998

==> 142

Здесь просто добавлена печать очередного числа, удовлетворяющего условиям задачи. Желающие могут убедиться, что все приведенне числа условиям задачи удовлетворяют.

Задача решена. Однако, прежде, чем переходить к следующей задаче, дадим решение задачи И. Сафронова, пригодное для реализации в языке, не поддерживающем арифметики неограниченной разрядности.

Поскольку верно равенство 7=23-1, то 2n-n=7*2n-3+2n-3-n. Поэтому, остаток от деления (2n-n) на 7 равен остатку от деления на 7 величины (2n-3-n). Далее: (2n-3-n) = 7*2n-6+2n-6-n. Остаток от деления (2n-3-n) на 7 равен остатку от деления на 7 величины (2n-6-n). Таким образом, чтобы оценить остаток от деления (2n-n) на 7 нужно вычитать из показателя степени по тройке до тех пор, пока показатель не станет меньше 32 (когда степень можно вычислить явно).

Вот программа на Лиспе, реализующая эту идею:


(prog (m n i k)
      (setq n 0)
      (for i 1 1000
         ( 
          (setq m i)
          (setq k (+ 1 (\ (- m 31) 3))) 
          (setq m (- m (* 3 k)))
          (cond ((= (% (- (^ 2 m) i) 7) 0) (setq n (+ 1 n))  ))
         )
      )
      (return n)
)


==> 142

Следует заметить, что время выполнения этой программы составляет чуть меньше 2 сек. Математика себя оправдывает!

Различные математические объекты

Встроенными типами Лиспа являются только целые и вещественные числа. Более сложные математические объекты (комплексные числа, векторы, матрицы) числа можно смоделировать. В нижеследующих разделах показывается, что это совсем не сложно, а динамическая природа списков позволяет легко создавать векторы и матрицы любых размеров. Неограниченная размерность целочисленной арифметики Лиспа позволяет построить точную рациональную арифметику (арифметику дробей).

Рациональная арифметика

С рациональными числами читатель, несомненно, знаком еще по школьному курсу арифметики. Тем не менее, рассмотрим строгое математическое определение рациональных чисел. При этом автор предполагает, что свойства целых чисел читателю известны.

Рассмотрим множество упорядоченных пар целых взаимно простых чисел (n , d). Первое число пары будем называть числителем, второе - знаменателем. Предполагаем, что d отлично от нуля. Взаимная простота чисел n и d означает, что числа n и d не имеют общих делителей, кроме единицы. Будем считать, что пары (n1 , d1) и (n2 , d2) равны тогда и только тогда, когда n1 = n2 и d1 = d2.

Следует особо подчеркнуть, что в наше множество пар целых включаются не всякие пары, а только пары взаимно-простых чисел. В частности, пара (0 , d) входит в наше множество только при d=1. Соответственно, пара (n , n) входит в наше множество только при n=1. Пары (0 , 1) и (1 , 1) играют в нашем множестве особую роль. Об этом - чуть ниже.

Теперь определим алгебраические операции на множестве пар.

Суммой пар (n1 , d1) и (n2 , d2) будем называть пару (n , d) , числитель которой равен:

n = (n1 * d2 + n2 * d1)/НОД((n1 * d2 + n2 * d1) , (d1 * d2))

а знаменатель:

d = (d1 * d2)/НОД((n1 * d2 + n2 * d1) , (d1 * d2))

Разностью пар (n1 , d1) и (n2 , d2) будем называть пару (n , d) , числитель которой равен:

n = (n1 * d2 - n2 * d1)/НОД((n1 * d2 + n2 * d1) , (d1 * d2))

а знаменатель:

d = (d1 * d2)/НОД((n1 * d2 + n2 * d1) , (d1 * d2))

Произведением пар (n1 , d1) и (n2 , d2) будем называть пару (n , d) , числитель которой равен:

n = (n1 * n2)/НОД((n1 * n2) , (d1 * d2))

а знаменатель:

d = (d1 * d2)/НОД((n1 * n2) , (d1 * d2))

В приведенных выше формулах символ НОД(x , y) означает наибольший общий делитель целых x и y. Использование НОД необходимо, поскольку при вычислении числителя и знаменателя может нарушиться взаимная простота.

Обратной паре (n , d) при n отличном от нуля, будем называть пару (d , n). Легко видеть, что произведение пар (n , d) и (d , n) дает пару (1 , 1).

Противоположной паре (n , d) будем называть пару (-n , d). Легко видеть, что сумма пар (n , d) и (-n , d) дает пару (0 , d).

Можно убедиться, что для определенных выше алгебраических операций будут справедливы сочетательный, распределительный и переместительный законы арифметики. Роль нуля будет играть пара (0 , 1), а роль единицы - пара (1 , 1). Осталось сказать, что пара (n , d) традиционно записывается в виде n/d и называется дробью. Множество целых чисел естественным образом вкладывается во множество дробей, если отожествить целое p с дробью p/1.

Множество дробей с двумя операциями, определенными выше, называется полем рациональных чисел и обозначается Q.

Переходим к моделированию рациональной арифметики на Лиспе. Целочисленная арифметика в нашем распоряжении уже имеется - она встроена в ядро Лиспа. Как следует из приведенных выше определений, нам прежде всего понадобится функция, вычисляющая НОД. Для этого существует классический алгоритм Евклида. Пусть требуется найти НОД двух целых X и Y. Очевидно, что если одно из чисел равно нулю, то НОД равен другому (ненулевому) числу. Если оба числа X и Y равны нулю, то НОД этих чисел неопределен. А при ненулевых X и Y следует поступать так:

1) Вычислить R - остаток от деления X на Y.

2) Если R=0, то НОД(X , Y)=Y

3) Если R <> 0, то положить X=Y; Y=R и перейти к шагу 1).

Алгоритм гарантированно сходится. Ниже приведен нерекурсивный вариант программы вычисления НОД двух чисел.


(defun gcd (x y) (cond 
                      ((AND (eq y 0) (eq x 0)) nil)
                      ((eq x 0) y)
                      ((eq y 0) x)
                      (T
                         (prog (xx yy r)
                               (setq xx x)
                               (setq yy y)
                          loop
                               (setq r (remainder xx yy))
                               (cond ((eq r 0) (return yy)))
                               (setq xx yy)
                               (setq yy r)
                               (go loop)
                         )          
                      )
                  )
)

==> gcd

(gcd 1212 6543)

==> 3

Название функции происходит от английского "the great common divisor", что по-русски как раз и означает "наибольший общий делитель".

Как представлять дробь в Лиспе? Наиболее естественное представление дроби - в виде двухэлементного списка. Первый элемент будет числителем, второй - знаменателем. А чтобы Лисп мог отличить дробь от произвольного двухэлементного списка, добавим в начало списка атом RATIONAL. Окончательно дробь будет представляться списком из трех элементов: атом RATIONAL, числитель и знаменатель.

В процессе работы нам понадобится программа "сокращения" дроби. Суть сокращения проста - деление числителя и знаменателя на их НОД. Вот соответствующая программа на Лиспе:


(defun  simplify (x) (prog (num denom g sgn)
                      (setq denom (cadr x))
                      (cond ((= denom 0) (raiseerror "Знаменатель равен нулю!")))
                      (setq num (car x))
                      (setq sgn 1)
                      (cond ((And (< num 0) (> denom 0)) (setq sgn -1))
                            ((And (> num 0) (< denom 0)) (setq sgn -1))
                            ((= num 0) (setq denom 1))
                      )
                      (setq num (abs num))
                      (setq denom (abs denom))
                      (setq g (gcd num denom))
                      (cond ((eq g 1) (return (list (* num sgn) denom)))
                            (T (return (list (\ (* num sgn) g) (\ denom g))))
                      )
                     )
)

==> simplify

(simplify '(6 3))

==> (2 1)

(simplify '(3 6))

==> (1 2)

(simplify '(0 6))

==> (0 1)

(simplify '(-6 6))

==> (-1 1)

(simplify '(6 -6))

==> (-1 1)

Функция simplify кроме деления на НОД числителя и знаменателя, выполняет еще два дополнительных действия: относит знак дроби к числителю и препятствует созданию дроби со знаменателем, равным нулю. Пусть читателя не удивляет, что функция simplify работает с двухэлементным списком: в приводимых ниже функциях манипулирования дробями simplify всегда применяется к хвосту списка, моделирующего дробь.

Теперь можно приступать к созданию функций для работы с дробями. Имена всех этих функций будут иметь префикс rat (рациональный). Начнем с функции создания дроби. Она оказывается очень простой:


(defun ratCreate (num denom) 
                  (cond ((null (flagp num 'FIXED)) (raiseerror "Числитель - не целое"))
                        ((null (flagp denom 'FIXED)) (raiseerror "Знаменатель - не целое"))
                        (T (cons 'RATIONAL (simplify (list num denom))))
                  )
)

==> ratCreate

(ratCreate -1 2)

==> (RATIONAL -1 2)

(ratCreate -6 3)

==> (RATIONAL -2 1)

(ratCreate 6 -3)

==> (RATIONAL -2 1)

Функция ожидает два параметра - числитель и знаменатель. Возвращает функция трехэлементный список: атом RATIONAL (признак дроби), числитель и знаменатель. К списку (числитель знаменатель) применяется функция simplify (что обеспечивает несократимость дроби и отнесение знака к числителю). Перед созданием списка функция проверяет наличие флага FIXED у значений числителя и знаменателя. Если числитель или знаменатель не являются числом типа FIXED - возбуждается состояние ошибки.

Теперь написать функции манипулирования рациональными оказывается совсем просто. Как ни странно, самой сложной функцией будет функция печати рационального числа. При печати желательно предусмотреть все возможности: чтобы рациональное со знаменателем 1 печаталось как целое, чтобы дробь с числителем 0 печаталась как 0, чтобы из неправильной дроби выделялась целая часть и печаталась отдельно.

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


(defun ratPrint (x)
       (cond ((<> (car x) 'RATIONAL) (raiseerror "ratPrint: Не дробь"))
             (T
               (prog (tmp num denom sgn)
                 (setq tmp (simplify (cdr x)))    ;; на всякий случай...
                 (setq num (car tmp))             ;; числитель
                 (setq denom (cadr tmp))          ;; знаменатель
                 (setq sgn (sign num))            ;; знак дроби
                 (setq num (abs num))             ;; берем абс. величину
                 (cond ((= num 0) (go @1) ))      ;; числитель=0
                 (cond ((< sgn 0) (prints "-")))  ;; если знак отрицат. 
                 (cond ((= denom num) (go @2) ))  ;; числитель=знаменатель
                 (cond ((= denom 1) (go @3) ))    ;; знаменатель=1 - целое
                 (cond ((> num denom)             ;; дробь неправильная
                        (prog nil                 ;; печатаем целую часть
                          (print (\ num denom))
                          (setq num (% num denom))
                        )
                       )
                 )
                 (prints "(")                     ;; печатаем дробную часть
                 (print num)
                 (prints "/")
                 (print denom)
                 (prints ")")
                 (go @Exit)
          @1     (print 0)
                 (go @Exit)
          @2     (print 1)
                 (go @Exit)
          @3     (print num)
          @Exit  (return x)                
               )  
             )
       )
                   
) 

==> ratPrint

(ratPrint (ratCreate 1 2))

(1/2)

==> (RATIONAL 1 2)

(ratPrint (ratCreate 45 75))

(3/5)

==> (RATIONAL 3 5)

(ratPrint (ratCreate 6 1))

6

==> (RATIONAL 6 1)

А вот и остальные функции манипулирования рациональными числами:


;;
;; Сложить две дроби
;;

(defun ratAdd (x y)
       (cond ((<> (car x) 'RATIONAL) (raiseerror "ratAdd: Не дробь"))
             ((<> (car y) 'RATIONAL) (raiseerror "ratAdd: Не дробь")) 
             (T (cons 'RATIONAL 
                  (simplify (list (+ (* (caddr y) (cadr x))
                                     (* (caddr x) (cadr y))
                                  )
                                  (* (caddr x) (caddr y))
                            )
                  )
                )
             )
       )
)

;;
;; Вычесть две дроби
;;

(defun ratSub (x y) 
       (cond ((<> (car x) 'RATIONAL) (raiseerror "ratSub: Не дробь"))
             ((<> (car y) 'RATIONAL) (raiseerror "ratSub: Не дробь")) 
             (T (cons 'RATIONAL 
                  (simplify (list (- (* (caddr y) (cadr x)) 
                                     (* (caddr x) (cadr y))
                                   )
                                   (* (caddr x) (caddr y))
                            )
                  )
                )
             )
       )
)

;;
;; Перемножить дроби
;;

(defun ratMult (x y) 
       (cond ((<> (car x) 'RATIONAL) (raiseerror "ratMult: Не дробь"))
             ((<> (car y) 'RATIONAL) (raiseerror "ratMult: Не дробь")) 
             (T (cons 'RATIONAL
                  (simplify (list (* (cadr x) (cadr y))
                                  (* (caddr x) (caddr y))
                            )
                  )                               
                )
             ) 
       )
)

;;
;; Разделить дроби
;;

(defun ratDiv (x y) 
       (cond ((<> (car x) 'RATIONAL) (raiseerror "ratDiv: Не дробь"))
             ((<> (car y) 'RATIONAL) (raiseerror "ratDiv: Не дробь")) 
             (T (cons 'RATIONAL
                  (simplify (list (* (cadr x) (caddr y))
                                  (* (caddr x) (cadr y))
                            )
                   )                               
                 )
              ) 
       )
)

;;
;; Обратить дробь
;;

(defun ratInv (x) 
       (cond ((<> (car x) 'RATIONAL) (raiseerror "ratInv: Не дробь"))
             (T (cons 'RATIONAL 
                  (simplify (list (caddr x)
                                  (cadr x)
                            )
                  )
                )
             )
       )
)

;;
;; Из рационального в плавающее
;;

(defun rat2flo (x)
       (cond ((<> (car x) 'RATIONAL)(raiseerror "rat2flo: Не дробь"))
             (T (/ (cadr x) (caddr x)))
       )
)

;;
;; Модуль дроби
;;

(defun ratAbs (x)
       (cond ((<> (car x) 'RATIONAL)(raiseerror "ratAbs: Не дробь"))
             (T (cons 'RATIONAL 
                  (list (abs (cadr x)) 
                        (caddr x)
                  )
                )
             )                
       )
)




Следует обратить внимание на то, что функция деления дробей не анализирует случай деления на нуль. В этом нет необходимости, поскольку соответствующую ситуацию "отлавливает" функция simplify.

Мы построили вполне корректную рациональную арифметику, причем, достаточно скромными средствами.

Комплексные числа

Прежде, чем строить систему комплексных чисел, напомним их математическое определение. Комплексным числом будем называть упорядоченную пару вещественных чисел (a , b). Две таких пары (a1 , b1) и (a2 , b2) будем считать равными в том и только в том случае, когда a1 = a2 и b1 = b2.

Теперь введем на множестве пар естественные алгебраические операции сложение и умножение.

Суммой комплексных чисел (a1 , b1) и (a2 , b2) будем называть новое комплексное число (с , d), такое, что:

c = a1 + a2
d = b1 + b2

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

Произведением комплексных чисел (a1 , b1) и (a2 , b2) будем называть новое комплексное число (с , d), такое, что:

c = a1 * a2 - b1 * b2
d = a1 * b2 + a2 * b2

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

Рассмотрим теперь пары вида (a , 0). Легко убедиться, что сумма и произведение таких пар тоже имеет вид (a , 0). Причем, произведение пар (x , 0) и (y , 0) равно (xy , 0), а сумма - (x+y , 0). Кроме того, произведение пары (a , 0) на произвольную пару (x , y) даст в результате пару (ax , ay). Все это позволяет отождествить пары вида (a , 0) с вещественными числами.

А теперь рассмотрим комплексное число (0 , 1). Легко убедиться, что квадрат этого числа (в смысле определенного выше умножения) равен числу (-1 , 0). Последнее число мы договорились отождествить с обычным вещественным числом -1. Число (0 , 1) в математике обозначается символом i. Таким образом, оказывается верным равенство:

i2 = -1

Кроме того, произвольное комплексное число (a , b) можно представить в виде: a + b*i, где a - сокращенная запись числа (a , 0), а b - сокращенная запись числа (b , 0).

Для произвольного комплексного числа X = (a , b) вещественное число a называется действительной частью X (обозначается Re(X)); а вещественное число b называется мнимой частью X (обозначается Im(X)).

Для произвольного комплексного числа X = (a , b) вещественное число r = (a2 + b2)1/2 называется модулем комплексного числа, а число fi = arctg(b/a) - его аргументом. С использованием модуля и аргумента любое комплексное число может быть представлено в эквивалентной тригонометрической форме:

(a , b) = r*(cos(fi) + i * sin(fi))

При возведении комплексного числа в целую степень имеет место замечательное соотношение (формула Муавра):

(a , b)n = (rn)*(cos(n*fi) + i * sin(n*fi))

Здесь n - целый показатель степени. Сопряженным к произвольному комплексному числу (a , b) будем называть число (a , -b). Легко убедиться, что для произвольного (a , b) имеет место:

(a , b)*(a , -b) = a2 + b2

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

После этого математического введения построить систему комплексных чисел на Лиспе будет совсем просто. Как и в случае рациональных чисел, будем моделировать комплексное число списком из трех элементов. Первый элемент этого списка - всегда атом COMPLEX - признак комплексного числа; два последующих элемента представляют собой действительную и мнимую части комплексного числа. Снова, как и в случае рациональных чисел, самой сложной функцией будет функция вывода комплексного числа. Остальные функции реализуются достаточно элементарно. Имена всех функций манипулирования комплексными числами будут начинаться с префикса "cplx".

Вот как выглядит функция cplxCreate - создать комплексное число:


;;
;;  Создать комплексное число
;;

(defun cplxCreate (x y) 

        (cond ((not (numberp x)) (raiseerror "cplxCreate: нечисловой аргумент"))
              ((not (numberp y)) (raiseerror "cplxCreate: нечисловой аргумент"))
              (T (cons 'COMPLEX (list (+ x 0.0) (+ y 0.0))))
        )
)

==> cplxCreate

Функция проверяет, чтобы значения аргументов были числами (типа FIXED или FLOAT). В теле функции сложение значений аргументов с числом 0.0 приводит к тому, что в списке действительная и мнимая часть хранятся как числа с плавающей точкой.

Как и при реализации рациональной арифметики, самой громоздкой функцией является функция печати комплексного числа. Тут важно предусмотреть печать комплексного числа без мнимой части, как действительного; чисто мнимого комплексного числа - без нулевой действительной части; у мнимой части не выводить коэффициент 1 при мнимой части. Собирая все вместе, получим:


;;
;;  Печать
;;

(defun cplxPrint (x) 
       (cond ((<> (car x) 'COMPLEX) (raiseerror "cplxPrint: неверен тип аргумента"))
             (T
                (prog (re im)

                  (setq re (cadr x))
                  
                  (setq im (caddr x))

                  (cond ((and (<= (abs re) 1.0E-15) (<= (abs im) 1.0E-15)) (go @PrZ)))

                  (cond ((and (> (abs re) 1.0E-15) (<= (abs im) 1.0E-15)) (go @PrR))) 

                  (cond ((and (<= (abs re) 1.0E-15) (> (abs im) 1.0E-15)) (go @PrI))) 

                  (print re)

                  (cond ((> im 0.0)
                           (prog nil
                               (prints "+")
                               (cond ((> (abs (- im 1)) 1.0E-15) (prog nil  (print im))))
                               (prints "J")
                           )
                        )
                        ((< im 0.0)
                           (prog nil
                               (prints "-") 
                               (setq im (abs im))
                               (cond ((> (abs (- im 1)) 1.0E-15) (prog nil  (print im))))
                               (prints "J")
                           )
                        )
                  )
                  
                  (go @Ret)

     @PrZ         (print 0)  (go @Ret)
     @PrR         (print re) (go @Ret)   
     @PrI          
                  (cond ((> im 0.0)
                           (prog nil
                               
                               (cond ((> (abs (- im 1)) 1.0E-15) (prog nil (print im))))
                               (prints "J")
                           )
                        )
                        ((< im 0.0)
                           (prog nil
                               (prints "-") 
                               (setq im (abs im))
                               (cond ((> (abs (- im 1)) 1.0E-15) (prog nil  (print im))))
                               (prints "J")
                           )
                        )
                  )

     @Ret         (return x)

                ) 
             )
       ) 
)

==> cplxPrint

Реализация остальных функций выглядят достаточно просто:


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

(defun cplxRe (x) (cond ((<> (car x) 'COMPLEX) 
                        (raiseerror "cplxRe: неверен тип аргумента"))
                        (T (cadr x))
                  )
)

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

(defun cplxIm (x) (cond ((<> (car x) 'COMPLEX)
                        (raiseerror "cplxIm: неверен тип аргумента"))
                        (T (caddr x))
                  )
)

;;
;;  Сопряжение
;;

(defun cplxConj (x) (cond ((<> (car x) 'COMPLEX) 
                           (raiseerror "cplxConj: неверен тип аргумента"))
                          (T (cons 'COMPLEX (list (cadr x) (- (caddr x))))
                          )
                  )
)

;;
;; Модуль
;;

(defun cplxAbs (x) (cond ((<> (car x) 'COMPLEX) 
                          (raiseerror "cplxAbs: неверен тип аргумента"))
                         (T (sqr (+ (* (cadr x) (cadr x)) (* (caddr x) (caddr x)))))  
                   )
)

;;
;; Аргумент
;;

(defun cplxArg (x) (cond
                      ((<> (car x) 'COMPLEX)
                       (raiseerror "cplxArg: неверен тип аргумента"))
                      (T 
                        (cond ((<= (abs (cadr x)) 0.1E-16) (* 0.5 _Pi (sign (caddr x))))
                               (T (atn (/ (caddr x) (cadr x))))
                         )
                       )  
                   )
)

;;
;;  Сложение 
;;

(defun cplxAdd (x y) (cond ((<> (car x) 'COMPLEX) 
                            (raiseerror "cplxAdd: неверен тип аргумента"))
                           ((<> (car y) 'COMPLEX) 
                            (raiseerror "cplxAdd: неверен тип аргумента"))
                           (T (cplxCreate (+ (cadr x) (cadr y)) (+ (caddr x) (caddr y))))
                     ) 
)

;;
;;  Вычитание 
;;

(defun cplxSub (x y) (cond ((<> (car x) 'COMPLEX) 
                            (raiseerror "cplxSub: неверен тип аргумента"))
                           ((<> (car y) 'COMPLEX) 
                            (raiseerror "cplxSub: неверен тип аргумента"))
                           (T (cplxCreate (- (cadr x) (cadr y)) (- (caddr x) (caddr y))))
                     ) 
)

;;
;;  Умножение 
;;

(defun cplxMult (x y) (cond ((<> (car x) 'COMPLEX) 
                             (raiseerror "cplxMult: неверен тип аргумента"))
                           ((<> (car y) 'COMPLEX) 
                             (raiseerror "cplxMult: неверен тип аргумента"))
                           (T (cplxCreate (- (* (cadr x) (cadr y)) (* (caddr x) (caddr y)))
                                          (+ (* (cadr x) (caddr y)) (* (caddr x) (cadr y))))
                           )                            
                     ) 
)

;;
;;  Деление
;;

(defun cplxDiv (x y) (cond ((<= (cplxAbs y) 0.1E-15)
                            (raiseerror "cplxDiv: Деление на нуль"))
                           (T
                              (prog (d Z)
                                (setq d (+ (* (cadr y) (cadr y)) (* (caddr y) (caddr y))))
                                (setq Z (cplxMult x (cplxConj y)))
                                (return (cons 'COMPLEX (list (/ (cadr Z) d) (/ (caddr z) d)))) 
                              )
                           )
                     )  
)

;;
;; Возведение в степень (формула Муавра)
;;

(defun cplxPow (x n)

       (cond ((or (<> (car x) 'COMPLEX)
                  (Not (fixedp n)))
                  (raiseerror "cplxPow: неверен тип одного из аргументов")
              )
             (T
               (prog (rr fi)
                  (setq rr (cplxAbs x))
                  (setq fi (cplxArg x))
                  (return  (cplxCreate (* (^ rr n) (cos (* fi n))) (* (^ rr n) (sin (* fi n)))))     
               )
             )
       )  
)

Снова, как и в случае рациональных чисел, мы без особого напряжения построили алгебру комплексных чисел. Читатель может убедиться, что функции корректно работают. Некоторое удивление может вызвать результат возведения числа в степень:


(cplxPrint (cplxPow (cplxCreate 0 1) 2))
-1.0-6.98296672221876E-15J
==> (COMPLEX -1.0 -6.98296672221876E-15)

Результат вызова (cplxCreate 0 1) есть просто мнимая единица (J). Возведение мнимой единицы в квадрат должно дать -1. У результата, приведенного выше, действительная часть действительно равна -1, а мнимая часть есть очень маленькая величина, но не нуль. Причина заключается в погрешности при вычислении тригонометрических функций (sin и cos).

Векторы и матрицы

n-мерным вектором над полем действительных чисел называется упорядоченный набор из n чисел вида:

(x1, x2, ... , xn)

Числа x1, x2 и т.д. называются координатами вектора. Два вектора считаются равными тогда и только тогда, когда они имеют одинаковую размерность (число координат) и при всех i от 1 до n i-я первого вектора равна i-й координате второго вектора.

С векторами можно выполнять различные действия. Простейшими из этих действий являются сложение векторов и умножение вектора на действительное число.

Суммой двух векторов одной и той же размерности называется вектор, координаты которого получаются сложением соответствующих координат первого и второго векторов. Так, если заданы два вектора:

(x1, x2, ... , xn)

и

(y1, y2, ... , yn)

то их суммой будет вектор с координатами:

((x1+y1), (x2+y2), ... , (xn+yn) )

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

Несколько более сложной операцией является скалярное произведение векторов. По определению скалярное произведение векторов

(x1, x2, ... , xn)

и

(y1, y2, ... , yn)

есть вещественное число, вычисляемое следующим образом:

(x1*y1) + (x2*y2) + ... + (xn*yn)

Модулем (или длиной) вектора называется квадратный корень из суммы квадратов координат вектора.

Как хорошо известно, векторы с двумя компонентами можно естественным образом отождествить с векторами на плоскости, а векторы с тремя компонентами - с векторами в пространстве. Теорема Пифагора показывает, что для векторов на плоскости и в пространстве модуль вектора совпадает с его обычной евклидовой длиной. Можно также убедиться, что скалярное произведение вектров есть произведение их модулей на косинус угла между ними.

Прямоугольной матрицей размерности (n*m) называется прямоугольная таблица вещественных чисел:

x1,1 x1,2 ... x1,m
x2,1 x2,2 ... x2,m
... ... ... ...
xn,1 xn,2 ... xn,m

Если количество строк матрицы равно количеству столбцов, то матрица называется квадратной. Две матрицы одинаковой размерности:

x1,1 x1,2 ... x1,m
x2,1 x2,2 ... x2,m
... ... ... ...
xn,1 xn,2 ... xn,m

и

y1,1 y1,2 ... y1,m
y2,1 y2,2 ... x2,m
... ... ... ...
yn,1 yn,2 ... yn,m

равны в том и только в том случае, когда при всех (1 <= i <= n) и (1 <= j <= m) имеет место xi,j=yi,j.

Суммой (разностью) двух матриц одинаковой размерности называется матрица, элементы которой вычисляются "покоординатным" сложением (вычитанием) элементов исходных матриц. Для приведенных выше матриц матричная сумма будет новой матрицей, элементы которой вычисляются в соответствии с соотношением: zi,j=xi,j + yi,j, а разностью - матрица, с элементами wi,j=xi,j - yi,j.

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

А вот произведение матриц определяется заметно сложнее, чем описанные выше операции.

Продолжение следует...
Сайт создан в системе uCoz