今回の学習項目です。
次のように配列aryが与えられたときに、 配列の要素の最小値を返す関数smallest(ary)を作成しなさい。
def smallest(ary) # #この部分を作る # end # end of def numbers = [4,12,45,21,18,7,20,2,51,16,10] print smallest( numbers )
出力は以下のようになる。
2
次のように配列aryと変数xが与えられたときに、配列の要素の中からその変数の値にもっとも近い要素を探して返す関数nearest(x,ary)を作成しなさい。
def nearest(x, ary) # #この部分を作る # end # end of def target = 15 numbers = [4,12,45,21,18,7,20,5,51,16,10] print nearest(target,numbers)
出力は以下のようになる。
16[絶対値]
配列の要素の中からある値に最も近い要素を探すためには、 「差の絶対値」が必要になります。 そのためには、.abs を使います。以下がその使用例です。
x = 10 y = 15 p (x-y).abs p (y-x).absこの実行結果は、どちらもxとyの差の絶対値、つまり5が表示されます。
配列の要素の中からある値に最も近い要素を探すためには、 配列の要素とその値との差の最小値を与える要素を探せばよいのです。 課題1-1として「配列の要素の最小値」を求めるプログラムを作成しましたが、 今回は「配列の要素と与えられた値との差の絶対値の最小値」 を考えることが違いです。
次のように要素が小さいものから大きなものへと並べられた (昇順にソートされている、と言います)配列aryが与えられたときに、 与えられた数xを「順番を狂わせないよう」配列に加えた配列を返す関数 insert(x,ary)を作りなさい。 以下がその使用例です。
def insert(x, ary) # #この部分を作る # end # end of def ary = [4,12,45] p insert(1, ary) p insert(8, ary) p insert(50,ary) p insert(10, [])
出力は以下のようになる。
[1, 4, 12, 45] [4, 8, 12, 45] [4, 12, 45, 50] [10][課題1-3のヒント]
問題では「すでにある配列に数を要素として加える」ように書いてあるが、
これをその通りやることは実際には難しい。そこで、
「与えられた条件を満たす配列を作って」返すようにすることを考えます。
おおまかな方針は次のようなものです。
注意: 3番目と4番目の処理を円滑に実現するため、
trueを初期値とする変数(flagとしましょう)を繰り返しに入る前に用意しておき、
繰り返しの間で「xをansに付け加えた場合」にその値をfalseにします。
そして、繰り返し終了後にその変数の値がtrueなら(つまりxがansに付け加えられていなければその時に限り)xをansに付け加えるようにするとよい。
この変数は以下の繰り返しにおいて、配列の要素とxをそもそも比較する必要があるかどうかの判定にも使えます。
その要素が与えられた数xよりも小さければ配列 ans に付け加える。
そうでなければ、(1)配列ansにxをまだ付け加えていなければ、
配列ansにxを付け加える。(2)さもなくば(配列ansにxを付け加えた後ならば)、
そのの要素を配列ansに付け加える。
課題1-3のプログラムを利用して、 配列の要素を小さいものから大きなものへと並び替える （「昇順にソートする」、もしくは単に「ソートする」といいます） プログラムisortを作成しなさい。
ここでの考え方は次のとおりです。
aryから順に取り出された要素をxとする。 変数 ans に insert(x, ans) の値を代入する（ansの値を更新する）。
def isort(ary) # #この部分を作る # end # end of def numbers = [4,12,45,21,18,7,20,5,51,16,10] p isort( numbers )
出力は以下のようになる。なお、この方式は挿入ソート(insertion sort)と呼ばれている。
[4, 5, 7, 10, 12, 16, 18, 20, 21, 45, 51]
課題1-4の方法でソートができる理由を述べなさい。また、 n個の要素を持つ配列をソートするとき、 ソートが完成するまでに（insertで行われている)要素の比較の合計回数は、 最悪の場合(回数がもっとも多い場合)には何回くらい必要だろうか。 具体的にそのような配列を例で示しながら説明しなさい。
課題1-1のsmallestを改変し、次のように配列aryが与えられたときに、 配列の要素の最小値とそれ以外の要素からなる配列を求めて、 それらを要素とする配列を返す関数 select(ary)を作成しなさい。
def select(ary) # #この部分を作る # end # end of def numbers = [4,12,45,21,18,7,20,2,51,16,10] p select( numbers )
出力は以下のようになる（これは一例であって必ずしもこのとおりではなくてもよい）。
[2, [12, 45, 21, 18, 7, 20, 4, 51, 16, 10]][課題1-6のヒント]
課題1-1と同様最小の要素を配列から取り出すが、
それ以外の要素を集めた配列も作り、その両方を要素とする配列を返す点が異なる。
それには、最小値の候補を記憶するための変数(変数名をsmallestとする)と、最小値以外の要素を記憶するための配列（初期値として空配列を与える, 変数名をrestとする）を最初に作っておき、
配列の要素を１つずつ調べ、それまでの最小値ならばsmallestの値とし、そうでなければrestに加えていく。ここで、smallestの値に変更があった場合には、昔のsmallestの値をrestに加えることを忘れないようにする。
そして最後に、関数の値として、[smallest, rest]を返せばよい。
課題1-6のプログラムを参考にして、 配列aryの要素を小さいものから大きなものへと並び替える（ソートする） プログラム ssort(ary) を作りなさい。これは選択ソート(selection sort)と呼ばれる方法です。
ここでの考え方は次のとおりです。
aryの要素を、最小の要素と、それ以外の要素からなる配列に分ける(課題1-6 の主要部分)。 そして、最小の要素を配列ansに付け加える。 また、最小の要素以外の要素からなる配列を変数aryの値とする。
課題1-7の方法でソートができる理由を述べなさい。また、 n個の要素を持つ配列をソートするとき、 配列に要素を加える操作は、最も回数が多い場合に何回くらい必要だろうか。 具体的にそのような配列を例で示しながら説明しなさい。
今までは関数を一つだけ定義してそれを使ったプログラムを考えてきました。 しかし実際の大きなプログラムは、関数(やあとで学ぶクラス)の定義をたくさん用意し (しかも、それらは一つのファイルに書くのではなく、いくつかのファイルに分けて書き)、 それらを必要に応じて組み合わせて使う、というものです。
ここではそのための一歩として、いくつかの関数を利用するプログラムについて考えます。 特に、関数の中で別な関数を利用するプログラムを中心に考えます。 そして、その特殊な例として再帰関数を取り上げます。
$KCODE = "s"
def hitoketa(kazu)
case kazu
when 1
return("いち")
when 2
return("に")
when 3
return("さん")
#
#この部分を作る
#
end # case
end # def of hitoketa
def yomiage(kazu)
if (kazu >= 100) # ちょっと大きすぎる
print "対象外です\n"
return nil
elsif (kazu >= 10) # ２桁の数
jukketa = kazu / 10
amari = kazu % 10
return hitoketa(jukketa)+" じゅう "+hitoketa(amari)
else # 一桁の数
return hitoketa(kazu)
end # if
end # def of yomiage
for x in [23, 31, 75, 89]
print x," => ", yomiage(x),"\n"
end #23, 31 はこのままでも表示するが、他は動かない
出力は以下のようになる。
23 => に じゅう さん 31 => さん じゅう いち 75 => なな じゅう ご 89 => はち じゅう きゅう[case文]
case kazu
when 1 # kazuの値が1の場合
文1
when 2 # kazuの値が2の場合
文2
when 3 # kazuの値が3の場合
文3
when 4 # kazuの値が4の場合
文4
else # それ以外の場合
文5
end
気がついた人もいるでしょうが、このプログラムは 「間違いではないが、日本語としては不自然」な数の表現を表示することがある。 どのような場合にそうなるかを考え、より自然な表現になるよう直すにはどうしたらよいかを考えてみよう。
def dist(p, q)
# p, qは座標、 p = [x1,y1], q = [x2, y2]
return (((p[0]-q[0])**2 + (p[1]-q[1])**2)**0.5) # √((x1-x2)**2+(y1-y2)**2)
end # def of dist
これを使って、次のように10個の点(座標の表現形式は先と同じで配列とする)
が与えられたときに、これらの点の間の距離の最小値を返すnearestPoints を作れ。
points = [[92, 44], [90, 46], [28, 64], [85, 61], [4, 14], [52, 20],
[90, 15], [93, 55], [35, 83], [55, 74]]
def nearestPoints(ary)
#
#この部分を作る
#
end # of def
p nearestPoints(points)
出力は以下のようになる。
2.82842712474619[課題2-2のヒント]
一つの方法は、すべての点を組み合わせ、その間の距離を計算し、 配列にいれておく。そして4月12日Aの課題2-2 のように、配列の最小値を答えるようにする。
課題2-2で作ったプログラムnearestPointsは、引数となる配列の大きさ(要素数) によらず答えられるものになっているだろうか？ もしも配列の大きさを10に固定して考えていた場合は、その配列の要素がどんなに大きくても答えられるように、直しなさい。また、引数となる配列の大きさをn (n > 2)とした時に、 すべての点の組み合わせから計算される距離の個数はどのくらいになるだろうか、 nで表してみよ。このことから、 nが大きな値になるにつれてどのようにプログラムnearestPointsの計算時間が大きくなると予想されるか、答えよ。
[課題2-3のヒント]再帰というと難しそうに聞こえますが、要するに 関数の中から関数を呼び出す一つの形式です。ただ先ほどの関数の使い方と違うのは、 「呼び出される関数が呼び出した関数と同じ関数」、つまり 「自分自身を呼び出す関数」というところにあります。
これは一見馬鹿げたもののように見えるかもしれません。 こんなのがうまく動くはずがない、と思うかもしれません。 確かに、下手に作ると動かないどころか、応答しない(迷宮入り？） プログラムになってしまいます。 そこで、ここではちゃんと動く再帰関数の作り方とその考えを学びます。
nを正の整数とした時、階乗n!を計算するプログラムを作成しなさい。 ただし、4月5日Bの課題3-6でやったのとは異なり、 繰り返しを使うのではなく、再帰関数として定義しなさい (以下のプログラムの欠けているところを埋めて完成させる)。 そして、いろいろな正の整数を引数に与えて、ちゃんと正しい答えが返ることを確かめなさい。
def factorial(m) # m! を計算する
if (m == 1)
return 1
else
return m * factorial( ) # ここを完成させる
end
end # def of factorial
n = 20
print "factorial(",n,") = ",factorial(n),"\n"
factorial(20) = 2432902008176640000[課題3-1のヒント]
n! = 1 * 2 * 3 * ... * (n-1) * nです。これは次のようにもかけます。
n! = n * (n-1) * ... * 3 * 2 * 1 = n * (n-1)!ここで factorial(n) はn!を計算する「はず」のものですから、 この関係から、factorial(n-1)とnとの積で表されるはずです、ね。
課題3-1で作ったプログラムを元に、間違って再帰のプログラムを作った場合に どんなことが起こるかを経験しましょう。そのために、次の注意を読んでおいてください。
注意：間違ったプログラムを作ってしまうとプログラムが止まらなくなって しまうことがあります。そのような時、Ctrlキーを押しながら C のキーを押すと、 プログラムは途中で強制的に終了します。
def fact(m) # m! を計算するつもり
return m * fact(m-1)
end # def of fact
n = 20
print "fact(",n,") = ",fact(n),"\n"
どんなことが起きたでしょうか。またそれはどうしてでしょうか？
説明しなさい。
課題3-1のプログラムと課題3-2のプログラムを比べて、 課題3-1のプログラムがちゃんと停止して正しい答えを返すことの説明を行いなさい。
再帰のプログラムをちゃんと理解して使いこなせるようになると、 プログラムの幅が広がります。 再帰のプログラムのこつは、終了条件(自分を再び呼び出すことなく答えを返す 処理）をまっさきに書くこと、そして繰り返し（自分を呼び出す「再帰」の部分） では、必ず引数が小さくなっていること(数の場合だけではなく後で見るように配列を引数とすることもありますが、その場合は要素数が少なくなっていることを意味します）、 そして再帰の呼び出しの部分は「ちゃんと動くもの」として仮定してプログラムの動きを考えること、です。
階乗の計算では、実は再帰よりも繰り返しを使う方がわかりやすく、 また効率がよいものでした。しかし、 再帰を使った方がプログラムが簡単になり、分かりやすくなる場合があります。 そのようなプログラムについてこれから見ていきましょう。
fibo(0) = 1 fibo(1) = 1 fibo(n) = fibo(n-1)+fibo(n-2) (n ≥ 2のとき)この関数fiboを使って次のように実行してみると
for n in 1..10
print "fibo(",n,") = ",fibo(n),"\n"
end
その結果は以下のようになる:
fibo(1) = 1 fibo(2) = 2 fibo(3) = 3 fibo(4) = 5 fibo(5) = 8 fibo(6) = 13 fibo(7) = 21 fibo(8) = 34 fibo(9) = 55 fibo(10) = 89[フィボナッチ関数]
a = [1,2,3] b = [4,5,6,7] c = a+b p cその結果は以下のようになる:
[1,2,3,4,5,6,7]この知識を前提として、配列aryを引数にとり、 配列aryの要素を小さいものから大きなものへと並び替える関数qsort(ary) を作成しなさい。ただし qsortの中身は次のように計算が行われるものとする。
変数aryに配列が値として与えられているとします。 次のように、「先頭の要素(pivot)よりも小さい要素を入れる」ために変数smallerに 空っぽの配列を与え、配列の要素をひとつずつ見て、 pivotよりも小さければ、配列smallerにいれていけばできます。
pivot = ary[0]
smaller = []
for i in 1..(ary.size-1)
if (ary[i] < pivot)
smaller << ary[i]
end
end
課題3-5の方法でソートができる理由を述べなさい。また、 n個の要素を持つ配列をソートするとき、 配列に要素を加える操作は、最も回数が多い場合に何回くらい必要だろうか。 具体的にそのような配列を例で示しながら説明しなさい。