Основные принципы задания констант и действий над ними видны из следующих примеров:
Арифметические вычисления:
gap> 12345/25; 2469/5 gap> -3; 17 - 23; -3 -6 gap> 3^132; 955004950796825236893190701774414011919935138974343129836853841 |
Действия с подстановками:
gap> (1,2,3); (1,2,3) gap> (1,2,3) * (1,2); (2,3) gap> (1,2,3)^-1; (1,3,2) gap> 2^(1,2,3); 3 gap> (1,2,3)^(1,2); (1,3,2) |
Задание символьных констант:
gap> 'a'; 'a' gap> "abc"; "abc" |
Порядок присваивания демонстрируется следующим примером:
gap> a:= (9 - 7) * (5 + 6); 22 gap> a; 22 gap> a:= 10; 10 gap> a * (a + 1); 110 |
Примечание 1. После присваивания присвоенное значение отображается в следующей строке вывода. Это можно подавить, если завершить команду двумя знаками ; вместо одного:
gap> w:= 2;; |
Примечание 2. Всякий раз, когда GAP возвращает значение, печатая его в следующей после команды строке, это значение присваивается переменной с именем last:
gap> (9 - 7) * (5 + 6); 22 gap> a:= last; 22 |
Аналогичным образом определяются переменные last2 и last3.
GAP содержит более 4000 стандартных функций. Пример обращения к нескольким из них приведен ниже:
gap> Factorial(17); 355687428096000 gap> Gcd(1234, 5678); 2 gap> Print(1234, "\n"); 1234 |
Кроме того, пользователь может вводить собственные функции. Наиболее просто это делается так:
gap> cubed:= x -> x^3; function( x ) ... end gap> cubed(5); 125 |
Другой способ определения функций и процедур изложен в пунктах 2.14 и 3.12. Рекомендации по разработке программ на языке GAP содержатся в Приложении A.
Список является заключенным в квадратные скобки набором объектов, разделенных запятыми. Например, список из первых десяти простых чисел можно задать следующим образом:
gap> primes:=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]; [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ] |
Затем к нему можно добавить следующие два простых числа:
gap> Append(primes, [31, 37]); gap> primes; [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 ] |
Если добавляется только один элемент, это можно сделать и по-другому:
gap> Add(primes, 41); gap> primes; [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 ] |
Указать отдельный элемент списка можно по его номеру в списке:
gap> primes[7]; 17 |
Этот же механизм позволяет присвоить значение существующему или новому элементу списка (функция Length определяет длину списка):
gap> Length(primes); 13 gap> primes[14]:= 43; 43 gap> primes; [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 ] |
При этом значение не обязательно должно присваиваться следующему элементу списка. Например, если двадцатым простым числом является 71, мы можем сразу присвоить значение 71 двадцатому элементу списка primes, пропуская недостающие элементы. Полученный список будет иметь длину 20:
gap> primes[20]:= 71; 71 gap> primes; [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,,,,,, 71 ] gap> Length(primes); 20 |
Список должен быть создан перед заданием его элемента (например, быть пустым списком [ ] ):
gap> lll[1]:= 2; Variable: 'lll' must have a value gap> lll:= [];; gap> lll[1]:= 2; 2 |
Функция Position возвращает номер первого элемента списка, имеющего заданное значение. Если в списке нет элемента с заданным значением, функция возвращает false:
gap> Position(primes, 17); 7 gap> Position(primes, 20); fail |
Заметим, что при всех приведенных выше изменениях списка primes длина списка изменялась автоматически. Функция IsBound для списков показывает, содержит ли список элемент с заданным номером (для записей - содержит ли запись указанное поле):
gap> k:= [ , 2, 3, , 5, , 7, , , , 11 ];; gap> IsBound(k[7]); IsBound(k[4]); IsBound(k[20]); true false false |
Список может состоять из объектов различных типов, например:
gap> lll:= [true, "This is a String",,, 3]; [ true, "This is a String",,, 3 ] |
Далее, список может являться частью другого списка:
gap> lll[3]:= [4,5,6];; gap> lll; [ true, "This is a String", [ 4, 5, 6 ],, 3 ] |
и даже частью самого себя:
gap> lll[4]:= lll; [ true, "This is a String", [ 4, 5, 6 ], ~, 3 ] |
Здесь знак ~ в четвертой позиции обозначает объект, вывод которого на экран (печать) производится в данный момент. Строки являются частным случаем списков, и печатаются без разделителей. Примеры задания строк и операций над ними:
gap> s1:=['H','e','l','l','o',' ','w','o','r','l','d','.']; "Hello world." gap> s2 := "Hello world."; "Hello world." gap> s1 = s2; true gap> s2[7]; 'w' |
Извлечение и изменение подмножеств списка производит оператор { }:
gap> sl := lll{ [ 1, 2, 3 ] };
[ true, "This is a String", [ 4, 5, 6 ] ]
gap> sl{ [ 2, 3 ] } := [ "New String", false ];
[ "New String", false ]
gap> sl;
[ true, "New String", false ]
|
Для изучения способов управления сложными структурами данных в GAP важно понимать различия между тождественными и равными объектами. В данном разделе это различие демонстрируется на примере списков. Аналогичные примеры могут быть подобраны и для записей.
Два списка равны (т.е. оператор сравнения = возвращает true) тогда и только тогда, когда они имеют одинаковую длину и их соответствующие элементы равны.
gap> numbers:= primes; [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,,,,,, 71 ] gap> numbers = primes; true |
Теперь изменим список numbers и снова сравним его с primes:
gap> primes[3]:= 4; 4 gap> numbers = primes; true |
Оказывается, что списки numbers и primes снова равны, а распечатав список primes, мы увидим, что primes[3]=4. Это объясняется тем, что списки primes и numbers не только равны, но и идентичны. Идентификаторы primes и numbers указывают на один и тот же список, и изменения в нем происходят при указании любого из его имен. Присваивание numbers:= primes создает не новый список, а только новое имя для уже существующего списка.
Если необходимо изменить список, совпадающий по содержанию с primes таким образом, чтобы сам список primes при этом не изменился, необходимо создать копию списка primes с помощью функции ShallowCopy (в следующем примере предварительно восстановим старое значения primes):
gap> primes[3]:= 5; 5 gap> primes; [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,,,,,, 71 ] gap> numbers:= ShallowCopy(primes); [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,,,,,, 71 ] gap> numbers = primes; true gap> numbers[3]:= 4; 4 gap> numbers = primes; false |
Примечание. Единственными объектами, которые могут быть изменены таким способом, являются списки и записи, т.к. только эти объекты в GAP могут состоять из других объектов. Например, после выполнения следующих команд значения i и j будут соответственно равны 2 и 1:
gap> i:= 1;; j:= i;; i:= i+1;; |
Упражнение. Объяснить, что происходит в результате выполнения команд:
gap> l:= []; [ ] gap> l:= [l]; [ [ ] ] gap> l[1]:= l; [ ~ ] |
Множествами в GAP называются списки специального вида. Элементы множества расположены последовательно (т.е. не содержат пробелов, как, например, список [ 2, 3, 5, , , , , , , , 31, 37, 41 ]), упорядочены (порядок сортировки GAP определяет самостоятельно) и встречаются в списке только один раз. Множества, как и списки, могут содержать объекты различных типов.
Проверить, является ли объект множеством, можно с помощью функции IsSet. Для каждого списка существует соответствующее ему множество, получаемое с помощью функции Set.
gap> fruits:=["apple", "strawberry", "cherry", "plum", "apple"];; gap> IsSet(fruits); false gap> fruits:= Set(fruits); [ "apple", "cherry", "plum", "strawberry" ] |
Заметим, что при этом исходный список fruits был изменен.
Для проверки принадлежности объекта множеству используется оператор in. Его также можно использовать для проверки принадлежности к списку, однако в первом случае проверка выполняется быстрее, т.к. сортировка позволяет использовать двоичный поиск вместо последовательного перебора.
gap> "apple" in fruits; true gap> "banana" in fruits; false |
Добавить к множеству новый элемент можно с помощью функции AddSet (обратите внимание на порядок следования элементов):
gap> AddSet(fruits, "banana"); gap> fruits; [ "apple", "banana", "cherry", "plum", "strawberry" ] gap> AddSet(fruits, "apple"); gap> fruits; # 'fruits' не изменилось [ "apple", "banana", "cherry", "plum", "strawberry" ] |
Пересечение, объединение и разность множеств определяются с помощью функций Intersection, Union и Difference. При этом аргументы могут быть обычными списками, тогда как результат всегда будет являться множеством.
gap> breakfast:= ["tea", "apple", "egg"]; [ "tea", "apple", "egg" ] gap> Intersection(breakfast, fruits); [ "apple" ] gap> Difference(breakfast,fruits); [ "egg", "tea" ] |
Те же операции над множествами производят функции IntersectSet, UniteSet и RemoveSet, но они не возвращают результат, а заменяют им первый аргумент.
Вектор является не содержащим пробелов списком элементов, принадлежащих общему полю.
gap> v:= [3, 6, 2, 5/2]; [ 3, 6, 2, 5/2 ] gap> IsRowVector(v); true |
Векторы умножаются на скаляры из любого поля, содержащего данное. Умножение двух векторов равной длины дает их скалярное произведение.
gap> 2 * v; [ 6, 12, 4, 5 ] gap> v * 1/3; # это эквивалентно команде v/3; [ 1, 2, 2/3, 5/6 ] gap> v * v; # скалярное произведение v на себя 221/4 |
Матрица - список векторов одинаковой длины, не содержащий пробелов:
gap> m:= [[1, -1, 1], > [2, 0, -1], > [1, 1, 1]]; [ [ 1, -1, 1 ], [ 2, 0, -1 ], [ 1, 1, 1 ] ] gap> m[2][1]; 2 |
Матрицы можно умножать на скаляры, векторы и другие матрицы (при этом умножение обобщается и возможно также при несответствии размеров):
gap> m:= [[1, 2, 3, 4], > [5, 6, 7, 8], > [9,10,11,12]]; [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ] ] gap> Display(m); [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ] ] gap> [1, 0, 0, 0] * m; [ 1, 2, 3, 4 ] gap> [1, 0, 0] * m; [ 1, 2, 3, 4 ] gap> m * [1, 0, 0]; [ 1, 5, 9 ] gap> m * [1, 0, 0, 0]; [ 1, 5, 9 ] gap> m * [0, 1, 0, 0]; [ 2, 6, 10 ] |
Заметим, что умножение вектора на матрицу приводит к линейной комбинации строк матрицы, тогда как умножение матрицы на вектор приводит к линейной комбинации ее столбцов. В последнем случае вектор рассматривается как вектор-столбец.
Подматрицы извлекаются или изменяются с помощью фигурных скобок:
gap> sm := m{ [ 1, 2 ] }{ [ 3, 4 ] };
[ [ 3, 4 ], [ 7, 8 ] ]
gap> sm{ [ 1, 2 ] }{ [2] } := [[1],[-1]];
[ [ 1 ], [ -1 ] ]
gap> sm;
[ [ 3, 1 ], [ 7, -1 ] ]
|
Первая пара скобок указывает выбранные строки, вторая - столбцы.
Другой способ создания новых структур данных - записи. Как и списки, записи - наборы других объектов (которые называются компонентами, или полями), обращение к которым происходит не по номеру, а по имени.
gap> date:= rec(year:=1992, month:="Jan", day:=13); rec( year := 1992, month := "Jan", day := 13 ) |
Изначально запись определяется как разделенный запятыми список присваиваний значений ее полям. Для обращения к значению соответствующего поля записи необходимо указать имя записи и имя поля, разделив их точкой. Определив запись, в дальнейшем можно добавлять к ней новые поля.
gap> date.year; 1992 gap> date.time:=rec(hour:=19,minute:=23,second:=12); rec( hour := 19, minute := 23, second := 12 ) gap> date; rec( year := 1992, month := "Jan", day := 13, time := rec( hour := 19, minute := 23, second := 12 ) ) |
Для определения, является ли объект записью, применяется функция IsRecord. Структуру записи можно получить с помощью функции RecNames:
gap> RecNames(date); [ "year", "month", "day", "time" ] |
Упражнение. Что происходит в результате выполнения команд:
gap> r:= rec();
rec(
)
gap> r:= rec(r:= r);
rec(
r := rec(
) )
gap> r.r:= r;
rec(
r := ~ )
|
Другим специальным видом списков являются целочисленные конечные арифметические прогрессии. Они описываются первым, вторым и последним элементами, разделенными соответственно запятой или двумя точками, и заключенными в квадратные скобки. Если прогрессия состоит из последовательных чисел, второй элемент может быть опущен.
gap> [1..999999]; #натуральные числа от 1 до 999999 [ 1 .. 999999 ] gap> [1,2..999999];#эквивалентно предыдущей команде [ 1 .. 999999 ] gap> [1,3..999999]; # здесь шаг равен 2 [ 1, 3 .. 999999 ] gap> Length( last ); 500000 gap> [ 999999, 999997 .. 1 ]; [ 999999, 999997 .. 1 ] |
Пример 1: вычислить произведение подстановок, являющихся элементами списка.
gap> pp:=[(1,3,2,6,8)(4,5,9), (1,6)(2,7,8)(4,9), > (1,5,7)(2,3,8,6), (1,8,9)(2,3,5,6,4), > (1,9,8,6,3,4,7,2) ];; gap> prod:= (); () gap> for p in pp do > prod:= prod * p; > od; gap> prod; (1,8,4,2,3,6,5) |
Пример 2: вычисление n! для n = 15.
gap> ff:= 1; 1 gap> for i in [1..15] do > ff:= ff * i; > od; gap> ff; 1307674368000 |
Пример 3: разложить на простые множители число 1333, используя список простых чисел primes.
gap> n:= 1333; 1333 gap> factors:= []; [ ] gap> for p in primes do > while n mod p = 0 do > n:= n/p; > Add(factors, p); > od; > od; gap> factors; [ 31, 43 ] gap> n; 1 |
Так как n=1, то процесс завершен (легко проверить, умножив 31 на 43).
Пример 4: составить список простых чисел, не превышающих 1000 (функция Unbind исключает элемент из списка).
gap> primes:= []; [ ] gap> numbers:= [2..1000]; [ 2 .. 1000 ] gap> for p in numbers do > Add(primes, p); > for n in numbers do > if n mod p = 0 then > Unbind(numbers[n-1]); > fi; > od; > od; |
Существует более удобный способ умножения элементов списка из чисел или подстановок.
gap> Product([1..15]); 1307674368000 gap> Product(pp); (1,8,4,2,3,6,5) |
Аналогичным образом работает функция Sum.
Пример 1:
Аргументами функции List является список и имя функции. В результате будут создан список значений заданной функции на элементах заданного списка. Например, для нахождения куба числа ранее была определена функция cubed. Составим с ее помощью список кубов чисел от 2 до 10.
gap> List([2..10], cubed); [ 8, 27, 64, 125, 216, 343, 512, 729, 1000 ] |
Чтобы сложить все эти величины, мы можем применить функцию Sum к последнему списку. Это же можно сделать, используя функцию cubed в качестве дополнительного аргумента функции Sum:
gap> Sum(last) = Sum([2..10], cubed); true |
Пример 2: получение списка простых чисел, меньших 30, из списка primes с помощью функции Filtered:
gap> Filtered(primes, x-> x < 30); [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ] |
Пример 3: оператор { } извлекает часть списка, определяемую номерами начального и конечного элементов списка:
gap> primes{ [1 .. 10] };
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ]
|
Ранее было показано, как обратиться к библиотечным, т.е. стандартным функциям GAP. Данный раздел посвящен разработке новых функций.
Пример 1: задать простейшую функцию, которая печатает на экране текст "hello, world!".
gap> sayhello:= function()
> Print("hello, world!\n");
> end;
function( ) ... end
|
При этом добавление к строке вывода символа \n приведет к тому, что следующее приглашение GAP появится на новой строке, а не непосредственно после напечатанного текста.
Определение функции начинается с ключевого слова function, после которого в скобках указываются формальные параметры. Скобки необходимы и в том случае, если параметры отсутствуют. Следует обратить внимание на отсутствие точки с запятой после первой команды. Определение функции завершается ключевым словом end.
Функция после ее определения является такой же переменной, как и целые числа, суммы и списки, и может быть присвоена другой переменной. Завершающий знак ";" в приведенном примере не принадлежит к определению функции, а завершает ее присвоение имени sayhello. После этого, в отличие от других присваиваний, значение функции sayhello отображается в сокращенной форме function( ) ... end, отображающей только ее формальные параметры, как наиболее интересную часть.
Полное значение sayhello может быть получено с помощью функции Print:
gap> Print(sayhello, "\n");
function ( )
Print( "hello, world!\n" );
return;
end
|
Обращение к данной функции произойдет по команде sayhello():
gap> sayhello(); hello, world! |
Однако данный пример не является типичным, так как введенная нами функция не возвращает ни одно значение, а только печатает текст.
Пример 2: задание функции, определяющей знак числа.
gap> sign:= function(n) > if n < 0 then > return -1; > elif n = 0 then > return 0; > else > return 1; > fi; > end; function( n ) ... end gap> sign(0); sign(-99); sign(11); 0 -1 1 |
Пример 3: Числа Фибоначчи определяются рекурсивно: f (1) = f (2) = 1, f (n) = f (n-1) + f (n-2).
Так как функция в GAP может обращаться сама к себе, то функция для вычисления n-го числа Фибоначчи может быть задана следующим образом:
gap> fib:= function(n) > if n in [1, 2] then > return 1; > else > return fib(n-1) + fib(n-2); > fi; > end; function( n ) ... end gap> fib(15); 610 |
Упражнение: Добавить к данной функции проверку того, что n является натуральным числом.
Пример 4: Функция gcd, вычисляющая наибольший общий делитель двух целых чисел по алгоритму Евклида, требует создания локальных переменных в дополнение к формальным параметрам. Описание локальных переменных, если они есть, должно предшествовать всем операторам, входящим в определение функции.
gap> gcd:= function(a, b) > local c; > while b <> 0 do > c:= b; > b:= a mod b; > a:= c; > od; > return c; > end; function( a, b ) ... end gap> gcd(30, 63); 3 |
Пример 5: Cоставим функцию, которая определяет количество разложений натурального числа (разложением данного числа называется невозрастающая последовательность натуральных чисел, сумма которых равна данному числу). Все множество разложений для данного числа n может быть разделено на подмножества в зависимости от максимального элемента разложения. Тогда количество разложений для n равняется сумме по всем возможным i количеств разложений для n-i, элементы которых меньше, чем i. Обобщая это, получаем, что количество разложений числа n, элементы которых меньше, чем m, является суммой (по i < m,n) количества разложений для n-i с элементами, меньшими, чем i. Отсюда получаем следующую функцию:
gap> nrparts:= function(n) > local np; > np:= function(n, m) > local i, res; > if n = 0 then > return 1; > fi; > res:= 0; > for i in [1..Minimum(n,m)] do > res:= res + np(n-i, i); > od; > return res; > end; > return np(n,n); > end; function( n ) ... end |
Желая составить функцию, которая имеет один аргумент, мы решили поставленную задачу с помощью рекурсивной процедуры с двумя аргументами. Поэтому понадобилось фактически ввести две функции. Единственной задачей одной из них является вызов другой с двумя равными аргументами.
При этом функция np является локальной по отношению к nrparts. Она могла бы быть определена и независимо, но тогда идентификатор np уже не мог бы быть использован для других целей, а если бы это все-таки произошло, функция nrparts не могла бы обратиться к функции np.
Теперь рассмотрим функцию np, имеющую две локальные переменные res и i. Переменная res используется для суммирования, i - параметр цикла. Внутри цикла опять происходит обращение к функции np, но уже с другими аргументами. Однако для быстродействия программы предпочтительнее избегать рекурсивных процедур, если только можно без них обойтись.
Упражнение: Предложить решение последней задачи, не используя рекурсивные процедуры.
generated by GAPDoc2HTML