我
偶尔看到了这样一道
问题：
输入一个整数n， 求从1到n这n个整数的十进制表示中1出现的次数。
unix脚本控的角度
"unix 传统上认为, 一行 shell 脚本胜过万行c程序." --无名师
我们先从一个unix平台上习惯用脚本解决问题的角度看这个问题。在unix下， 我们很少用算法的眼光去看问题， 因为unix已经聚集了各种优雅的小工具了， 其中不乏sort这种算法相关的，我们仅仅把各种工具用管道连接起来， 就可以完成几乎任何的工作了， 当然这取决于使用者的分解及组合问题的能力。 手中有锤， 心中有钉，我们看到这个问题时， 就不会想到数字， 而是想到字符串， 想到文本流。仅仅用一句命令， unix脚本控就得到了这个问题的一种解决方法：
seq -s "" 1000 | awk -F'1' '{print NF-1}'
它产生从1到1000的流， 作为awk的输入， 并以“1“作为分隔域， 然后打印出域的个数与1的差， 得到的就是1出现的次数了。 很遗憾， awk对域的个数大小有限制，不能超过2^15-1， 比如当n=55814时， 它刚好不能工作：
seq -s "" 55814 | awk -F'1' '{print NF-1}'
它提示：
awk: program limit exceeded: maximum number of fields size=32767 FILENAME="-" FNR=1 NR=1
我们可以给出一个效率更低的解决方法：
time seq -s "" 123456 | awk 'a+=gsub("1",""){print a}'
它的运行时间看起来难以忍受：
real 0m10.319s user 0m0.784s sys 0m9.477s
这种工作方式的优势不在于高效， 而在于灵活和简洁， 它的io流的机制使得unix下的各种小工具可以像用胶水一样被粘接起来, 利于自动化.
scheme初学者的递归思维模式
我最近着迷于函数式编程的优雅和统一。
这里有一个
关于lisp迷人的故事. 我这个scheme初学者也忍不住用我拙劣的想法写了下面这个递归版的解法：
(define how-many-x-from-1-to-n
(lambda (x n)
(if (= n 0)
(if (= x 0) 1 0)
(+ (how-many-x-from-1-to-n x (- n 1))
(how-many-x-in-y x n)))))
(define how-many-x-in-y
(lambda (x y)
(if (< y 10)
(if (= x y) 1 0)
(+ (how-many-x-in-y x (quotient y 10))
(how-many-x-in-y x (modulo y 10))))))
看起来不错，寥寥几行递归就可以求解了。这对scheme初学者是一种很大的鼓舞。不过， 它很慢。让我们的通过进一步的思考改善它：
进一步的递归
我们看还有什么有利的信息没有用上。对于这个问题，一个障碍就是我们只看到了需要统计的数字1，我们需要一个众生平等的观念去切入。通过添加前导“0”, 我们发现，从000, 001, 002, ..., 998, 999这一系列数字中，每一个数字都是平等的，0到9这十个数字在中间占的比例是一样多的。而且，前导0的添加并没有影响到其他数字的个数。于是，我们得到这样一个重要的公式，令f(n)为从1到n这n个整数的十进制表示中1出现的次数,m为n的位数, 当n中所有的位都为9时，有
f(n) = m * (n + 1) / 10; (当组成n的所有的位都为9时。m为n的位数)
可以用scheme这样来描述：
(define (all-digits-is-9? n)
(if (< n 10) (if (= n 9) #t #f)
(if (= (modulo n 10) 9) (all-digits-is-9? (quotient n 10))
#f)))
(define (f n)
(cond ((< n 10) (if (> n 0) 1 0))
((all-digits-is-9? n) (quotient (* (+ n 1) (how-many-digit n)) 10))))
(define (how-many-digits n)
(if (< n 10) 1 (+ 1 (how-many-digits (quotient n 10)))))
为了描述方便，再定义一个函数g(n1,n2) =f(n2)-f(n1-1)，表示n1,n1+1,...,n2这些整数的十进制表示中1出现的次数。来看最高位不为9其余位全位9的情况，以3999为例：
f(3999) = g(0,0999) + g(1000,1999) + g(2000,2999) + g(3000,3999)
对于低三位，包含1的个数在每一项中都是相同的， 等于f(999)，对于最高位，包含1的数只分布在\1000,1999\这个区间，它的最高位总共有10^(m-1)个1。令h为n十进制表示中最高位的数字，nr为除了最高位之外其余位数组成的数值，当除了最高位不为9外其余位全为9时，我们得到下面的式子：
f(n)=(h+1)*f(nr) + 10^(m-1)
我们把这个最新信息更新到scheme去：
(define (f n)
(cond ((< n 10) (if (> n 0) 1 0))
((all-digits-is-9? n) (quotient (* (+ n 1) (how-many-digits n)) 10))
((all-digits-is-9-ignore-first? n)
(+ (* (+ (first-digit n) 1)
(f (del-first-digit n)))
(expt 10 (- (how-many-digits n)
1))))))
并且加入新定义
(define (all-digits-is-9-ignore-first? n) ;; n > 9
(all-digits-is-9? (del-first-digit n)))
数字全为9以及除最高位不为9其余位全为9的n解决了，那么其他的数字呢？我们需要把其他数拆分成我们已经解决的数，这样就可以利用前面的公式了。 观察n=67187时这个普通的状况，它可以分为几个区间来计算：[0,59999]，[60000,67187],前一个区间我们已经刚才已经解决了，它属于除了最高位外其余位数全为9的情况。让我们继续解决后一个区间的普通情况，我们离目标已经很近了。我们还是用刚才的分析方法，考虑到它的最高位不为1，它完全等于把最高位去掉的f(7187). 即：
g(60000,67187)=f(7187)
再看另外一种最高位为1的情况，比如g(10000,17245), 统计时就要加上最高位的1了。它可以表示为：
g(10000,17245)=f(7245) + 7245
我们把这个最新得到的信息更新到scheme， 完整的求解这个问题的scheme代码已经出来了：
(define (how-many-digits n)
(if (< n 10) 1 (+ 1 (how-many-digits (quotient n 10)))))
(define (first-digit n)
(quotient n (expt 10 (- (how-many-digits n) 1))))
(define (del-first-digit n)
(modulo n (expt 10 (- (how-many-digits n) 1))))
(define (max_x-1_9s n) ;; n > 9
(- (- n (del-first-digit n)) 1))
(define (all-digits-is-9? n)
(if (< n 10) (if (= n 9) #t #f)
(if (= (modulo n 10) 9) (all-digits-is-9? (quotient n 10))
#f)))
(define (all-digits-is-9-ignore-first? n) ;; n > 9
(all-digits-is-9? (del-first-digit n)))
(define (f n)
(cond ((< n 10) (if (> n 0) 1 0))
((all-digits-is-9? n) (quotient (* (+ n 1) (how-many-digits n)) 10))
((all-digits-is-9-ignore-first? n)
(+ (* (+ (first-digit n) 1)
(f (del-first-digit n)))
(expt 10 (- (how-many-digits n)
1))))
(else (+ (f (max_x-1_9s n))
(f-from-a-zeros-to-n (+ (max_x-1_9s n) 1) n)))))
(define (f-from-a-zeros-to-n a-zeros n)
(if (= (first-digit a-zeros) 1) (+ (del-first-digit n) (f (del-first-digit n)) 1)
(f (del-first-digit n))))
试试有多快：
(f 322566932356566)
输出：
560127253483017.0
我通过time csi 源文件的方式测试n=322566932356566的时间，从加载csi解释器， 到装载scheme代码， 到计算， 最后退出。整个过程只花了不到十分之一秒的时间：
real 0m0.038s
user 0m0.016s
sys 0m0.004s
它的核心计算过程是递归， 但它的效率不逊色于非递归的任何版本。
数学的角度
工具的便利常常阻止我们进一步的深入思考，去探寻那深层的规律。对于数学控来说，得到一个通项公式才是最终的目的。通过递推关系， 利用生成函数等各种技巧，求得一个通项公式，这是很有趣的。 留给各位去继续吧。