Упражнения по программированию

Раздел 2.2.1

1. Свойство евклидовости утверждает, что для заданных а и ненулевого 6 существует единственное частное q и остаток , такие, что

Напишите процедуру QUO, которая возвращает частное .

Напишите процедуру MOD, которая возвращает наименьший неотрицательный остаток .

с. Напишите процедуру LAVMOD, которая возвращает минимальный по абсолютной величине остаток , такой, что

Раздел 2.2.2

1. Используя ЕА, напишите процедуру GCDLCM, которая для заданных a и b возвращает Эта процедура должна возвращать значения для любого а. Выполните эту процедуру для следующих входных данных:

Если возникнут трудности с переполнением (т.е. если максимальное представимое целое число равно то выразите наименьшее общее кратное в виде (например,

2. Выберите 500 пар случайных чисел в интервале от 1 до 500. Для каждой пары вычислите используя процедуру из предыдущего упражнения. Найдите в процентах долю пар, состоящих из взаимно простых чисел. Сравните полученное число (процентов) с т.е. определите, насколько эта доля близка к 0.60793 (Дирихле).

Раздел 2.2.3

1. Напишите подпрограмму GLE (линейное уравнение общего вида (General Linear Equation)), которая по заданным а, b, с, таким, что а и b не равны нулю одновременно, возвращает X, у и t, где

и, если то — решение с наименьшим положительным Эта подпрограмма должна сначала использовать ХЕА, чтобы найти решение уравнения а затем использовать теорему 2.2.4. Выполните подпрограмму для следующих входных данных:

Раздел 2.2.4

1 (Лагранж, 1798). Пусть — полином с целыми коэффициентами, не имеющий рациональных корней и имеющий в точности один вещественный корень Напишите процедуру нахождения (вместе с любой добавочной информацией, которую вы хотите получить) неполных частных (от слов partial guotiens) числа , используя следующий алгоритм с экспоненциальным временем работы (который включает в основном только операции сложения; для его понимания необходимо овладеть материалом гл. 7):

1. [Инициализация] Положить

2. Для (в таком порядке) и для (в таком порядке) вычислить [Этот шаг основан на методе Руффини-Горнера, который обсуждается в разд. 3.1.2; корни полинома на единицу меньше, чем корни полинома где получается из исходного полинома после ряда преобразований.]

3. [Продолжить?] Если то положить и перейти к шагу 2.

4. Выдать значение следующего частичного приближения, заменить коэффициенты на и перейти к шагу 1. [Корни функции взаимны (reciprocals) с корнями полинома

Попробуйте выполнить этот алгоритм для полинома и аналогичных полиномов.

Раздел 2.3.1

1. Используя рассмотренный в тексте метод решета, постройте вектор всех простых чисел, не превосходящих 100.

2. Найдите 20 наибольших простых чисел используя приведенный в тексте метод.

Раздел 2.3.2

1. Напишите процедуру LCE (Linear Congruence Equation), которая по заданным ненулепым возвращает

, где

и, если , то — наименьшее неотрицательное решение по модулю см. теорему 2.3.22. Процедура должна использовать GLE (разд. 2.2.3). Выполните эту программу для следующих входных данных:

2. Используя LCE, напишите процедуру MODINV, которая по заданным возвращает и t, где

и, если , то — наименьшее неотрицательное решение по модулю . Выполните программу для следующих входных данных:

3. а. Реализуйте GRAk и используйте его для решения следующих систем:

b. Модифицируйте алгоритм так, чтобы он возвращал наименьший по абсолютной величине остаток, LAVGCRA, и выполните его для указанных выше входов.

Раздел 2.3.4

1. Опишем процедуру получения разложения числа на простые множители. Используя метод решета, построим таблицу простых чисел и проверим, делится ли на простые числа Если делителей нет, то просто (см. также упр. 2 разд. 2.3.1). Если какое-либо делит , то найдем наибольшую степень числа , которая делит . Запомним и для нового частного проверим, делится ли оно на последующие простые числа Если новых делителей не будет найдено, то либо и все простые делители уже найдены, либо — еще один простой делитель ( может иметь не более одного простого делителя ). Напишите процедуру FACT, находящую разложение на простые множители для чисел Вам потребуется таблица простых чисел Используйте эту процедуру для разложения чисел 9583, 9973, 16384, 17017 и 29957.