Поиск GCD языка Array Code C

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

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int A[10]={112, 160, 180, 240, 288, 32, 480, 96, 60, 72};
    int i;
    int j;
    int minimum = A[0];
    int GCD;
    int temp;

    for (i=1;i<9;i++)
    {
        if( A[i] < minimum)
        {
            minimum = A[i];
        }
    }

    for (i=1; i < minimum/2; i++)
    {
        for (j = 0; j < 9;j++)
        {
            GCD = 2*i;
            temp = ((A[j])/(GCD));
            int check = temp%1;
            if (check == 0)
                break;
        }
    }

    printf("The Greates Common Denominator is: %d", GCD);

    return 0;
}

c arrays for-loop greatest-common-divisor
person Cod_Ubau    schedule 15.01.2014    source источник
comment
Обратите внимание, что temp % 1 всегда будет равно нулю.   -  person Jonathan Leffler    schedule 15.01.2014
comment
@JonathanLeffler, как правильно проверять десятичные дроби ??   -  person Cod_Ubau    schedule 15.01.2014
comment
Поскольку вы сохраняете результаты в int переменных, не будет никаких «десятичных чисел» (при условии, что вы имеете в виду дробные числа).   -  person Jonathan Leffler    schedule 15.01.2014
comment
Я не думаю, что вам нужно найти наименьшее число. Вы можете рассчитать: int g = a[0]; for (i = 1; i < 10; i++) { g = gcd(a[i], g); } должно работать нормально (где gcd() — это функция для вычисления НОД двух чисел.   -  person Jonathan Leffler    schedule 15.01.2014

Ответы (4)


arrow_upward
2
arrow_downward 

#include <stdio.h>

static int gcd(int x, int y)
{
    int r;

    if (x <= 0 || y <= 0)
        return(0);

    while ((r = x % y) != 0)
    {
        x = y;
        y = r;
    }
    return(y);
}

int main(void)
{
    int A[10] = { 112, 160, 180, 240, 288, 32, 480, 96, 60, 72 };
    int g = A[0];

    for (int i = 1; i < 10; i++)
        g = gcd(g, A[i]);

    printf("The Greatest Common Denominator is: %d\n", g);

    return 0;
}

Ответ 4. Это совершенно верно; это НОД 32 и 60; все остальное делится на 4.

При желании вы можете оптимизировать цикл с помощью:

    for (int i = 1; i < 10 && g != 1; i++)
        g = gcd(g, A[i]);

Когда НОД равен 1, он больше не увеличивается,

person Jonathan Leffler    schedule 16.01.2014

arrow_upward

arrow_downward

person    schedule
comment
Умная рекурсия; спасает ли это что-нибудь по сравнению с простой итерацией? Мне кажется, что он будет выполнять такое же количество вычислений GCD, но использует дополнительное пространство в стеке (по большей части это не является существенным фактором). - person Jonathan Leffler; 16.01.2014
comment
@JonathanLeffler с помощью простого цикла, наверное, хорошо. Стек также требуется доп. Я думаю, как нет много достоинств. - person BLUEPIXY; 16.01.2014
comment
Есть вероятность, что преимущество этого метода (можно переписать в простой цикл) можно свести к вычислению остатка. например в этом случае мои 15, ваши 21. - person BLUEPIXY; 16.01.2014

arrow_upward

arrow_downward

person    schedule
comment
Вы можете добавить небольшое объяснение того, почему ваш код работает для OP; Убедитесь, что вы добавили соответствующие части кода - person techspider; 10.06.2016

arrow_upward

arrow_downward

person    schedule
comment
Добро пожаловать в Stack Overflow! Всего несколько советов: вы должны прокомментировать свой код, объясняя внесенные вами изменения и почему это работает. Также помогает, если вы придерживаетесь изменений, требуемых пользователем. Например, меня смущает, что теперь вместо исходного входного массива требуется ввод. - person George; 24.07.2018