Другой способ создания новых структур данных —
записи. Как и списки, записи —наборы других
объектов (которые называются компонентами, или
полями), обращение к которым происходит не по
номеру, а по имени.
Пример:
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 ) )
>Большинство сложных структур, с которыми
работает GAP, являются именно записями (например,
группы, групповые кольца, таблицы характеров).
GAP имеет множество стандартных функций
(аргументы которых являются записями), которые
изменяют значения существующих полей или
добавляют новые поля к своим аргументам. Так,
функция Size вычисляет размер(порядок) своего
аргумента (например, группы) и сохраняет
найденное значение в поле size. При последующем
обращении к этой функции вместо ее вычисления
будет использовано сохраненное ее значение.
Для определения, является ли объект записью,
применяется функция IsRecord. Стуктуру записи можно
получить с помощью функции RecFields:
gap> RecFields(date);
[ "year", "month", "day",
"time" ]
Упражнение. Что происходит в результате
выполнения команд:
gap> r:= rec();
rec(
)
gap> r:= rec(r:= r);
rec(
r := rec(
) )
gap> r.r:= r;
rec(
Другим специальным видом списков являются
целочисленные конечные арифметические прогрессии.
Они описываются первым, вторым и последним
элементами, разделенными соответственно запятой
или двумя точками, и заключенными в квадратные
скобки. Если прогрессия состоит из
последовательных чисел, второй элемент может
быть опущен.
Пример:
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" );
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
gap> sign("abc");
1 #strings are defined to be
greater than 0
Пример 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:
Составим функцию, которая определяет
количество разложений натурального числа
(разложением данного числа называется
невозрастающая последовательность натуральных
чисел, сумма которых равна данному числу). Все
множество разложений для данного числа 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, но уже с другими аргументами. Однако
для быстродействия программы предпочтительнее
избегать рекурсивных процедур, если только можно
без них обойтись.
Упражнение: Предложить решение последней
задачи, не используя рекурсивные процедуры.
|