12/7 アルゴリズムと計算量(2)

前回までの補足

• 演習室内は飲食禁止です．ペットボトルを持ち込む際もバッグ等の中に入れてください．
• 前回の計測は，RubyBenchmarkの機能を利用して，

  require 'benchmark'
  Benchmark.measure{ 「式」 }.total
  

  で「式」の実行時間を計測して，gnuplotでグラフにしたものです．

前回の感想，質問より

Q.

0から順に数え上げるフィボナッチ数の計算のプログラム

def fibl(k)
  f=1
  p1=1
  for i in 2..k
    p2 = p1     #fib(i-2)
    p1 = f      #fib(i-1)
    f = p1 + p2 #fib(i)
  end
  f             #fib(k)
end

で，forの繰り返し部分

    p2 = p1     #fib(i-2)
    p1 = f      #fib(i-1)
    f = p1 + p2 #fib(i)

の中に変数iが現れません．

  for i in 2..k

は何のためにあるのでしょうか?

A.

  for 「変数」 in 「式1」 .. 「式2」
    「命令1」
    ...
    「命令n」
  end

という構文は，「変数」の値を「式1」から「式2」の値まで1つずつ順に 変化させながら，「命令1」から「命令n」を毎回実行する繰り返しを意味します．
ここまでは「命令1」から「命令n」の中で「変数」の値を参照する例が出てきまし たが，フィボナッチ関数の例では出てきていません．この例での変数iは，繰り返 し回数を覚えておくために使われます．「命令1」から「命令n」までを繰り返し回数k-1回繰り返すだけなので，

  for i in 1..(k-1)

でも良いわけですが，元のプログラムとの関連からを考えて，2からkまで変化させています．

11/16の課題投票

• 12/6までにCFIVEの11/16の課題，質問に画像，プログラムを提出したのは62名(11/16の課題)
• 投票システムを使って投票(1-62)をおこなう．
• 自分の作品以外で良いものを3つまで順位をつけて投票する．
• システム上は自分の作品に投票したり，1-3位まで同じ作品に投票したりも できるが，そのような投票は後でチェックして除く．

投票システム

ruby vote.rb 選択肢番号

今日の練習，投票

• 第5章の練習，投票

関連リンク

• 配布プログラム
• Rubyリファレンスマニュアル
• CFIVE利用の手引

教科書の補足

• 情報科学入門: Rubyを使って学ぶ / 配付プログラムにあるプログラムは一括ダウンロードできます．allcode.zipをダウンロードして，ファインダーからダブルクリックするとallcodeというフォルダーができます．その下にすべてのファイルが入っています．そこのファイルをすべて，講義用のフォルダー(is11)にコピーすると良いでしょう．
• 情報科学入門: Rubyを使って学ぶ / 配付プログラムの中には練習問題のチェックプログラムが含まれています．たとえば，第1章の練習問題をテストする時には，同じディレクトリに，練習問題で作成したプログラムを教科書で指定されたファイル名で置いて，

  ruby check.rb ex01.rb
  

  と実行すると，関数を与えた時の入力と出力があっていることが確認できます．

今日の課題

• 講義中に投票を求められるので，投票システムを使って投票をする．
• 講義で用いた練習問題で自分が解いたプログラムとその説明，今回の講義の感想，改善意見等(100文字以上)をCFIVEの掲示板CFIVEの掲示板12/7の課題，質問に書き込んでください．