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

Nishen · Регистрация: 26.02.2015

Студворк — интернет-сервис помощи студентам

Ребята, приветствую Вас!

Написал алгоритм нахождения НОД для одной из обучающих программ:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
if (tempFirstNum > tempFirstDenom) {
    int temp = tempFirstNum;
    tempFirstNum = tempFirstDenom;
    tempFirstDenom = temp;
}
 
for (int i = 2; i <= tempFirstNum; i++) {
    while (tempFirstNum % i == 0 && tempFirstDenom % i == 0) {
        gcd *= i;
        tempFirstNum /= i;
        tempFirstDenom /= i;
    }
}

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

Он приводил пример с какой-то сайта, якобы более лучшего алгоритма. Можете Вы сравнить?

Вот код с сайта:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
if (a > b) {
       long tmp = a;
        a = b;
        b = tmp;
    }
 
    while (a > 1L && b > 1L) {
        for (long i = 2; i <= a; i++) {
            if (a % i == 0 && b % i == 0) {
                nod *= i;
                a /= i;
                b /= i;
                break;
            }
            if (a % i == 0) {
                a /= i;
                break;
            }
            if (b % i == 0) {
                b /= i;
                break;
            }
        }
    }

Добавлено через 2 минуты
Например, при умножении $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{4}{5}$ на $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{126}{7}$ мой алгоритм быстрее справляется.

@volframka · 27.01.2016, 17:25

Сообщение от Nishen

мой алгоритм быстрее справляется.

Если в конкретней задачи твой алгоритм справляется быстрее, то его и оставляй.
Сам неоднократно сталкивался, что ассимптотически один алгоритм быстрее другого, а на практике - нет.
Очень сильно зависит от компилятора, что он сделает. В твоем случае, приведи алгоритмы к одному виду и ты поймешь, что они почти одинаковые.
Возможно, ассимптотически, второй алгоритм быстрее (проходов меньше), честно, я не вникал. Но у него много "ифов", а иф работает не очень быстро, поэтому, на практике, может быть все что угодно...

greg zakharov · 27.01.2016, 17:47

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
 
using namespace std;
 
int main(void) {
  unsigned int i, j;
  
  cout << "i = "; cin >> i;
  cout << "j = "; cin >> j;
  
  while (i != j) {
    if (i > j) i = i - j; else j = j - i;
  }
  
  cout << "nod = " << i << endl;
  
  return 0;
}

@Dimension · 27.01.2016, 17:49

Сообщение от volframka

Если в конкретней задачи твой алгоритм справляется быстрее, то его и оставляй

ну и совет ,в 1 примере быстро работает ,в 1000 других нет

Сообщение от volframka

Сам неоднократно сталкивался, что ассимптотически один алгоритм быстрее другого, а на практике - нет.

пример хоть одного привести сможете?

Nishen · 27.01.2016, 18:08 **[ТС]**

Да, я уже нашел, что, например, при $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{7}{8} + \frac{6}{7}$ мой алгоритм совершает довольно большое число лишних итераций, намного больше.

@volframka · 27.01.2016, 19:55

Сообщение от Dimension

ну и совет ,в 1 примере быстро работает ,в 1000 других нет

Не в конкретном тесте, а в конкретной задачи! Это очень сильные разные вещи.
Примеров тьма! Хоть qsort возьми стандартной реализации. Его асимтотика работы N log N. Но худшее время работы - квадрат. И если у тебя в реальной задачи постоянно идут такие примеры, то лучше сменить алгоритм!
Конечно, можешь проявить смекалку и сказать, что его можно рандомизировать и пр. Но я просто привел пример. Если ты до этого додуматься не смог, то объяснять про обработку изображения я тебе не буду.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .

Nishen 1358 / 856 / 366 Регистрация: 26.02.2015 Сообщений: 3,814
	27.01.2016, 18:08 [ТС]
	Да, я уже нашел, что, например, при $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{7}{8} + \frac{6}{7}$ мой алгоритм совершает довольно большое число лишних итераций, намного больше. 0