2.3. Задание на контрольно-курсовую работу.

№ Вар.

Название

Метод вычисления

1

Нахождение наибольшего общего делите (НОД) и наименьшего общего кратного (НОК)

Алгоритм Евклида для нахождения НОД:

1. большее число делим на меньшее

2. если делиться без остатка – это НОД

3. если есть остаток, то большее число заменяем на остаток от деления (r=a1-(a1/a1)a2)

4. переходим к пункту 1.

Нахождение НОК:

НОК( a , b) = a*b / НОД(a, b)

2

Расширенный алгоритм Евклида

НА ВХОДЕ: два неотрицательных числа a и b: a>=b

НА ВЫХОДЕ: d=НОД(a,b) и целые x,y: ax + by = d.

1. Если b=0 положить d:=a, x:=1, y:=0 и возвратить (d,x,y)

2. Присвоить x₂:=1, x₁:=0, y₂:=0, y₁:=1

3. Пока b>0

3.1 q:=[a/b], r:=a-qb, x:=x₂-qx₁, y:=y₂-qy₁

3.2 a:=b, b:=r, x₂:=x₁, x₁:=x, y₂:=y₁, y₁:=y

4. Присвоить d:=a, x:=x₂, y:=y₂ и возвратить (d,x,y)

3

Нахождение обратного элемента

Важно: Элемент a во множестве чисел n обратим тогда и только тогда, когда НОД(a,n)=1. То есть ответ есть не всегда. Из определения обратного элемента прямо следует алгоритм.

НА ВХОДЕ: а из множества чисел n.

НА ВЫХОДЕ: обратный к а в кольце, если он существует.

1. Использовать расширенный алгоритм Евклида для нахождения x и y, таких что ax + ny = d, где d=НОД(a,n).

2. Если d > 1, то обратного элемента не существует.

Иначе возвращаем x.

4. Выход d,x,y такие что d=НОД(a,b)=ax+by

4

Возведение в степень по модулю

1. Присваиваем начальные значения переменным: S=1, V=W,c=a

2. Если V=0, то СТОП

3. Если значение V является нечетным (V mod 2=1), то присваиваем новые значения переменным: Z=Sc mod n (n - множество чисел) и V=(v-1)/2 и переходим к шагу 5. В противном случае переходим к шагу 4

4. Выполняем присваивание V=V/2

5. Выполняем присваивание c=c² mod n

6. Переходим к шагу 2

ВЫХОД: Значение S=a^W mod n

5

Нахождение простых чисел в диапазоне от a до b

ВАЖНО: простым числом называется число, которое делится без остатка только на единицу и само на себя.

1. Определяется диапазон чисел

2. Используется алгоритм Евклида для нахождения наибольшего общего делителя (НОД)для чисел в диапазоне от а до и

3. Если НОД>1, то выполняется шаг 7

4. Для чисел проверяется отношение

5. Если сравнение не выполняется, то переход к шагу 7

6. Выдается последовательность простых чисел

7. Выдается результат, что число составное

6

Умножение матрицы на простое число

1. Проверить является ли число простым (см. вариант 5)

2. Умножить матрицу на число (называемое скаляр).

Если A — матрица и x — скаляр, то C = xA — матрица , в которой .

3. При делении

7

Умножение матриц

Две матрицы различного размера могут быть перемножены, если число столбцов первой матрицы совпадает с числом строк второй матрицы. Если A — матрица размера , а матрица B размера , то произведением будет матрица C размером . Если элемент матрицы A обозначить , а каждый элемент матрицы B обозначить , то элемент матрицы C — — вычисляется следующим образом:

8

Нахождение определителя матрицы

Определитель (детерминант) — квадратная матрица A размера , обозначаемая как det (A) — скалярное вычисление рекурсивно, как это показано ниже:

1.

2. , где A_ij получается из A удалением i -той строки j -того столбца.

Детерминант определяется только для квадратной матрицы

9

Решение квадратного уравнения вида ax²+bx+c=0

• при корней два, и они вычисляются по формуле:        (1)

• при корень один :

при корней нет.

10

Сложение и вычитание матриц

Операция сложения двух матриц может применяться, если матрицы имеют одинаковое число столбцов и строк. Сложение записывают как C =A + B. В этом случае полученная в результате матрица C имеет тот же самый номер строк и столбцов, как A или B. Каждый элемент C — сумма двух соответствующих элементов A и B:

Операция вычитания производится аналогично сложению, за исключением того, что каждый элемент В вычитается из соответствующего элемента A: .

11

Нахождение частного решения уравнения вида ax=b(mod n)

Уравнение этого типа может не иметь ни одного решения или иметь ограниченное число решений. Предположим, что НОД (a, n) = d. Если d не делит b, решение не существует. Если d делит b, то имеется d решений.

Если d делит b, то для того, чтобы найти решения, выполняются следующие действия:

1. Сократить уравнение, разделив обе стороны уравнения (включая модуль) на d.

2. Умножить обе стороны сокращенного уравнения на мультипликативную инверсию, чтобы найти конкретное решение x₀.

12

Программа нахождения частного решения линейных диофантовых уравнений ax+by=c

Найти значения целых чисел для x и y, которые удовлетворяют этому уравнению. Этот тип уравнения либо не имеет решений, либо имеет бесконечное число решений. Пусть d = НОД (a, b). Если d не делит c, то уравнение не имеет решения. Если d делит c, то мы имеем бесконечное число решений. Одно из них называется частным, остальные — общими.

Частное решение

Если d делит c, то можно найти частное решение вышеупомянутого уравнения, используя следующие шаги.

1. Преобразуем уравнение к a₁x + b₁y = c₁, разделив обе части уравнения на d. Это возможно, потому, что d делит a, b, и c в соответствии с предположением.

2. Найти s и t в равенстве a₁s + b₁t = 1, используя расширенный алгоритм Евклида.

3. Частное решение может быть найдено:

Частное решение: X₀ = (c/d)s и y₀ = (c/d) t

13

Программа решения уравнения вида ax+c=b(mod n)

Сначала нужно привести уравнение к форме ax=b(mod n). Для этого к обеим сторонам уравнения прибавляется или отнимается число с. Затем выполняются действия из задания 11.

14

Программа нахождения арифметической прогрессии

Арифметическая прогрессия — числовая последовательность вида

,

то есть последовательность чисел (членов прогрессии), каждое из которых, начиная со второго, получается из предыдущего добавлением к нему постоянного числа (шага или разности прогрессии):

15

Программа нахождения геометрической прогрессии

Формула геометрической прогрессии для нахождения членов прогрессии . Для решения задачи определить интервал чисел

16

Сценарий сортировки методом пузырька

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива

17

Сценарий сортировки методом Шелла

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

18

Сценарий сортировки вставками

На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве

19

Сценарий сортировки методом выбора

Исходный массив длиной N разбивается на две части: итог и остаток. Участок массива, называемый итогом, располагается с начала массива и должен быть упорядоченным, а участок массива, называемый остатком, располагается вплотную за итогом и содержит исходные числа не отсортированной части исходного массива

20

Сценарий быстрой сортировки

Выбираем в массиве некоторый элемент, который будем называть опорным элементом. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.

Реорганизуем массив таким образом, чтобы все элементы со значением меньшим или равным опорному элементу, оказались слева от него, а все элементы, превышающие по значению опорный — справа от него. Обычный алгоритм операции:

Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.

Вычисляется индекс опорного элемента m.

Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше либо равен опорному.

Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.

Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.

Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно, изменяется именно индекс опорного элемента и алгоритм продолжает свое выполнение. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.

Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.