Алгоритмы - Рабочая тетрадь 2. Числовые алгоритмы поиск наибольшего общего делителя, факторизация чисел, поиск простых чисел, псевдослучайные числа Теоретический материал
 Скачать 1.1 Mb.
|
|
1 Дисциплина «Алгоритмы решения прикладных задач» Рабочая тетрадь 2. Числовые алгоритмы: поиск наибольшего общего делителя, факторизация чисел, поиск простых чисел, псевдослучайные числа Теоретический материал Алгоритмы поиска наибольшего общего делителя НОД – наибольший общий делитель, – число, делящее без остатка пару чисел и являющееся наибольшим из возможных делителей. Например: НОД(8, 6)=2; НОД(12, 8)=4. Очень важное понятие, необходимость в вычислении которого возникает достаточно часто. Простой расчетной формулы для НОД не существует. Решение полным перебором возможно, но для больших чисел необходимо большое количество вычислительных операций. Хорошее решение проблемы поиска наибольшего общего делителя двух чисел нашел еще Евклид. В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары. Блок-схема алгоритма выглядит следующим образом: Для уменьшения количества вычислительных операций новая пара положительных чисел формируется не в результате вычитания из большего числа меньшего, а в результате деления большего числа на меньшее. В результате новая пара положительных чисел формируется из делителя и остатка от деления. Как только остаток от деления становится равным нулю, вычисления прекращаются. 2 Искомый наибольший общий делитель – это делитель на последнем шаге вычислений. Примеры для обоих подходов (вычитание и деление): Пример 1 демонстрирует поиск наибольшего общего делителя двух чисел методом вычитания Алгоритмы факторизации Факторизация – это задача разбиения числа на множители. Известно, что любое число можно представить в следующем виде A=a 1 k1 a 2 k2 …a n kn , где a i – простые числа, k i – натуральные числа. Такое разложение существует всегда и называется оно каноническим разложением числа. Для построения канонического разложения достаточно научиться находить только один делитель. Получив делитель и поделив на него число A (до тех пор, пока это возможно, поскольку число может поделиться на найденный простой делитель несколько раз), мы переходим к задаче поиска делителя для меньшего числа. Например, если найден первый простой делитель числа A, то A=B∙a 1 k1 , где a 1 – простое число, а k1 – количество раз, на которое число A поделилось. Например, число 60 делится на 2 (первое простое число) 2 раза, то есть 60=15∙2 2 . Далее необходимо осуществлять поиск простого делителя числа 15. Итоговое каноническое разложение числа 60 имеет вид: 60=2 2 ∙3∙5. Таким образом, для поиска канонического разложения числа необходимо осуществить поиск именно простых делителей. Для этого можно изначально рассматривать в качестве кандидатов на делитель только простые числа, которые могут быть первоначально найдены с помощью одного из алгоритмов: например, решето Эратосфена или решето Сундарама. Поиск возможного делителя, если речь не идет о скорости – задача простая. Достаточно перебрать все простые числа от 2 до √𝐴 и для каждого из них проверить делимость числа A. 3 Пример 2 демонстрирует алгоритм нахождения наименьшего положительного целого делителя (большего единицы) для заданного числа, а также определение того, сколько раз число будет делиться на этот делитель без остатка Алгоритм Ферма для разделения числа на 2 множителя 4 Естественно, алгоритм Ферма может привести к тому, что по крайней мере один из найденных множителей не будет простым числом. В этом случае необходимо для составного множителя применить снова алгоритм Ферма для разбиения его на множители. Пример 3 иллюстрирует применение алгоритма Ферма для разбиения числа на 2 множителя Поиск простых чисел с помощью решета Эратосфена Простое число – это число, делящееся только на единицу и на себя. Определение дает и несложный метод поиска простых путем полного перебора вариантов. Необходимо записать цикл, проходящий все целые числа от 2 до некоторой границы, и для каждого числа пытаться найти нетривиальный (отличный от 1 и самого числа) делитель. Если такой делитель найден, то число составное, иначе – простое. Боле эффективный метод – решето Эратосфена. q √𝑞 5 Пример 4 иллюстрирует работу алгоритма «Решето Эратосфена». Люка-Лемера_Число_Мерсе́нна_—_число_вида_2_n_-1'>Алгоритмы поиска простых чисел. Числа Мерсенна. Тест Люка-Лемера Число Мерсе́нна — число вида 2 n -1, где n — натуральное число; такие числа примечательны тем, что некоторые из них являются простыми при больших значениях n. Названы в честь французского математика Маре́на Мерсенна, исследовавшего их свойства в XVII веке. 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16 383, 32 767, 65 535, 131 071, … 6 Не все числа Мерсенна являются простыми, однако простых чисел среди всех чисел Мерсенна очень много. По этой причине числа Мерсенна удобно использовать для получения большого простого числа. Для проверки числа Мерсенна на простоту существует простой тест Люка- Лемера. Это алгоритм, который предполагает на первом этапе построение последовательности по следующему правилу: То есть последовательность всё время одна и та же. Например, третье число Мерсенна 2 3 -1=7. Для проверки его на простоту с помощью теста Люка-Лемера необходимо построить последовательность (она приведена выше). Третье число Мерсенна (7) должно делить без остатка второй член последовательности (14). Действительно, 14%7=0. Математическим языком операция «%» записывается словом mod. То есть можно записать 14(mod 7)=0. Поскольку числа в последовательности очень быстро становятся большими, то при программной реализации каждый получаемый член последовательности заменяется на остаток от деления на рассматриваемое число Мерсенна. При этом для получения следующего члена последовательности используется именно остаток от деления с предыдущего шага. Алгоритм Люка-Лемера (на псевдокоде) выглядит следующим образом: 7 Примеры применения теста Люка-Лемера к простому и составному числам Мерсенна: Пример 5 демонстрирует построение последовательности для теста Люка- Лемера с учетом нахождения остатков от деления на число Мерсенна Псевдослучайные числа. Числа фон Неймана В различных технических и математических приложениях часто необходим ряд случайных чисел. Числа называются случайными в силу того, что в их ряду нет никакой закономерности, зная некоторое количество последовательных чисел ряда, нельзя вычислить следующее. Устройство или программа, получающая такие числа, называется генератором случайных чисел. О принципиальной возможности существования случайных последовательностей можно спорить. 8 Нетрудно встретить мнение, что все процессы, существующие в природе или созданные человеком, строго закономерны. Но, во всяком случае, если это и так, то некоторые из закономерностей настолько сложны и управляются настолько большим количеством параметров, что фактически их невозможно отследить за разумное время с использованием разумного количества ресурсов. Алгоритм фон Неймана для генерации псевдослучайных чисел состоит в следующем. Предположим, что некоторое случайное, достаточно большое число уже известно. Определить такое число совершенно не представляет проблему: так как оно первое, то оно может быть просто любым. Пусть, например, нас интересуют 5-значные случайные числа. Возьмем в качестве первого число 14 563. Возведем его в квадрат, получим 212 080 969. Возьмем из середины пять цифр 20 809. Это и будет следующее случайное число. Псевдослучайность получаемой последовательности очевидна. Каждое следующее число совершенно однозначно определяется предыдущим. Но нас это смущать не должно. Если неизвестно, как получены числа, то они выглядят вполне случайно. Но у метода есть более серьезный недостаток. Если последовательность продолжить, то может проявиться так называемый период. Периодом называется строго повторяющаяся последовательность чисел. Впрочем, для алгоритма фон Неймана можно подобрать исходное число, дающее период только после очень большого количества шагов. Пример 6 иллюстрирует получение второй, третьей и четвертой цифр пятизначного числа Пример 1 Задача: Написать на языке C++ программу для поиска наибольшего общего делителя двух чисел методом вычитания Решение: 9 Ответ: Пример 2 Задача: Написать на языке C++ программу для нахождения наименьшего положительного целого делителя (большего единицы) для заданного числа A, а также определения того, сколько раз число A будет делиться на этот делитель без остатка (кратность остатка) Решение: 10 Ответ: Пример 3 Задача: Написать на языке C++ программу для разбиения заданного числа на 2 множителя с помощью алгоритма Ферма Решение: 11 Ответ: Пример 4 Задача: Написать на языке C++ программу для поиска простых чисел, не превосходящих заданную границу, с помощью алгоритма «Решето Эратосфена» Решение: 12 Ответ: Пример 5 Задача: Написать на языке C++ программу для построение последовательности для теста Люка-Лемера с учетом нахождения остатков от деления на заданное число Мерсенна Решение: 13 Ответ: Пример 6 Задача: Написать на языке C++ программу для получение второй, третьей и четвертой цифр пятизначного числа Решение: Ответ: 14 Задание 1 Задача: Написать программу для поиска наибольшего общего делителя (числа вводятся с клавиатуры после запуска программы): Нечетные варианты: наибольший делитель трех чисел методом деления (для поиска остатка отделения в языке C++ используется операция %) Четные варианты: наибольший общий делитель четырех чисел метолом вычитания Решение: Ответ: Задание 2 Задача: Написать программу для факторизации заданного с клавиатуры числа методом простого перебора (указать простые множители и их кратность). Для анализа числа на простоту использовать решето Эратосфена Решение: Ответ: Задание 3 Задача: Написать программу для факторизации заданного с клавиатуры числа методом Ферма (указать простые множители и их кратность). Для анализа числа на простоту использовать решето Эратосфена Решение: Ответ: Задание 4 Задача: Написать программу для проверки на простоту числа Мерсенна с использование теста Люка-Лемера. С клавиатуры вводится номер числа Мерсенна Решение: 15 Ответ: Задание 5 Задача: Написать программу для генерации последовательности из 10 пятизначных чисел фон Неймана Решение: Ответ: Задание 6* Задача: Написать программу для поиска простых чисел по алгоритму «Решето Сундарама» Решение: Ответ: |