Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.69
HeroYukki
0 / 0 / 0
Регистрация: 01.07.2012
Сообщений: 15
#1

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

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

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

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

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

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

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

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

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

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

7
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 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 / 4
Регистрация: 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
Эксперт С++
3051 / 1696 / 265
Регистрация: 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 / 0
Регистрация: 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
Эксперт С++
4228 / 2202 / 150
Регистрация: 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 / 0
Регистрация: 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
Привет! Вот еще темы с ответами:

Алгоритм Евклида для одномерных массивов - C++
Всем привет. Задача в общем такая: Нужно реализовать алгоритм нахождение НОДа(Наибольшего общего делителя) двух длинных целых чисел. Нашел...

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

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

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


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

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

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