Лабораторна робота № 2 Списки. Цілі числа

Дана лабораторна робота призначена для вивчення прийомів роботи із списками на прикладі дій над цілими числами.

Докладні відомості по даних темах містяться: - в розділі "Структури даних" <file:///e:\document\alex\web-site\papers\metgap43\3-data.htm> даної методичної допомоги; - в розділі "Цілі числа, алгоритм Евкліда і розкладання на множники" <file:///e:\document\alex\web-site\examples\integers.htm> учбових матеріалів до курсу алгебри і теорії чисел; - в розділі "Lists and Records" введення в систему GAP <file:///d:\ Комп'ютерна%20алгебра\metgap43\tppmsgs\msgs0.htm>; - в розділах "Integers", "Number theory" і "Lists" довідкового керівництва за системою GAP <file:///d:\ Комп'ютерна%20алгебра\metgap43\tppmsgs\msgs0.htm>.

Завдання лабораторної роботи є реальними завданнями з наступного видання: В.У.Грібанов, П.І.Тітов, Збірка вправ по теорії чисел, М., Освіта, 1964 (далі - ГТ), і після номера варіанту вказаний номер відповідного завдання в [ГТ]. Студентам рекомендується ознайомитися з приведеним в [ГТ] вирішенням даних завдань, щоб побачити, що теоретичне їх рішення ефективніше, ніж простий перебір, виконаний ними в учбових цілях в даній лабораторній роботі.

Залежно від конкретного завдання, при виконанні роботи корисними можуть опинитися наступні функції і операції (детальний їх опис див. в документації):Collected(list)Повертає новий список newlist, який для кожного елементу x початкового списку list містить відповідний йому список з двох елементів, перший з яких є самим елементом x, а другою показує кратність його входження в список list, наприклад: gap> Collected([ 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 5, 5, 7 ]); [ [ 2, 8 ], [ 3, 4 ], [ 5, 2 ], [ 7, 1 ] ]

Combinations( list [, до ] )Повертає безліч всіляких комбінацій (неврегульованих наборів без повторень), складених з до елементів списку list (який може навіть містити однакові елементи кілька разів). Якщо до не вказано, повертаються всі можливі комбінації, складені з елементів списку list, наприклад: gap> Combinations( [1,2,2,3] ); [ [ ], [ 1 ], [ 1, 2 ], [ 1, 2, 2 ], [ 1, 2, 2, 3 ], [ 1, 2, 3 ], [ 1, 3 ], [ 2 ], [ 2, 2 ], [ 2, 2, 3 ], [ 2, 3 ], [ 3 ] ]

Divisorsint(n)Повертає список натуральних дільників цілого числа n

Factorsint(n)Повертає розкладання цілого числа n на прості множники у вигляді їх списку

Filtered(list, x -> f(x))Повертає список тих елементів x із списку list, для яких виконується умова f(x)=true

Forall(list, x -> f(x))Перевіряє, що для кожного елементу x із списку list виконується умова f(x)=true

Forany(list, x -> f(x))Перевіряє, що існує хоч би один елемент x із списку list, для якого виконується умова f(x)=true

Gcd(a1, a2 ...) Gcd(list)Обчислює найбільшого загального дільника цілих чисел a1, a2 ... або цілих чисел із списку list

Length(list)Визначає довжину списку list

а mod bа mod b повертає залишок від ділення а на b

Phi(n) Обчислює функцію Ейлера \Phi( n )

Product(list)Обчислює твір всіх елементів списку list

Sum(list)Обчислює суму всіх елементів списку list

Приклад (ГТ 77): Скільки чисел в інтервалі від 1 до 120 ділиться на одне і лише одне з чисел 2, 3 або 5 ?

Спочатку ми отримаємо список цих чисел, а потім визначимо їх кількість: gap> l := Filtered( [ 1 .. 120 ], i -> > Length( Filtered( [2,3,5], j -> i mod j = 0 ))= 1 ); [ 2, 3, 4, 5, 8, 9, 14, 16, 21, 22, 25, 26, 27, 28, 32, 33, 34, 35, 38, 39, 44, 46, 51, 52, 55, 56, 57, 58, 62, 63, 64, 65, 68, 69, 74, 76, 81, 82, 85, 86, 87, 88, 92, 93, 94, 95, 98, 99, 104, 106, 111, 112, 115, 116, 117, 118 ] gap> Length(l); 56

Цей же результат можна було б отримати і за допомогою однієї команди: gap> Length( Filtered( [ 1 .. 120 ], i -> > Length( Filtered( [2,3,5], j -> i mod j = 0 ))= 1 )); 56