对数器--验证算法的正确性

对数器是用于验证算法正确性的一种测试方法。对数器的基本思想是使用一个简单但是正确的算法（暴力算法）生成问题的答案，然后用待测试的算法也生成答案，最后比较两者的结果是否一致。如果结果不一致，就说明待测试的算法可能存在问题。

下面是一个示例，使用对数器验证选择排序的正确性：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int* arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

void selectionSort(int* arr, int length) {
    if (arr == NULL || length < 2) {
        return;
    }
    for (int i = 0; i < length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < length; j++) {
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        swap(arr, i, minIndex);
    }
}

// 暴力算法（正确的排序方法）
void correctSort(int* arr, int length) {
    for (int i = 0; i < length - 1; i++) {
        for (int j = i + 1; j < length; j++) {
            if (arr[j] < arr[i]) {
                swap(arr, i, j);
            }
        }
    }
}

// 验证算法的正确性
int validateSort(int* arr, int length) {
    int* copy = malloc(sizeof(int) * length);
    for (int i = 0; i < length; i++) {
        copy[i] = arr[i];
    }

    selectionSort(arr, length); // 待测试的算法
    correctSort(copy, length);  // 暴力算法

    for (int i = 0; i < length; i++) {
        if (arr[i] != copy[i]) {
            free(copy);
            return 0; // 验证失败
        }
    }

    free(copy);
    return 1; // 验证成功
}

int main() {
    srand(time(NULL)); // 设置随机数种子

    for (int i = 0; i < 1000; i++) { // 随机生成1000个测试用例
        int length = rand() % 100 + 1; // 随机数组长度
        int* arr = malloc(sizeof(int) * length);

        for (int j = 0; j < length; j++) {
            arr[j] = rand() % 1000; // 随机数组元素
        }

        if (!validateSort(arr, length)) {
            printf("Validation failed!\n");
        }

        free(arr);
    }

    printf("Validation passed!\n");

    return 0;
}

这个示例中，correctSort 函数使用了简单但是正确的排序算法（冒泡排序），selectionSort 函数是待测试的算法。validateSort 函数用来验证两个算法的结果是否一致。主函数中使用对数器生成了1000个随机测试用例，然后对每个测试用例进行验证。如果验证失败，程序输出 “Validation failed!”，否则输出 “Validation passed!”。