C 语言第30题：辗转相除法手写过程逐步打印

题目

辗转相除法手写过程逐步打印

思路

在 GCD 循环里每步 printf 当前 a,b 与 a%b；直到余数 0，最后一非零除数即 GCD，也可逐步打印商。

解题分析

本题重点是展示辗转相除每一步的商和余数，算法与第 23 题相同，多的是格式化输出，便于对照手算。

完整程序

#include <stdio.h>

int main(void)
{
    int a, b;
    if (scanf("%d %d", &a, &b) != 2) {
        return 1;
    }
    int x = a, y = b;
    while (y) {
        printf("%d / %d = %d ... %d\n", x, y, x / y, x % y);
        int t = x % y;
        x = y;
        y = t;
    }
    printf("gcd = %d\n", x);
    return 0;
}

运行示例

输入：

48 18

输出：

48 / 18 = 2 ... 12
18 / 12 = 1 ... 6
12 / 6 = 2 ... 0
gcd = 6