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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 44, средняя оценка - 4.89
Fantom.AS
2 / 1 / 0
Регистрация: 17.11.2010
Сообщений: 121
#1

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

17.11.2010, 18:53. Просмотров 5455. Ответов 0
Метки нет (Все метки)

Написал программу для нахождения НОД через алгоритм Евклида.
Сделал нахождение представления НОД вида 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 минут
к тому же, прога неправильно считает, если одно из чисел отрицательное
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.11.2010, 18:53
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Расширенный алгоритм Евклида (C++):

Расширенный алгоритм Евклида - C++
Дело движется к реализации RSA, но уже на этом этапе возникли проблемы. Дело в том что у меня большие числа реализованы на массивах (под...

Расширенный алгоритм Евклида - C++
Здравствуйте, форумчане! Подскажите пожалуйста как реализовать такое задание(код самого алгоритма Евклида прилагается): Программа должна...

RSA, Расширенный алгоритм Евклида. Код на С++ - C++
Доброго времени суток ,форумчане) тут такой вопрос: есть Расширенный алгоритм Евклида. ( кто сможет простым языком разъяснить ,как...

алгоритм евклида - C++
не могу выкупить ничего что происходит и как решить. вот мое задание : : : : Даны натуральные а и b, не равные 0 одновременно. Найти d =...

Алгоритм Евклида - C++
Привет всем. Задача такова, надо написать программу на С++ для поиска Самого Малого Кратного (СМК) по алгоритму Евклида. Дано три...

Алгоритм Евклида - C++
Здравствуйте! Подскажите пожалуйста какие ошибки есть в алгоритме, который я составил? int gcd (int a, int b) { int t; if...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.11.2010, 18:53
Привет! Вот еще темы с ответами:

Необычный алгоритм Евклида - C++
Помогите,пожалуйста!Написал програму,не могу найти ,где в ней ошбка.Условие:дано натуральное число n ичислаа1,а2,а3,...,аn,которые вводятся...

Визуализировать алгоритм Евклида - C++
Визуализировать алгоритм эвклида

Реализовать обобщенный алгоритм Евклида - C++
Ребят,необходимо реализовать обобщенный алгоритм Евклида. Заранее благодарен! Добавлено через 3 минуты желательно с...

Алгоритм Евклида. Переведите с Паскаля на С++ - C++
begin g 0 : = b; g 1 : = a; i : = 1 while g i ! = 0 do begin ...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

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