課題S-A-1 解説

課題S-A-1

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

(1)

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

(2)

整数のリストを入力とし、リストの要素のうちその絶対値が最大となるものを返す関数 absmaxを定義せよ。ただし、入力が空リストの場合は0を返すものとする。

Schemeプログラミングにおいては（あるいはプログラミング全般において）、関数の再帰的定義はとても重要です。この演習課題は云わばその練習問題ですが、まずはもっと基本的な所からきちんと押さえておいた方がいいでしょう。基礎情報・情報演習に特化したSchemeの解説も用意してあるので、参考にしてください。

関数の再帰的定義がどういうものかさえ分かってしまえば、Schemeプログラミングの課題はそれほど難しいものではありません。

また、与えられた問題を単純化・分割化して問題を解いてみることはプログラミングをする上でとても重要です。複雑な問題ではミスをしたときにどこを間違えたのか分からないので、問題を簡単なものに分解していく論理的な考え方が求められます。

（１）の解説

↑top
↑
↓

ｎ＾^ｍ

課題は単純にnを2m回掛け合わせるのではなくと書いてありますが、寧ろ単純にかけるだけの関数を作って一度練習してみるといいでしょう。

(define (^ n m)
  (if (zero? m)
      1
      (* n (^ n (- m 1)))
      ))

見ての通り、ｎをｍ回かけるだけの関数です。例えば、(^ 2 32)ならば32回も2をかけるだけです。これ、効率が悪いと思いませんか？

大体知っていると思いますが、ｎのｍ乗を表すのに、ｎ＾ｍという風にハットを用いた表記をすることがあります。ｎ^ｍと指数を肩に乗せて表せない場合（平のテキスト、メールなど）に、よく用いられる表記です。また、多くのプログラミング言語ではべき乗演算子として^を採用しています。

ｎ＾^{２＾^ｍ}

(^ 2 32)のように、指数ｍが２のべき乗の形をしている場合は、例えば(^ (^ 2 16) 2)と変えるだけで一気にかける回数を半分近く減らすことができます。数学的には2^³²も(2^¹⁶)^²も等価ですが、かける回数でみると計算量はまったく違うことがわかると思います。

そこで次はn^^{2^^m}を計算する関数を作ってみましょう。ここで重要なのは、n^^{2^^m}=(n^^{2^^m-1})^²であることです。

(define (^ n m)
  (if (zero? m)
      1
      (* n (^ n (- m 1)))
      ))
(define (^2^ n m)
  (if (zero? m)
      n
      (^ (^2^ n (- m 1)) 2)
      ))

このように、たとえ2^¹⁰²⁴でも1000回も再帰する必要はなく、実質的に10回の再帰だけで済ませられることが分かります（※1024は2の10乗）。文字通り、計算量のオーダーが違うというわけです。

ｎ＾^２ｍ

もう気付いていると思いますが、一般のn^^mの場合でも、同じような手法で掛ける回数を減らせますね。つまり、ｍが偶数ならば(n^^m/2)^²、ｍが奇数ならばn*(n^^(m-1)/2)^²という風に、指数の偶奇で場合分けして指数部分を分解していけばいいのです。

ちなみに、このときの指数部の分解は、二進法表記と１対１で対応します。Wikipediaなどにズバリで載っているので、興味がある人は見てみるといいでしょう。

課題では指数が偶数のべき乗を求める関数pow(n,m)=n^^2mを作ればいいわけです。つまり、ｍが偶数ならば(pow(n,m/2))^²、ｍが奇数ならば(n*pow(n,(m-1)/2)^²と定義することで、powをpow自身で再帰定義できます。ｍは正整数なので、再帰終了条件はpow(n,1)=n*nとするのがいいでしょう。

ここで、偶数・奇数の判定にmoduloが使え、m/2及び(m-1)/2を求めるのにはquotientが使えます。(modulo n m)はｎをｍで割った余りを求め、(quotient n m)はｎをｍで割った商[n/m]（※整数値）を求めます。

（２）の解説

↑top
↑

absoluteじゃないmaximum

とりあえずまずは、絶対値に関係なく、リストの要素のうち最大のものを返す関数を定義してみましょう。（maxそのものはSchemeで元から定義されているので、名前は_maxとします。）

(define (_max ls)
  (if (null? (cdr ls))
      (car ls)
      (if (> (car ls) (_max (cdr ls))
             (car ls)
             (_max (cdr ls))
             ))))

このプログラムは最適化（無駄な計算を省いたりして計算量を減らすこと）をしていません。とりあえず_maxを再帰的に定義するにはどのようにすればいいのか、このプログラムを眺めながら考えてみてください。

absoluteのmaximum

課題のabsmaxを実装するには、上のアルゴリズムと同じようなプログラムで、比較時の値として絶対値をとればいいのです。ここで、Schemeで絶対値を求める関数はabsです。ただし、_maxではlsのcdrが空リストの場合が再帰終了条件ですが、absmaxは入力が空リストである場合が再帰終了条件であり、その場合０を返さなければいけないことに注意してください。

また、上の_maxは最適化していないので計算量が多いことにも気をつけてください。例えば、_maxの中で_max自身が２回使われているので、明らかに余分な計算をしています。この_maxに無駄が多いというのが分からないのであれば、デバッグモードなどを活用して実際にプログラムの動きを追ってみるといいでしょう。

S2S