Форум программистов, компьютерный форум CyberForum.ru

Расширенный алгоритм Евклида - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 44, средняя оценка - 4.89
Fantom.AS
 Аватар для Fantom.AS
2 / 1 / 0
Регистрация: 17.11.2010
Сообщений: 121
17.11.2010, 18:53     Расширенный алгоритм Евклида #1
Написал программу для нахождения НОД через алгоритм Евклида.
Сделал нахождение представления НОД вида d=a*v+b*u:

Код:

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
25
void alg_evclid(long int a, long int b, long int *x, long int *y, long int *d)
{   /* calculates a * *x + b * *y = gcd(a, b) = *d */
    long int q, r, x1, x2, y1, y2;
    if (b == 0) //если один из множителей равен 0
    {
        *d = a, *x = 1, *y = 0;
        return;
    }
    x2 = 1, x1 = 0, y2 = 0, y1 = 1;
 
    while (b > 0) 
    {
        q = a / b; 
        r = a - q * b;
        *x = x2 - q * x1; 
        *y = y2 - q * y1;
        //промежуточный вывод
        printf("\n%d=%d*%d+%d",a,b,q,r);
        a = b; b = r;
        x2 = x1; x1 = *x; y2 = y1; y1 = *y;
        
    }   //end while (b>0)
 
    *d = a, *x = x2, *y = y2;
}   //end alg_evklid
Основу этого фрагмента кода взял отсюда:
Расширенный алгоритм Евклида
Кто может разъяснить как находится представление НОД ?
поэтапно и подробно, если можно?
Очень важно и нужно...
__________________

Добавлено через 4 часа 37 минут
к тому же, прога неправильно считает, если одно из чисел отрицательное
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.11.2010, 18:53     Расширенный алгоритм Евклида
Посмотрите здесь:

Необычный алгоритм Евклида C++
Алгоритм Евклида с использованием рекурсии C++
C++ Алгоритм Евклида
Алгоритм Евклида + системы счисления C++
RSA, Расширенный алгоритм Евклида. Код на С++ C++
НОД двух чисел алгоритм Евклида C++
C++ алгоритм евклида
Алгоритм Евклида C++
Расширенный алгоритм Евклида C++
C++ Алгоритм Евклида для одномерных массивов
Алгоритм Евклида. Переведите с Паскаля на С++ C++
C++ Реализовать обобщенный алгоритм Евклида

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 04:50. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru