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

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

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

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

04.07.2014, 10:11. Просмотров 368. Ответов 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.07.2014, 10:11     Даны два числа А и B. Найти их наибольший общий делитель
Посмотрите здесь:
C++ Даны два числа. Найти их наибольший общий делитель
C++ С клавиатруы вводится 2 числа, найти их наибольший общий делитель.
шестнадцатеричных числа. Определить наибольший общий делитель C++
C++ Найти наибольший общий делитель
C++ Найти НОД (наибольший общий делитель)
Найти наибольший общий делитель многочленов C++
C++ Найти NOD(a, b, c), (наибольший общий делитель)
[Qt 5] Задание:Найти наибольший общий делитель n и m C++
Найти наибольший общий делитель чисел C++
C++ Найти наибольший общий делитель двух чисел
Найти наибольший общий делитель двух чисел C++
C++ Найти наибольший общий делитель целых чисел х и у

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dani
1278 / 636 / 56
Регистрация: 11.08.2011
Сообщений: 2,277
Записей в блоге: 2
Завершенные тесты: 1
04.07.2014, 10:19     Даны два числа А и B. Найти их наибольший общий делитель #2
http://e-maxx.ru/algo/extended_Euclid_algorithm
_Лето_
1 / 1 / 0
Регистрация: 03.11.2013
Сообщений: 68
04.07.2014, 11:07  [ТС]     Даны два числа А и B. Найти их наибольший общий делитель #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;
}
Dani
1278 / 636 / 56
Регистрация: 11.08.2011
Сообщений: 2,277
Записей в блоге: 2
Завершенные тесты: 1
04.07.2014, 11:08     Даны два числа А и B. Найти их наибольший общий делитель #4
Лучше задаться вопросом: как в функцию main вы добавили другую функцию
_Лето_
1 / 1 / 0
Регистрация: 03.11.2013
Сообщений: 68
04.07.2014, 11:13  [ТС]     Даны два числа А и B. Найти их наибольший общий делитель #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
Yandex
Объявления
04.07.2014, 11:13     Даны два числа А и B. Найти их наибольший общий делитель
Ответ Создать тему
Опции темы

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