Rubyによるプログラミング ほんの入り口(その3)

ここではプログラミング言語Rubyを用いて演習を行います。少ない履修時間でプログラムとは何であるかを原理的に理解することを目的としています。本格的なプログラミングを学ぶためにはそれぞれのプログラミング言語の演習を履修することをお勧めします。

1.配列

様々なプログラミング言語に出てくる基本的な概念の一つである配列(array)について説明します。

配列とは、何かが入る箱がいくつか並び、箱の位置を数字で指定して中のデータを読み書きできるものです。箱の位置を指定する数字のことを添字(index)と言い、並んだ箱の数のことを配列の大きさと言います。箱の中に入る物は同じ種類のデータしか許していない言語もありますし、Rubyのように箱ごとに異なる種類のデータを入れられる言語もあります。例えば配列を入れることも可能です。

Rubyでは、配列もオブジェクトの一つです。配列からデータを読み出したり書き込んだりするのもメッセージによります。以下はirbで試してみたの場合の説明です。

> a = [1,3,5,7,9] # 最初の要素が12番目の要素が3...という大きさ5の配列

=> [1, 3, 5, 7, 9]

> a.size # 配列の大きさを返すメッセージ

5

> a.class # 配列のクラスはArray

=> Array

[1,3,5,7,9]というのは最初の要素が12番目以下の要素が3,5...という大きさ5の配列で、上の文によりaという変数に配列が入ります。printpによりこのままの形で表示されます。

添字が0から始まるか1から始まるかの違いを除き、他のプログラミング言語の場合とほぼ同様に以下のようになります。

> a[0]

=> 1

> a[3]

=> 5

Rubyの場合には添字が0から始まることがわかります。実はこれはa(に入っているオブジェクトに)[] 0というメッセージを送っているのです。以下を試してみてください。

> a.[] 0

=> 1

a[0]というのはa.[] 0Cなどのプログラミング言語と同じように見えるように表記しているのです。配列の、ある添字の内容を変えるには以下のようにします。

> a[0]=a[1]+3

=> 6

> a

=> [6, 3, 5, 7, 9]

> a.[]=1,4

=> 4

> a

=> [6, 4, 5, 7, 9]

2.Rubyの配列はスタックやキューも兼ねている

Rubyの場合には配列をオブジェクトとして実装しているので、様々な機能を追加することが可能であり、そうしても自然であり、実際そうしてあります。

> a = [1, 2, 3, 4, 5]

=> [1, 2, 3, 4, 5]

> a.push 6 # 配列の大きさを1増やし、最後にデータを入れる

=> [1, 2, 3, 4, 5, 6]

> a.shift # 配列の最初のデータを取り除く

=> 1 # 入れたデータを順に取り出す仕組みをキューと呼びます

> a # push[0]というメッセージで配列をキューとして使えます

=> [2, 3, 4, 5, 6] # 今の場合には、最初1,2,3,4,5というデータがこの順にキューに

# 入っていたところ、最後に6というデータを追加し、その後

# キューから最初のデータである1を取り出しました

> a.pop # 配列の最後のデータを取り除く

=> 6 # 入れたデータを逆順に取り出す仕組みをスタックと呼びます

> a # pushpopというメッセージで配列をスタックとして使えます

[2, 3, 4, 5]



3. 配列に対する操作

配列に対し様々な操作が可能になっています。それらのうち、基本的なものからごく一部を選び、和、差、要素ごとの操作などについて説明します。

> a = [1, 2, 3, 4]

> b = [5, 6, 7, 8]

> c = [1, 3, 5]

> a+b # 2つの配列をくっつける

=> [1, 2, 3, 4, 5, 6, 7, 8]

> a-c # 最初の配列から2番目の配列の要素を削除

=> [2, 4]

> a.each {|x| print x+3, ' '};puts # 各要素ごとに{}内の操作を行う

4, 5, 6, 7 # |x|は函数の仮引数に相当する

=> [1, 2, 3, 4] # xに配列の各要素が入り、それぞれに

# ついて{}内が実行される

> a.each_index {|i| print a[i]+i, ' '};puts # 各添字ごとに{}内の操作を行う

1 3 5 7 # 各添字がiに代入され、{}内が実行される

=> [1, 2, 3, 4]

> a = [nil, 1, 3, nil, nil, 4, nil, 5, nil]

> a.compact # 配列からnilという要素を取り除く 

=> [1, 2, 3, 4, 5]

上の例でa.each {|x| print x+3,' '}{}内をブロック、あるいはコードブロックと呼びます。ブロックとはプログラムの断片であり、メッセージの引数の一つとして送ることが可能になっています(ここでは{}で囲まれていますが、do … endという形式のものもあります)。ブロックを伴って呼び出され、繰り返し処理を行うメソッドのことをイテレータと呼びます。この場合のeachはその一つです。ブロックは引数をとる場合があり、その場合には変数を「,」で区切ったものを||で囲んで仮引数とします。aの各要素がxに代入されて{}内が実行されることになります。Rubyではブロックは繰り返し以外の処理にも用いられ、そのような場合があるために一般にブロックを引数にとるメソッド呼び出しを、ブロック付きメソッド呼び出しと呼びます。この機能はRubyの大きな特徴の一つであり、非常に柔軟な記述が可能になっています。

4.エラトステネスの篩

ここでは配列とブロックを使った例題として、エラトステネスの篩(ふるい)と呼ばれる手法により、ある数までの素数をすべて求めてみます。以下がそのプログラムです。

a=[nil,nil];for i in (2..ARGV[0].to_i);a.push i;end

a.each_index{|x| (2*x).step(a.size,x) {|i| a[i]=nil} if a[x]}

p a.compact

ここで、初期値.step(限度, 増分) {...}という文が出てきています。これもイテレータと呼ばれる文の一種で、以前出てきたforと同種の処理を行う目的のものです。forとの違いは、forでは指定した範囲で、ある変数の値を1ずつ増やしつつ以降の文を繰り返し実行しましたが、stepでは初期値から初めて増分ずつ足してゆき、限度以内で{}内を繰り返し実行します。

このプログラムでは、最初に2つのnilがあり、その後2以上与えられた数までの数値を要素として持つ配列を最初の行で作っています。この時点では、01は素数でなく、素数だとわかっているのは2だけで、3以降は素数である可能性がある数値が配列中に残っている状態です。ある添字の要素がnilでなければその添字の値自身がその添字の要素として入っています。

2行目で、配列の各要素について、それがnilでなければその数の2倍の添字位置から配列の最後までの、その数の倍数の添字位置の要素をnilに置き換えるという操作を繰り返し行います。ここではブロックが2重、即ちループが2重になっていることに注意してください。また、if文でnilfalseと同様に偽として扱われることにも注意してください。

3行目では合成数の位置に入っているnilを消しています。

非常に簡潔な記述が可能であることがわかります。

5.3つ目の課題

3つ目の課題はオプションです。即ち、提出したい人だけが提出してください。

先の節である数nまでの素数をすべて求める方法を見てみました。今度はまず、ある数までの素数の表を求め、それを使って入力した数mを素因数分解するプログラムを書いてください。mは、コマンドラインの引数として与えるようにしてください。また、出力の形式は以下のようなものとしてください。

[[素因数1, 個数1], [素因数2, 個数2], … ,[素因数k, 個数k]]

素因数iの個数i乗をi=1,...,kについてすべて掛け合わせた結果がmとなります。また、個数i1以上の自然数です。ただし、あらかじめ求めた素数の表が、mの分解に足りない場合には、その旨を出力するようにしてください。その場合、途中まで行える分解の結果も表示してください。

例えば[2,3,5,7]という素数の表を求めていた場合、53の素因数分解には7*7 < 53なので表が足りません。63の分解であれば32回割り切れて7となりますので分解できます。3339=3*3*7*53の分解は、32回割って7で割ると53となり、7*7<53なので表が足りませんが、[[3,2],[7,1][53,1]]というところまでは分解できます。ただしこの場合には最後の53が素数かどうかはわからないということになります(今の場合にはたまたま素数です)。表が足りない場合には、素数かどうかわからない部分も指示するようにしてください。例えば「[[3,2],[7,1][53,1]](ただし最後の因数は素数とは限りません)」などと出力すれば十分です。

これまでに学習したプログラミングの技法以外の技法を用いても構いません。