Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
0 / 0 / 1
Регистрация: 26.02.2018
Сообщений: 29

Расширенный алгоритм Евклида для отрицательных чисел

17.10.2022, 16:21. Показов 691. Ответов 1

Студворк — интернет-сервис помощи студентам
Приветствую! Подскажите, пожалуйста, как правильно вычислять коэффициенты соотношения Безу для случая отрицательных чисел в реализации расширенного алгоритма Евклида. Вот мой код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cmath>
#include <tuple>
 
using namespace std;
 
tuple<int, int, int> xgcd(int a, int b, int s1 = 1, int s2 = 0, int t1 = 0, int t2 = 1) {
    if (b == 0) {
        return {abs(a), s1, t1};
    }
    int q = a / b;
    return xgcd(b, a - q * b, s2, s1 - q * s2, t2, t1 - q * t2);
}
 
int main(double argc, char ** argv) {
    tuple<int, int, int> result = xgcd(-10, -15);
    cout << get<0>(result) << " " << get<1>(result) << " " << get<2>(result) << endl;
 
    return 0;
};
В представленном случае (-10, -15) НОД рассчитывается правильно, а вот коэффициенты Безу требуют инвертирования знака. Как правильно поступить с ними? Заранее спасибо!)
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
17.10.2022, 16:21
Ответы с готовыми решениями:

Расширенный алгоритм Евклида и обратная матрица
Привет всем! пишу лабу шифр хилла ,чтоб дешифровать надо найти обратную матрицу , нам сказали вычислять с помошью расширенного...

Расширенный алгоритм Евклида с "усечёнными" остатками
Здравствуйте, уважаемые форумчане! Подскажите, пожалуйста, где можно прочитать про расширенный алгоритм Евклида с...

Расширенный алгоритм Евклида для двух взаимно простых чисел, буду благодарен)
Расширенный алгоритм Евклида для двух взаимно простых чисел. Выведите результат на экран.

1
Модератор
Эксперт функциональных языков программирования
3134 / 2281 / 469
Регистрация: 26.03.2015
Сообщений: 8,877
19.10.2022, 22:16
Если сумма чисел меньше нуля, то инвертировать?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
19.10.2022, 22:16
Помогаю со студенческими работами здесь

Реализуйте расширенный алгоритм Евклида для двух взаимно простых чисел. Результат выведите на экран
Реализуйте расширенный алгоритм Евклида для двух взаимно простых чисел. Результат выведите на экран. Желательно с комментариями

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

Расширенный алгоритм Евклида для RSA
Нужно реализовать поиск d , для Алгоритма RSA. Не совсем понимаю логику, что от меня требуется Задание: 1. Выбираются два простых...

Расширенный алгоритм Евклида для вычисления мультипликативного обратного
Расширенный алгоритм Евклида для вычисления мультипликативного обратного.

Расширенный алгоритм Евклида
Написал программу для нахождения НОД через алгоритм Евклида. Сделал нахождение представления НОД вида d=a*v+b*u: Код: void...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Новые блоги и статьи
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image
8Observer8 27.01.2026
Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
влияние грибов на сукцессию
anaschu 26.01.2026
Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android
8Observer8 26.01.2026
Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д.
8Observer8 25.01.2026
Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf
8Observer8 25.01.2026
Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly
8Observer8 24.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
моя боль
iceja 24.01.2026
Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru