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

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(charstr,intc) { return; }

void cn0(charstr,intc); void(arr[256])(charstr,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(charstr,intc) { ++(*c); arr*str; }

int GetStringLength(char*str) { int c=0; arr*str; return c; }

int main() { char*s="abcdefg"; printf("%d",GetStringLength(s)); return 0; }

面试题lambda演算