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

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

Войти
Регистрация
Восстановить пароль
 
alex-sm93
0 / 0 / 0
Регистрация: 20.01.2013
Сообщений: 9
#1

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

22.01.2013, 14:17. Просмотров 502. Ответов 0
Метки нет (Все метки)

Всем привет.
Задание следующее: Найти НОД двух чисел по Алгоритму Евклида. Найти НОД трех чисел по этому же алгоритму. Подсчитать кол-во делений с остатком и определить наихудшую тройку чисел (с точки зрения вычислительных затрат), не превосходящих 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++ Найти наибольший общий делитель (НОД), используя алгоритм Евклида
Наибольший общий делитель (НОД) двух целых положительных чисел A и B, используя алгоритм Евклида C++
Алгоритм Евклида для n целых чисел C++
НОД двух чисел алгоритм Евклида C++
C++ Наибольший общий делитель НОД по алгоритму Евклида
C++ Вычисление НОД по алгоритму Евклида (как организовать код?)
C++ Найти наибольший общий делитель двух чисел используя алгоритм Евклида
Последовательность натуральных чисел, вычисление их НОД методом Евклида C++
Найти наибольший общий делитель трех заданных натуральных чисел, используя алгоритм Евклида C++
C++ Найти наибольший общий делитель двух введенных чисел, используя алгоритм Евклида
C++ Определить функцию, которая находит наименьшее общее кратное двух чисел, используя алгоритм Евклида
Найти НОД двух целых чисел по алгоритму Евклида. C++

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

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

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