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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ упорядочивание по алфавиту http://www.cyberforum.ru/cpp-beginners/thread192648.html
как элементы структуры типа char упорядочить по алфавиту? О_о
C++ Передача массива в класс Как правильно передать одномерный массив в класс? И если можно то пример передачи.. Спасибо! http://www.cyberforum.ru/cpp-beginners/thread192644.html
треугольник C++
помогите пожалуйста проверить можно ли из векторов a(a1,a2), b(b1,b2) c(c1,c2) образовать треугольник
C++ Некорректное условие
Найдите натуральные числа из промежутка (а; b) такие, чтобы сумма цифр искомого числа, а также сумма цифр следующего за ним числа делились бы на k. Тесты и результаты. 1)а=1; Ь=1500; k=8. 79; 169; 259; 349; 439; 529; 619; 709; 789; 969; 1069; 1159; 1249; 1339; 1429; 1519. 2) a=200; b=4000; k=7. Таких чисел нет. 3)а=1;Ь=1000; к=4. 39; 79; 129; 169: 219; 259; 309; 349; 389; 439; 479; 529;...
C++ очередь http://www.cyberforum.ru/cpp-beginners/thread192597.html
Помогите пожалуйста((( даны компьютер и класс "пакет"! у пакета есть своя длина, номер, адрес! есть очередь Q1 и Q2, и мы должны сформировать Q2 из пакетов с одним адресом.
C++ Стек и очередь (С++) Привет! Помогите пожалуйста решить задачу!!!!!!!! Надо создать очередь,в нем стоят буквы латинского алфавита (a,b,c,d......z).Потом эти буквы надо распределить в два стека.В первый стек гласные буквы(а,i,e,u,o,y), во второй стек согласные буквы. Заранее спасибо!!!! подробнее

Показать сообщение отдельно
Fantom.AS
 Аватар для Fantom.AS
2 / 1 / 0
Регистрация: 17.11.2010
Сообщений: 121
17.11.2010, 18:53     Расширенный алгоритм Евклида
Написал программу для нахождения НОД через алгоритм Евклида.
Сделал нахождение представления НОД вида 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 минут
к тому же, прога неправильно считает, если одно из чисел отрицательное
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 21:53. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru