文章目录

• 扩展欧几里得&简版printf函数实现
• • 一、扩展欧几里得
  • 二、简版 printf 函数实现

扩展欧几里得&简版printf函数实现

一、扩展欧几里得

欧几里得算法可以快速求解 a * x + b * y = 1 方程的一组整数解。

当 b = 0 时，可得 a * x = 1，当 a = 1，x = 1，y = 任意值 时满足条件。欧几里得算法最后一步也是 b = 0 时，返回 a 的值。求解一组解的过程与欧几里得算法的流程类似，属于递归和回溯的应用。

#include <stdio.h>

int ex_gcd(int a, int b, int *x, int *y) {
        if (!b) {
                *x = 1, *y = 0;
                return a;
        }
        int xx, yy, ret = ex_gcd(b, a % b, &xx, &yy);
        *x = yy;
        *y = xx - a / b * yy;
        return ret;
}

int main() {
        int a, b, x, y;
        while (~scanf("%d%d", &a, &b)) {
                printf("ex_gcd(%d, %d) = %d\n", a, b, ex_gcd(a, b, &x, &y));
                printf("%d * %d + %d * %d = %d\n", a, x, b, y, a * x + b * y);
        }
}

此代码为扩展欧几里得算法，解决的问题是： a * x + b * y = gcd(a, b) 的一组整数解。

二、简版 printf 函数实现

#include <stdio.h>
#include <stdarg.h>
#include <inttypes.h>

int output_num(int x, int digit) {
        int cnt = 0;
        while (x) {
                putchar(x % 10 + '0'), ++cnt;
                x /= 10;
        }
        return cnt;
}

int reverse_num(int x, int *temp) {
        int cnt = 0;
        do {
                *temp = *temp * 10 + x % 10;
                x /= 10;
                cnt++;
        } while (x);
        return cnt;
}

// const 代表可以接收一个常量，是不允许被修改的 
int my_printf(const char *frm, ...) {
        int cnt = 0;
        va_list arg;
        va_start(arg, frm);
        #define PUTC(a) putchar(a), ++cnt
        // 字符串的末尾是字符 '\0', '\0' = 0 
        for (int i = 0; frm[i]; i++) {
                switch (frm[i]) {
                        case '%': {
                                switch (frm[++i]) {
                                        case '%': PUTC(frm[i]); break;
                                        case 'd': {
                                                int x = va_arg(arg, int);
                                                uint32_t xx = 0;
                                                if (x < 0) {
                                                        PUTC('-');
                                                        xx = -x;
                                                }
                                                int x1 = xx / 100000, x2 = xx % 100000;
                                                int temp1 = 0, temp2 = 0;
                                                int digit1 = reverse_num(x1, &temp1);
                                                int digit2 = reverse_num(x2, &temp2);
                                                if (x1) digit2 = 5;
                                                else digit1 = 0;
                                                cnt += output_num(temp1, digit1);
                                                cnt += output_num(temp2, digit2);
                                        } break;
                                        case 's': {
                                                const char *str = va_arg(arg, const char *);
                                                for (int i = 0; str[i]; i++) {
                                                        PUTC(str[i]);
                                                }
                                        } break;
                                  }
                        } break;
                        default: PUTC(frm[i]); break;
                }
        }
        #undef PUTC
        va_end(arg);
        return cnt;
}

int main() {
        int a = -123;
        printf("hello world!\n");
        my_printf("hello world!\n");
        printf("int (a) = %d\n", a);
        my_printf("int (a) = %d\n", a);
        printf("INT32_MAX = %d\n", INT32_MAX);
        my_printf("INT32_MAX = %d\n", INT32_MAX);
        printf("INT32_MIN = %d\n", INT32_MIN);
        my_printf("INT32_MIN = %d\n", INT32_MIN);
        return 0;
}