程序对拍

有些时候，我们不知道写出的程序是否正确，或者明确地知道有错误，但不清楚问题在哪里，手工试了多组测试数据都没问题，这时可以考虑对拍。

对拍有三个要素：待验证程序、参考程序和随机数据生成器。

参考程序可以是通过暴力方法求解代码或者别人的正确代码，而随机数生成器则需根据实际要求定制，但有些基础函数还是可以复用的。

生成随机数必须先初始化种子：

#include <sys/time.h>
#include <stdlib.h>
void init() {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    srand(tv.tv_usec);
}

生成一个范围在[lo, hi]内的随机正整数：

int randn(int lo, int hi) {
    return lo + rand() % (hi - lo + 1);
}

生成n（nlo<=n<=nhi）个范围在[lo, hi]内的随机数：

void nrandn(int nlo, int nhi, int lo, int hi) {
    int i, n = randn(nlo, nhi);
    printf("%d\n", n);
    for (i = 1; i <= n; i++)
        printf("%d%c", randn(lo, hi), i == n ? '\n' : ' ');
}

随机打乱顺序：

void shuffle(int a[], int n) {
    int i, j, k;
    for (i = 0; i < n; i++) {
        j = i + rand() % (n - i);
        k = a[i]; a[i] = a[j]; a[j] = k;
    }
}

生成lo~hi的一个排列：

void permutation(int lo, int hi) {
    int i, *a = malloc(sizeof(int) * (hi - lo + 1));
    for (i = lo; i <= hi; i++)
        a[i-lo] = i;
    shuffle(a, hi - lo + 1);
    for (i = lo; i <= hi; i++)
        printf("%d%c", a[i-lo], i == hi ? '\n' : ' ');
    free(a);
}

随机生成字符串：

void randstr(char *str, int llo, int lhi) {
    int llen = randn(llo, lhi), slen = strlen(str);
    while (llen--) {
        int x = rand() % slen;
        putchar(str[x]);
    }
}

随机生成一棵树：

void randtree(int n) {
    int *a = malloc(sizeof(int) * n);
    int *p = malloc(sizeof(int) * n);
    int i, pn = 0, q;
    printf("%d\n", n);
    for (i = 0; i < n; i++) a[i] = i + 1;
    shuffle(a, n);
    p[pn++] = a[0];
    for (i = 1; i < n; i++) {
        q = rand() % pn;
        printf("%d %d\n", p[q], a[i]);
        p[pn++] = a[i];
    }
    free(a); free(p);
}

假设待验证程序为x，参考程序为b，随机数生成器为gen，可循环调用比较输出是否一致，直到找出输出不一样的输入数据为止。

#!/bin/bash
idx=1
while true; do
    echo "Case $idx:"
    ./gen >data
    ./x <data >x.out
    ./b <data >b.out
    diff x.out b.out &>/dev/null
    if [ $? -ne 0 ]; then
        cat data
        echo "Your Answer:"
        cat x.out
        echo "Expect Answer:"
        cat b.out
        break
    fi
    let idx++
done