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

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

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

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

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

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

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

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

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

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

7
Mr.X
Эксперт С++
3182 / 1709 / 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
Hi4ko
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
Mr.X
Эксперт С++
3182 / 1709 / 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
Fenixsar
3 / 3 / 1
Регистрация: 26.08.2008
Сообщений: 19
19.07.2012, 17:21 5
Цитата Сообщение от HeroYukki Посмотреть сообщение
Самый главный вопрос: это вообще как? Сколько не гуглил, а алгоритма такого я не нашел.
Врешь, дорогой, гугл все знает
1
HeroYukki
0 / 0 / 0
Регистрация: 01.07.2012
Сообщений: 15
19.07.2012, 18:15  [ТС] 6
Hi4ko, Огромное спасибо, шикарный код.

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

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

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

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

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

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


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

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

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