Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.53/19: Рейтинг темы: голосов - 19, средняя оценка - 4.53
0 / 0 / 0
Регистрация: 01.07.2012
Сообщений: 15
1

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

19.07.2012, 15:23. Просмотров 3673. Ответов 7
Метки нет (Все метки)

Задача:
Составить рекурсивную функцию, реализующую алгоритм Евклида для n целых чисел.

Самый главный вопрос: это вообще как? Сколько не гуглил, а алгоритма такого я не нашел. Или нужно алгоритм для двух чисел переделать под несколько? Разъясните, пожалуйста, что-куда, кодом или на пальцах, мне главное понять.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.07.2012, 15:23
Ответы с готовыми решениями:

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

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

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

Найти НОД двух целых чисел по алгоритму Евклида.
задание: Найти НОД двух целых чисел по алгоритму Евклида.

7
Эксперт С++
3204 / 1731 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
19.07.2012, 16:32 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;                 
    }
}
1
74 / 74 / 12
Регистрация: 21.10.2010
Сообщений: 376
19.07.2012, 16:32 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;
}
1
Эксперт С++
3204 / 1731 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
19.07.2012, 17:03 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;                 
    }
}
1
3 / 3 / 1
Регистрация: 26.08.2008
Сообщений: 31
19.07.2012, 17:21 5
Цитата Сообщение от HeroYukki Посмотреть сообщение
Самый главный вопрос: это вообще как? Сколько не гуглил, а алгоритма такого я не нашел.
Врешь, дорогой, гугл все знает
1
0 / 0 / 0
Регистрация: 01.07.2012
Сообщений: 15
19.07.2012, 18:15  [ТС] 6
Hi4ko, Огромное спасибо, шикарный код.

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

Fenixsar, ну раз вру давайте ссылки, скажу спасибо.
0
Эксперт С++
4251 / 2225 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
19.07.2012, 18:20 7
Если бы все те, кто предоставил свой вариант, помнили свойство (x,1) = 1, то сразу бы написали более оптимальный вариант программы.

Цитата Сообщение от HeroYukki Посмотреть сообщение
Hi4ko,
Fenixsar, ну раз вру давайте ссылки, скажу спасибо.
Просто посмотрите свойства НОД в любой книге по теории чисел. Даже в банальной википедии это есть
http://ru.wikipedia.org/wiki/%... 2%E5%EB%FC
1
3 / 3 / 1
Регистрация: 26.08.2008
Сообщений: 31
19.07.2012, 18:26 8
Цитата Сообщение от HeroYukki Посмотреть сообщение
Fenixsar, ну раз вру давайте ссылки, скажу спасибо.
Первая ссылка в гугле: Вики
Там же и примеры реализации можно самому попробовать разобрать.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.07.2012, 18:26

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Написать шаблоны функций для для вычисления суммы произведений двух соседних чисел для трех целых чисел и в одномерном массиве целых чисел
Написать шаблоны функций для для вычисления суммы произведений двух соседних чисел для трех целых...

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

Алгоритм поиска целых чисел для уравнения
Есть система уравнений вида: Нужно найти такие целые числа x и y от нуля до n, при которых оно...

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


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.