Перейти к главе: Начало 1 2 3 4 A B C Bib Ind
 [Начало книги]  [Содержание]   [Предыдущая глава]   [Следующая глава] 

3 Структуры данных в GAP
 3.1 Константы и операторы
 3.2 Переменные и присваивания
 3.3 Функции
 3.4 Списки
 3.5 Тождественность и равенство списков
 3.6 Множества
 3.7 Векторы и матрицы
 3.8 Записи
 3.9 Арифметические прогрессии
 3.10 Использование циклов
 3.11 Дальнейшие операции со списками
 3.12 Функции

3 Структуры данных в GAP

3.1 Константы и операторы

Основные принципы задания констант и действий над ними видны из следующих примеров:

Арифметические вычисления:


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"

3.2 Переменные и присваивания

Порядок присваивания демонстрируется следующим примером:


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.

3.3 Функции

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.

3.4 Списки

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


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; 
Error, 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 ] 

3.5 Тождественность и равенство списков

Для изучения способов управления сложными структурами данных в 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; 
[ ~ ] 

3.6 Множества

Множествами в 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, но они не возвращают результат, а заменяют им первый аргумент.

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

Вектор является не содержащим пробелов списком элементов, принадлежащих общему полю.


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 ] ] 

Первая пара скобок указывает выбранные строки, вторая - столбцы.

3.8 Записи

Другой способ создания новых структур данных - записи. Как и списки, записи - наборы других объектов (которые называются компонентами, или полями), обращение к которым происходит не по номеру, а по имени.


gap> date:= rec(year:=1992, month:="Jan", day:=13);
rec( day := 13, month := "Jan", year := 1992 )

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


gap> date.year; 
1992 
gap> date.time:=rec(hour:=19,minute:=23,second:=12); 
rec( hour := 19, minute := 23, second := 12 )
gap> date; 
rec( day := 13, month := "Jan",
  time := rec( hour := 19, minute := 23, second := 12 ), year := 1992 )

Для определения, является ли объект записью, применяется функция IsRecord. Структуру записи можно получить с помощью функции RecNames:


gap> RecNames(date); 
[ "time", "year", "month", "day" ]

Упражнение. Что происходит в результате выполнения команд:


gap> r:= rec(); 
rec( 
   ) 
gap> r:= rec(r:= r); 
rec( 
  r := rec( 
       ) ) 
gap> r.r:= r; 
rec( 
  r := ~ ) 

3.9 Арифметические прогрессии

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


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 ] 

3.10 Использование циклов

Пример 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; 

3.11 Дальнейшие операции со списками

Существует более удобный способ умножения элементов списка из чисел или подстановок.


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 ] 

3.12 Функции

Ранее было показано, как обратиться к библиотечным, т.е. стандартным функциям 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, но уже с другими аргументами. Однако для быстродействия программы предпочтительнее избегать рекурсивных процедур, если только можно без них обойтись.

Упражнение: Предложить решение последней задачи, не используя рекурсивные процедуры.

 [Начало книги]  [Содержание]   [Предыдущая глава]   [Следующая глава] 
Перейти к главе: Начало 1 2 3 4 A B C Bib Ind

generated by GAPDoc2HTML