Эта статья появилась на свет совершенно неожиданно. Мне на глаза случайно попался код вычисления НОД на C#.
С первого взгляда мне даже всё понравилось: простенько, лаконичненько и без лишнего выпендрёжа. Однако чем дольше я рассматривал этот код, тем больше возникало сомнений в его эффективности. Я решил сделать маленькое исследование.
В адаптации на C++ код выглядел примерно так:
using namespace std; int main() < int a, b; cin >> a >> b; for (int i = a; i > 0; i—) < if (a % i == 0 b % i == 0) < cout НОД?» Вот, кстати, описано нахождение НОД через каноническое разложение на простые множители, которое мы уже реализовали. А вот что-то новенькое.
Алгоритм Евклида.
В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары.
Реализуем рекурсивную версию:
Наибольший общий делитель. 5 класс.
if (a > b) < long tmp = a; a = b; b = tmp; >return gcd04(a, b — a); >
Считается, что рекурсивные алгоритмы менее эффективны, чем итерационные, за счёт накладных расходов на вызов функции. Для проверки делаем и итерационный вариант.
05 алгоритм Евклида (итерационный)
b) < long tmp = a; a = b; b = tmp; >b = b — a; > return a; >
Кстати, в Викиучебнике есть и другие реализации алгоритма Евклида.
06 бинарный алгоритм (рекурсивный)
- НОД(0, n) = n; НОД(m, 0) = m; НОД(m, m) = m;
- НОД(1, n) = 1; НОД(m, 1) = 1;
- Если m, n чётные, то НОД(m, n) = 2*НОД(m/2, n/2);
- Если m чётное, n нечётное, то НОД(m, n) = НОД(m/2, n);
- Если n чётное, m нечётное, то НОД(m, n) = НОД(m, n/2);
- Если m, n нечётные и n > m, то НОД(m, n) = НОД((n-m)/2, m);
- Если m, n нечётные и n < m, то НОД(m, n) = НОД((m-n)/2, n);
07 бинарный алгоритм (итерационный)
if (a % 2L == 0L b % 2L != 0L) < a /= 2L; continue; >if (a % 2L != 0L b % 2L == 0L) < b /= 2L; continue; >if (a > b) < tmp = a; a = b; b = tmp; >tmp = a; a = (b — a) / 2L; b = tmp; > if (a == 0) return nod * b; else return nod * a; >
Кстати, в Викиучебнике есть и другие реализации бинарного алгоритма Евклида.
08 бинарный алгоритм (итерационный) с использованием битовых операций
Поскольку отличительной особенностью бинарного алгоритма является возможность использования битовых сдвигов вместо медленных операций деления и умножения, грех такой возможностью не воспользоваться.
Эта версия функции по логике полностью совпадает с предыдущей, но операции деления и умножения на 2 заменены арифметическими сдвигами, а проверка на чётность – на проверку младшего бита числа.
>= 1L; b >>= 1L; continue; > if (((a 1L)) < a >>= 1L; continue; > if ((a 1L) == 0L)) < b >>= 1L; continue; > if (a > b) < tmp = a; a = b; b = tmp; >tmp = a; a = (b — a) >> 1L; b = tmp; > if (a == 0) return nod * b; else return nod * a; >
Ещё немного подготовки
Итак, функции, на которые хватило времени, мозгов и фантазии написаны. Можно допиливать «испытательный стенд» и приступать к тестированию.
#37. Алгоритм Евклида для нахождения НОД | Python для начинающих
Как показали результаты тестовых прогонов, время работы функций сильно зависит от входных данных. Поэтому было решено генерировать случайные пары чисел. Однако выяснилось, что совсем случайные пары чисел слишком часто являются взаимно простыми. Поэтому я решил к паре случайных чисел добавлять случайный множитель. Получилось, что даже если изначально в паре числа были взаимно просты, то алгоритм поиска НОД должен будет вычислить именно этот добавленный множитель.
В остальном алгоритм тестирования прост: для каждого набора случайных данных берётся одна из тестируемых функций и прогоняется REPEAT_TIMES раз. Время работы функции записывается в элемент массива, соответствующий этой функции. После того, как все тесты пройдены, результаты из массива делятся на количество наборов данных – получаем среднее время для набора.
#include #include #include using namespace std; // // здесь должны быть определения функций вычисления НОД // struct sub < long(*func)(long, long); const char * comm; >; sub arr[] = < < gcd01, «01 перебор от произвольного числа » >, < gcd02, «02 перебор от минимального числа » >, < gcd03, «03 с разложением на делители » >, < gcd04, «04 алгоритм Евклида рекурсивный » >, < gcd05, «05 алгоритм Евклида итерационный » >, < gcd06, «06 бинарный алгоритм рекурсивный » >, < gcd07, «07 бинарный алгоритм итерационный » >, < gcd08, «08 бинарный алгоритм итерац. со сдвигом » >>; const unsigned int RAND_TIMES = 500u; const unsigned long REPEAT_TIMES = 10000uL; int main() < clock_t the_time; double elapsed_time; setlocale(LC_ALL, «Russian»); long a, b, c, nod; srand((unsigned int)time(NULL)); double times[sizeof(arr) / sizeof(sub)] = < 0.0 >; for (unsigned int t = 0u; t < RAND_TIMES; t++) < c = rand() % 50 + 1; a = (rand() % 1000 + 1) * c; b = (rand() % 1000 + 1) * c; for (unsigned int alg = 0u; alg < sizeof(arr) / sizeof(sub); alg++) < the_time = clock(); for (unsigned long m = 0uL; m < REPEAT_TIMES; m++) < nod = arr[alg].func(a, b); >elapsed_time = double(clock() — the_time) / CLOCKS_PER_SEC; times[alg] += elapsed_time; > printf(«%4u НОД(%7ld, %7ld) = %7ldn», t + 1, a, b, nod); > printf(«nСреднее время для %d пар случайных чисел:n», RAND_TIMES); for (unsigned int alg = 0; alg < sizeof(arr) / sizeof(sub); alg++) < printf(«%s: %8.4f сек.n», arr[alg].comm, times[alg] / RAND_TIMES); >return 0; >
Тестирование
Программа компилировалась под MS Visual Studio 2013 и TDM-GCC 4.8.1 в режиме 64-bit Release.
Среднее время для 500 пар случайных чисел: ——————————————————- 01 перебор от произвольного числа : 0.5022 сек. 02 перебор от минимального числа : 0.3256 сек. 03 с разложением на делители : 0.0063 сек. 04 алгоритм Евклида рекурсивный : 0.0007 сек. 05 алгоритм Евклида итерационный : 0.0008 сек. 06 бинарный алгоритм рекурсивный : 0.0006 сек.
07 бинарный алгоритм итерационный : 0.0003 сек. 08 бинарный алгоритм итерац. со сдвигом : 0.0002 сек.
Как и ожидалось, первый алгоритм катастрофически неэффективен. Алгоритм №2 – минимальный костыль для №1 – работает почти в 2 раз быстрее.
Третий алгоритм неожиданно показал очень достойный результат: в 50 раз быстрее алгоритма №2.
Четвёртый и пятый варианты – алгоритм Евклида: рекурсивная версия, как ни странно, обогнала итерационную. По сравнению с третьим вариантом время улучшилось почти на порядок.
Бинарный алгоритм Евклида показал наилучшие результаты. Из трёх вариантов реализации рекурсивная версия – самая неторопливая. Наилучший результат у оптимизированной версии с использованием битовых операций.
Итого, самая производительная версия работает более чем в 2500 раз быстрее, чем изначальный вариант.
Примечание. Время, указанное в таблице – это время выполнения REPEAT_TIMES вызовов функции.
Выводы
Выводы достаточно банальны, но всё же:
- Первый пришедший на ум алгоритм решения какой-то задачи часто неоптимален. Хотя и может правильно и достаточно приемлемо работать в определённых условиях.
- Всегда надо попробовать подумать над усовершенствованием алгоритма или над альтернативным вариантом.
- Учите математику!
- Если есть возможность, посмотрите что сделали люди до вас. Может не стоит изобретать велосипед?
- Оптимизируйте код.
Источник: code-live.ru
Наибольший общий делитель
Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольшее число, на которое делятся числа m и n. Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не равно нулю.
Алгоритм был придуман Евклидом в Древней Греции более 2000 лет назад и основан на следующем правиле.
Для любых целых чисел x, y > 0 выполняется равенство
НОД (x, y) = НОД (x % y, y)
Любое число, которое делит оба числа x и y, делит также и x — y, поэтому
НОД (x, y) ≤ НОД (x — y, y).
Аналогично, любое число, которое делит оба числа x − y и y, делит также и их сумму x, поэтому
НОД (x, y) ≥ НОД (x — y, y).
Требуемое равенство получается последовательным вычитанием y из x.
Идея алгоритма отыскания наибольшего общего делителя заключается в том, чтобы отнимать от большего меньшее, пока числа не станут равны. Полученное число и является наибольшим общим делителем.
Например, необходимо определить наибольший общий делитель чисел 50 и 20.
- находим 50-20=30. Из трех чисел 50, 20, 30 отбрасываем наибольшее.
- находим 30-20=10. Из трех чисел 30, 20, 10 отбрасываем наибольшее.
- находим 20-10 = 10. Из трех чисел 20, 10, 10 отбрасываем наибольшее.
- 10=10, значит это число является наибольшим общим делителем исходных.
Реализацию указанного алгоритма удобно произвести с использованием рекурсивной процедуры.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include
using namespace std;
// Функция нахождения НОД
int NOD( int n1, int n2)
int div;
if (n1 == n2) // если числа равны, НОД найден
return n1;
int d = n1 — n2; // Находим разность чисел
if (d < 0) // если разность отрицательная,
d = -d; // меняем знак
div = NOD(n1, d); // вызываем функцию NOD() для двух наименьших чисел
>
else // если разность n1-n2 положительная
div = NOD(n2, d); // вызываем функцию NOD() для двух наименьших чисел
>
return div;
>
int main()
int n1, n2;
cout cin >> n1;
cout cin >> n2;
cout cin.get(); cin.get(); return 0;
>
Результат выполнения
Комментариев к записи: 1
Источник: prog-cpp.ru
Программа для нахождения НОД чисел
Исходник программы, задача которой — нахождение наибольшего общего делителя (НОД или Алгоритм Евклида) для двух, введённых с клавиатуры чисел. Используется цикл WHILE, есть пояснительные комментарии ко всем важным строкам программы. Скачать исходник просмотреть исходный код программы можно ниже.
Исходный код программы:
var a,b,c: integer; //Описание переменных begin //Начало программы writeln(‘Введите a,b: ‘); //Диалог с пользователем read(a,b); //Чистывание чисел while b<>0 do //Вход в цикл while, пока b не равно 0 begin c := a mod b; //Присваивание с остатка деления a/b a := b; b := c; end; writeln(‘Наибольший Общий Делитель = ‘,a); //Вывод делителя end.//конец программы
Дата: 2012-04-07 18:52:48 Просмотров: 46833
Теги: Паскаль исходник Pascal WHILE циклы
Источник: zedpost.ru