連続する整数の「7」の個数を数える(解説)

ちょっとコードがひどかったので書き直しましたｗ
手続き seven だけ再掲します。

(define (seven num)
  (define (iter n q r s k cnt)
    (if (= n 0)
	cnt
	(iter (quotient n 10)
	      (quotient q 10)
	      (remainder q 10)
	      (+ s (* r (expt 10 k)))
	      (+ k 1)
	      (cond ((= r 7) (+ cnt (count-seven (* r (expt 10 k))) 1 s))
                    ((> r 7) (+ cnt (count-seven (* r (expt 10 k))) (expt 10 k)))
	            (else (+ cnt (count-seven (* r (expt 10 k)))))))))
  (iter num (quotient num 10) (remainder num 10) 0 0 0))

ロジックの簡単な解説。

桁毎に処理するのですが、桁以下が 0 の時の切り番の 7 の数を数えるのが基本です。
たとえば、6543 で 1000 の位の桁の処理は、6000 までに 7 がいくつ現れるか計算します。
(count-seven 手続き)

以下特殊処理です。

・桁の数字が 7 のとき

下位の桁の数を足します。プラス 1 は補正です。
例えば、7543 で 7000 の桁を計算するときは、7000 までに 7 が現れる個数に 543 を足します。
さらに、7000 で 7 が 1 つ現れるので +1 して補正します。

・桁が 7 より大きいとき

例えば 8543 のときは、8000 までに 7 が現れる個数を求めますが 7000 番台分の 7 の出現個数を計算して足します。

・桁が 7 より小さいとき

例えば 5543 のときは、5000 までに 7 が現れる個数を普通に求めます。

という処理を下位の桁から上位の桁へ再帰的に行っています。
n が 0 になったら cnt を返して終了します。
プログラムの計算量は、数字の桁数に対し O(N) です。