プログラミングプロジェクト＃ 3 – 制御構造 (2)、配列久野 靖 (電気通信大学)

2018.6.27

はじめに

1

今回はまず、前回の課題の解説と併せて、制御構造などで追加すべき点を説明します。その後の本日の内容としては、次のものを取り上げます。

• 制御構造の組み合わせについて (再)• データ構造と配列

2

前回演習問題の解説

2.1

演習 1a — 枝分かれの復習

演習 1a は例題とほとんど同じです。まず擬似コードを見てみましょう。

• max2: 数 a、b の大きいほうを返す•
もし a > b であれば、•result ← a。
•
そうでなければ、•
result ← b。
•枝分かれ終わり。
•result を返す。
Ruby では次のとおり。
def max2(a, b)
if a > b
result = aelse
result = bend
return resultend
これも、次のような「別解」があり得ます。

• max2x: 数 a、b の大きい方を返す•
result ← a。
•もし b > result であれば、•result ← b。
•枝分かれ終わり。
•result を返す。
これの Ruby 版は次のとおり。

1def max2x(a, b)
result = a
if b > result then result = b end
return resultend
どちらが好みですか? これもどちらが正解ということはありません。
ところで、「2 数が等しい場合はどうするのか」について皆様の中には迷った人がいると思います。
問題には「異なる数」と書いてあるので考えなくてもよいのですが、仮にそれが書いていなかったとします。そうなると、等しい場合について何らかの指示が本来あるべきですよね。たとえば次のものがあり得ます。

• 「等しい場合はその等しい数を返す」• 「等しい場合は何が返るかは分からない」• 「等しい数を渡してはならない」
上 2 つの場合は例解のままで OK です (2 番目では何が返ってもよいので、等しい数でもよい)。最後の場合はどうでしょう。次の考え方があり得ます。

(a) 「渡してはならない」以上、渡されることはないのだから、例解のままでよい(b) 「渡してはならない」値が渡されたのだから、エラーを表示するなどして警告するべきどちらにも (互いに裏返しの) 利点と弱点があります。(a) の方が簡潔で短く間違いが起きにくいですが、(b) の方が起きるべきでないことが起きていることが分かるので対処が必要な場合には有用です。
で、あなたは発注者 (教員) の注文を受けてこの課題をやっているわけですから、正解は発注者に「どうしますか」と確認することです。そうすれば、どちらにするかは決められるでしょう。勝手に(b) を選んでプログラムを複雑で間違いやすいものにするのはいかがかと思いますし、発注者が「等しい場合はその等しい数を返す」と書き忘れただけだったら目もあてられませんね。

2.2

演習 1b — 枝分かれの入れ子

演習 1b はもう少し複雑です。まず考えつくのは、a と b の大きいほうはどちらかを判断し、それぞれの場合についてそれを c と比べるというものでしょうか。

• max3: 数 a、b、c で最大のものを返す•
もし a > b であれば、•もし a > c であれば、•result ← a。
•
そうでなければ、•result ← c。
•枝分かれ終わり。
•
そうでなければ、•
もし b > c であれば、•result ← b。
•
そうでなければ、•result ← c。
•枝分かれ終わり。
•枝分かれ終わり。
•result を返す。
かなり大変ですね。これを Ruby にしたものは次のとおり。

2def max3(a, b, c)
if a > b
if a > cresult = aelse
result = c
endelse
if b > cresult = belse
result = cendend
return result
endこうなると字下げしてないとごちゃごちゃになるでしょう? しかし字下げしてあってもこれはかなり苦しいですね。一般に、if の中に if を入れると非常に分かりづらくなるので、できるだけ避けたほうがよいのです。
ところで、先の別解から発展させるとどうなるでしょう?

• max3x: 数 a、b、c で最大のものを返す•
result ← a•
もし b > result であれば、result ← b。
•
もし c > result であれば、result ← c。
•result を返す。
「もし」の擬似コードが 1 行に書かれていますが、この場合はこちらののほうが見やすいと思ったのでそうしてみました。 Ruby でも次のとおり (こんどはどちらが好みですか?)。

def max3x(a, b, c)
result = a
if b > result then result = b end
if c > result then result = c end
return resultend一般には、枝分かれの中に枝分かれを入れるよりは、枝分かれを並べるだけで済ませられればそのほうが分かりやすいと言えます。また、この方法では入力の数 N がいくつになっても簡単に対処できるという利点があります。
実は、さらなる別解があります。それは、既に max2 を作ったわけですから、それを利用するというものです。

def max3xx(a, b, c)
return max2(a, max2(b, c))end
このように、一度作って完成したものは後から別のものを作る時の「部品」として使える、というのは重要な考え方です。このことも覚えておいてください。

3

2.3

演習 1c — 多方向の枝分かれ

演習 1c は 3 通りに分かれるので、if の中にまた if が入るのはやむをえないはずです。Ruby コードを見てみましょう。

def sign1(x)if x > 0
return "positive."else
if x < 0return "negative."else
return "zero."endendendこのような「複数の条件判断」はよく使うので、実はこれは if の入れ子にしなくても書けるようになっています。具体的には、if 文には「elsif 条件 then 動作」という部分を途中に何回でも入れられ、それを使うと次のようになります。

def sign2(x)if x > 0
return "positive."
elsif x < 0
return "negative."
else
return "zero."end
end
順序が前後しましたが、擬似コードだと次のようになります。

• 実数 x を入力する。
• もし x > 0 ならば、•
「positive.」を返す。
• そうでなくて x < 0 ならば、•「negative.」を返す。
• そうでなければ、•「zero.」を返す。
• 枝分かれ終わり。
「そうでなくて〜ならば、」は何回現われても構いません。また、そのどれもが成り立たない場合は「そうでなければ」に来るわけですが、この部分は不要なら無くても構いません。
ところで、最大値の問題にちょっと戻ると、複合条件を使えば「a > b && a > c」なら a が最大だと分かりますから、これを利用した 3 方向枝分かれで書くこともできます (変数を使わず値を返すスタイルにしてみました)。

def max3y(a, b, c)
if a > b && a > creturn a4

elsif b > creturn belse
return cendendただし、この方法でも N が 4、5 と増えてくると条件の中の比較演算が増えて、一般に N 2 に比例してしまいます。だからいけないというわけではなく、N の個数が多くなければ、このやり方を使ってもよいかも知れません。

2.4

演習 2 — 平方根計算の経過表示

演習 2 は誤差を指定する平方根計算に経過表示と回数表示をつけるというものでした。さっそく見てみましょう。

def sqrt2(x, e)w = x; h = 1.0; n = 0
while w - h > e do
w = 0.5 * (w + h); h = x / w; n = n + 1
puts "#{n}: w = #{w}, h = #{h}"endreturn hend
計算そのものは変えていませんが、回数を数える変数 n を追加し、最初は 0 にします。そして、1 回計算するごとに「n+1 を計算して n に入れ直す」ことで 1 ずつ増やします。実行例を見てみましょう。

irb> sqrt2 2, 0.000000001
1: w = 1.5, h = 1.3333333333333333
2: w = 1.4166666666666665, h = 1.411764705882353
3: w = 1.4142156862745097, h = 1.41421143847487
4: w = 1.4142135623746899, h = 1.4142135623715002=> 1.4142135623715002
確かにすぐに終わります。なお、n を増やしてから表示しているので、1 から表示が始まるようになっています。

2.5

演習 3a〜3c — 繰り返し

この辺は簡単なのでプログラムだけ示します (べき乗は計算するだけなら 2**n でよいのですが、繰り返しを使うという前提なのでループを使います)。

def pow2(n)result = 1
n.times do result = result * 2 end
return resultend
def fact(n)result = 1
n.times do |i| result = result * (i+1) end
return resultend
5階乗の方は「1 × 2 ×…× N」を計算したいわけですが、times が渡して来るカウント値は「0, 1, …,N-1」なので、全部 1 足してから掛けています。しかしそれはちょっと分かりにくいですね。
実は、N .times の代わりに N .step(M , d) という別のメソッドを使うと、初項 N 、終項 M 、増分 d を指定して計数ループを作ることができます (d は指定しないと「1」が使われます)。これを使えば、階乗は次のようにもっと分かりやすくなります。

def factx(n)result = 1
1.step(n) do |i| result = result * i end
return resultend
上の step は「i を 1 から n まで 1 ずつ増やしながら」という擬似コードに対応します。
組み合わせの数を整数で計算できるようにするためには「小さい側から」掛けて・割って・掛けて・4×5×6×7のように並べて左から 1 列ずつ乗算・除算の順割ってのようにしないとうまくいきません。 1×2×3×4で計算するわけです。この順序でやれば、除算が常に割り切れるので、誤差なしで計算できます (浮動小数点で計算してしまうと、誤差が現れるのでいまいちだと思います)。

def comb(n, r)
result = 1
1.step(r) do |i|result = result * (i + (n-r)) / iend
return resultend

制御構造の組み合わせ (再)3

簡単なプログラムでは制御構造として「枝分かれ」「繰り返し」のどちらかを 1 つだけを使えば済みますが、もう少し込み入ったプログラムになると、ある制御構造 (枝分かれ、繰り返し) の内側にさらに制御構造を入れることになります。たとえば、「0〜99 の数を順に打ち出すが、ただし 3 の倍数の時だけは fizz と打ち出す」という例を考えてみます。 1• fizz1: 3 の倍数の時だけ fizz•
変数 i を 0 から 100 の手前まで変えながら繰り返し、•もし i が 3 の倍数ならば、•「fizz」と出力。
•そうでなければ、•i を出力。
•枝分かれ終わり。
•以上を繰り返し。
これを Ruby に直したものは次のようになります。

def fizz1
100.times do |i|
if i % 3 == 0
海外で古くからある言葉遊びに fizzbuzz というのがあります。これは輪になって「1, 2, . . .」と順に数を唱えますが、ただし数が 3 の倍数なら「fizz」、5 の倍数なら「buzz」、3 と 5 の公倍数なら「fizzbuzz」と (数の代わりに) 言わなければならず、間違えたりつっかえたりしたら負けで輪から抜ける、というものです。日本で有名なのは世界のナベアツの「3 の倍数と 3 がつく数字の時だけアホになります」というネタですが、ナベアツも fizzbuzz をヒントにこのネタを考案したという説があります。
16

puts(’fizz’)
elseputs(i)
end
end
end
動かしてみましょう。

irb> fizz1fizz
12fizz
(途中略)
97
98
fizz
=> 100irb>
このように、基本的な制御構造を組み合わせていけば、いくらでも複雑なプログラムが作成できます。
これはちょうど、簡単な規則と単語からいくらでも複雑な文章が (日本語や英語で) 作れるのと同じだと考えてください。
演習 1 上の fizz プログラムを打ち込んでそのまま動かせ。動いたら、繰り返しと枝分かれを組み合わせて次の動作をする Ruby プログラムを作成せよ。

a. 0 から 99 までの数のうち、 2 の倍数でも 3 の倍数でもないものだけを順に打ち出す。
b. 0 から 99 までの数を順に打ち出すが、ただし 3 の倍数の時は fizz、5 の倍数の時は buzz、3 の倍数かつ 5 の倍数の時は fizzbuzz と (いずれも数値の代わりに) 打ち出す (fizzbuzz 問題)。2c. 0 から 99 までの数を順に打ち出すが、ただし 3 の倍数と 3 がつく数字の時は数値の代わりに aho と打ち出す。
以下の 3 問は前回の演習 5〜7 と (ほぼ) 同じなので、やってしまった人はご勘弁ください。というか、今回解説する時間がないので次回解説するため、ここに再録しています。
演習 2 2 数 a、b の最大公約数 (greatest common divisor、GCD) を求めるアルゴリズムを次に示す。

• gcd1: 整数 x、y の最大公約数を返す•
x ≠ y である間繰り返し、•x ＞ y なら、•x ← x - y。
•そうでなければ、•y ← y - x。
•枝分かれ終わり。
•繰り返し終わり。
•x を返す。
2fizzbuzz 問題については、「(米国で) プログラマを募集して応募者にこの問題のプログラムを書かせてみたら書けない奴が多い。だから応募者のふるい分けに使っている」という話があります。本当だとしたら、これを書けた人はプロ級かも (そんなわけはない)。

7

これを Ruby プログラムにして動かせ。これで最大公約数が求まる理由も併せて説明すること。
(ヒント: x > y ならば gcd(x, y) = gcd(x − y, y) 等のこと (つまり x と y の大きいほうから小さいほうを引いても 2 数の最大公約数は変化しないこと) を示せばよいわけですね。 )演習 3 「正の整数 N を受け取り、N が素数か否かを (true/false で) 返す Ruby プログラム」を書け。まず擬似コードを書き、それから Ruby に直すこと。(ヒント: N が素数ということは、 Nを 2〜N − 1 のいずれで割っても割り切れない、つまり剰余が 0 でないということ。剰余は演算子%で計算できるのでしたね。 )演習 4 「正の整数 N を受け取り、N 以下の素数をすべて打ち出す Ruby プログラム」を書け。待ち時間 10 秒以内でいくつの N まで処理できるか調べて報告せよ。 N が大きくなるように工夫してくれるとなおよい。(ヒント: 処理を速くするためには、(1) 割ってみる数をできるだけ少なくとどめる、(2) 素数の候補とする数をできるだけ少なくとどめる、という 2 点を工夫するとよいでしょう。たとえば 2 は別扱いして奇数だけ扱うなど。 )4配列とその利用

4.1

データ構造の概念と配列

ここまでではプログラムが扱うデータは個々の「値」であり、1 つの変数に 1 つの値が入っていました。しかしこのやり方では、大量のデータを扱うのが困難なのは明らかです。ではどうするかというと、複数のデータを組にしたり、列として並べるなどの「構造」を持たせて扱う、というのが答えです。この、データに持たせる構造のことをデータ構造 (data structures) と言います。
プログラミング言語の用語では、データの種類のことをデータ型 (data types)、その中で「整数」「実数」など単一の値から成るものを基本データ型 (primitive data types) と呼びます。それと対比して、組や列など複数の値が集まったデータのことは複合データ型 (compound data types) と呼びます。実は文字列は、中に複数の文字が含まれているので複合データ型だといえます。
今回は複合データ型のうちでもよく使われる配列 (array) を取り上げます。配列は既に「[1, 2, 3]のように値を並べたもの」として言及したことがありますが、要するに値が一列に並んだものです。
図 1 のように、整数であれば 1 つの変数に 1 つの値しか入れられませんが、配列を使うことで 1 つの変数に一連の値を入れることができます。
xarray5913325ab

図 1: 配列の概念
図 1 を見て不思議に思ったことはないでしょうか。具体的には、基本型では変数の位置に「箱」が書かれていてそこに値が入っていますが、複合型では少し離れたところにデータを入れる場所があって、変数からはそこに矢印が出ています。
実はこの矢印はデータのありかを示す参照 (reference — ありかを指す値で、実体はメモリ上の番地だと思ってよい) です。そして、変数に配列を入れると、配列本体はどこか別の場所に置かれ、変数にはその場所への参照が入ります。そして、「b = a」のように変数間で代入をした時、基本型では値 (箱の中身) がコピーされますが、複合型では参照 (矢印) がコピーされるだけで、本体は 1 つのまま (単に 2 つの変数が同じ場所を指すだけ) です。33

Ruby の場合。C 言語はまた違います。

8

さらに、「2 つの変数が同じ場所を指している」状態でその複合データの中身を書き換えると、複合データは 1 つだけなので、どちらの変数から見た複合データも同じように変化していることになります。このあたりの挙動は間違えやすいので注意が必要です。

4.2

配列の生成

配列を使うには、まず配列を作り出す必要があります。その方法が色々ありますので、ここではそれらについて説明しておきます。

a = [1, 2, 3]# 直接指定a = Array.new(100, 0) # 要素数と初期値
a = Array.new(100) do 0 end # 要素数とブロック
a = Array.new(100) do |i| 2*i end # 〃1 番目の方法はこれまでにも使ってきた、各要素を直接指定する方法です。 4 この方法は、比較的少数の値を用意する場合に使います。
2 番目は、要素数と初期値を指定する方法で、要素数の多い配列を用意するときにはこの方法が一番単純です。53・4 番目も、要素数と初期値を指定する方法ですが、初期値として値を計算するブロック (do〜end) を指定するところが違います (この場合はブロックの中で式を直接指定します。メソッドではないので return は書けません)。 0 などと定数を指定した場合は 2 番目と変わりませんが、ブロックは(times などと同様) 「何番目」というパラメタを受け取ることができるので、それを用いて計算により初期値を決めてもよいのです。
配列は後からメソッド push で要素を追加できます。上の例の 4 番目と次は同じ結果になります。
a = []# 0 要素の配列を作り100.times do |i| a.push(2*i) end # 0〜198 を追加
現在の配列の長さ (要素数) は、メソッド length で取得できます。上の例では a.length は 100 です。
演習 5 ブロックを指定する形で 10 要素の配列を生成し、初期値を (a)〜(d) のようにしなさい。
(a)10987654321(b)0101010101(c)4321012345(d)1111100000

なお、初期値を指定するブロックの中でも if を使えます。

if 条件 then 式 1 else 式 2 end
この if は「if 式」であり、条件の成否に応じて「式 1」「式 2」のいずれかが全体の値となります。

4
値を並べて書く方法は「そのまま値を書く」ことから「配列リテラル」と呼ぶこともあります。しかし、配列では初期値を指定するのに変数や任意の式を指定できるので、厳密に言えば「そのまま」ではありません。Ruby の用語でもこの書き方は配列式 (array expression) というのが正式な呼び方です。
5
初期値を指定しないと各要素の初期値は nil になります。

94.3

配列の利用いちど用意してしまえば、配列の個々の要素は 1 つの変数と同様に扱えます。ここで「どの要素か」を指定するのに [...] の中に式を書いて指定します。これを添字 (index) と呼びます。たとえば上の例だと a[0]〜a[99] という要素があることになります (0 番目から数えることは慣れないと忘れやすいので注意してください)。
また、Ruby ではまだ用意していない添字番号 (たとえば上で「100 番」とか) の要素を参照するとnil が返ります。飛び離れた添字番号 (たとえば上で「200 番」とか) に値を格納すると、そこまでの途中の要素は全部 nil で埋められます。
では、配列を与えてその合計を求めるというのをやってみましょう (合計は積分とかで散々やったので簡単ですね)。

• arraysum : 配列 a の数値の合計を求める•sum ← 0。
•i を 0 から配列要素数の手前まで変えながら繰り返し、•sum ← sum + a[i]。
•繰り返し終わり。
•sum を返す。
Ruby コードは次のとおり。
def arraysum(a)sum = 0a.length.times do |i|sum = sum + a[i]endreturn sum
end
一応、動かすところの様子を示します。

irb> arraysum([1,2,3,4,5])=> 15
実は Ruby では「配列の各要素を取りながら周回するループ」というのもあって、そのほうが少し簡単になります。コードだけ示しておきます。

def arraysum1(a)sum = 0a.each do |x|
sum = sum + x
end
return sumend# x に配列の各要素が順次入る

合計ならこのほうが少し簡単ですが、「何番目」を必要とする場合もあるので、その場合には計数ループを使うことになるでしょう。 6
演習 6 上記の配列合計プログラムの好きな方をそのまま打ち込んで動かせ。動いたらこれを参考に下記のような Ruby プログラムを作れ。 7
メソッド each index で配列の添字を順次取り出してループすることもできます。
「返す」の場合は上の例と同様に return を使い、「出力する」の場合は puts を使って画面に直接 (その場で) 出力させてください。return は使った瞬間にそのメソッド呼び出しは終ってしまうので、複数回 return を使うことはできません。
6710

a. 数の配列を受け取り、その最大値を返す。
b. 数の配列を受け取り、最大値が何番目かを返す。なお先頭を 0 番目とし、最大値が複数あればその最初の番号が答えであるとする。
c. 数の配列を受け取り、最大値が何番目かを出力する。なお先頭を 0 番目とし、最大値が複数あればそれらをすべて出力する。
d. 数の配列を受け取り、その平均より小さい要素を出力する (例: 1、4、5、11 → 1、4、5)。
e. 数の配列を受け取り、その内容を「小さい順」に並べて出力する (例: 4, 11, 5, 1 → 1, 4,5, 11)。
演習 7 「素数列挙」の問題は、配列を使うとより高速にできる可能性がある。次の 2 つの方針を用いたプログラムを作成し、これまでに作ったものと速度を比較せよ。

a. 素数は値の大きいところではまばらにしかないので、これまでに見つかった素数を配列に覚えておき、新たな素数の候補をチェックする時に「これまで見つかった素数で割ってみて割り切れなければ素数」という方針にすれば、チェックする回数がかなり少なくできる。
b. 別の考え方として、 N 未満の素数を打ち出すのに次の方針を用いるのはどうだろう。 89• 論理値が並んだ要素数 N の配列を作り、全部「真」に初期化。
• 2 から始めて順次、その番号が「真」の値は素数として出力。
• 2、4、6、…と、2 の倍数番目の部分を「偽」に変更。
• 3、6、9、…と、3 の倍数番目の部分を「偽」に変更。
• 同様に、素数を出力するごとにその倍数番目を「偽」に変更。

本日の課題 3A
「演習 1」で動かしたプログラム (どれか 1 つでよい) を含むレポートを提出しなさい。プログラムと、簡単な説明が含まれること。アンケートの回答もおこなうこと。

Q1. 制御構造の組み合わせができるようになりましたか。
Q2. 配列について学びましたが、使えそうですか。
Q3. 本日の全体的な感想と今後の要望をお書きください。

次回までの課題 3B「演習 1」〜「演習 7」(ただし演習 5 は除く) の (小) 課題から選択して 2 つ以上プログラムを作り、レポートを提出しなさい。配列の内容を含むことを強く勧めます。プログラムと、課題に対する報告・考察 (やってみた結果・そこから分かったことの記述) が含まれること。アンケートの回答もおこなうこと。

Q1. 配列が使いこなせるようになりましたか。
Q2. 疑似コードを書くのと、Ruby に直すのと、打ち込んで動かすのとで掛かった手間の比率を教えてください。
Q3. 課題に対する感想と今後の要望をお書きください。

これは「方針」であって、まだ擬似コードでもないことに注意してください。
この方法を考案したのはギリシャの哲学者エラトステネス (Eratosthenes) であり、この方法を彼の名前を冠してエラトステネスのふるい (sieve of Eratosthenes) と呼びます。なぜ「ふるい」かというと、素数でないもの (各数の倍数) をふるい落としてしまうと、残ったものは素数だ、という方針でできているからです。
8911