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

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

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

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

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

пожалуйста помогите решить задачу на си++. даны натуральные числа а и б,обозначенные соответственно числитель и знаменатель дроби.сократить дробь т.е. найти такие нат числа p и q,не имеющие общих делителей,что p/q=a/b (определить функцию для расчета наибольшего общего делителя двух натуральных чисел используя алгоритм эвклида).помогите очень прошу,заранее спасибо
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.05.2012, 21:45     Расчет наибольшего общего делителя двух натуральных чисел используя алгоритм эвклида
Посмотрите здесь:
Нахождение наибольшего общего делителя двух натуральных чисел C++
Составить программу для нахождения наибольшего и наименьшего общего делителя и наименьшего общего кратного двух натуральных чисел C++
C++ Нахождение наибольшего общего делителя и наименьшего общего кратного двух натуральных
C++ Написать функции рекурсивной и не рекурсивной реализации алгоритма Евклида нахождения наибольшего общего делителя (НОД) двух натуральных чисел
Написать алгоритм нахождения наибольшего общего делителя трех чисел C++
C++ Написать подпрограмму нахождения наибольшего общего делителя двух чисел
Написать программу вычисления наибольшего общего делителя двух целых чисел Dev C++ 4.9.9.2 C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
спасибо большое вам всем за помощь)))
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.05.2012, 22:54     Расчет наибольшего общего делителя двух натуральных чисел используя алгоритм эвклида
Еще ссылки по теме:
C++ Напишите рекурсивную функцию вычисления наибольшего общего делителя двух положительных целых чисел
Рекурсивный алгоритм Евклида нахождения наибольшего общего делителя C++
C++ Нахождение наибольшего общего делителя для 6-и чисел
C++ Нахождение наибольшего общего делителя для элементов массива целых чисел
Найти наименьшее из четырех чисел используя алгоритм поиска наибольшего из двух чисел C++

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

Или воспользуйтесь поиском по форуму:
instagib
122 / 85 / 3
Регистрация: 14.02.2011
Сообщений: 340
30.05.2012, 22:54     Расчет наибольшего общего делителя двух натуральных чисел используя алгоритм эвклида #11
Анель, кнопочку "спасибо" нажимайте
Yandex
Объявления
30.05.2012, 22:54     Расчет наибольшего общего делителя двух натуральных чисел используя алгоритм эвклида
Ответ Создать тему
Опции темы

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