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

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;
}