Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Вывести на экран все четные делители числа N https://www.cyberforum.ru/ cpp-beginners/ thread768795.html
Вывести на экран все четные делитесь числа N. Помогите написать программу))
C++ Игра
Доброе время суток! Хочу написать свою первую, простую игру на С++. Посоветуйте с чего начать.
C++ Регрессия (не трудная по идеи задача) дарствуйте, у меня есть задача которую я хотел бы решить. Как решается задача а в Excel 2003 (тут картинки с описанием) вот окно всеми знакомой программы http://s3.uploads.ru/A8Jem.png итак,... https://www.cyberforum.ru/ cpp-beginners/ thread768786.html C++ вектор Почему программа только до половины работает? #include <iostream> #include <vector> using namespace std; int main() { vector<int>vec; https://www.cyberforum.ru/ cpp-beginners/ thread768780.html
C++ Расширение функциональности #define
Visual Studio 2012, Win7x64Prof У меня есть код условно на 10 строк, в котором меняется 2-3 параметра. Например, создание нового класса путем наследования с добавлением public указателя (надо...
C++ Описать структуру с именем TRAIN Описать структуру с именем TRAIN ,содержащую следующие поля: - название пункта назначения ; - номер поезда; - время отправления; Написать программу, выполняющую следующие действия: - ввод с... https://www.cyberforum.ru/ cpp-beginners/ thread768622.html
C++ Напечатать таблицу https://www.cyberforum.ru/ cpp-beginners/ thread768617.html
Концентрация хлорной извести в бассейне объемом V=1000м в кубе составляет 10г/л. Через одну трубу в бассейн вливают чистую воду объемом скорость Q=150м в кубе/час, через другую трубу с такой же...
Программа записывающая целые числа C++
Написать программу, запрашивающую целые числа ,....,, среди которых могут быть повторяющиеся члены . Выяснить , имеется ли в последовательности хотя бы одна пара совпадающих чисел, вывести их номера...
C++ Удаление класса изнутри Завершается все корректно. Но насколько безопасна такая конструкция? class A { public: A(){} void func(){ delete this; } }; https://www.cyberforum.ru/ cpp-beginners/ thread768598.html C++ Написать геодезическую задачу(найти ошибку) C++ https://www.cyberforum.ru/ cpp-beginners/ thread768591.html
#include<stdio.h> #include<math.h> #include<conio.h> #include<iostream.h> #include<fstream.h> void input( float *ds, ) { float p; int i,n=9;
программа перескакивает определение элемента класса C++
Программа просто проскакивает date a(); #include <iostream> #include <time.h> #include <vector> #include <date.h> using namespace std; int main() { int r = 0;
C++ Задача про числа Коллатца https://www.cyberforum.ru/ cpp-beginners/ thread768579.html
Даны 2 числа, i j. Нужно вывести максимальную длину цикла для последовательности Коллатца (если An четно, то An+1 = An/2, если нет, то An+1=An*3+1) Программу написал, но elJudge говорит, что ответ...
0 / 0 / 1
Регистрация: 20.01.2013
Сообщений: 9
0

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

22.01.2013, 14:17. Показов 1079. Ответов 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/%... 0%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"

Вернуться к обсуждению:
Алгоритм Евклида. НОД. Тройка чисел C++
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
22.01.2013, 14:17
Готовые ответы и решения:

НОД двух чисел алгоритм Евклида
Найти найбольший общий делитель двух чисел по алгоритму Евклида. Использовать рекурсию.

Найти НОД двух чисел, используя алгоритм Евклида
Требуется найти наибольший общий делитель двух заданных натуральных чисел, используя алгоритм...

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

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

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.01.2013, 14:17
Помогаю со студенческими работами здесь

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

С++ НОД, Бинарный алгоритм Евклида
Доброе время суток Столкнулся с бинарным алгоритмом Евклида. В целом не могу понят как...

Алгоритм Евклида для нахождения НОД
Уважаемые форумчане, никак не получается написать алгоритм Евклида, возможно не хватает знаний,...

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

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

НОД нескольких чисел используя метод Евклида
Проходит только 14 тестов из 32. Без массивов пожалуйста :) Напишите функцию для нахождения...

0
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru