スポンサーサイト

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

[Ruby][アルゴリズム入門]写像

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

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

写像とは

写像(しゃぞう、mapping, map)とは、二つの集合が与えられたときに、一方の集合の各元に対し、他方の集合のただひとつの元からなる集合を指定して結びつける対応のことである。

……わかりにくいですね。

ものすごい噛み砕いていうと、あるデータ範囲を別のデータ範囲に変換することを写像といいます。

例えば、成績が65~75点ならC評価、76~85点ならB評価、86~95ならA評価、それ以上ならS評価という具合に、点数というデータ範囲を評価というデータ範囲に変換してますね。これが写像です。
……自分で言ってて心がズキズキしてきた。成績に例えるんじゃなかった。

ヒストグラム(度数分布)

度数分布(どすうぶんぷ、Frequency Distribution)とは、統計において標本として得られたある変量の値のリストである。一般に量の大小の順で並べ、各数値が現われた個数を表示する表(度数分布表)で示される。

度数分布は先程の写像の概念と全く同じです。乱暴に言ってしまえば、ある値を一定の量で区切って、それぞれにランクをつければ度数分布になります。

ヒストグラム(度数分布図、柱状グラフ、Histogram)とは、縦軸に度数、横軸に階級をとった統計グラフの一種で、データの分布状況を視覚的に認識するために主に統計学や数学、画像処理等で用いられる。

ようするに度数分布でランク分けした数値がどれほどの量あるかを一目で見れるようにしたもの、ですね。
文章で説明するより、実際に動いているものを見た方がずっとわかりやすいのでさっさとコードを書くことにしましょう。

ヒストグラム(度数分布)の例題

例題:0~100点までの点数を10点幅で区切って(0~9、10~19、…、90~99、100の11ランク)、各ランクのヒストグラムを求める。

今回ヒストグラムを描画するツールとして、DXrubyというライブラリを使用します。使うのにDirectXがインストール差れてる必要があります。
このライブラリ、さくっと画像が書けてスクリーンショットもさっくり撮影できて便利です。まあ私が使い慣れてるってだけなんですけどね。
=begin
度数分布(ヒストグラム)
=end

require 'dxruby'

# 度数分布を行う
def frequency_distribution(result)
  # 度数分布保存用配列。0で初期化
  histo = Array.new(11, 0)
  result.each do |i|
    rank = i / 10 # 度数を計算
    histo[rank] += 1 if (0..10).include?(rank)
  end
  return histo
end

# 成績データ
result = [35, 25, 56, 78, 43, 66, 71, 73, 80, 90, 0, 73, 35, 65, 100, 78, 80, 85, 35, 50]
histo = frequency_distribution(result)

###########################################
# 度数分布の計算はここまで。
# 以下ヒストグラムを描画するためのDXRubyの記述
###########################################

# 棒グラフの棒
bar = Image.new(50, 50, [255, 204, 153, 51])

# 範囲を表示するためのフォント設定
font = Font.new(15)
rank_str = ["  0..9", "10..19", "20..29", "30..39", "40..49", "50..59", "60..69", "70..79", "80..89", "90..99", "  100"]

# 境界線
lines = Image.new(bar.width * 11 + 1, bar.height * 8 + 1)
12.times do |n|
  pos = n * bar.width
  lines.line(0, pos, lines.width, pos, [255, 255, 255, 255]) if n <= 8
  lines.line(pos, 0, pos, lines.width, [255, 255, 255, 255])
end

Window.loop do
  # グラフを描画
  histo.each_with_index do |elem, i|
    elem.times do |j|
      Window.draw( 45 + i * bar.width, 400 - j * bar.height, bar)
    end
  end

  # 文字を描画
  rank_str.each_with_index do |elem, i|
    Window.drawFont( 50 + i * bar.width, 450, elem, font)
  end

  8.times do |n|
    Window.drawFont(25, 70 + n * bar.width, (8 - n).to_s, font)
  end

  # 境界線設定
  Window.draw(45, 50, lines)

  # スクリーンショット機能
  if Input.keyPush?(K_F12) == true then
    if ! File.exist?("screenshot") then
      Dir.mkdir("screenshot")
    end
    Window.getScreenShot("screenshot/screenshot" + Time.now.strftime("%Y%m%d_%H%M%S") + ".jpg")
  end

  # エスケープキーで終了
  break if Input.keyPush?(K_ESCAPE)
end
このプログラムを実行して出てきたウインドウのスクリーンショットを取った画像が以下になります。
ヒストグラムの描画

あまりにも適当ですが、お分かりいただけるでしょうか。

暗号

暗号(あんごう、cryptography, cipher, code)あるいは暗号化(あんごうか、Encryption)とは、第三者に通信内容を知られないように行う特殊な通信(秘匿通信)方法のうち、通信文を見ても特別な知識なしでは読めないように変換する表記法(変換アルゴリズム)のことである。通信ではなく保管する文書等の内容を秘匿する方法としても用いることができる。

あるデータを、簡単に理解されないよう別のデータに置き換える暗号も写像の一種と言えます。
def cyptography(ango)
  table = ['Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P', 'A', 'S', 'D', 'F', 'G', 'H', 'J', 'K', 'L', 'Z', 'X', 'C', 'V', 'B', 'N', 'M', '?']
  ango.each_byte do |c|
    if 'A'.ord <= c && c <= 'Z'.ord
      index = c - 'A'.ord
    else
      index = table.size - 1
    end
    print table[index]
  end
end

ango = "KSOIDHEPZ"
cyptography(ango) #=>ALGORITHM


シーザーの暗号

def caesar(ango)
  leng = 'Z'.ord - 'A'.ord + 1
  ango.each_byte do |byte|
    reango = 'A'.ord + (byte - 'A'.ord - 1) % leng
    print "#{reango.chr}"
  end
end

ango = "ABCDEFG"
caesar(ango) #=>ZABCDEF


イクスクルーシブオア(排他的論理和)による暗号

def xor(ango)
  ango.each_byte do |byte|
    reango = byte ^ 0x07
    print "#{reango.chr}"
  end
end

ango = "ABCDEFG"
xor(ango) #=>FEDCBA@
スポンサーサイト

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

[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)
河西 朝雄

商品詳細を見る

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

[就活]面接レポ

今回の面接で聞かれたことをつらつらと。

所要時間:15分
面接官人数:2人
面談形式:個人面談

(1)当社を志望した理由
(2)当社に入社できたとして、5年後の自分はどうなっているか
(3)↑になるために、今から何を努力すべきか
(4)(年齢が高かったので)何があったのか
(5)資格は何かもっているか?
(6)ちょこっとだけ研究の事を
(7)(個の業種は)かなり厳しい仕事だが、出来ると思うか?その根拠は?
(8)何か質問は?

……もっとちゃんと対策ねっておくべきだったなぁ。

テーマ : 就活 - ジャンル : 就職・お仕事

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