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

Алгоритм Евклида. НОД. Тройка чисел - C++

Восстановить пароль Регистрация
 
alex-sm93
0 / 0 / 0
Регистрация: 20.01.2013
Сообщений: 9
22.01.2013, 14:17     Алгоритм Евклида. НОД. Тройка чисел #1
Всем привет.
Задание следующее: Найти НОД двух чисел по Алгоритму Евклида. Найти НОД трех чисел по этому же алгоритму. Подсчитать кол-во делений с остатком и определить наихудшую тройку чисел (с точки зрения вычислительных затрат), не превосходящих N.
Вот что сделал я:
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
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
using namespace std;
 
int Nod(int a, int b, int &count); //прототип функции, высчитывающей НОД
 
int main()
{
    int z1, z2, z3; //3 числа, вводятся с клавиатуры
    int pick; //переменная для выбора режима (найти НОД 2-х или3-х чисел)
    int count=0; //переменная для подсчета кол-ва делений
    cout<<"Viberi kol-vo chisel (2||3)"<<endl;
    cin>>pick;
    if(pick==2)
    {
        cout<<"Vvedi a&b"<<endl;
        cin>>z1>>z2;
        cout<<"Nod="<<Nod(z1, z2, count)<<endl;
    }
    else
    {
        cout<<"Vvedi a&b&c"<<endl;
        cin>>z1>>z2>>z3;
        cout<<"Nod="<<Nod(z3, Nod(z1, z2, count), count)<<endl;
    }
    cout<<"Kol-vo delenii="<<count<<endl;
    system("pause");
    return 0;
}
 
int Nod(int a, int b, int &count)
{
    //если число, из которого вычитаем второе, меньше - поменять значения местами
    if(a<b)
        swap(a, b);
    while(a>b)
    {
        a-=b;
        count++;
    }
    if(a!=b)
        return Nod(b, a, count);
    else
        return a;
}
Но, кажется, я использовал какую то другую вариацию алгоритма Евклида.
------->Помогите выполнить последнее задание "определить наихудшую тройку чисел (с точки зрения вычислительных затрат), не превосходящих N."

Добавлено через 45 секунд
Вот сам алгоритм http://ru.wikipedia.org/wiki/%D0%90%...B8%D0%B4%D0%B0

"Для иллюстрации, алгоритм Евклида будет использован, чтобы найти НОД 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"
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.01.2013, 14:17     Алгоритм Евклида. НОД. Тройка чисел
Посмотрите здесь:

C++ Описать функцию NOD2(A,B) целого типа,находящую наибольший общий делитель(НОД) двух целых положительных чисел А и В,используя алгоритм Евклида:....
C++ Написать функции рекурсивной и не рекурсивной реализации алгоритма Евклида нахождения наибольшего общего делителя (НОД) двух натуральных чисел
C++ Найти наибольший общий делитель (НОД), используя алгоритм Евклида
наибольший общий делитель (НОД) двух целых положительных чисел A и B, используя алгоритм Евклида: C++
C++ Найти наибольший общий делитель (НОД) двух введенных натуральных чисел, используя алгоритм Евклида
Алгоритм Евклида для n целых чисел C++
НОД двух чисел алгоритм Евклида C++
Последовательность натуральных чисел, вычисление их НОД методом Евклида C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 14:34. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru