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

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

Войти
Регистрация
Восстановить пароль
 
_Лето_
1 / 1 / 0
Регистрация: 03.11.2013
Сообщений: 68
#1

Даны два числа А и B. Найти их наибольший общий делитель - C++

04.07.2014, 10:11. Просмотров 389. Ответов 4
Метки нет (Все метки)

Задание: Даны два числа А и B. Найти их наибольший общий делитель НОД(A,B) и два числа U и V, такие, что А*U + B*V = НОД(A,B)

Если с первой частью я разобрался, то как решить уравнение не понимаю. Там же может быть бесконечное число этих решений, разве нет? И как это вообще искать, если уравнение всего одно?

Код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int main()
{
    setlocale(LC_ALL, "Russian");
    int a,b,c,d,u,v;
 
    cout << "Введите a:";
    cin >> a;
    cout << "Введите b:";
    cin >> b;
  while (b!=0)
    {
      c = a % b;
      a = b;
      b = c;
 
   }
   d = a;
cout << d;
d = u*a+v*b;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.07.2014, 10:11
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Даны два числа А и B. Найти их наибольший общий делитель (C++):

Даны два числа. Найти их наибольший общий делитель - C++
Пожалуйста, помогите у меня превышено время работы Даны два числа. Найти их наибольший общий делитель. Формат входных данных Вводятся...

Даны два натуральных числа. Получить их наибольший общий делитель (НОД), используя алгоритм Евклида - C++
Даны два натуральных числа. Получить их наибольший общий делитель (НОД), используя алгоритм Евклида. С помощью оператора цикла for ...

С клавиатруы вводится 2 числа, найти их наибольший общий делитель. - C++
Буду очень благодарег=(( 1. С клавиатруы вводится 2 числа, найти их наибольший общий делитель. 2. Разложение в степенной ряд e ^ x. ...

шестнадцатеричных числа. Определить наибольший общий делитель - C++
Помогите сделать задание, завтра сдавать... Заданы два длинных неотрицательных шестнадцатеричных числа. Напишите программу, определяющую...

Найти наибольший общий делитель - C++
помогите написать программу на С ++ задано 2 целые числа m и n, найти их наибольший общий делитель d и целые числа a и b такие, что d =...

[Qt 5] Задание:Найти наибольший общий делитель n и m - C++
Здравствуйте, вот, дали задание для первого курса. Не могли бы помочь? Если можно, не очень сложный код, чтобы понятно было Заранее...

4
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
04.07.2014, 10:19 #2
http://e-maxx.ru/algo/extended_Euclid_algorithm
0
_Лето_
1 / 1 / 0
Регистрация: 03.11.2013
Сообщений: 68
04.07.2014, 11:07  [ТС] #3
Я попытался совместить ту функцию, но в итоге все равно не компилируется... Я просто не понимаю, как работает тот код, ведь по сути x=x1, а y=y1. Как из тех же самых чисел, получается что-то другое?

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
#include <iostream>
using namespace std;
int main()
{
 
  int gcd (int a, int b, int & x, int & y)
{  setlocale(LC_ALL, "Russian");
 
    cout << "Введите a:";
    cin >> a;
    cout << "Введите b:";
    cin >> b;
    if (a == 0)
        {
        x = 0; y = 1;
        return b;
        }
    int x1, y1;
    int d = gcd (b%a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    cout << d << ", " << x << ", " << y;
    return d;
}
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
04.07.2014, 11:08 #4
Лучше задаться вопросом: как в функцию main вы добавили другую функцию
0
_Лето_
1 / 1 / 0
Регистрация: 03.11.2013
Сообщений: 68
04.07.2014, 11:13  [ТС] #5
Я убрал main и поставил void

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
26
27
28
29
30
31
32
void gcdext (int a, int b, int *d, int *x, int *y)
 
{
    setlocale(LC_ALL, "Russian");
    cout << "Введите a:";
    cin >> a;
    cout << "Введите b:";
    cin >> b;
 
  int s;
 
  if (b == 0)
 
  {
 
    *d = a; *x = 1; *y = 0;
 
    return;
 
  }
 
  gcdext(b,a % b,d,x,y);
 
  s = *y;
 
  *y = *x - (a / b) * (*y);
 
  *x = s;
 
  cout <<*x<<", " <<y;
 
}
Но тепеhь компилятор ругается на отсутствие WinMain@16
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.07.2014, 11:13
Привет! Вот еще темы с ответами:

Найти наибольший общий делитель чисел - C++
Найти наибольший общий делитель чисел M и N используя метод Эйлера: если M делится на N, то НОД (N, M) = N, иначе НОД (N, M) = НОД (M % N,...

Найти наибольший общий делитель многочленов - C++
Помогите пожалуйста , нужно сделать работу по с ++ , вот задание : Найти наибольший общий делитель многочленов Р (х) и Q (x). ...

Найти НОД (наибольший общий делитель) - C++
1) НОД(наибольший общий делитель) Даны два числа a и b 0&lt;a,b&lt;INT_MAX INT_MAX - максимальное доступное число, которое умещается в...

Найти NOD(a, b, c), (наибольший общий делитель) - C++
Помогите, как объявить функцию с двумя параметрами? &quot;Даны натуральные числа a, b, c. Найти NOD(a, b, c), (наибольший общий делитель)...


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

Или воспользуйтесь поиском по форуму:
5
Yandex
Объявления
04.07.2014, 11:13
Ответ Создать тему
Опции темы

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