![]() |
Алгоритм СтайнаАлгоритм Стайна (также еще распространено название Бинарный алгоритм вычисления НОД)- это расширенная версия евклидова алгоритма для вычисления наибольшего общего делителя (НОД) для пары целых чисел. Алгоритм Стайна обеспечивает большую эффективность за счет использования операторов побитового сдвига. ![]() Наибольший общий делитель В одной из своих предыдущих статей я показал версию евклидова алгоритма для C#, описанную греческим математиком Евклидом Александрийским. Этот алгоритм может быть использован для вычисления наибольшего общего делителя (НОД) двух целых чисел. GCD - это наибольшее целое число, в котором оба целых числа можно разделить без создания остатка. Например, GCD 210 и 124 составляет 42, так как оба значения можно разделить на 42 без остатка, давая результаты 5 и 3 соответственно. Самая базовая версия евклидова алгоритма работает путем многократного вычитания. Я не буду здесь описывать это подробно, лучше посмотрите предыдущую статью. Алгоритм Стайна Алгоритм Стайна, опубликованный в 1967 г. Джозеф Стайном, является еще одним алгоритмом для вычисления НОД двух значений. Он оптимизирован для использования в вычислениях, использует быстрые побитовые сдвиги, а не обычно более медленные операции повторного вычитания, деления или модуля . Компьютеры, использующие платформу .NET, как правило, имеют процессоры, которые изначально поддерживают разделение, поэтому разница в эффективности может быть не столь выраженной. Однако алгоритм по-прежнему интересен. Алгоритм Стейна использует ряд правил:
Давайте создадим метод, реализующий алгоритм Стайна. Начните с создания сигнатуры, которая соответствует таковой в предыдущем методе Евклида. public static uint Stein(uint value1, uint value2) { }Чтобы реализовать правила 1 и 2, нам нужно проверить, является ли одно из двух значений равным нулю или соответствуют ли они. Эти сценарии вызывают возвращение значения без дальнейших рекурсивных вызовов метода. if (val1 == 0) return val2; if (val2 == 0) return val1; if (val1 == val2) return val1;Наконец, мы можем определить, какие из значений являются нечетными и четными, чтобы мы могли применить остальные правила с рекурсивным вызовом. Первый оператор if идентифицирует, когда оба значения четные, и применяет правило 3. Вторые и третьи операторы if фиксируют одно четное и одно нечетное число, применяя правило 4. Последний оператор if и заключительный оператор else выполняются, когда оба значения являются нечетными. Они оба применяют правило 5. bool val1IsEven = (val1 & 1u) == 0; bool val2IsEven = (val2 & 1u) == 0; if (val1IsEven && val2IsEven) return Stein(val1 >> 1, val2 >> 1) << 1; else if (val1IsEven && !val2IsEven) return Stein(val1 >> 1, val2); else if (val2IsEven) return Stein(val1, val2 >> 1); else if (val1 > val2) return Stein((val1 - val2) >> 1, val2); else return Stein(val1, (val2 - val1) >> 1);Тестирование метода Чтобы выполнить простой тест, добавьте следующую строку кода в метод Main и запустите программу. Она вычисляет НОД 116150 и 232704. Результат должен быть равен 202. int nod = Stein(116150, 232704); ![]() Напоминаю, что вы в любое время можете обратиться ко мне за помощью по любым алгоритмам или языкам программирования. За умеренную плату я вам с удовольствием помогу решить любую проблему, связанную с программированием и алгоритмами. ![]() Автор этого материала - я - Пахолков Юрий. Я оказываю услуги по написанию программ на языках Java, C++, C# (а также консультирую по ним) и созданию сайтов. Работаю с сайтами на CMS OpenCart, WordPress, ModX и самописными. Кроме этого, работаю напрямую с JavaScript, PHP, CSS, HTML - то есть могу доработать ваш сайт или помочь с веб-программированием. Пишите сюда. ![]() |
Мои услуги
|
© upread.ru 2013-2023 При перепечатке активная ссылка на сайт обязательна. |