C語言復習筆記：17 種實用小演算法解決實際問題

編輯：關於C語言

前言

本文整理 17 種經典 C 語言小演算法，涵蓋日期計算、進制轉換、數學問題、圖形列印、遞迴、貪婪等核心技巧，每題附完整代碼與核心邏輯解析，適合面試複習與工程參考。

1. 日期轉年內天數 (含閏年)

核心：累加月份天數表 + 閏年判斷 (y%400==0)||(y%4==0&&y%100!=0) + 閏年且月>2 加 1。


int dayOfYear(int y, int m, int d) {
    static const int mdays[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
    int sum = d;
    for (int i = 0; i < m-1; i++) sum += mdays[i];
    if (m > 2 && (y%400==0 || (y%4==0 && y%100!=0))) sum++;
    return sum;
}

2. 十進制轉十六進制 (手動實現)

核心：反覆取模 16，餘數 0-9 對應 '0'-'9'，10-15 對應 'A'-'F'，結果反序輸出。


void decToHex(unsigned int n) {
    if (n == 0) { putchar('0'); return; }
    char buf[32]; int i = 0;
    while (n) {
        int r = n % 16;
        buf[i++] = (r < 10) ? '0'+r : 'A'+r-10;
        n /= 16;
    }
    while (i--) putchar(buf[i]);
}

3. 字母金字塔列印 (技巧：預存陣列)

核心：計算行數、寬度，用二維陣列暫存字元，利用對稱性填充左右兩側。


void printLetterPyramid(char top) {
    int n = top - 'A' + 1;
    int width = 2*n - 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < width; j++) {
            int mid = n - 1;
            char c = (abs(j-mid) <= i) ? 'A' + i - abs(j-mid) : ' ';
            putchar(c);
        }
        putchar('\n');
    }
}

4. 浮點數冪運算 (遞迴/迭代)

核心：處理負指數 (倒數)、零指數 (返回 1)、快速冪 (二進制分解指數)。


double power(double base, int exp) {
    if (exp == 0) return 1;
    if (exp < 0) return 1 / power(base, -exp);
    double result = 1;
    while (exp) {
        if (exp & 1) result *= base;
        base *= base;
        exp >>= 1;
    }
    return result;
}

5. 輸出小於 N 的所有質數 (試除法優化)

核心：只試除至 sqrt(n)，跳過偶數，用 6k±1 進一步優化。


bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n%2==0 || n%3==0) return false;
    for (int i = 5; i*i <= n; i += 6)
        if (n%i==0 || n%(i+2)==0) return false;
    return true;
}
void primesUnder(int N) {
    for (int i = 2; i < N; i++) if (isPrime(i)) printf("%d ", i);
}

6. 輾轉相除法求最大公約數 (GCD) / 最小公倍數 (LCM)

核心：gcd(a,b) = gcd(b, a%b) 直到 b=0。lcm = a/gcd*b (避免溢位)。


int gcd(int a, int b) {
    while (b) { int t = a%b; a = b; b = t; }
    return a;
}
long long lcm(int a, int b) {
    return (long long)a / gcd(a,b) * b;
}

7. 漢諾塔遞迴解法

核心：移動 n-1 盤到輔助柱 → 移動第 n 盤到目標柱 → 移動 n-1 盤從輔助柱到目標柱。


void hanoi(int n, char from, char aux, char to) {
    if (n == 1) { printf("%c->%c\n", from, to); return; }
    hanoi(n-1, from, to, aux);
    printf("%c->%c\n", from, to);
    hanoi(n-1, aux, from, to);
}

8. 乒乓球賽配對 (全排列+條件篩選)

核心：三層迴圈生成對手排列，條件過濾 (a不和x、c不和x/z)。


void matchPairs() {
    for (char i='x'; i<='z'; i++)
        for (char j='x'; j<='z'; j++)
            if (i!=j)
                for (char k='x'; k<='z'; k++)
                    if (i!=k && j!=k && i!='x' && k!='x' && k!='z')
                        printf("a-%c b-%c c-%c\n", i, j, k);
}

9. 函數區間最大值 (數值逼近)

核心：在區間內等距取樣比較，或用黃金分割/三分法優化。示例為簡單掃描。


double findMax(double (*f)(double), double l, double r, double eps) {
    double maxv = f(l);
    for (double x = l; x <= r; x += eps)
        if (f(x) > maxv) maxv = f(x);
    return maxv;
}

10. 質因數分解

核心：從 2 試除至 sqrt(n)，能整除則輸出並除盡，否則 i++。剩餘 n>1 為質數。


void factorize(int n) {
    printf("%d=", n);
    for (int i = 2; i*i <= n; i++)
        while (n%i == 0) { printf("%d*", i); n/=i; }
    if (n > 1) printf("%d", n);
    putchar('\n');
}

11. 百錢百雞 (古典不定方程)

核心：公雞 5 元、母雞 3 元、小雞 1/3 元，共 100 元買 100 隻。雙重迴圈 + 整數判斷。


void hundredChickens() {
    for (int cock=0; cock<=20; cock++)
        for (int hen=0; hen<=33; hen++) {
            int chick = 100 - cock - hen;
            if (cock*5 + hen*3 + chick/3 == 100 && chick%3==0)
                printf("公%d 母%d 小%d\n", cock, hen, chick);
        }
}

12. 字串交叉合併 (指標操作)

核心：兩指標輪流輸出字元，至較短字串結尾，再接剩餘部分。


void interleave(char *a, char *b) {
    while (*a && *b) { putchar(*a++); putchar(*b++); }
    while (*a) putchar(*a++);
    while (*b) putchar(*b++);
    putchar('\n');
}

13. 完數 (完美數) 尋找

核心：因子和等於自身。優化：只遍歷至 sqrt(n)，成對累加因子。


bool isPerfect(int n) {
    if (n <= 1) return false;
    int sum = 1;
    for (int i = 2; i*i <= n; i++)
        if (n%i == 0) { sum += i; if (i != n/i) sum += n/i; }
    return sum == n;
}

14. 容器倒水移動 (模擬/狀態空間)

核心：三容器倒水操作，BFS/DFS 搜尋目標狀態。此處展示單步倒水邏輯。


void pour(int *from, int *to, int cap_to) {
    int space = cap_to - *to;
    int amount = (*from < space) ? *from : space;
    *from -= amount; *to += amount;
}

15. 猴子吃桃 (逆向遞推)

核心：第 n 天剩 x，第 n-1 天 = (x+1)*2。從第 10 天剩 1 反推至第 1 天。


int monkeyPeach(int days) {
    int peach = 1;
    while (--days) peach = (peach + 1) * 2;
    return peach;
}

16. 字元統計 (字母/空格/數字/其他)

核心：getchar() 迴圈，ctype.h 分類函數 (isalpha, isspace, isdigit)。


void countChars() {
    int c, alpha=0, space=0, digit=0, other=0;
    while ((c=getchar()) != '\n' && c != EOF) {
        if (isalpha(c)) alpha++;
        else if (isspace(c)) space++;
        else if (isdigit(c)) digit++;
        else other++;
    }
    printf("字母%d 空格%d 數字%d 其他%d\n", alpha, space, digit, other);
}

17. 貪婪算法：區間調度 / 活動選擇

核心：按結束時間排序，貪婪選擇最早結束且不衝突的活動。


typedef struct { int s, e; } Act;
int cmp(const void *a, const void *b) { return ((Act*)a)->e - ((Act*)b)->e; }

void activitySelect(Act a[], int n) {
    qsort(a, n, sizeof(Act), cmp);
    int last = -1, cnt = 0;
    for (int i = 0; i < n; i++)
        if (a[i].s >= last) { last = a[i].e; cnt++; }
    printf("最多可安排 %d 項活動\n", cnt);
}

總結：演算法分類與核心技巧對照表

類別	題目	核心技巧	時間複雜度
日期/數學	1,2,4,5,6,10,11,13	模運算、試除法、輾轉相除、不定方程	O(√n) ~ O(n)
遞迴/分治	7,15	問題分解、逆向推導	O(2^n), O(n)
排列組合/搜尋	8,14	全排列生成、狀態空間搜尋	O(n!), 指數級
貪婪/排序	17	局部最優→全域最優、排序預處理	O(n log n)
字串/指標	12,16	指標遍歷、字元分類	O(n)
幾何/圖形	3	座標對稱、陣列暫存	O(n²)