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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.70
Анель
0 / 0 / 0
Регистрация: 30.05.2012
Сообщений: 9
#1

Расчет наибольшего общего делителя двух натуральных чисел используя алгоритм эвклида - C++

30.05.2012, 21:45. Просмотров 3697. Ответов 10
Метки нет (Все метки)

пожалуйста помогите решить задачу на си++. даны натуральные числа а и б,обозначенные соответственно числитель и знаменатель дроби.сократить дробь т.е. найти такие нат числа p и q,не имеющие общих делителей,что p/q=a/b (определить функцию для расчета наибольшего общего делителя двух натуральных чисел используя алгоритм эвклида).помогите очень прошу,заранее спасибо
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.05.2012, 21:45
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Расчет наибольшего общего делителя двух натуральных чисел используя алгоритм эвклида (C++):

Нахождение наибольшего общего делителя двух натуральных чисел - C++
1)Используя функцию NOD нахождения наибольшего общего делителя двух натуральных чисел, сократить данную обычную дробь M / N. / /...

Составить программу для нахождения наибольшего и наименьшего общего делителя и наименьшего общего кратного двух натуральных чисел - C++
Составить программу для нахождения наибольшего и наименьшего общего делителя и наименьшего общего кратного двух натуральных чисел по...

Нахождение наибольшего общего делителя и наименьшего общего кратного двух натуральных - C++
Составить программу для нахождения наибольшего общего делителя и наименьшего общего кратного двух натуральных чисел (НОК(А,В)= А*В/ НОД...

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

Написать алгоритм нахождения наибольшего общего делителя трех чисел - C++
Написать алгоритм нахождения наибольшего общего делителя трех чисел C++ помогите пожалуйста, желательно с объяснением

Написать подпрограмму нахождения наибольшего общего делителя двух чисел - C++
Написать подпрограмму нахождения наибольшего общего делителя двух чисел N и M по реккурентному соотношению: (N=23345 M=9135 =>...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
instagib
122 / 85 / 3
Регистрация: 14.02.2011
Сообщений: 340
30.05.2012, 21:51 #2
Анель,
Цитата Сообщение от Анель Посмотреть сообщение
определить функцию для расчета наибольшего общего делителя двух натуральных чисел используя алгоритм эвклида
Найти наибольший общий делитель (НОД) двух введенных натуральных чисел, используя алгоритм Евклида
Анель
0 / 0 / 0
Регистрация: 30.05.2012
Сообщений: 9
30.05.2012, 21:53  [ТС] #3
я не знаю как его находить(((
instagib
122 / 85 / 3
Регистрация: 14.02.2011
Сообщений: 340
30.05.2012, 21:56 #4
Анель, Вы хотите код, или объяснение?
Анель
0 / 0 / 0
Регистрация: 30.05.2012
Сообщений: 9
30.05.2012, 21:59  [ТС] #5
лан с этим эвклидом сама разберусь.помогите с первой частью задачи(до скобок),мне нужно написать программу на си++,я не знаю как
instagib
122 / 85 / 3
Регистрация: 14.02.2011
Сообщений: 340
30.05.2012, 22:08 #6
Анель, Вот Ваша решенная задача:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
template <typename T>
T gcd (T a, T b) {
        while (b) {
                a %= b;
                swap (a, b);
        }
        return a;
}
int main()
{
    int a, b,div;
    cout << "Input a: ";    cin >> a;
    cout << "Input b: ";    cin >> b;
    div = gcd(a,b);
    cout << "Fraction: " << a << " / " << b;
    a/=div;
    b/=div;
    cout << endl << "Fraction: " << a << " / " << b;
    cin.get();
    return 0;
}
Анель
0 / 0 / 0
Регистрация: 30.05.2012
Сообщений: 9
30.05.2012, 22:10  [ТС] #7
огромное спасибо вам,а вы можете ее мне объяснить??извините что достаю
rinat_w
89 / 85 / 4
Регистрация: 13.11.2011
Сообщений: 192
Завершенные тесты: 1
30.05.2012, 22:19 #8
Анель, если тебе еще нужно:
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
#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int a,b,x,y;
    cout<<"a="; cin>>x;
    cout<<"b="; cin>>y;
    a=x;
    b=y;
    int r;
    while (r>0){
          if (a>b){
                   r=a-b;
                   a=b;
                   b=r;
          }
          else{
               r=b-a;
               b=a;
               a=r;
          }
    }
    cout<<x<<"/"<<y<<"="<<x/b<<"/"<<y/b<<endl;
    system("pause");
    return 0;
}
немного набыдлокодил
instagib
122 / 85 / 3
Регистрация: 14.02.2011
Сообщений: 340
30.05.2012, 22:20 #9
Анель,
Цитата Сообщение от instagib Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
template <typename T>
T gcd (T a, T b) {
* * * * while (b) {
* * * * * * * * a %= b;
* * * * * * * * swap (a, b);
* * * * }
* * * * return a;
}
Для иллюстрации, алгоритм Евклида будет использован, чтобы найти НОД a = 1071 и b = 462. Для начала, от 1071 отнимем кратное значение 462, пока не получим знаменатель меньше чем 462. Мы должны дважды отнять 462, (q0 = 2), оставаясь с остатком 147
1071 = 2 × 462 + 147.
Затем от 462 отнимем кратное значение 147, пока не получим знаменатель меньше чем 147. Мы должны трижды отнять 147 (q1 = 3), оставаясь с остатком 21.
462 = 3 × 147 + 21.
Затем от 147 отнимем кратное значение 21, пока не получим знаменатель меньше чем 21. Мы должны семь раз отнять 21 (q2 = 7), оставаясь без остатка.
147 = 7 × 21 + 0.
Таким образом последовательность a>b>R1>R2>R3>R4>...>Rn в данном конкретном случае будет выглядеть так:
1071>462>147>21
Так как последний остаток равен нулю, алгоритм заканчивается числом 21 и НОД(1071, 462)=21.


Цитата Сообщение от instagib Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{
* * int a, b,div;  \\1*
* * cout << "Input a: "; * *cin >> a; \\2*
* * cout << "Input b: "; * *cin >> b;  \\2*
* * div = gcd(a,b);  \\3*
* * cout << "Fraction: " << a << " / " << b; \\4*
* * a/=div; \\5*
* * b/=div;  \\5*
* * cout << endl << "Fraction: " << a << " / " << b; \\6*
* * cin.get(); \\ожидаем нажатия Enter для выхода.
* * return 0;
}
(*1)Тут 3 переменные - числитель (a), знаменатель(b) и Наиб.Общ.Делит.(div) который добудится функцией gcd(). Вводим значения в a и b(2*). потом находим наиб.общ.делит. - он сохранится в переменной div(3*).
Выводим старую дробь(чтоб было с чем сравнивать(4*). После, сокращаем числитель(a) и знаменатель(b) на НОД(5*). и выводим результат(6*).

Не по теме:

жмите кнопочку "Спасибо" ))

Анель
0 / 0 / 0
Регистрация: 30.05.2012
Сообщений: 9
30.05.2012, 22:53  [ТС] #10
спасибо большое вам всем за помощь)))
instagib
122 / 85 / 3
Регистрация: 14.02.2011
Сообщений: 340
30.05.2012, 22:54 #11
Анель, кнопочку "спасибо" нажимайте
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.05.2012, 22:54
Привет! Вот еще темы с ответами:

Написать программу вычисления наибольшего общего делителя двух целых чисел Dev C++ 4.9.9.2 - C++
Помогите написать программу! Написать программу вычисления наибольшего общего делителя двух целых чисел. Наибольший общий делитель...

Напишите рекурсивную функцию вычисления наибольшего общего делителя двух положительных целых чисел - C++
(Greatest Common Divisor, GCD). Для этого воспользуйтесь следующими свойствами: GCD(a,b)=GCD(b,amodb) GCD(0,a)=a ...

Разработать и испытать рекурсивную функцию для вычисления общего делителя двух введенных натуральных чисел - C++
Разработать и испытать рекурсивную функцию для вычисления общего делителя двух введенных натуральных чисел. с++ Помогите пожалуйста.

Рекурсивный алгоритм Евклида нахождения наибольшего общего делителя - C++
Даны натуральные числа n, m. Найти НОД(n,m). Рекурсивный алгоритм Евклида нахождения наибольшего общего делителя основан на соотношении...


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

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

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