Купить Matlab  |  Mathematica  |  Mathcad  |  Maple  |  Statistica  |  Другие пакеты Поиск по сайту
Internet-класс  |  Примеры  |  Методики  |  Форум  |  Download
https://hub.exponenta.ru/


Система компьютерной алгебры GAP.
А.Б.Коновалов

В начало

 

Приложение

Структуры данных
К предыдущему разделуК следующему разделу

3.8  Записи

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

Пример:

    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(

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

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

В начало страницы К предыдущему разделуК следующему разделу

Приложение

| На первую страницу | Поиск | Купить Matlab

Исправляем ошибки: Нашли опечатку? Выделите ее мышкой и нажмите Ctrl+Enter


Copyright © 1993-2024. Компания Softline. Все права защищены.

Дата последнего обновления информации на сайте: 04.03.17
Сайт начал работу 01.09.00