情報科学概論
2002.7.16
この授業の成績評価方法はシラバスに記載されている通り,宿題と実技試験の総
合判断となります.現在想定しているものは別ページの通りです.
7月23日は実技試験です.試験は,座席指定はしませんが,使用可能な端末の配
置は制限しますので,勝手に起動しないでください.また,教科書,参考書の持
ち込みが可能です.
実際の方式は,予定としては,web上に試験問題を置き,解答用紙(テキストファ
イル)をダウンロードして解答を記入し,メールに添付して提出することになっ
ています.
出席に関する注意事項を説明しますので,その注意を良く聞いてから,電子メールにより出席の申告をしてください.「件名」は
gairon 7-16 attend s0240**
のように自分の学生番号を使って下さい.なお,入力ミスがあると出席として認
められないことになりますので,慎重に行ってください.文
字はすべて1バイト文字 (半角英数字) です.途中に入るスペースは一度に一個だけと
してください.スペースは全部で3個です.また,**の部分は自分の学生番号の下二桁
です.
数値や文字列を格納しておくものとして,変数や定数が定義できます.宿題の状
況を見ていると,かなりの人が忘れているようですが,名前が大文字で始まるも
のは「定数」です.一つのスクリプトの中で2度以上値を代入しようとすると,
警告が出ます.
最近の宿題で良く見られた例として,同じ名前の変数を違う目的で何度も使うと
言うことがありました.例えば,次のようなスクリプトを考えてみましょう.
この例では変数は2つ使われており,a と sum という名前で
す.最初の行で a に1が代入されているのですが,そのあと,for
ループの変数としても a をつかって
しまったところ,最終行のように出力すると,a
の値は1で無くなってしまいました.for
ループのように毎回初期化することが前提になっ
ている変数は同じものを何度も使って構いませんが,
そうではない変数に同じ名前をつけるのはやめましょ
う.
この授業で良く使った定数に ARGV があります.コマンドライン引数
を順に格納していく配列ですが,数値を代入してもデフォルトでは文字列として
扱うので,演算をする場合には,整数化したり実数化する必要があります.注意
してください.
プログラミングとは,あらかじめ考えうる全ての場合についてその対策を用意し,
条件ごとに別の流れを選択しながら進める手順書を作成することにたとえられま
す.そのような場合ごとに流れを変えることが条件分岐であり,ある条件を満た
す場合とそうでない場合の組み合わせで順次処理を行っていきます.そこで,そ
のような条件を満たす場合を真,そうでない場合を偽として値を得ることにより
プログラム上で判断できる形式が必要になります.
例えば,西暦の紀元後の年号から閏年を判定する作業手順は図1のようになります.
図1 うるう年判定の流れ
プログラミングで使用する if 文はそのために利用され,ある定義し
た条件を満たす場合とそうでない場合について処理を分けます.処理は二者択一
だけでなく,より複雑にも出来ますが,この授業の範囲外なので説明は省略しま
した.
上記の判定スクリプトを実際に自分で作ってみましょう.動作の検証には、ター
ミナルで使用できる cal コマンドが有効です.自分が入力した年の2
月を見てみれば判定できるでしょう.
作成上注意するのは, if で始まった処理は必ず end で終
了することで,これは if の処理の及ぶ範囲を限定するためです.こ
の範囲指定によりいわゆる「入れ子」と呼ばれる多重構造も可能となります.
この授業では初期化や終了条件の分かりやすさから,for ループを多
用してきました.使い方はだいたい分かっているようですが,多重にする場合に
は引数の順番に注意しましょう.
順列組合わせを実習したときに,階乗を使用し
ましたが,階乗は結構計算に時間のかかるものです.なるべく,少ないステップ
数で処理を終えるためには,少し工夫が必要でした.以下ではもう一度組合わせに
ついて計算してみましょう.
m個のものからn個を取る組合わせは,
mCnと表現さ
れます.計算は,
となります.まじめに計算すると3つの階乗を求めなければなりません.
しかし,先ほどの分数を良く見てみましょう.n!で約分すると,分子は,m×(m-1)×(m-2)×…×
(m-n+1)になり,分母は(m-n)!です.だいぶ計
算が楽になりそうです.また,約分をどうするかは,(m-n)と
nのどちらが大きいかでちょっと変ってきます.大きい方で約分する方
が計算時間が短くなりそうです.
for ループを利用してこの楽な方法で組合わせの数を計算
するスクリプトを考えてみましょう.そこでは完全な形の階乗は一つしか使用
しません.
配列は数値や文字列を順番に格納しておく入れ物です.中身を参照する際には,
「何番目の要素か」を示す序数を引数として指示します.序数は0から始まる
ことを思い出してください.要素が5個の配列の最後の項は4番目の項として参
照されます.
多重配列の要素をすべて参照するためには多重のループが必要でした.授業では
行列の例などを示しましたが,今回は数値の並べ替えを考えてみましょう.ま
ず,コマンドライン引数から適当な個数の数値を入力し,配列に取り込む部分
を次のように作ります.
上のスクリプトはただ単に入力した数値を配列に直して表示するだけです.では,
その数値を小さい方から大きい方へ順番に並べ替えるアルゴリズムを考えてみま
しょう.これには,単純なものからスマートなものまでたくさんの種類が知られ
ており,数値の数が多くなっても短時間で出来るものが理想です.しかし,ここ
では,最も基本的なアルゴリズムであるすべての数値を比較する方式を考えます.
のようにすることにより実現できます.さて,実際に比較をする部分を自分で考
えてみましょう.ちなみに,私は7行で書きました.
比較が終わると出力です.次のような行を用意しておけば,比較が分かりやすい
でしょう.
a = 1
sum = 0
for a in 0..5
sum += a
end
puts a
m!
------------
(m-n)!n!
m = ARGV[0].to_i
n = ARGV[1].to_i
def fact(k)
if k == 0
1
else
k*fact(k-1)
end
end
puts fact(m) / fact(m-n) / fact(n)
以前に紹介した関数定義の def がここでは階乗の定義のために使われ
ています.また,定義のやり方は「再帰的」と呼ばれる方法で,「数学的帰納法」
を応用したものが使用されています.この計算ではmが大きくなると結構
時間がかかるようになります.
array = []
max = ARGV.size
for i in 0..max-1
array[i] = ARGV[i].to_i
end
print "Before sort, "
p array
要素の入れ替えについては,
array[i], array[j] = array[j], array[i]
print "After sort, "
p array
ページトップに戻る