Странное поведение в моем коде для определенного теста

Question

Предполагается, что программа меняет местами соседние элементы, у которых нет общего знаменателя, и элемент можно поменять местами только один раз.Когда я запускаю программу, почти для любого ввода работает нормально.За исключением этого:

100 // ввод для количества элементов

48 92 76 93 17 38 59 34 53 99 58 20 50 0 38 37 16 36 91 12 59 1 76 82 2076 7 72 13 70 64 23 81 70 41 69 11 0 16 41 37 83 41 99 73 79 4 38 24 32 87 38 95 24 77 30 61 13 89 67 87 76 22 31 67 31 25 90 6 76 21 43 40 55 7291 91 28 18 58 72 71 83 22 99 23 86 58 75 53 69 29 5 55 46 8 98 55 19 46 // elements

Для этого ввода программа зависает и ничего не печатает.Кто-то знает, что происходит в этом конкретном случае?

#include <stdio.h>
int nzd(int a, int b)
{
    if(a==b || b==0) 
        return a;
    if(a>b) 
        return nzd(a-b, b);
    return nzd(a, b-a);
}
int swap(int *niza, int i)
{
    int temp;
    temp=*(niza+i);
    *(niza+i)=*(niza+i+1);
    *(niza+i+1)=temp;
}
int main()
{
    int a[100], n, i;
    scanf("%d", &n);
    for(i=0; i<n; i++)
    {
        scanf("%d", &a[i]);
    }
    for(i=0; i<n; i++)
    {
        if(i+1==n) continue;
        if(nzd(a[i], a[i+1])==1)
        {
            swap(a, i);
            i++;
        }
    }
    for(i=0; i<n; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

Answer 1

Ваша функция nzd() не может правильно обработать регистр a == 0 и застревает в бесконечном цикле.Вы должны также разобраться с этим делом:

int nzd(int a, int b)
{
    if(a==b || a==0 || b==0) 
        return a;
    if(a>b) 
        return nzd(a-b, b);
    return nzd(a, b-a);
}

Answer 2

Ваша функция gcd проверяет регистр b==0, но не регистр a==0.Поскольку вы пропускаете эту проверку, в итоге вы набираете nzd(0, b-0);, что точно так же, как и предыдущий вызов.Это помещает вас в бесконечный цикл рекурсии, который в конечном итоге вызовет переполнение стека.

Добавьте проверку для этого случая в вашу функцию:

if(a==b || b==0 || a == 0)

Кроме того, более быстрая реализация gcd, называемаяАлгоритм Евклида выглядит следующим образом:

int gcd(int a, int b)
{
    if (b==0) {
        return a;
    } else {
        return (b, a%b);
    }
}