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

Алгоритм Евклида для n целых чисел - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.69
HeroYukki
0 / 0 / 0
Регистрация: 01.07.2012
Сообщений: 15
19.07.2012, 15:23     Алгоритм Евклида для n целых чисел #1
Задача:
Составить рекурсивную функцию, реализующую алгоритм Евклида для n целых чисел.

Самый главный вопрос: это вообще как? Сколько не гуглил, а алгоритма такого я не нашел. Или нужно алгоритм для двух чисел переделать под несколько? Разъясните, пожалуйста, что-куда, кодом или на пальцах, мне главное понять.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.07.2012, 15:23     Алгоритм Евклида для n целых чисел
Посмотрите здесь:

C++ Описать функцию NOD2(A,B) целого типа,находящую наибольший общий делитель(НОД) двух целых положительных чисел А и В,используя алгоритм Евклида:....
наибольший общий делитель (НОД) двух целых положительных чисел A и B, используя алгоритм Евклида: C++
C++ Найти наибольший общий делитель (НОД) двух введенных натуральных чисел, используя алгоритм Евклида
НОД двух чисел алгоритм Евклида C++
C++ Найти наибольший общий делитель двух чисел используя алгоритм Евклида
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mr.X
Эксперт С++
 Аватар для Mr.X
2797 / 1573 / 246
Регистрация: 03.05.2010
Сообщений: 3,649
19.07.2012, 16:32     Алгоритм Евклида для n целых чисел #2
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::vector<int>    T_int_numbers;
/////////////////////////////////////////////////////////////////////////////////////////
int  euclid(T_int_numbers  int_numbers)
{
    if( int_numbers.size() == 1 )
    {
        return  int_numbers.front();
    }
 
    if( int_numbers.size() == 2 )
    {
        int&  a = int_numbers.front ();
        int&  b = int_numbers.back  ();
        if(b == 0)
        {
            return  a;
        }
        else
        {
            a %= b;
            std::swap(a, b);
        }
        return  euclid( int_numbers );
    }
    T_int_numbers  new_int_numbers;
    new_int_numbers.push_back
        (
            int_numbers.back()
        );
 
    int_numbers.pop_back();
    new_int_numbers.push_back
        (
            euclid( int_numbers )
        );
 
    return  euclid( new_int_numbers );
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    for(;;)
    {
        std::cout   <<  "Введите количество чисел: ";
        int     n   =   0;
        std::cin    >>  n;
 
        if(n <= 0)
        {
            break;
        }
 
        std::cout   <<  "Введите "
                    <<  n
                    <<  " целых чисел:"
                    <<  std::endl;
 
        T_int_numbers  int_numbers;
        for(int  i = 0; i < n; ++i)
        {
            std::cout   <<  "#"
                        << i + 1
                        <<":"
                        <<  '\t';
            int     x   =   0;
            std::cin    >>  x;
            int_numbers.push_back(x);
        }
 
        std::cout   <<  "НОД этих чисел равен: "
                    <<  euclid(int_numbers)
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl;                 
    }
}
Hi4ko
74 / 74 / 4
Регистрация: 21.10.2010
Сообщений: 376
19.07.2012, 16:32     Алгоритм Евклида для n целых чисел #3
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;
 
int gcd (int a, int b,int num) {
        while (b) {
                a %= b;
                swap (a, b);
        }
int z;
if(num - 1 >= 0){
    cin >> z;
    return gcd(a,z,--num);
}
return a;
}
 
int main(){
int n,x,y;
cin >> n;
cin >> x >> y;
cout << gcd(x,y,n-2) << endl;
}
Mr.X
Эксперт С++
 Аватар для Mr.X
2797 / 1573 / 246
Регистрация: 03.05.2010
Сообщений: 3,649
19.07.2012, 17:03     Алгоритм Евклида для n целых чисел #4
Еще вариант:
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::vector<int>    T_int_numbers;
/////////////////////////////////////////////////////////////////////////////////////////
int  euclid(T_int_numbers  int_numbers)
{
    if( int_numbers.size() == 1 )
    {
        return  int_numbers.front();
    }
 
    int     a   =   int_numbers.back();
    int_numbers.pop_back();
    int     b   =   int_numbers.back();
    int_numbers.pop_back();
 
    if(b == 0)
    {
        int_numbers.push_back(a);
    }
    else
    {       
        int_numbers.push_back(a % b);        
        int_numbers.push_back(b);
    }
    return  euclid( int_numbers );
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    for(;;)
    {
        std::cout   <<  "Введите количество чисел: ";
        int     n   =   0;
        std::cin    >>  n;
 
        if(n <= 0)
        {
            break;
        }
 
        std::cout   <<  "Введите "
                    <<  n
                    <<  " целых чисел:"
                    <<  std::endl;
 
        T_int_numbers  int_numbers;
        for(int  i = 0; i < n; ++i)
        {
            std::cout   <<  "#"
                        << i + 1
                        <<":"
                        <<  '\t';
            int     x   =   0;
            std::cin    >>  x;
            int_numbers.push_back(x);
        }
 
        std::cout   <<  "НОД этих чисел равен: "
                    <<  euclid(int_numbers)
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl;                 
    }
}
Fenixsar
 Аватар для Fenixsar
3 / 3 / 0
Регистрация: 26.08.2008
Сообщений: 19
19.07.2012, 17:21     Алгоритм Евклида для n целых чисел #5
Цитата Сообщение от HeroYukki Посмотреть сообщение
Самый главный вопрос: это вообще как? Сколько не гуглил, а алгоритма такого я не нашел.
Врешь, дорогой, гугл все знает
HeroYukki
0 / 0 / 0
Регистрация: 01.07.2012
Сообщений: 15
19.07.2012, 18:15  [ТС]     Алгоритм Евклида для n целых чисел #6
Hi4ko, Огромное спасибо, шикарный код.

Mr.X, тоже спасибо, но пока не понимаю векторы, на днях буду учить)

Fenixsar, ну раз вру давайте ссылки, скажу спасибо.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
19.07.2012, 18:20     Алгоритм Евклида для n целых чисел #7
Если бы все те, кто предоставил свой вариант, помнили свойство (x,1) = 1, то сразу бы написали более оптимальный вариант программы.

Цитата Сообщение от HeroYukki Посмотреть сообщение
Hi4ko,
Fenixsar, ну раз вру давайте ссылки, скажу спасибо.
Просто посмотрите свойства НОД в любой книге по теории чисел. Даже в банальной википедии это есть
http://ru.wikipedia.org/wiki/%CD%E0%...E8%F2%E5%EB%FC
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.07.2012, 18:26     Алгоритм Евклида для n целых чисел
Еще ссылки по теме:

C++ Реализуйте алгоритм сортировки для массива, содержащего указатели на объекты-множества целых чисел
C++ Алгоритм Евклида для одномерных массивов
Найти наибольший общий делитель трех заданных натуральных чисел, используя алгоритм Евклида C++

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

Или воспользуйтесь поиском по форуму:
Fenixsar
 Аватар для Fenixsar
3 / 3 / 0
Регистрация: 26.08.2008
Сообщений: 19
19.07.2012, 18:26     Алгоритм Евклида для n целых чисел #8
Цитата Сообщение от HeroYukki Посмотреть сообщение
Fenixsar, ну раз вру давайте ссылки, скажу спасибо.
Первая ссылка в гугле: Вики
Там же и примеры реализации можно самому попробовать разобрать.
Yandex
Объявления
19.07.2012, 18:26     Алгоритм Евклида для n целых чисел
Ответ Создать тему
Опции темы

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