スポンサーサイト

上記の広告は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@

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

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

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