11/11 関数から「計算」へ(2), アルゴリズムと計算量(1)

質問と回答

Q.

>ΣnCk (k=0,1,,,n) = 2^n
>Σ(nCk)^2 (同上) = 2nCn
>であるが
>Σ(nCk)^3 (同上) = ???

>３乗の計算に関して何か知っている人がいれば教えてください。

A.

たぶん母関数を使って求まるのでしょうが，私も答えを知らないので，答えを知っているひとは答えてあげてください．

Q.

集合論における自然数の構成を負うために以下のコードを書きました:

def zerol()
 return Set.new()
end

def succ(s)
 return s | Set.new([s])
end

def number(n)
 s = zerol()
 for i in 1..n
   s = succ(s)
 end
 return s
end

succ の性質から明らかに s ⊂ succ(s) とならなければならないはずですが、superset?, subset? を使うとこれが正しく判定されないようです。

A.

面白いことに気がつきましたね．RubyのSetにおいて，ドキュメントを見ると，「2つのオブジェクトの等価性は Object#eql? と Object#hash によります。なぜなら、Set は Hash を記憶として使っているからです。」と書かれています．一般のオブジェクト同士の同値性の完全な判定は非常にコストがかかるので，オブジェクトのアドレスをベースにしたハッシュ値を用いて同値性を判定するのが普通です．そのため，

irb(main):043:0> Set.new().hash()
=> 681390
irb(main):044:0> Set.new().hash()
=> 670910
irb(main):045:0> Set.new().eql?(Set.new())
=> false

のように，同値性を判断できなくなっているのです．

配列などの場合は，要素のハッシュ値を元に配列全体のハッシュ値を計算するようになっているので，

[1,2,3]==[1,2,3]

なども判定できるのですが，次の例のように自分自身を要素を含むような配列を作ると，途端にハッシュ値を計算できなくなります．

irb(main):046:0> a=[1,2,3]
=> [1, 2, 3]
irb(main):047:0> a[1]=a
=> [1, [...], 3]
irb(main):048:0> a.hash()
SystemStackError: stack level too deep
	from (irb):48:in `hash'
	from (irb):48
	from :0

Setクラスのhash関数を定義し直せば，問題の例は扱えるようにはなると思いますが，「自分自身を要素に含む集合」を定義すると同様の問題が生じる可能性はあります．

前回の課題について

CFIVEの掲示板11/4の課題，質問への書き込みは 11/11 10:00現在で 47名．
典型的な解法(素数)
- 想定した解法
```
def prime(n)
  sod(n,n-1)==1
end
```
- どうしてもif文を使いたい人は，
```
def prime(n)
  if sod(n,n-1)==1
    true
  else
    false
  end
end
```
  ここで，以下のようにtrueやfalseを"true"や"false"と書くと真偽値ではなく文字列を返すということになり，
```
def prime(n)
  if sod(n,n-1)==1
    "true"
  else
    "false"
  end
end
```
```
x=4
if prime(x)
  x=x*2
else
  x=x-1
end
x
```
  となってしまう．
- 別解
```
def prime(n)
  sod(n,n)==n+1
end
```
  とすると，prime(1)がfalseになるが，元々の練習問題ではn=1という入力が来ることは想定していないのでここまで気を使う必要はない．

典型的な解(combination)

教科書の漸化式を用いる．

def combination(n,k)
  if k>n
    0
  else
    if k==0
      1
    else
      combination(n-1,k-1)+combination(n-1,k)
    end
  end
end

階乗を定義

def factorial(n)
  if n<2
    1
  else
    n*factorial(n-1)
  end
end
def combination(n,k)
  factorial(n)/(factorial(k)*factorial(n-k))
end

combination_loopをそのまま書くという解答は想定していなかったが，禁止していたわけではないので，認める．

投票システム

vote.rbをダウンロードして，ホームディレクトリに保存する．ドックからターミナルを起動して，

ruby vote.rb 選択肢番号

のように使う．

練習，投票

今日の課題