동네가수

다소 쉬운 과제라고 생각했으나 %연산으로 나머지를 구하게되면 -2 % 10 의 결과가 -2가 나오는 현상이 발생하기 때문에

[ 나누어지는수 = 몫 * 나누는수 + 나머지 ] 식에서 [몫 * 나누는수] 를 이항하여 나머지를 구하는 함수를 작성하여

해결하였다. 소스코드는 아래와 같다.

// 확장된 유클리드 알고리즘 수행

#include <stdio.h>
#include <math.h>

// 모듈러 함수 -> [나누어지는수 = 몫 x 나누는수 + 나머지] 를 이항을 이용하여
// [나누어지는수 - 몫 x 나누는수 = 나머지] 형태로 하여 나머지를 구한다.
int mod(int a, int b)
{
    if (b > 0)
        return (int) (a - floor((float) a / (float) b) * b);
    else
        return (int) (a - ceil((float) a / (float) b) * b);
}   

// 포인터를 매개변수로 받아 변수값들을 교환한다.
void shift(int *n1, int *n2, int n)
{
    *n1 = *n2;
    *n2 = n;
}

int main(int argc, char *argv[])
{
    int q, a, b, r;            // 몫, 정수1, 정수2, 나머지
    int s, s1 = 1, s2 = 0;    // s, s1, s2
    int t, t1 = 0, t2 = 1;    // t, t1, t2

    printf("확장된 유클리드 알고리즘을 수행합니다.\n\n");
    printf("두 정수를 입력해 주세요 : ");

    scanf("%d %d", &a, &b);
   
    printf("\n");
    printf("\n 몫   정수1 정수2 나머지 s1  s2   s  t1  t2   t\n");

    // 알고리즘 수행구간
    while (b != 0)
    {
        q = floor((float)a / (float)b);
        r = mod(a, b);

        s = s1 - s2 * q;
        t = t1 - t2 * q;

        printf("%3d %5d %5d %5d %5d %3d %3d %3d %3d %3d\n", q, a, b, r, s1, s2, s, t1, t2, t);
       
        // 값 이동 구간
        shift(&a, &b, r);
        shift(&s1, &s2, s);
        shift(&t1, &t2, t);
    }
    printf("%9d %5d %11d %11d\n\n", a, b, s1, t1);

    return 0;
}