лист 3 листов 3

Задание 1. Действия с полиномами (в списочном представлении)

Полином p(x) представляется как последовательность мономов Q = (q(1), q(2), ..., q(n)), где каждый из мономов есть пара q(i) = (коэф(i), степ(i)), при этом коэф(i) – коэффициент при степени x^степ(i), коэф(i)  0 и целое степ(i)  0. Такое представление называют разреженным.

Пусть последовательность (q(1), ..., q(n)) упорядочена по убыванию степеней мономов, т. е. степ(i) > степ(i + 1) для i 1..n – 1. Таким образом,

p(x)  коэф(1) x^степ(1) + коэф(2) x^степ(2)+...+ коэф(n) x^степ(n)

есть полином степени степ(1).

Например, полином 1999 x¹²⁸ 33 x²¹+ 777 x + 13 представляется последовательностью

((1999, 128), (33, 21), (777,1), (13, 0)).

Последовательность Q, представляющая полином, может быть реализована в виде Л1-списка. Информационный элемент списка – пара: коэф и степ, где степ – натуральное число стандартного типа (N0), а коэф может быть целым или вещественным числом стандартного типа, а также представлять рациональное число (на базе стандартных целых), «длинное» целое или «длинное» рациональное число.

Варианты задания с полиномами:

1. Полиномы одной переменной с вещественными коэффициентами. Операции: ввод, вывод, +, , *, подстановка p(q(x)).

2. Полиномы одной переменной с вещественными коэффициентами. Операции: div, mod, gcd (нод).

3. Полиномы одной переменной с вещественными коэффициентами. Операции: ввод, вывод, +, , *, p(x)ⁿ, дифференцирование, интегрирование.

4. Полиномы одной переменной с длинными целыми коэффициентами. Операции: ввод, вывод, +, , *. Для длинных целых – списочное представление (см. п.2 задания 2).

5. Полиномы одной переменной с длинными рациональными коэффициентами. Операции: ввод, вывод, +, . Для длинных рациональных – списочное представление (см. п.5 задания 2).

6. Полиномы трех переменных с вещественными коэффициентами. Операции: ввод, вывод, +, , дифференцирование, интегрирование.

7. Полиномы трех переменных с вещественными коэффициентами. Операции: ввод, вывод, +, , *.

8. Полиномы трех переменных с длинными целыми коэффициентами. Операции: ввод, вывод, +, . Для длинных целых – списочное представление (см. п.2 задания 2).

Задание 2. Длинная арифметика

Общая формулировка задания дана в 5.2 в [6]. Варианты заданий:

9. Целые числа. Операции: +, , *, div, mod, gcd.

10. Целые числа. Операции: сравнение, +, , *, div, mod, xn.

11. Целые числа. Операции: сравнение, +, , *.

12. Целые числа. Л2-список. Операции: сравнение, +, , *, div, mod.

13. Рациональные числа (с длинной арифметикой): для целых списочное представление в динамической памяти. Операции: сравнение, сокращение, +,  , *, / (на основе НОД, НОК).

14. Школьная арифметика с визуализацией действий «в столбик», реализованная на основе «длинной арифметики» (учесть размер экрана и т. п.). Списочное представление в динамической памяти. Операции: +, , *, div, mod.

Примечания.

Задание 5.2. [6: Сборник задач по структурному программированию].

Действия с целыми многозначными числами.

Многозначное число A представляется в виде массива целых чисел a₁, a₂, …, a_n путем разбиения его цифр на группы по t цифр. Каждая группа цифр, обозначенная a_i, является целым числом, не превосходящим по величине некоторого фиксированного числа m.

Другими словами число A представляется в системе счисления с основанием m, а a₁, a₂, …, a_n - это цифры числа в этой системе счисления.

Пример.

Пусть имеется многозначное число: 31415926535897932384626433832795028841972.

Для представления его при помощи массива целых чисел нужно выбрать основание системы счисления m , т.е. тип элемента массива. Допустим, что мы выбрали тип int, который представляется в данном трансляторе двумя байтами. Тогда максимальное значение m = 32767.

Неудобство этого основания в том, что для перевода исходного числа в такую систему счисления (и обратно) необходимо выполнять соответствующие операции (деление).

Вспомнив о способе перевода двоичного числа в восьмеричное число (и обратно), а также, почему этот алгоритм так прост, можно взять в качестве основания системы счисления m = 10000.

Тогда для представления исходного числа в эту систему счисления нужно его разбить (справа-налево) на части по четыре цифры. Тогда исходное число будет представлено в массиве num типа int следующим образом.

num [0] = 3

num [1] = 1415

num [2] = 9265

num [3] = 3589

num [4] = 7932

num [5] = 3846

num [6] = 2643

num [7] = 3832

num [8] = 7950

num [9] = 2884

num [10]= 1972.

При выполнении операций над таким представлением нужно помнить, что максимальное значение в элементе массива == 9999 (цифры в представлении числа – это 0000, 0001, 0002, … , 999), и не забывать, например, о единице переноса при сложении, которая может быть == 0001, 0002, … , 9999.

Конец примечаний