スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

[Ruby][アルゴリズム入門]アルゴリズムとは、漸化式

最近プログラミングでショックな出来事があったため、基礎から勉強しなおすことに決めました。
(配列のサイズミスって○時間悩んだなんて言えない……)

プログラムの基礎と言えばアルゴリズム。
手元にある唯一のアルゴリズム入門書、「改訂C言語によるはじめてのアルゴリズム入門」(初版)を片手に、内容を全てRubyで書いてみることにしました。
ついでに、この本を読んでみて感じた不満点なども補完出来るようにチャレンジしています。

三日坊主で終わりそうな気もします。

第一章「ウォーミングアップ」 目次

1-0 アルゴリズムとは
1-1 漸化式
1-2 写像
1-3 順位付け
1-4 ランダムな順列
1-5 モンテカルロ法
1-6 ユークリッドの互除法
1-7 エラトステネスのふるい

アルゴリズムとは

アルゴリズム(英: Algorithm)とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための効率的手順を定式化した形で表現したものを意味する。算法(さんぽう)と訳されることもある。

コンピュータにアルゴリズムを指示するための(電子)文書をプログラムという。人間より速く大量に正しい結果を導くことができるのがコンピュータの強みであるが、そのためには正しいアルゴリズムに基づくプログラムが必要である。

アルゴリズムの評価

  1. 信頼性が高いこと
  2. 処理効率がよいこと
  3. 一般性があること
  4. 拡張性があること
  5. わかりやすいこと
  6. 移植性

1-0に関しては、あまり書くことも無いので以上。
以下1-1。

漸化式とはなにか

さて、最初のテーマは漸化式です。
算数用語集・数学用語集で調べると、

数列で隣り合う2項または3項の間に成り立つ一定の関係を式で表したものを漸化式という。

なんだか分かるような分からないような。

プログラム的に考えるなら、漸化式とは自分自身(an)を定義するのに、1次低い自分自身(an-1 )を用いて表し、0次(a0)はある値に定義されているというものです。

例えばこの式
an = an-1 + 2

これは、1つ数字がわかっていれば、その次の数字はその数字+2になる、という意味。
判明している数字を初項といいますが、その初項が1だった場合、

1,3,5,7,9,11,………

といった数列になります。
どこがプログラム的やねんと似非関西弁でツッコミをいれたくなりますが、この考え方をすると再帰や繰り返しを使用して簡単にプログラミングすることができるのです。

例として先程の数列を繰り返しで書いてみると、
# first:初項, number:数列anのn
def a_n(first, number)
  print "#{first},"
  ans = first
  number.times do
    ans += 2
    print "#{ans},"
  end
end

a_n(1, 5) #=> 1,3,5,7,9,11,
Rubyでは出力結果を#=>の形で示すことが多いので、今後この記号があった場合は出力結果を示していると読んでください。
このように、前の数値に2を足すことで次の数値を求めることが出来ています。
これから先出てくるプログラムや数式は、どんなに難しく見えてもこの延長線上でしかありません。

nCrを求める

n個の中からr個を選ぶ組み合わせの数をnCrと表現します。CはCombination(組み合わせ)の頭文字です。

普段計算する場合、組み合わせは以下の式で求めます。
組み合わせの一般的な計算式

n!はプログラムでよく使う否定(not)ではなく、階乗(1からnまでを全て掛けた数)という意味です。

Rubyは小さな数の場合Fixnum、大きな数の場合Bignumと内部のデーター型を自動で切り替えてくれるのですが、C言語でプログラミングする場合一般的なint型の変数だと13!でオーバーフローしてしまうため注意が必要です。

また、Rubyの場合もFixnumの範囲でデータを扱う方が高速・省メモリと利点が大きいため、工夫してみましょう。

まず、nCrを漸化式で表すと以下のようになります。

組み合わせの漸化式

このとき、nC0は初項を表しています。

これを繰り返しで表現する場合、初期値を1とし、それに係数((n -r + 1) / r)を繰り返しのたび+1しながら順次かけあわせて行えばかなり大きなnにたいしてもFixnumの範囲内に収まります。

これをプログラムとして書くと、こうなります。
=begin
漸化式(nCrの計算)
=end
def combi(n, r)
  p = 1
  for i in 1..r
    p = p * (n - i + 1) / i
  end
  return p
end

for n in 0..5
  for r in 0..n
    print "#{n} C #{r} = #{combi(n, r)}  "
  end
  puts
end
#=>0 C 0 = 1  
#=>1 C 0 = 1  1 C 1 = 1  
#=>2 C 0 = 1  2 C 1 = 2  2 C 2 = 1  
#=>3 C 0 = 1  3 C 1 = 3  3 C 2 = 3  3 C 3 = 1  
#=>4 C 0 = 1  4 C 1 = 4  4 C 2 = 6  4 C 3 = 4  4 C 4 = 1  
#=>5 C 0 = 1  5 C 1 = 5  5 C 2 = 10  5 C 3 = 10  5 C 4 = 5  5 C 5 = 1 

シンプルですね。ちなみに13C6(13Crの組み合わせの最大値)でも答えは1716ですので、余裕でFixnumの範囲内に収まります。

13!を力任せに解くプログラムと比較して、前述したアルゴリズムの評価では処理効率が高いと言えるでしょう。

Horner(ホーナー)の方法

Hornerの方法とは、一元n次多項式を計算するときの簡単な(計算量の少ない)算法である。

上記のページでHornerの方法については、利点や具体的な使用方法についてまで言及されているのでこんな記事読んでないでこちらのページを読んでください(コラ

さて、実装の話です。
以下の多項式は、

Hornerの方法1

xについて括れるだけ括ると以下のような形になります。

Hornerの方法2


具体例としてα0=1、α1=2、α2=3、α3=4、α4=5の、
多項式
について考えると、
Hornerの方法

となり、これを漸化式にすると、

Hornerの方法の漸化式

という形になる。これをHornerの方法と言うんですね。この方法だとn回の掛け算とn回の足し算だけで多項式の計算を行うことができます。

これをプログラムで書くと、

=begin
Hornerの方法
=end

def fn(x, a, n)
  p = a[n]
  (n - 1).downto(0) do |i|
    p = p * x + a[i]
  end
  return p
end

a = [1, 2, 3, 4, 5]
for x in 1..5
  puts "fn(#{x}) = #{fn(x, a, 4)}"
end
やってることは組み合わせnCrと変わらないことがわかりますね。

漸化式の例

1:階乗
階乗
=begin
階乗
=end

def factorial(n)
  ans = 1
  for i in 1..n
    ans =i * ans
  end
  return ans
end

for n in 0..5
  puts "#{factorial(n)}"
end


2:べき乗

冪(べき、英語: power, exponentiation)あるいは冪乗(べきじょう)、累乗(るいじょう) とは、ある一つの数同士を繰り返し掛け合わせるという操作のこと、あるいはそれによって得られる数のことである。

べき乗
=begin
べき乗
=end

def exponentiation(x, n)
  ans = 1
  n.times do
    ans =x * ans
  end
  return ans
end

for n in 0..5
  puts "#{exponentiation(2, n)}"
end


3:フィボナッチ(Fibonacci)数列

初項と第2項を1とし、第3項以後次々に前2項の和をとって得られる数列。

フィボナッチ数列
=begin
フィボナッチ(Fibonacci)数列
=end

def fibonacci(n)
  fn_1 = 1
  fn_2 = 1
  ans = 0
  return 1 if n <= 2
  (n - 2).times do
    ans = fn_1 + fn_2
    fn_2 = fn_1
    fn_1 = ans
  end
  return ans
end

puts fibonacci(100) #=> 354224848179261915075


4:テイラー展開

テイラー展開は式を簡単にするためにある

自然数を展開すると、
自然数の展開
となる、このときの第n項Enは、
テイラー展開の漸化式
=begin
テイラー展開
=end

def taylor_expansion(x, n)
  # n:自然数の第n項En
  # x:自然数e^xの係数x
  e_n = 1
  n.times do
    e_n = (x / n) * e_n
  end
  return e_n
end

# 自然数e^10の第5項E5
puts taylor_expansion(10, 5) 


Pascalの三角形

nCrを次のように並べたものをPascalの三角形といいます。
Pascalの三角形

このPascalの三角形をプログラムを使って書いてみます。中身は殆ど上記で使用した組み合わせのプログラムと一緒です。
=begin
Pascalの三角形
=end
def combi(n, r)
  p = 1
  for i in 1..r
    p = p * (n - i + 1) / i
  end
  return p
end

for n in 0..12
  for t in 0..((12 - n) * 3 - 1)
    print " "
  end
  for r in 0..n
    print "#{combi(n, r)}".rjust(3) + "   "
  end
  puts
end

このプログラムを実行すると、
                                      1   
                                   1     1   
                                1     2     1   
                             1     3     3     1   
                          1     4     6     4     1   
                       1     5    10   10     5     1   
                    1     6    15   20   15     6     1   
                 1     7    21   35   35   21     7     1   
              1     8    28   56   70   56   28     8     1   
           1     9    36   84  126 126   84   36     9     1   
        1    10   45  120 210 252 210 120   45    10     1   
     1    11   55   65  330 462 462 330 165   55   11     1   
  1    12   66  220 495 792 924 792 495 220   66   12     1   

という図が得られます。この図から、
Pascalの三角形から求まった公式
という公式が求まります。というよりこれが言いたいがための図なんですね、Pascalの三角形って。
これもまた、簡単にプログラムで表現出来そうな公式ですが、第四章に回します。いや、この本がそう書いてあるので。

C言語によるはじめてのアルゴリズム入門 改訂第3版C言語によるはじめてのアルゴリズム入門 改訂第3版
(2008/10/02)
河西 朝雄

商品詳細を見る

テーマ : プログラミング - ジャンル : コンピュータ

コメント
コメントの投稿
管理者にだけ表示を許可する

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。