第4章の練習，投票

再帰による反復計算の定義---再帰による和の定義

def sum(n)
  if n>=2
    sum(n-1)+n
  else
    1
  end
end

約数の和

def divisible(x,y)
  x%y==0
end

def sod(k,n)
  if n>=2
    if divisible(k,n)
      sod(k,n-1)+n
    else
      sod(k,n-1)
    end
  else
    1
  end
end

条件を満たす値を探す

load("./divisible.rb")
def gd(k,n)
  if divisible(k,n)
    n
  else
    gd(k,n-1)
  end
end

irb(main):037:0* gd(20,19)
=> 10
irb(main):038:0> gd(100,99)
=> 50
irb(main):039:0> gd(9,8)
=> 3

練習

素数とは，1と自分自身しか約数がないような数である．上で定義した関数sodを使ってnが素数の時にのみtrue, そうでない時にfalseとなるような関数prime(n)を定義せよ
```
irb(main):045:0> prime(6)
=> false
irb(main):046:0> prime(7)
=> true
irb(main):047:0> prime(107)
=> true
irb(main):048:0> prime(961)
=> false
```

n個からk個を選ぶ組み合わせ数 nCkを求める combination(n,k)を定義せよ(標準テキスト練習4.2)

irb(main):067:0> combination(5,2)
=> 10
irb(main):068:0> combination(10,5)
=> 252
irb(main):069:0> combination(1,1)
=> 1

次の結果は何?

def fact(n)
  if n==1
    1
  else
    n*fact(n-1)
  end
end

irb(main):012:0> fact(50)

0
100
3628800
2432902008176640000
30414093201713378043612608166064768844377641568960512000000000000

繰り返しによる和の定義

def sum_loop(n)
  s=0
  for i in 1..n
    s=s+i
  end
  s
end

irb(main):015:0> sum_loop(3)
=> 6
irb(main):016:0> sum_loop(10)
=> 55

条件を満たす値を探す繰り返し

load("./divisible.rb")
def gd_loop(k,n)
  while !divisible(k,n)
    n=n-1
  end
  n
end

irb(main):035:0> gd_loop(20,19)
=> 10
irb(main):036:0> gd_loop(100,99)
=> 50
irb(main):037:0> gd_loop(9,8)
=> 3

配列と繰り返しを使った組み合わせ数の計算

def make1d(w)
  a=Array.new(w)
  for i in 0..(w-1)
    a[i]=0
  end
  a
end
def make2d(h,w)
  a=Array.new(h)
  for i in 0..(h-1)
    a[i]=make1d(w)
  end
  a
end

def combination_loop(n,k)
  c=make2d(n+1,n+1)
  for i in 0..n
    c[i][0]=1
    for j in 1..(i-1)
      c[i][j]=c[i-1][j-1]+c[i-1][j]
    end
    c[i][i]=1
  end
  c[n][k]
end

irb(main):062:0> combination_loop(5,2)
=> 10
irb(main):063:0> combination_loop(10,5)
=> 252

次の結果は何?

irb(main):001:0> combination_loop(40,32)

40
91390
76904685
137846538820
12641060643775

言葉探し

def match(s,p)
  i=0
  w=p.length()
  while submatch(s,i,p,w)< w
    i=i+1
  end
  i
end

def submatch(s,i,p,w)
  j=0
  while j< w && s[(i+j)..(i+j)]==p[j..j]
    j=j+1
  end
  j
end

irb(main):031:0> submatch("balalaika",1,"alai",4)
=> 3
irb(main):032:0> submatch("balalaika",3,"alai",4)
=> 4
irb(main):042:0> match("balalaika","alai")
=> 3

次の結果は何?

irb(main):001:0> submatch("akaiakaiaka",4,"aka",3)

次の結果は何?

irb(main):001:0> match("makkanaaka","aka")