課題S-A-1 解説

課題S-A-1

[ quoted from ] 情報演習課題S-A-1（※）一部抜粋・改変

(1)

正整数 n および非負整数 m を受け取り、 n^{^m} を計算する再帰関数powを定義せよ。ただし、組込み関数exptを使ったり単純にnをm回掛け合わせるのではなく、以下の性質を利用して再帰的に関数を定義すること。
$n^(2k+1)=n*(n^k)^2, n^(2k)=(n^k)^2$
ヒント schemeで商を求める関数はquotient、剰余を求める関数はmodulo です。

(2)

0, 1, 2, 3, 4, 5, 6, 7, 8, 9のうちいずれかを要素とする自然数のリスト (a_{_1} a_{_2} … a_{_n}) を入力とし、10進表記 a_{_n}…a_{_2}a_{_1} が表す数を計算する関数digitを定義せよ。ただし、入力が空リストの場合は0を返すものとする。

ほぼ去年度の問題と同じなので、課題S-A-1(1)解説(H.20)を参考にしてください。

但し、去年は n^{^2m} を計算する関数の実装が課題で、今年のは n^{^m} です。また引数 m も、去年は「正整数」(i.e. 1以上の整数)だったのに対し、今年は「非負整数」(i.e. 0以上の整数)と指定されています。 pow(n, 0) = 1 に注意して再帰終了条件を考えてください。

(2)解説

↑top
↑

10進展開を計算する問題です。ロジック自体は(1)よりもこちらの方が単純なので、(1)でつまずいたら先にこちらを考えてみるのもいいかもしれません。

さて、まずは10進表記 a_{_n}…a_{_2}a_{_1} を式で表すと、次のようになります。

$a_n … a_2 a_1 = Σa_i*10^(i-1) [1≦i≦n]$

10^{^i-1}は先ほど作った関数 pow （あるいは組み込み関数 expt でも）を使えば (pow 10 (- i 1)) で簡単に計算できますね。ということは、あとは summation Σ を表現できればいいわけですね。

再帰ループ

普通の手続き型言語であれば、こういった summation などを表現するために、「繰り返し」構文が用意されています。しかし、 Scheme のような関数型言語では、繰り返し処理を表現するために「再帰」を利用します。(1)でもやりましたね。

番号付きのループを再帰関数でやる例です:

; ループ中の値を確認するための関数
(define (check number symbol)
  (begin
    (display number)
    (display ":")
    (display symbol)
    (display "\n")
    ))

; 再帰関数でループする例1
(define (forward-recursive-loop index ls)
  (if (null? ls)
      (check index 'end)
      (begin
        (check index (car ls))
        (forward-recursive-loop (+ index 1) (cdr ls)) )
   ))
(forward-recursive-loop 0 '(a b c))

ちなみに、 forward-recursive-loop のように、入力リストが空かどうか判定し、 car に対する何らかの処理をして再帰的に cdr にも同じ処理を施していくというパターンはよく使います。そのため、こういった再帰処理を一般化した foldl (fold-left; 左畳み込み), foldr (fold-right; 右畳み込み) という組み込み命令も存在します（但、処理系による）。実際、 foldl を上手に使えば digit は1行で実装できます。

これらを踏まえた上で、digitを作ってみます:

(define (digit-loop ls i)
  (if (null? ls)
      0
      (+ (* (car ls) (pow 10 i))
         (digit-loop (cdr ls) (+ i 1)) )
   ))
(digit-loop '(1 2 3 4) 0)

計算量の最適化

じゃぁこれで完成？いえいえ、不正解です（私は正解を丸々載せる程気前よくありません）。呼び出すとき、入力に余分な 0 を必要としていて、問題の要求を正確に満たしていないからです。じゃぁ引数を合わせて別名の命令を作ればどうかと言うと、それでもまだ半正解（改善の余地あり；所謂△）です。

理論通り計算できているのになぜ半正解なのか疑問に思う人がいるかもしれませんが、計算機科学（そしてプログラミング）では、「計算量」（計算の効率の良さ）を非常に気にするのです。理論数学上は計算可能だからといって、コンピュータで同じものを計算できるかどうかは全く別の問題なのです。

ではどうするのか。実は、(1)でべき乗を計算させる関数を定義させて(2)の誘導になっているのかと思いきや、(2)はべき乗を使う必要がないのです。（ひょっとしたら引っかけ…なのかもしれない。多分そんな意図はない。）

(1)で単純にnをm回掛け合わせるのではなくと明記されているのは、単純に掛けるアルゴリズムでは計算量が $O(m)$ (i.e. 約 m 回）になるのに対して、指数分解を利用すれば計算量が $O(log_2(m))$ (i.e. 約 log_{_2}m 回)と激減するからです。(2)にはそのような指示はないので、上のプログラムでもひょっとすると正解かもしれません。しかし、よく考えてみると何度も 10^{^i} を計算していて無駄が多いと思いませんか？ 10^{^i} を計算した後に、 10^{^i+1} を一から計算し直すのは、無駄が多いですよね？

さて、ここまで来ればもう気づいた人もいるかもしれません。最後にヒントとして次の等式変形を載せておくので、あとは自分で考えてみてください。

$Σa_i*10^(i-1) = a_1+10*(a_2+10*(a_3+…+10*a_n)…)$

S2S