Эта программа на языке Go реализует расширенный алгоритм Евклида для многочленов над рациональными числами. Он вычисляет наибольший общий делитель (НОД) двух многочленов, а также коэффициенты Безу.
Расширенный алгоритм Евклида - это способ найти наибольший общий делитель двух целых чисел и одновременно найти коэффициенты идентичности Безу. Этот алгоритм расширен на многочлены над рациональными числами в данной реализации.
-
Временная сложность:
- В худшем случае, когда два многочлена имеют максимальную степень n, время выполнения алгоритма составляет O(n^3), так как на каждой итерации выполняются операции деления многочленов, умножения и вычитания с полиномиальным временем выполнения.
-
Пространственная сложность:
- Пространственная сложность алгоритма зависит от количества коэффициентов в многочленах. Она также оценивается как O(n^2), так как в каждый момент времени в памяти хранятся два многочлена и их коэффициенты.
add(p, q *polyRing) *polyRing: Сложение двух многочленов.sub(p, q *polyRing) *polyRing: Вычитание двух многочленов.mul(p, q *polyRing) *polyRing: Умножение двух многочленов.div(p, q *polyRing) (*polyRing, *polyRing): Деление двух многочленов и возвращает частное и остаток.extendedEuclideanPoly(f, g *polyRing) (*polyRing, *polyRing, *polyRing): Реализует расширенный алгоритм Евклида для многочленов.String() string: Возвращает строковое представление многочлена.testExtendedEuclidean(numTests int): Запускает случайные тесты на расширенный алгоритм Евклида. (Степень от 1 до 5)testExtendedEuclideanLength(maxLength int): Тестирует время выполнения алгоритма в зависимости от длины многочлена.generateRandomPolynomial(degree int) *polyRing: Генерирует случайный многочлен указанной степени.colorize(text, color string) string: Окрашивает текст в указанный цвет.
- Запустите программу.
- Введите степень и коэффициенты первого многочлена.
- Введите степень и коэффициенты второго многочлена.
- Программа вычислит НОД двух многочленов вместе с коэффициентами Безу (U(x) и V(x)).
- По желанию, вы можете выбрать запуск случайных тестов или тестирование времени выполнения в зависимости от длины многочлена.
Убедитесь, что у вас установлен Go. Клонируйте репозиторий и запустите go run main.go.