解説 4月26日A

今回の学習項目です。


再帰関数の復習

課題1-1

Rubyでは、配列から、ひと続きの複数個の要素からなる配列(部分配列) を取り出すことが簡単にできます。例えば、以下を実行すると、

a = [1,2,3,4,5,6,7]
p a[2..4]
その結果は以下のようになります:
[3, 4, 5]
ここで、2..4はfor文で使われていたように「範囲」を表すもので、 この場合、配列の指標が「2から4までの範囲」であることを表しています。 ですから、[a[2],a[3],a[4]] という配列が返された、というわけです。

この知識を前提として、配列aryを引数にとり、 配列aryの要素を小さいものから大きなものへと並び替える関数msort(ary) を作成しなさい。ただし msortの中身は次のように計算が行われるものとする。

  1. aryの要素数が1以下なら、aryの値を返して終了
  2. aryの要素をほぼ半分ずつになるようわける。 それぞれの配列を仮に変数 a, bの値とする。
  3. aを引数としてmsortした結果を変数 asの値とする。 つまり、 as = msort(a)
  4. 同様に、bを引数としてmsortした結果を変数 bsの値とする。
  5. as と bs から、すべての要素を小さい順に並べた配列を作り、 (マージする、といいます)これを返して終了。
このソートはマージ・ソート(merge sort)と呼ばれています。

[配列の要素をほぼ半分ずつに分けた配列を作る]

考え方は次のとおりです。変数aryの値として配列が与えられているとします。 その配列の要素数を求めます。仮にそれを n します。 するとこの配列を二つに分けた一つは、ary[0..(n-1)/2] となります。 たとえばaryが8個の要素を持つ配列なら ary[0..3]、 つまり [ a[0], a[1], a[2], a[3] ] という配列が得られます。 それでは、もうひとつはどうなるでしょう?nを使ってあらわしてみましょう。

[2つの配列から、すべての要素を小さい順に並べた配列を作る]

このプログラム作成で一番難しいポイントですので、いきなり大きな配列で試さずに、 まずは小さな配列で動くことを確かめるようにしましょう。

配列asとbsをマージする手法は次のとおりです:
  1. 空っぽの配列を作っておきます。仮にこれを変数 result の値としておきます。
  2. asが空っぽの配列なら、result+bs (つまりresultとbs の要素を合わせた配列)を返して終了。
    逆に bsが空っぽの配列なら、result+asを返して終了。
  3. asの先頭の要素を変数ax、bsの先頭の要素を変数bxの値とする。
  4. ax < bx ならば resultにaxを追加する。そしてasから先頭の要素axを取り除いて手順2に行く。
    そうでなければ (ax ≥ bxのはずだから) resultにbxを追加する。そしてbsから先頭の要素bxを取り除いて手順2に行く。
ここで、配列aryの先頭の要素を「取り除く」ことは、 ary.shift という操作で行えます。なお、ary.shift 自体は、取り除かれる先頭の要素を値として返すことに注意してください。言い換えれば、ary.shift の実行後に、ary の値が変化して、先頭の要素が取り除かれた配列になる、ということです。

課題1-2

課題2-1の方法でソートできる理由を述べなさい。また、 n個の要素を持つ配列をソートするとき、 配列に要素を加える操作は、最も回数が多い場合に何回くらい必要だろうか。 具体的にそのような配列を例で示しながら説明しなさい。

課題1-3

与えられた配列aryは以下のように、要素として配列も、 配列以外のものも含むものとする。

ary = [ [1, [2,3]], 4, [5,6], [[7,8],9] ]
このような配列に対し、次のように、配列以外のすべての要素を 取り出した配列を返す関数 flatten(ary) を作りなさい。
p flatten(ary)
の結果:
[1, 2, 3, 4, 5, 6, 7, 8, 9]

[課題1-3のヒント]

関数flattenは必ず配列を返すことに注意しよう。 これは引数として [1,2,3] が与えられたら [1,2,3]を返す。 また、[ [1,2] ] ならば [1,2] を返す。

ここで「配列以外」のものが引数に来た時も配列にして返すことにすると問題がやさしくなる。つまり flatten(10) は [10]という配列を返すものとするのである。

そう仮定すれば、次のようにプログラムを組めば良いことがわかる。

  1. 引数 ary が配列でなければ、[ ary ]を返して終了。
  2. そうでなければ、空っぽの配列(仮に変数 result の値とする)を用意する。
  3. 引数 ary の要素の先頭から要素を一個一個取り出し、次を行う。
    取り出された要素を x とすると、result = result + flatten(x)
  4. aryの要素すべてに上を行った後、resultを返す。

[引数が配列かどうかの判定]
引数が配列かどうかの判定方法は、 4月12日Bの学習項目オブジェクトで学びましたし、 4月19日Aの課題3-7で実践しています。

クラスとインスタンス

変数が一つの値だけを記憶できるのに対して、配列は指標(インデックス) によっていろいろな値を区別して記憶できることを学んできました。 そして配列はプログラミングで重要なデータ構造の一つであることも学びました。

実際、配列はとても使いやすくてわかりやすいデータ構造ですが、 問題がないわけではありません。その一つは、配列に記憶されている要素を取り出したり書き換えたりする(このような操作を「アクセス」といいます)ときに、 指標のような数を指定しなければならない、ということです。 つまり、数ではなく「名前」をつけて呼べると、もっと使いやすくなるはずです。

また、配列が使いやすいだけに、その裏返し的な問題があげられます。 たとえば「中京太郎さんの住所や電話番号などの情報(名簿の一項目)」でも 「トランプのカード(スーツと数)」でも「木構造におけるノード」でもなんでも かんでも配列を使って表すことができます。 しかし、外から見ればみんな配列ですから、これが本当は何を表しているのか、 名簿の項目なのか、トランプのカードなのか、木のノードなのかはわかりません。 すると、本来はトランプのカードを表す配列に「電話番号を返す」という関数を間違って適用したり、 本当は名簿の項目をあらわす配列に「ノードの親を返す」という関数を間違って適用したりすることもあるかもしれません。

ここで紹介するクラス(とインスタンス)は、これらの問題を解決する一つの、 そして重要な仕組みです。 簡単にいえば、クラス(とインスタンス)によって次のことが可能になります。

ここまでで、「クラス(とインスタンス)」と書いてきたことに気がついた人がいるかもしれません。名簿クラスやカードクラスは「配列」に相当するオブジェクトの型をあらわし、 インスタンスは特定の配列(たとえば [1,2,3])に相当します。 クラスがなければインスタンスは作れませんし、メソッドは基本的にインスタンスに対して適用されます。このように、クラスとインスタンスは、あわせて一つ仕組みなのです。

クラスの定義とインスタンスの作り方:トランプのカードクラスを例に

ここではトランプのカードを例にクラスの定義とインスタンスの作り方を示します。

ここで、トランプのカードのクラスの名前をCardとし、個々のカードはスーツ(suit)と数(num)という二つの情報を持っているものとします。 ただしジョーカーは除外し、A,J,Q,Kはそれぞれ 1,11, 12, 13という数とします。 また、スーツは"spade", "heart", "diamond", "club"というような文字列であらわすものとします。

このように決めると、スーツと数を持つカードのクラスは次のように定義されます:


   class Card    # クラスの定義の始まり
           # クラスの名前Cardが大文字から始まることに注意
        def initialize(s, n)    # インスタンスを作るためのメソッドです
            @suit = s     # suitという「要素」を定義
            @num = n      # numという「要素」を定義
        end
   end

クラスの名前はCardのように大文字で始めなければなりません。 また、initializeメソッドはそのクラスのインスタンス、 つまり個々のオブジェクトを作るためのメソッドです。 ただし、インスタンスを作るときは initialize ではなく newというメソッドを呼び出します。 この new はinializeメソッドを呼び出して、インスタンスが作られます (なぜ、そのようにややこし関係になっているのででしょうね?)

initializeメソッドの定義の中にこのクラスのインスタンスが持つべき要素を書き込みます。 この例はCardを扱っていますから suit と num という2つの要素をもつものとしてあります。 これらを「インスタンス変数」といいます。その名前の由来は、インスタンスが作られた時にそのインスタンスを構成する要素だからです。 なお、@suit のように、インスタンス変数suitの前に@をつけることに注意してください。 このインスタンス変数に値をセットすることで、作られたインスタンスに、 そのような情報が書かれることになります(いままでの関数定義と異なり、 initializeメソッドが終了しても、インスタンス変数は値を保持しています)。

なお、initializeメソッドの引数は、個々のオブジェクトを作る時に必要とされる要素の値が入ります。 つまり、インスタンスを作るときは、要素に具体的な値とともにnewメソッドが呼び出されます。 例えば、スペードのAのカードに相当するインスタンスは次のように作られます。 この時の引数である"spade" と1はそれぞれinitializeメソッドの引数である sとnに値として渡され、作られたインスタンスのそれぞれsuitとnum というインスタンス変数の値となります。

  spadeA = Card.new("spade", 1)

課題2-1

先に定義されたCardクラスを用いて、スペードのAからKまでの13個のインスタンスを作って配列 spades にいれることを考えました。 以下はそのためのコードです。あいている部分を補って完成させてください。

  # ここに Cardクラスの定義が入る  

  spades = [ ]
  for i in 1..13
     #     
     #ここに適切なプログラムを書く 
     #     
  end # for

課題2-2

課題2-1の結果、spadesにはスペードのAからKまでのインスタンスを要素にもつ配列が代入されています。 そこで、以下を実行したらどのような表示がなされるか、書きなさい。 また、その表示にはどのような意味があるか答えなさい (推測する、ウェブで調べる、本で調べるなど、いろいろ試みてください)。

p spades[3] 

課題2-3

名簿の項目を表すためのクラスの名前をMeiboKomoku とします。 MeiboKomokuクラスのインスタンスには、名前 name、住所 address、郵便番号 zip、 電話番号 phone という要素を持つものとします。 このようなMeiboKomokuのクラスの定義を書きなさい。 また、中京太郎さんに対応するインスタンスを作るコードを書きなさい。なお、 中京太郎さんの情報は以下のとおりとします: 名前は"Taro Chukyo"、住所は"Kaizu-cho, Toyota, Aichi"、郵便番号は"470-0348"、 電話番号は "0565-46-1211"。

インスタンス変数へのアクセス

先に、クラスの定義と、そのクラスのインスタンスを作る方法について述べました。 そして、具体的にCardというクラスを定義し、スペードのAのカードに相当するインスタンスを作ってspadeAの値とする方法もみてきました。

しかし、それで手に入れることができたのはCardクラスのインスタンスの作成手段と 変数spadeAに値として入ったオブジェクト(Cardクラスのインスタンス)だけです。 言い換えれば、spadeAのインスタンス変数の値を取り出したり、 もしくはそれを書き換えたりする(これらの操作のことを「アクセス(access)する」といいます) ことはできません。

ここではCardクラスを例にとり、そのインスタンス変数にアクセスするための方法、 attr_accessorを紹介します。 次を見てください。

   class Card    # クラスの定義の始まり
        def initialize(s, n)    # インスタンスを作るためのメソッドです
            @suit = s     # suitという「要素」を定義
            @num = n      # numという「要素」を定義
        end
        attr_accessor :suit,:num   # インスタンス変数へのアクセスを可能にする
   end
これは、attr_accessorを組み入れたCardクラスの改訂版です。 ここで、attr_accessor の後に、スペースを挟んで、「前にコロン : を置いたインスタンス変数を書く」(インスタンス変数の間にはコンマ , を挟む)ということに注意してください。 このようにCardクラスを定義すると、次のように、インスタンス変数の名前を「インスタンスに対するメソッド」としてその値を取り出したり、書き換えたりすることができるようになります。
spadeA = Card.new("spade", 1)    # Cardクラスのインスタンスを作る
p spadeA.suit     # spadeAのsuitインスタンス変数の値を取り出す
spadeA.num = 13   # spadeAのnumインスタンス変数の値を書き換える
p spadeA.num

課題2-4

課題2-3で定義したMeiboKomokuクラスの定義に attr_accessor 文を付け加え、 name、address、zip、phone インスタンス変数すべてにアクセスできるようにしなさい。

また、課題2-3と同じように、中京太郎さん (名前は"Taro Chukyo"、住所は"Kaizu-cho, Toyota, Aichi"、郵便番号は"470-0348"、 電話番号は "0565-46-1211")の名簿項目のインスタンスを作り、 電話番号を取り出せることを確かめた後に、電話番号を"0565-46-1299"に変更できることを確かめなさい。

インスタンスメソッドとインスタンス変数へのアクセス

課題2-2では、Cardクラスのインスタンスがp命令でどのように表示されるかをみました。 これは読みやすいとはとても言えないものでした。

そこで、Cardクラスのインスタンスの情報を「美しく」表示させることを考えます。 そのためにメソッドを定義しましょう。このメソッドの名前をshowとしておきます。 これは inisitalizeメソッドと同様に、 次のようにCardクラスの定義の中に書かれます。 ここで、このメソッドの中では、Cardクラスのインスタンス変数にアクセスするのに、 @もドットも必要ないことに注意してください。

   class Card    # クラスの定義の始まり
        def initialize(s, n)    # インスタンスを作るためのメソッドです
            @suit = s     # suitという「要素」を定義
            @num = n      # numという「要素」を定義
        end  # def of initialize
        attr_accessor :suit,:num   # インスタンス変数へのアクセスを可能にする
        def show  # インスタンスの表示のためのメソッド
           return "["+suit+" "+num.to_s+"]"   # 表示例: [spade 3]
        end # def of show
   end # of class Card

[to_s]

今の例では num は数で、suitは文字列ですから suit+num とやるとエラーになります。 そこで、は数から文字列を作れれば、+はこれらの文字列を結合した文字列を作る演算となります。 そこで使われているto_sメソッドは、「文字列」を返すためのメソッドです。 以下を実行してその働きを確認してください。
p 321
p 321.to_s

このように定義されたインスタンスメソッドは、次のように「インスタンス.show」 のように呼び出されます。

課題2-5

上のように改定したCardクラスを用いて、以下を実行した時に、どのような表示がなされるか予想し、実行結果と比較せよ。
spadeA = Card.new("spade", 1)    # Cardクラスのインスタンスを作る
p spadeA.show

課題2-6

showは引数を持たないメソッドでしたが、次に引数をもつメソッドを考えましょう。 ここで考えるメソッドは「カードの強さを比較する」メソッド compare です。 2枚のカードの強さは次のように決められるものとします。 以下で定義する compare メソッドは、引数としてCardクラスのインスタンスをとり、 それよりも強ければ1を、弱ければ-1を、引き分けの場合は0を返すものです。 ただしこのままでは完成してませんので、穴埋めして完成させなさい。
   class Card    # クラスの定義の始まり
       def initialize(s, n)    # インスタンスを作るためのメソッドです
           @suit = s     # suitという「要素」を定義
           @num = n      # numという「要素」を定義
       end  # def of initialize
       attr_accessor :suit,:num   # インスタンス変数へのアクセスを可能にする
       def show  # インスタンスの表示のためのメソッド
           return "["+suit+" "+num.to_s+"]"   # 表示例: [spade 3]
       end # def of show
       def compare(c)
          return 0 if (num == c.num) && (suit == c.suit)
          if (num > c.num) 
               return 1
          elsif (num < c.num) 
              return -1
          else
              # ...
              # この部分を穴埋めせよ
              # ...
          end # if
     end  # def of compare
   end # of class Card
# テスト
 spadeA = Card.new("spade", 1) 
 heartA = Card.new("heart", 1) 
 clubK = Card.new("club", 13) 
 p heartA.compare(spadeA)
 p clubK.compare(heartA)
 p spadeA.compare(spadeA)

課題2-7

(時間がない場合はやらなくてもよい)
トランプカードを使ったゲームの一つ、『戦争ゲーム」をシミュレーションするプログラムを作ってみましょう。 以下は、rand関数を利用して、ランダムに一枚作ってmineとyoursという配列にいれる例です。
suits = ["spade","heart","diamond","club"]
mine = []
yours = []
mine << Card.new(suits[rand(4)],rand(13)+1)
yours <<  Card.new(suits[rand(4)],rand(13)+1)

これを利用して、まず自分のカードと相手のカードをそれぞれランダムに10枚用意します。 次に、自分のカードと相手のカードを一枚ずつ取り出し、強さを比べます。 10枚すべて対戦させ、自分のカードが勝った枚数が相手のカードが勝った枚数を上回れば、あなたの勝ちです。

ただ、勝った負けただけを表示するのでは面白くないので、 次の例で示すように一枚ずつ勝ち負けの判定を表示した後に、勝敗の総合判定をするようにしなさい。 ただしここで自分のカードはmyCard、相手のカードはyourCardとしています。
  print "自分のカード:", myCard.show," 相手のカード:",yourCard.show," ... "
  if (myCard.compare(yourCard) > 0) 
      print "勝った!\n"
  elsif (myCard.compare(yourCard) < 0) 
      print "負けた...\n"
  else
      print "引き分け\n"
  end # if

「アルゴリズムとデータ構造」のホームに戻る