您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C語言算法實戰： amicable numbers（親和數）查找與快速排序完整實現

編輯：關於C

題目一：3000 以內親和數對查找

定義：若 sum(divisors(a)) = b 且 sum(divisors(b)) = a（a != b），則 (a,b) 為親和數對。如 (220, 284)。

優化**：因子成對出現，遍歷至 sqrt(n) 即可累加雙側因子。

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

int sum_proper_divisors(int n) {
    int sum = 0;
    for (int i = 1; i <= (int)sqrt(n); i++) {
        if (n % i == 0) {
            sum += i;
            int pair = n / i;
            if (pair != i && pair != n) sum += pair; // 排除自身與重複
        }
    }
    return sum;
}

int main(void) {
    for (int x = 1; x < 3000; x++) {
        int y = sum_proper_divisors(x);
        if (y > x && y < 3000 && sum_proper_divisors(y) == x) {
            printf("%d %d\n", x, y);
        }
    }
    return 0;
}

輸出：

220 284
1184 1210
2620 2924

題目二：快速排序（遞歸分治）

核心邏輯：單趟分區將基準值歸位，左側 ≤ 基準，右側 ≥ 基準，遞歸處理子區間。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 1000

void quick_sort(int a[], int left, int right) {
    if (left >= right) return;

    int i = left, j = right;
    int pivot = a[left];           // 選最左為基準

    while (i < j) {
        while (i < j && a[j] >= pivot) j--; // 從右找小於 pivot
        if (i < j) a[i++] = a[j];
        while (i < j && a[i] <= pivot) i++; // 從左找大於 pivot
        if (i < j) a[j--] = a[i];
    }
    a[i] = pivot;                  // 基準歸位

    quick_sort(a, left, i - 1);
    quick_sort(a, i + 1, right);
}

int main(void) {
    int a[N + 1], i;               // 1-based 便於邏輯
    srand((unsigned)time(NULL));
    for (i = 1; i <= N; i++) a[i] = rand() % (N + 1);

    printf("原序列（前20）: ");
    for (i = 1; i <= 20; i++) printf("%d ", a[i]);
    putchar('\n');

    quick_sort(a, 1, N);

    printf("排序後（前20）: ");
    for (i = 1; i <= 20; i++) printf("%d ", a[i]);
    putchar('\n');
    return 0;
}