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

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

Войти
Регистрация
Восстановить пароль
 
deepLulz
4 / 4 / 0
Регистрация: 12.02.2012
Сообщений: 46
#1

Наибольший общий делитель для последовательности - C++

26.03.2012, 14:46. Просмотров 1075. Ответов 7
Метки нет (Все метки)

Знаю, что решений задач по алгоритму Евклида на форуме полно, но не одна не подходит. Задание звучит следующим образом:
Дано натуральное число N и натуральные числа a1,a2,a3...aN. Найти наибольший общий делитель.
Массивы использовать нельзя. То есть числа я ввожу следующим образом:
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
main(){
    float a;
    unsigned int i,n;
    printf("n=");
    scanf("%u",&n);
    for(i=1;i<=n;i++){
        printf("a%u=",i);
        scanf("%f",&a);
    }
    return 0;
}
То есть изначально я не знаю ни сколько будет цифр ни какие они. Так же нельзя никуда их сохранять, я думаю это очевидно, так как неизвестно сколько переменных мне нужно зарезервировать и какие в следствии "пускать в бой".
В чистом виде алгоритм Евклида в моем случае не подходит, так что может есть у кого какие предположения и предложения?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.03.2012, 14:46     Наибольший общий делитель для последовательности
Посмотрите здесь:

Наибольший общий делитель C++
C++ наибольший общий делитель
C++ Наибольший общий делитель для массива целых чисел
Наибольший общий делитель на С++ C++
Разработать функцию, которая для заданного натурального числа N и M возвращает их наибольший общий делитель. C++
Определить наибольший общий делитель для 3-х введенных с клавиатуры чисел C++
Наибольший общий делитель для двух 80-значных чисел C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
x1Mike7x
214 / 127 / 6
Регистрация: 06.11.2010
Сообщений: 234
26.03.2012, 14:51     Наибольший общий делитель для последовательности #2
C++
1
2
3
4
5
6
7
cin >> n >> r; // предполагается, что n > 0
for ( int i = 1; i < n; ++i )
{
    cin >> x;
    r = gcd( x, r );
}
cout << r << endl;
Суть в том, что НОД для последовательности чисел ( например, для 4х чисел ) = НОД( а1, НОД( а2, НОД( а3, а4 ) ) ).
deepLulz
4 / 4 / 0
Регистрация: 12.02.2012
Сообщений: 46
26.03.2012, 15:14  [ТС]     Наибольший общий делитель для последовательности #3
x1Mike7x, какое конкретно действие выполняет функция gcd? Как ее можно заменить чисто математическим способом?

Добавлено через 14 минут
Написал
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <iostream>
#include <conio.h>
 
main(){
    int i,n,x,nod;
    printf("N=");
    scanf("%u",&n);
    for(i=1;i<=n;i++){
        printf("a%u=",i);
        scanf("%f",&x);
        nod = GCD(x,nod);
    }
    getch();
    return 0;
}
Но при попытке скомпилировать "error: iostream: No such file or directory"
diagon
Higher
1921 / 1187 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
26.03.2012, 15:18     Наибольший общий делитель для последовательности #4
Цитата Сообщение от deepLulz Посмотреть сообщение
gcd
greatest common divisor(наибольший общий делитель)

Цитата Сообщение от deepLulz Посмотреть сообщение
"error: iostream: No such file or directory"
Так уберите iostream, у вас код на С.
Hemull
47 / 47 / 1
Регистрация: 12.03.2012
Сообщений: 108
26.03.2012, 15:21     Наибольший общий делитель для последовательности #5
deepLulz, gcd = нод
deepLulz
4 / 4 / 0
Регистрация: 12.02.2012
Сообщений: 46
26.03.2012, 17:55  [ТС]     Наибольший общий делитель для последовательности #6
Цитата Сообщение от diagon Посмотреть сообщение
Так уберите iostream, у вас код на С.
Вообще то на C++. Если убираю iostream то "indefined reference to GCD".
И повторю вопрос еще раз: какие математические операции производит GCD?
Hemull
47 / 47 / 1
Регистрация: 12.03.2012
Сообщений: 108
26.03.2012, 17:59     Наибольший общий делитель для последовательности #7
C++
1
2
3
4
5
6
7
while(a!=b)
    {
    if(a>b)
    a=a-b;
    else b=b-a;
    }
    return a
чисто математически
чтоб использовать #include <iostream> надо дописать using namespace std;
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.03.2012, 18:02     Наибольший общий делитель для последовательности
Еще ссылки по теме:

Найти наибольший общий делитель для элементов произвольного одномерного массива C++
C++ Найти наиболее больший общий делитель для последовательности
Разработать функцию, которая для заданных натуральных чисел N и M возвращает их наибольший общий делитель C++
Вывести наибольший общий делитель всех элементов заданной последовательности целых чисел C++
C++ Наибольший общий делитель для двух чисел

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

Или воспользуйтесь поиском по форуму:
deepLulz
4 / 4 / 0
Регистрация: 12.02.2012
Сообщений: 46
26.03.2012, 18:02  [ТС]     Наибольший общий делитель для последовательности #8
Hemull, но опять же, этим можно пользоваться когда 2 известных числа, а если их неизвестное множество?
Yandex
Объявления
26.03.2012, 18:02     Наибольший общий делитель для последовательности
Ответ Создать тему
Опции темы

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