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

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

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

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

26.03.2012, 14:46. Просмотров 1160. Ответов 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++
Всем привет! Тут такая задачка, не могу понять как делать( Помогите, пожалуйста. Определить наибольший общий делитель для двух...

Наибольший общий делитель для двух 80-значных чисел - C++
Помогите, пожалуйста, написать программу для нахождения НОД для двух 80-значных чисел. Я так понимаю, что это нужно реализовать через...

Наибольший общий делитель для массива целых чисел - C++
Подскажите кто-нибудь алгоритм для нахождения НОД целых чисел в количестве более 2-х

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
x1Mike7x
216 / 129 / 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
1929 / 1195 / 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;
deepLulz
4 / 4 / 0
Регистрация: 12.02.2012
Сообщений: 46
26.03.2012, 18:02  [ТС] #8
Hemull, но опять же, этим можно пользоваться когда 2 известных числа, а если их неизвестное множество?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.03.2012, 18:02
Привет! Вот еще темы с ответами:

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

Разработать функцию, которая для заданного натурального числа N и M возвращает их наибольший общий делитель. - C++
Привет всем кто читает эту тему! Пожалуйста, кому не трудно помогите с задачами на функци, заранее огромное спасибо. I Разработка...

Найти наиболее больший общий делитель для последовательности - C++
Дано натуральное число n и натуральные числа a1, a2, ..., an. Найти наиболее больший общий делитель для заданной последовательности....

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
26.03.2012, 18:02
Ответ Создать тему
Опции темы

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