查表法求解'自然数对'问题

一月 29, 2008

‘自然数对’是这样的一对自然数，他们的和与差的结果都是平方数，比如：自然数对32和68，根据定义32+68 = 100 = 10^2，68-32 = 36 = 6^2。现在的题目是：根据输入的两个100以内的自然数，打印出这两个整数之间的所有自然数对。

这道题不难，而且限制了范围，在两个100以内的自然数区间，很多人马上就能给出程序。这道题的有两个点需要思考：一个是关于平方数的判断；另一个就是两个数的组合控制。

关于平方数的判断，多数人采用的方法就是利用现成的sqrt函数来做判断。当然也有人和我想的一样，采用表查询的方法。因为题目明确限制了范围是两个100以内的数，试想一下100以内最大的两个数的和99+98=197，也就是说100以内自然数对的和如果是平方数的话，肯定是下面集合中的一个，这个集合为{1,4,9,16,25,36,49,64,81,100,121,144,169,196}。那么既然我们已经肯定了如此，我们还何必去做sqrt操作呢，直接在这个集合中查找不就行了，这也是一种最简单的查表法，至于表的存储结构和查询算法可自定义(影响性能)。

关于数的组合控制，很多人都会使用两层循环，这没错。除了循环，递归也是一个不错的方法。简单的看了下，这个例子还是比较符合递归的两个条件的：
1、有basis case；
2、规模逐渐缩小；

基于上述两点，这里给出一个简单的实现：
int square_number_tbl[] = {1,4,9,16,25,36,49,64,81,100,121,144,169,196};

int is_natural_number_pair(int a) {
    int i;
    //简单的顺序查找
    for (i = 0; i < sizeof(square_number_tbl)/sizeof(square_number_tbl[0]); i++) {
        if (square_number_tbl[i] == a) return 1;
    }
    return 0;
}

//find natural number pair
void find_nnp(int a, int b) {
    int i;
    if (b – a <=0) { //basis case
        return;
    }

    i = a;
    do {
        if (is_natural_number_pair(b+i) && is_natural_number_pair(b-i)) {
            printf("%d, %d\n", b, i);
        }
        i++;
    }while (i <= b);
    return find_nnp(a, b-1);//recursive invoke
}

int main() {
    int a, b; //we suppose that b is greater than a, and both are less than 100
    printf("Please Input two integrals (1，100):");
    scanf("%d %d",&a,&b);

    find_nnp(a, b);
}

完成这个后，突然又想到的一个方法：根据输入的范围[a, b]动态构造一张矩阵，矩阵的x轴方向和y轴方向的都是由a->b的数轴。矩阵中的数值按如下方式初始化M(x, y) = x + y; M(y, x) = y – x; (y > x)；初始化完矩阵后，对矩阵进行一次扫描，并在is_natural_number_pair的帮助下找到所有自然数对。