Курсовая с практикой на тему Алгоритм Евклида и Бинарный алгоритм нахождения наибольшего общего делителя

Содержание:

Введение 3

1. Деление на множестве целых чисел 5

2. Наибольший общий делитель 6

3. Простые и составные числа 8

4. Алгоритм Евклида 13

5. Бинарный алгоритм Евклида 15

6. Решение практических задач 16

Выводы 24

Список использованной литературы 25

Введение:

Введение

Первое описание алгоритма Евклида находится в книгах «Начал» (датируемых III веком до н. э.), что делает его одним из старейших численных алгоритмов, используемых в наше время. Оригинальный алгоритм был предложен только для натуральных чисел и геометрических длин (вещественных чисел). Однако в XIX веке он был обобщён на другие типы чисел, такие как целые числа Гаусса и полиномы от одной переменной.

Для данного алгоритма существует множество теоретических и практических применений. В частности он широко распространён криптографии. Также алгоритм используется при решении диофантовых уравнений, при построении непрерывных дробей. Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел.

Долгое время алгоритм Евклида был самым эффективным способом отыскания наибольшего общего делителя(НОД), однако с появлением электронно-вычислительных машин ситуация изменилась. Учет специфических особенностей выполнения арифметических операций компьютером позволил построить более эффективную (для программной реализации) версию алгоритма Евклида.

Данная курсовая работа посвящена ознакомлению с базовыми понятиями теории чисел. Структурно и логически она состоит из двух частей: теоретической и практической. В теоретической даются основные определения, понятия, и свойства чисел, приводятся леммы и теоремы теории делимости, а также алгоритмы нахождения НОД – обычный и бинарный алгоритмы Евклида и их разновидности. В практической рассматриваются конкретные примеры вычислений с применением описанных в теоретической части способов и алгоритмов нахождения НОД.

Цель исследования: расширить знания о свойствах чисел, связанных с делимостью.

Достижение поставленной цели требует решения следующих основных задач:

— закрепить пройденный лекционный материал;

— проработать учебную и тематическую литературу;

— изучить различные алгоритмы вычисления НОД и выявить наиболее рациональные из них;

— самостоятельно решить ряд заданий.

Работа актуальна поскольку развивает интерес к предмету, любознательность и логическое мышление.

Заключение:

Выводы

В процессе проделанной работы в соответствии с ее целями и задачами были рассмотрены следующие вопросы:

— отношение делимости и его свойства;

— определение наибольшего общего делителя;

— простые и составные числа, их свойства;

— разложение составных чисел на простые множители (основная теорема арифметики);

— обычный и бинарный алгоритмы Евлида.

По результатам решения практических задач проведено сравнение алгоритмов нахождения НОД и сделаны такие выводы:

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

— если числа достаточно большие, то нахождение НОД путем перечисления всех делителей чисел – процесс трудоемкий и ненадежный, т.к. можно легко допустить ошибку, тогда НОД находится с помощью обычного алгоритма Евклида, этот алгоритм наиболее простой и распространенный;

— для реализации программ нахождения НОД чисел на ЭВМ целесообразно использовать бинарный алгоритм, вследствие аппаратных особенностей выполнения вычислительных операций.

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

Фрагмент текста работы:

1. Деление на множестве целых чисел

1. Отношение делимости и его свойства.

Определение. Целое число делится на целое число , если существует такое целое число , что .

Число называется делимым, – делителем, – частным (от деления). Если делится на , это обозначают и говорят, что кратно .

Отношение делимости является бинарным отношением на множестве целых чисел и имеет следующие свойства:

1) – отношение делимости рефлексивно;

2) из и следует – отношение делимости транзитивно;

3) если , то и , т.е. отношение делимости сохраняется при замене знаков делимого и делителя;

4) если и , то и ;

5) если и , то ;

6) нуль делится на любое число ;

7) любое число делится на 1;

8) если , то не существует такого , что , т.е. деление на 0 невозможно.

Все перечисленные свойства легко доказываются на основе определения.

2. Деление с остатком.

Определение. Число делится на с остатком, если существуют такие числа и , что , где .

Число называется неполным частным, а – остатком.

Теорема. Какие б не были целые числа и , всегда можно и при этом единственным способом разделить на с остатком.

Доказательство.