Top | INDEX | UP

コンピュータ概論 第04回


第02/03回について

アンケート回収数

02回(10/24)03回(10/31)
3コマ3940
4コマ4442
02回演習3 の間違い指摘 (Thanks!)
puts x -> puts a
席が足らない。
足りているはずなのですが…。
時間の無駄 -- 講義の方向性が不明瞭で中途半端である。
前回に少し触れました。
次に進みたいので課題出してほしい。
検討します(一応「暇な人向け」問がありますね)。
もっと深く学べるサイトを紹介してほしい。
調べてみます。
プリント配布を希望します。
検討します。
もっと実用的なプログラムを。
「数学科」という意味で「実用的」なプログラムはやる予定です
アルゴリズムって?
01回参照、講義で実例やります。
このプログラムは覚える必要ある?
覚えなくてよいので、自分で書けるようになってください。

その他: トラブルなどについては講義中に質問・解決するようにしてください。 またネットワーク絡みのトラブルについては情報処理センターや生協に相談してください。


論理演算

if や while などの条件部に書く論理式を組み立てるときに使われる論理演算に and / or / not があります。それぞれ、and (論理積)は「かつ」、or (論理和)は「または」、not (論理否定)は「でなければ」に相当します。

and / or
AB A and B A orB
truetrue truetrue
truefalse falsetrue
falsetrue falsetrue
falsefalse falsefalse
not
Atruefalse
notAfalsetrue

参考: ベン図 in ウィキペディア

また and は && 、 or は || 、not は ! と書くこともできます(基本的には好みの問題、文法的には若干の違いがありますが)。

複雑な論理式では演算の順序を明確にするために括弧を使いましょう。 たとえば ( A and B ) or CA and ( B or C ) は異なる論理式です。

例1: x は y 以上 → x => y あるいは not (x < y)

例2: x が y より小さく、かつ、 x2 が y より大きい。 → x < y and x**2 > y

例3: x と y が等しいか、x が負値かつ x2 と y2 が等しい → x == y or ( x < 0 and x**2 == y**2 )


第3回の続き


プログラム(続)

関数(メソッド)定義

ある操作について名前を付けます。

def funname(var1, var2, ...)
  commands
end

funname が関数(メソッド)名、var1 を仮引数(カリヒキスウ)といいます。仮引数はゼロ個でも1個でも複数個でもかまいません。 また関数名は英小文字(a-z)で始まる英数字と '_' からなる文字列です(このあたり厳密には嘘なので 正確なところはリファレンスマニュアルを参照してください)。

関数は funname(e1, e2, ...) という形で呼出されます(関数呼出し)。このとき e1, e2 を引数(ヒキスウ)と呼びます。引数の数は関数定義の仮引数の数と一致します。

def square(n)     # 2乗を計算する関数の定義
  return n**2
end

puts square(10)   # 関数呼出し
puts square(20)   # 関数呼出し

return n でその関数を終了して値( n )を返します。 関数内の最後(endの直前)まで実行された場合は 最後の文を実行して、その値を返します。

def sum_of_squares(x,y)  # x^2 + y^2 を計算する関数の定義
  return x*x + y*y
end

puts sum_of_squares(3,4)

同じ値を返す関数でも定義の方法は複数あることが普通です。

def fact1(n) # 階乗の計算(1)
  s = 1
  for i in 1 .. n
    s *= i
  end
  return s
end

def fact2(n) # 階乗の計算(2) ... 再帰的定義
  if (n > 0)
    return n * fact2(n-1)
  else
    return 1
  end
end

puts fact1(10)       # 10!
puts fact2(10)       # 10!
puts fact1(fact2(5)) # (5!)! = 120!
----------------------------------------------------------------------
fact1(5)
  s = 1
  i = 1
  s *= i    # s は 1
  i = 2
  s *= i    # s は 1*2 = 2
  i = 3
  s *= i    # s は 1*2*3 = 6
  i = 4
  s *= i    # s は 1*2*3*4 = 24
  i = 5
  s *= i    # s は 1*2*3*4*5 = 120
  return s  # fact1(5) の値は 120 となる

fact2(5)
  5 * fact2(4)                    # n = 5 > 0 だから
  5 * 4 * fact2(3)                # n = 4 > 0 だから
  5 * 4 * 3 * fact2(2)            # n = 3 > 0 だから             
  5 * 4 * 3 * 2 * fact1(1)        # n = 2 > 0 だから
  5 * 4 * 3 * 2 * 1 * fact1(0)    # n = 1 > 0 だから
  5 * 4 * 3 * 2 * 1 * 1           # n = 0 なので fact1(n) = 1
  5 * 4 * 3 * 2 * 1
  5 * 4 * 3 * 2
  5 * 4 * 6
  5 * 24
  120                             # fact2(5) の値は 120 となる
----------------------------------------------------------------------

変数のスコープ: 仮引数や関数内で定義された変数は、関数の外からは見えません。 関数外や別関数内に同名の変数があっても、それは無関係です。

def f(x)
  y = x+1     
  return y
end

x=5
y=10
puts x + f(y)

問2: 2つの数を引数として大きい方の値を返す関数 max と、小さい方の値を返す関数 min を定義してください。

def max(x,y)
  if x > y
    return x
  else
    return y
  end
end

def min(x,y)
  if x < y
    return x
  else
    return y
  end
end

問3: 引数 n (> 0)に対して m2 < n となる最大の m を返す関数 isquare を定義してみましょう。

def isquare(n)
  i=0
  while true
    if (i+1)**2 > n
      return i
    end
    i += 1
  end
end

puts isquare(99)

問4: Fibonacci 数列の定義は以下のとおりです。

n を引数として Fn を返す関数を定義してみましょう。

def fib1(n)
  if n==0
    return 0
  elsif n==1
    return 1
  else
    return fib1(n-1) + fib1(n-2)
  end
end

for n in 0 .. 5
  puts fib1(n)
end
----------------------------------------------------------------------
fib1(5)
fib1(4) + fib1(3)
fib1(3) + fib1(2) + fib1(2) + fib1(1)
fib1(2) + fib1(1) + fib1(1) + fib1(0) + fib1(1) + fib1(0) + fib1(1)
fib1(1) + fib1(0) + fib1(1) + fib1(1) + fib1(0) + fib1(1) + fib1(0) + fib1(1)
1 + 0 + 1 + 1 + 0 + 1 + 0 +1
5
----------------------------------------------------------------------

def fib2(n)
  a = 1        # F(1)
  b = 0        # F(0)
  while n > 0  # n 回ループする
    t = a
    a += b
    b = t
    n -= 1
  end
  return b
end

for n in 0 .. 5
  puts fib2(n)
end

# コメント: Ruby では a, b = a+b, a という多重代入も可能だかここでは触れない

問7: for n in 0 .. 25 くらいで fib1 と fib2 の計算時間を比較してみましょう。

問8: fib2(n) で Fn が計算できることの証明。

Vn = ( Fn+1 )
Fn
R = ( 11 )
10
と定義したとき
( Fn+1 ) = ( 11 ) ( Fn )
Fn 10 Fn-1
すなわち Vn = R Vn-1 となる。よって
( Fn+1 ) = ( 11 ) n


( F1 )
Fn 10 F0
すなわち Vn = Rn V0 が成立する。ここで
V0 = ( F1 ) = ( 1 )
F00
したがって、まず
a = 1
b = 0
と変数 a, b の値を代入後に a, b を(同時に) a+b, a で置き換える 計算を n 回くりかえすと a = Fn+1 , b = Fn となっている。

このように「アルゴリズム」が異なると計算時間などが大幅に違ってくることがあります。 したがって、ある問題を解くときにより効率的なアルゴリズムを適用するのが賢い方法です。


暇な人向けの問: Ackermann 関数

def a(x,y)
  if x==0    then return y+1
  elsif y==0 then return a(x-1,1)
  else            return a(x-1,a(x, y-1))
  end
end

def f0(n) return a(0,n) end
def f1(n) return a(1,n) end
def f2(n) return a(2,n) end
def f3(n) return a(3,n) end
def f4(n) return a(4,n) end
  1. 計算結果を元に関数 f1, f2, f3, f4 の簡潔な数学的定義を予測してみましょう。
  2. その予測が正しいことを証明してみましょう。
  3. 自分のPC上で f3(n), f4(n) は n がどれくらいの大きさになるまで計算できるでしょうか?