求字符串长度不许使用循环和条件

2014-10-31

同事在群里发了一道题目:求字符串长度,但不许用任何判断语句、循环语句。据说这个题目还是某个常青藤大学入学的题目。

当然方法肯定是多种多样的。这里聊下如果是我解这道题的第一反应。不许用循环那么可以采用递归,递归是可以实现循环的。像scheme语言中就没有提供循环的语法。

int length(const char *str) {
    if(str[0] == '\0') {
        return 0;
    }
    return 1+length(++str);
}

但是这里用到了判断语句,递归是要有出口的,肯定要有判断,但是题目又不能用判断语句,怎么办呢?

用lambda演算可以实现判断语句。为了方便描述,使用scheme代码:

(define true (lambda (x y) x))
(define false (lambda (x y) y))
(define if
    (lambda (cond then else)
        (cond then else)))

可以测试一下我们自己实现的if函数:

(if true 1 2)   ;;返回1
(if false 1 2)  ;;返回2

一步一步分解一下:

    (if true 1 2)
=> ((lambda (cond then else)
    (cond then else))
    true 1 2) ;;将if写成它原本函数的样子
=> (true 1 2) ;;将参数true 1 2代入到函数中得到
=> ((lambda (x y) x) 1 2) ;;将true写成它原本函数的样子
=> 1 ;;将参数1 2代入到函数中

如果我面试别人答出了这种方法,我会直接给面试者通过的。因为用到了lambda演算的一些知识,了解这些的一般是真正热爱计算机的一小波人(当然,需要考察面试者是巧合看过题目,还是认真研究过,可以继续问Y组合子之类的深一点),至少十有八九SICP应该是读过的。这些是对计算机的本质的认知有着不懈的追求,有理想的程序员。

这道题其它的方式也可以做,比如说如果某人对自己的汇编很自信,也可以用汇编写,循环就是jmp,条件也是je。一样没有使用循环和条件,满足题目要求。图灵和丘奇,计算机起源的两种不同流派。

如果是从智力题的角度,搬弄一些奇技淫巧,各种方法就更多了。比如网上看到这个,很巧妙地使用了'\0'等于0来做if判断,并使用0号位数组做退出。

void c0(char*str,int*c) {
    return;
}

void cn0(char*str,int*c);
void(*arr[256])(char*str,int*c)={c0,cn0,cn0,cn0
,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0
,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0
,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0
,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0
,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0
,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0
,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0
,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0
,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0,cn0};

void cn0(char*str,int*c) {
    ++(*c);
    arr[*str](str+1,c);
}

int GetStringLength(char*str) {
    int c=0;
    arr[*str](str+1,&c);
    return c;
}

int main() {
    char*s="abcdefg";
    printf("%d",GetStringLength(s));    
    return 0;
}
面试题lambda演算