Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
123 lines (98 sloc) 5.11 KB
title tags categories date
判断语句有多少种替代方法
C
奇技淫巧
数学
计算机
2016-03-03 10:58:02 -0800

先来看一道C语言编程题:

#include <stdio.h>
#include <stdlib.h>
int main() {
    int array[100], i, n;
    for(i = 0; i < 100; i++)
    array[i] = i;
    /* 在下方补全代码 */

    /* 在上方补全代码 */
    return 0;
}

补全代码,使得程序将array的内容乱序输出,不得重复或遗漏,不得使用条件判断语句。

一个符合出题人意图的正确答案应该是:产生一个0~99的随机数,打印该项,然后交换该项和第99项;接下来产生一个0~98的随机数,打印该项,交换该项和第98项;产生0~97的随机数……依此类推。程序如下:
for(i = 100; i; i--) {
    n = rand() % i;
    printf("%d\n", array[n]);
    array[n] = array[i-1];
    /* 题目没有规定array不能被破坏,因此这样就可以了 */
}

不过,这道题本身所提出的限制有很大问题——究竟什么才叫“判断语句”?如果仅仅是不允许出现if的话,有许许多多绕开限制的方式。下面先给出最容易想到的,使用了判断语句的答案,然后研究如何绕开题目限制:

i = 0;
while(i < 100) {
    n = rand() % 100;
    if(array[n] != -1) {
        printf("%d\n", array[n]);
        array[n] = -1;
        i++;
    }
}

循环语句其实就包含了条件判断的功能,因此用循环语句可以代替判断语句:

i = 0;
while(i < 100) {
    n = rand() % 100;
    while(array[n] != -1) {
        printf("%d\n", array[n]);
        array[n] = -1;
        i++;
        break;
    }
}

不过这样一来,可以从根本上优化一下程序流程——把算法改成“不断生成随机数,直到选中的是没打印过的数字为止”:

for(i = 0; i < 100; i++) {
    do {
        n = rand() % 100;
    } while(array[n] == -1);
    printf("%d\n", array[n]);
    array[n] = -1;
}

不过,貌似(我说貌似,是因为这道题是一个同学拿来问我的,而他也不太清楚评判的具体标准)还有一条规定是,补写的部分只能出现一个循环语句,这样的话上述的方法就不行了。不过不要紧,我们还有?:运算符:

i = 0;
while(i < 100) {
    n = rand() % 100;
    array[n] != -1 ? (
        printf("%d\n", array[n]),
        array[n] = -1,
        i++
    ) : 0;
}

万一?:也被禁止使用了呢?毕竟它生来就是做条件判断用的。这也好办,还有另外一组神奇的运算符可以使用,就是&&||。以&&为例:

i = 0;
while(i < 100) {
    n = rand() % 100;
    array[n] != -1 && (
        printf("%d\n", array[n]),
        array[n] = -1,
        i++
    );
}

C标准规定,&&||运算符必须先对左侧的表达式求值,如果这一步就能确定整个表达式的值,那么右侧的表达式不得被求值。也就是说,a&&b这个表达式会先对a求值,如果a为假,那么结果肯定是假,b不会被求值。仅当a为真时b才会被求值。用&&代替判断语句,在其他脚本语言,尤其是shell中是很常见的做法。例如shell经常会有如下程序段:

test -f file && cat file # 若file存在,则打印其内容

它等价于下面这段更冗长的程序:

if test -f file; then
    cat file
fi

但是,万一&&也被禁止使用呢?实际上只使用基本的数学运算就能写出条件判断了,数学运算总不可能被禁止吧。我们只需让条件表达式的值为0或1,然后设计一个巧妙的乘法运算即可实现目的:

i = 0;
while(i < 100) {
    n = rand() % 100;
    printf("%d\n" + (array[n]==-1)*3, array[n]);
    i += (array[n]!=-1);
    array[n] = -1;
}

根据array[n]==-1的值的不同,printf的第一个参数可能是"%d\n"也可能是"",而如果是后一种情况,多余的第二个参数会被忽略,不起作用。这看似是一种怪异的“奇技淫巧”,不过却隐含了一个道理:纯粹使用数学运算就能写出条件判断。曾经高中时有同学固执地认为“分段函数定义时根据x所在的区间进行了判断,只用公式是做不到这一点的。分段函数是一种不正常的,和公式定义的函数截然不同的函数”。作为反驳,我找到了这种只使用数学运算就能构造出分段函数的方法。以该分段函数为例:

\[ f(x) = \begin{cases} 1-x^2 & x<3 \\ x+5 & x>3 \end{cases} \]

\[ f(x) = \frac{6+x-x^2}{2} + \frac{x-3}{|x-3|} , \frac{4+x+x^2}{2} \]

美中不足的是,这样产生的是定义域不完整的函数。毕竟,分段函数常常是不连续函数,不连续函数和连续函数还是有本质区别的,一般数学运算能构造出的都是连续函数。但在计算机领域,要处理的数字本来就是离散的,这种方法就没有缺陷了。