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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Вывести на экран все четные делители числа N http://www.cyberforum.ru/cpp-beginners/thread768795.html
Вывести на экран все четные делитесь числа N. Помогите написать программу))
C++ Игра Доброе время суток! Хочу написать свою первую, простую игру на С++. Посоветуйте с чего начать. http://www.cyberforum.ru/cpp-beginners/thread768788.html
C++ Регрессия (не трудная по идеи задача)
дарствуйте, у меня есть задача которую я хотел бы решить. Как решается задача а в Excel 2003 (тут картинки с описанием) вот окно всеми знакомой программы http://s3.uploads.ru/A8Jem.png итак, делаем следующее http://s2.uploads.ru/Ja9Fd.png > http://s2.uploads.ru/ZhL5s.png > http://s3.uploads.ru/hVXbw.png
C++ вектор
Почему программа только до половины работает? #include <iostream> #include <vector> using namespace std; int main() { vector<int>vec;
C++ Расширение функциональности #define http://www.cyberforum.ru/cpp-beginners/thread768702.html
Visual Studio 2012, Win7x64Prof У меня есть код условно на 10 строк, в котором меняется 2-3 параметра. Например, создание нового класса путем наследования с добавлением public указателя (надо новое название, конструктор). Функцией всего этого не сделаешь, надо чтобы генерился "текст" кода с новыми названиями. Итак, в коде делаю запись (сначала указываю название нового класса, а потом новый...
C++ Описать структуру с именем TRAIN Описать структуру с именем TRAIN ,содержащую следующие поля: - название пункта назначения ; - номер поезда; - время отправления; Написать программу, выполняющую следующие действия: - ввод с клавиатуры данных в массив, состоящий из K<=10 элементов типа TRAIN; - записи должны быть упорядочены по номерам поездов; - вывод на экран информации о поезде, номер которого введен с клавиатуры; -... подробнее

Показать сообщение отдельно
alex-sm93
0 / 0 / 0
Регистрация: 20.01.2013
Сообщений: 9

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

22.01.2013, 14:17. Просмотров 505. Ответов 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"
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 18:27. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru