Комп’ютерна алгебра (стр. 5 )

У наступному прикладі зміна списку приводить до виконання команд для нових його елементів:

gap> l := [ 1, 2, 3, 4, 5, 6 ];;
gap> for i in l do
> Print( i " " );
> if i mod 2 = 0 then Add( l, 3*i/2 ); fi;
> od; Print( "\n" );
9 9
gap> l;
[ 1, 2, 3, 4, 5, 6, 3, 6, 9, 9 ]

А в наступному - не приводить:

gap> l := [ 1, 2, 3, 4, 5, 6 ];;
gap> for i in l do
> Print( i " " );
> l := [];
> od; Print( "\n" );

gap> l;
[ ]

Тепер розглянемо два варіанти циклу FOR, що залишилися:

for variable in iterator do statements od;
for variable in object do statements od;

Для цього необхідно спочатку ввести деякі поняття, що характеризують об'єкти, з якими працює GAP.

Кожен об'єкт має свій тип. Тип об'єкту - це інформація, яка використовується для того, щоб вирішити, чи застосовна до об'єкту дана операція, і, для вибору методу її застосування у разі позитивної відповіді. Наприклад, тип двох об'єктів визначає, чи можуть вони бути помножені один на одного, і якщо так, то яким способом. Аналогічно, тип об'єкту визначає, чи може бути обчислений порядок (розмір) цього об'єкту, і якщо так, то як.

Тип об'єкту складається з двох основних частин, що характеризують різні аспекти об'єкту, а саме з сімейства, до якого він належить, і з набору фільтрів.

Сімейство визначає відношення даного об'єкту до інших об'єктів. Наприклад, сімейство утворюють всі підстановки. Інший приклад сімейства - сімейство всіх колекцій (collections), підстановок. Останнє сімейство містить безліч всіх груп підстановок як підмножина. Третій приклад - сімейство всіх раціональних функцій з коефіцієнтами з деякого сімейства.

Фільтр можна описати як послідовність true і false, що характеризує відповідні параметри даного типу об'єктів (наприклад, Isabelian, Isprime, Isgroup і тому подібне). Хоча при виборі методу фільтри не розрізняються по їх походженню і застосуванню, їх можна класифікувати (з невеликими виключеннями) на категорії, уявлення, властивості, а також тестери атрибутів.

Набор елементів, лежачих в одному сімействі, називається колекцією. Прикладами колекцій є однорідні списки, а також домени (domain) - так в GAP називаються множини з додатковою структурою, наприклад, група, клас зв'язаних елементів, векторний простір і так далі

Хай тепер C - колекція. Тоді ітератор Iterator(C) дозволяє організувати перебір всіх елементів цієї колекції без повторень. В цьому випадку цикл FOR еквівалентний наступному циклу:

while not Isdoneiterator(iterator) do
variable := Nextiterator(iterator)
statements
od;

Якщо ж D - домен, то результат виконання циклу вигляду

for variable in domain do

має бути таким же, як результат виконання циклу вигляду

for variable in Aslist(D) do

Якщо в циклі FOR об'єкт object не є списком або ітератором, то обчислюватиметься Iterator(object). Якщо це обчислення буде успішним, то буде реалізований перебір по ітератору.

gap> g := Group((1,2,3,4,5),(1,2)(3,4)(5,6));
Group([ (1,2,3,4,5), (1,2)(3,4)(5,6) ])
gap> count := 0;; sumord := 0;;
gap> for x in g do
> count := count + 1; sumord := sumord + Order(x); od;
gap> count;
120
gap> sumord;
471

Така конструкція використовує набагато менше пам'яті, оскільки ітератор може бути набагато компактнішим, ніж список всіх елементів.

З циклу FOR можна вийти до його виконання, використовуючи оператора break. Це особливо ефективно в комбінації з циклом по ітератору, наприклад, для пошуку елементу з потрібною властивістю в деякому домені. Цей оператор може бути використаний тільки усередині циклу.gap> g := Group((1,2,3,4,5),(1,2)(3,4)(5,6));
Group([ (1,2,3,4,5), (1,2)(3,4)(5,6) ])
gap> for x in g do
> if Order(x)= 3 then
> break;
> fi; od;
gap> x;
(1,4,3)(2,6,5)

Оператора continue відміняє виконання частини циклу, що залишилася, і переходить відразу у виконанню следющей ітерації. Цей оператор також може бути використаний тільки усередині циклу.

gap> g := Group((1,2,3),(1,2));
Group([ (1,2,3), (1,2) ])
gap> for x in g do
> if Order(x)= 3 then
> continue;
> fi; Print(x,"\n"); od;
()
(2,3)
(1,3)
(1,2)

2.14 Функції

Формат:

function ( [ arg-ident {, arg-ident} ] )
[ local loc-ident {, loc-ident} ; ]
statements
end

Приклад функції, яка визначає n-е число Фібоначчі:

gap> fib := function ( n )
> local f1, f2, f3, i;
> f1 := 1; f2 := 1;
> for i in [3..n] do
> f3 := f1 + f2; f1 := f2; f2 := f3;
> od;
> return f2;
> end;;
gap> List( [1..10], fib );
[ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]

Ту ж функцію можна визначити рекурсивно:

gap> fib := function ( n )
> if n < 3 then
> return 1;
> else
> return fib(n-1)+ fib(n-2);
> fi;
> end;;
gap> List( [1..10], fib );
[ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]

Відмітимо, що рекурсивна версія вимагає 2 * fib(n)-1 кроків для обчислення fib(n), тоді як ітеративна вимагає тільки n-2 кроку.

Обидві, проте, не є оптимальними, оскільки бібліотечна функція Fibonacci вимагає порядку Log(n) кроків.

Запис arg-ident -> expr є коротким записом для функції

function ( arg-ident ) return expr; end

Тут arg-ident - один ідентифікатор, тобто таким чином не можна задати функцію від декількох змінних.

Приклад типового використання такого запису:

gap> Sum( List( [1..100], x -> x^2 ));
338350

3 СТРУКТУРИ ДАНИХ

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

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

Приклад 1:

gap> 12345/25;
2469/5
gap> -3;;
-3
-6
gap> 3^132;

Приклад 2 (операції з підстановками):

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)

Приклад 3 (завдання рядка):

gap> 'a';
'a'

3.2 Змінні і привласнення

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

Приклад 1:

gap> a:=* (5 + 6);
22
gap> а;
22
gap> a:= 10;
10
gap> а * (а + 1);
110

Примітка 1. Після привласнення привласнене значення відображається в наступному рядку виводу. Це можна подавити, якщо завершити команду двома знаками ";" замість одного:

gap> w:= 2;;

Примітка 2. Всякий раз, коли GAP повертає значення, друкуючи його в наступному після команди рядку, це значення привласнюється змінною з ім'ям last :

gap>* (5 + 6);
22
gap> a:= last;
22