スポンサーサイト

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

ドロップボックス、使ってみませんか? ver.2

私はDropboxというオンラインストレージ(インターネット上のHDDのようなもの)を利用しているのですが、そのDropboxが今回、ユーザーを紹介したら保存容量増やしてやるぜへっへっへと悪魔のささやきをしてきたので、即答でハンコを押すことにしました。

詳しくはこちら

今ドロップボックスと契約すると、2GBの容量+250MBの容量がくっついてくるそうです。
深夜の通販番組もびっくりのお得商品ですよ、奥様。しかも無料。

詳しい使い方は以下を見れば大体わかります。
Dropbox徹底解剖 - 一度使ったら手放せなくなる! オンラインストレージサービスの本命 | Web担当者Forum

まだ使ってない人は、一度試してみることをおすすめしますよ!2台以上PCを持っている人は、作業効率が倍増すること請け合いです。MacとWindows、LinuxとWindows間でのファイルのやり取りも信じられないくらい簡単になるので、ぜひ一度お試しください。
スポンサーサイト

テーマ : Webサービス - ジャンル : コンピュータ

[Ruby]数字の桁を漢字で表示するモジュールを作ったよ

最近アルゴリズムの本を勉強しつつブログに書いたりしているのですが、そのとき出力した結果がものすごい桁数の数字であることがあります。

まあ、こうやってブログに貼り付ける分にはそのままでもいいのですが、人に口頭で数字を伝えるときにいちいち桁を数えて読み上げるのは非常にめんどくさい。

そこで、FixnumとBignumを拡張するモジュール組んで読み込ませることで、整数を読み上げやすい形式に変換するプログラムを組んでみました。俺得。

# encoding: cp932
module Toj
  def to_j
    number = self
    digit = ["万", "億", "兆", "京", "垓", "禾予", "穣", "溝", "澗", "正",
             "載", "極", "恒河沙", "阿僧祇", "那由他", "不可思議", "無量大数"]
    ketasu = digit.size
    shuturyoku = Array.new
    ketasu.times do |i|
      numbers_stack = Array.new
      4.times do |j|
        stack = number - number / 10 * 10
        numbers_stack.unshift("#{stack}")
        number = number / 10
      end
      shuturyoku.unshift(numbers_stack.join.to_i.to_s)
      if number > 0
        shuturyoku.unshift(digit[i])
      else
        break
      end
    end
    puts shuturyoku.join
  end
end

class Fixnum
  include Toj
end

class Bignum
  include Toj
end

number = 95849480083929012345
number.to_j #=>9584京9480兆839億2901万2345

(自分だけかもしれないけど)便利!

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

[ゲーム]ネットで手に入るゲーム製作(AI)に関する資料

ゲームAIについて


マッチ箱の脳
ゼビウスセミナー
y_miyakeのゲームAI千夜一夜
[GDC 2009#02]「ゲームAI」とは何か? AIプログラマーのギルドがセミナーを開催
ゲームAI連続セミナー「ゲームAIを読み解く」全講演資料(2009年11月改訂版)

Twitter上でのAI議論


Togetter - まとめ「ゲームAIラウンドテーブル・オン・ツイッター(2010年4月期)」
Togetter - まとめ「ゲームAIラウンドテーブル・オン・ツイッター第2回-前半-(2010年5月期)」
Togetter - まとめ「ゲームAIラウンドテーブル・オン・ツイッター第2回-後半-(2010年5月期)」

オセロ


リバーシプログラムの作り方 サンプル
-鶯教-コンピュータ・リバーシ講座
オセロプログラムの作り方

アルゴリズム


A*探索アルゴリズムにチャレンジ - mirichiの日記
経路探索アルゴリズムA* - gan2 の Ruby 勉強日記
経路探索アルゴリズムA*をRubyで実装してみた - gan2 の Ruby 勉強日記
Rubyで最短経路を探索しよう! - hp12c
e
Rubyでローグライクダンジョン生成 - アーユルベーダはインドのエステみたいなもん
【DiGRA公開講座】モンテカルロ木探索とは何か?|遠藤雅伸公式blog「ゲームの神様」
ダイクストラ法(最短経路問題)
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
2010-03-13 - らいおんの隠れ家:遺伝的アルゴリズム
脳とベイジアンネット

学会など


日本デジタルゲーム学会
国際ゲーム開発者協会日本(IGDA日本)
Serious Games Japan
CEDEC 2010 | CESA Developers Conference


用語集


ゲーム批評用語小辞典

ゲームデザイン


ゲームデザインの理論
げーむ ぷれいあびりてぃー(↑の人が書いてるブログ)
Well Played 1.0
ゲーム作者の集い[ゲームヘル2000]レベルデザイン
なぜ、人はゲームにハマルのか?
第一回
第二回
第三回


大学とゲーム


ゲームとアカデミーの素敵なカンケイ
第一回
第二回(ゲームAIについての記事です.参考文献表あり)
第三回


フリーで遊べる著作権的に完全アウトなゲームたち


パックマン
ゼビウス
ギャラガ
マリオ


ゲームプログラミングについて


言語別ゲームプログラミング制作講座一覧
ジャンル別ゲームの作り方とアルゴリズムまとめ
TNKソフトウェア - クラスまみれのゲームプログラミング入門
リバーシプログラムの作り方 サンプル
O-Planning ゲーム制作のちょっといい話: ゲームエンジン・目次
O-Planning ゲーム制作のちょっといい話: SIG-Glocalizationの記事まとめ


ゲームプランナー編


ゲーム企画書の書き方:新卒篇
企画書の書き方

ゲーム研究


ゲーム研究の方法と意義についての序説(伊藤憲二)
Spore におけるゲームAI技術とプロシージャル
同人ゲームの全体像(改訂版)
ゲーム情報学から見たコンピュータ囲碁
モンテカルロ木探索 理論編
モンテカルロ木探索 実践編
これからのゲームAIの作り方
ゲーム作りの文化のために―独立系デベロップメントシーンの比較試論―
サッカーシミュレーションのAI、サッカーゲームのAI1
サッカーシミュレーションのAI、サッカーゲームのAI2
ゲーム産業における職業とキャリア ヒット数
70年代・80年代のゲーム開発環境について
80年代・90年代のゲーム開発環境について
2000年代・現在の環境とHSP、プログラミング教育について
テキスト解析による日米ゲームレビューの比較

番外編


http://togetter.com/li/831

最終更新日 2009/12/04

テーマ : ゲーム - ジャンル : ゲーム

[Ruby][アルゴリズム入門]補間

第二章「数値計算」 目次

総合目次

2-1 乱数
2-2 数値積分
2-3 テイラー展開
2-4 非線形方程式の解法
2-5 補間
2-6 多桁計算
2-7 長いπ
2-8 連立方程式の解法
2-9 線形計画法
2-10 最小2乗法

ラグランジュ補間

何組かのx, yデータが与えられているとき、これらの点を通る補間多項式をラグランジュ補間により求め、データ点以外の点を求める。

(x0, y0), (x1, y1), …, (xn-1, yn-1)というn個の点が与えられたとき、これらの点を全て通る関数f(x)は次のように求められる。
ラグランジュ補間のf(x)を求める式
def lagrange(x, y, n, t)
  s = 0.0
  n.times do |i|
    p = y[i]
    n.times do |j|
      p = p * (t - x[j]) / (x[i] - x[j]) unless i == j
    end
    s = s + p
  end
  return s
end

x = [0.0, 1.0, 3.0, 6.0, 7.0]
y = [0.8, 3.1, 4.5, 3.9, 2.8]

puts "      x       y"
(0.0).step(7.0, 0.5) do |t|
  printf "%7.2f%7.2f\n"%[t, lagrange(x, y, 5, t)]
end


ニュートン補間

何組かのx, yデータが与えられているとき、これらの点を通る補間多項式をニュートン補間により求め、データ点以外の点を求める。

ニュートンの補間公式
fj(x)を,fj(xi)=yi,i=0,・・・,j
を満たす高々j次の多項式とすると,
fj+1(xi)=yi,i=0,・・・,j,j+1
を満たす高々j+1次の多項式fj+1(xi)は適当な定数cj+1に対して次の式で与えられる。

fj+1(x)=fj(x)+cj+1(x-x0)(x-x1)・・・(x-xj)

ニュートンの補間公式
def newton(x, y, n, t)
  flag = true
  a = Array.new(100) # 係数配列
  w = Array.new(100) # 作業用
  if flag
    n.times do |i|
      w[i] = y[i]
      (i - 1).downto(0) do |j|
        w[j] = (w[j + 1] - w[j]) / (x[i] - x[j])
      end
      a[i] = w[0]
    end
    flag = false
  end
  s = a[n - 1]
  (n - 2).downto(0) do |i|
    s = s * (t - x[i]) + a[i]
  end
  return s
end

x = [0.0, 1.0, 3.0, 6.0, 7.0]
y = [0.8, 3.1, 4.5, 3.9, 2.8]

puts "      x       y"
(0.0).step(7.0, 0.5) do |t|
  printf "%7.2f%7.2f\n"%[t, newton(x, y, 5, t)]
end

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

[Ruby][アルゴリズム入門]非線形方程式の解法

第二章「数値計算」 目次

総合目次

2-1 乱数
2-2 数値積分
2-3 テイラー展開
2-4 非線形方程式の解法
2-5 補間
2-6 多桁計算
2-7 長いπ
2-8 連立方程式の解法
2-9 線形計画法
2-10 最小2乗法

2分法

方程式f(x)=0の根を二分法により求める。

1次方程式(グラフ上で直線)以外の方程式を非線形方程式と呼ぶ。このような方程式の根(f(x)^2が最小値(=0)になるxの値)を求める方法に二分法がある。
1:根の左右にある2点a,bをlowとhighの初期値とする。
2:lowとhighの中間点xをx=(low + high) / 2で求める。
3:f(x) > 0なら根はxより左にあるからhigh = xとし、上限を半分に狭める。f(x) < 0なら根はxより右にあるからlow = xとし、下限を半分に狭める。
4:f(x)が0か|high - low| / |low| < EPSになったときのxの値を求める根とし、そうでないなら2以後を繰り返す。EPSは収束判定値で、適当な精度を選ぶ。
# encoding: cp932
def f(x)
  return x * x * x - x + 1
end

EPS = 1e-08  # 打ち切り誤差
LIMIT = 50   # 打ち切り回数

low = -2.0
high = 2.0

1.upto(LIMIT) do |k|
  x = (low + high) / 2
  if f(x) > 0
    high = x
  else
    low = x
  end

  if f(x) == 0 or (high - low).abs < low.abs * EPS
    puts "x = #{x}"
    break
  end
  if k == LIMIT
    puts "この試行回数、または誤差設定では収束しない"
  end
end


ニュートン法

方程式f(x)=0の根をニュートン法により求める。

1:根の近くの適当な値x0を初期値とする。
2:y = f(x)のx = x0における接戦を引き、x軸と交わったところをx1とし、以下同様の手順でx2, x3, …, xn-1, xnと求めて行く。
3:ニュートン法の収束判定になったときのxnの値を求める根とし、そうでないなら2以降を繰り返す。EPSは収束判定値で、適当な精度を選ぶ。

xnは、
ニュートン法のxnを求める式
と前の値xn-1を用いて求めることができる。ニュートン法の方が2分法より収束が早い。
# encoding: cp932
def f(x)
  return x * x * x - x + 1
end

def g(x)
  return 3 * x * x - 1
end

EPS = 1e-08  # 打ち切り誤差
LIMIT = 50   # 打ち切り回数

x = -2.0

1.upto(LIMIT) do |k|
  dx = x
  x = x - f(x) / g(x)
  if (x - dx).abs < dx.abs * EPS
    puts "x = #{x}"
    break
  end
  if k == LIMIT
    puts "この試行回数、または誤差設定では収束しない"
  end
end

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

[Ruby][アルゴリズム入門]テイラー展開

第二章「数値計算」 目次

総合目次

2-1 乱数
2-2 数値積分
2-3 テイラー展開
2-4 非線形方程式の解法
2-5 補間
2-6 多桁計算
2-7 長いπ
2-8 連立方程式の解法
2-9 線形計画法
2-10 最小2乗法

e^x

e^xをテイラー展開を用いて計算する。

# encoding: cp932
def myexp(x)
  eps = 1e-08;
  s = 1.0
  e = 1.0
  d = 1.0
  1.upto(200) do |i|
    d = s
    e = e * x / i
    s += e
    return s if (s - d).abs < eps * d.abs
  end
  return 0.0
end

puts "    x       myexp(x)        exp(x)"
0.step(40, 10) do |x|
  printf "%5.1f%14.6g%14.6g\n"%[x, myexp(x), Math.exp(x)]
end


負の値版e^x

e^xのxが負の場合にも対応できるようにする。

# encoding: cp932
def myexp(x)
  eps = 1e-08;
  s = 1.0
  e = 1.0
  d = 1.0
  a = x.abs # xの絶対値を取り、計算にはこれを使う
  1.upto(200) do |i|
    d = s
    e = e * a / i
    s += e
    if (s - d).abs < eps * d.abs
      # 元のxの値が0以上ならそのまま、0以下なら1/sを返す。
      if x > 0
        return s
      else
        return 1.0 / s
      end
    end
  end
  return 0.0
end

puts "    x       myexp(x)        exp(x)"
-40.step(40, 10) do |x|
  printf "%5.1f%14.6g%14.6g\n"%[x, myexp(x), Math.exp(x)]
end


cos x

cos xをテイラー展開により求める

# encoding: cp932
def mycos(x)
  eps = 1e-08
  s = e = d = 1.0
  # xの値を0~2πに収める
  x = x % (2 * 3.14159265358979)
  k = 1
  1.step(200, 2) do |k|
    d = s
    e = -e * x * x / (k * (k + 1))
    s += e
    return s if (s - d).abs < eps * d.abs
  end
  return 9999.0
end

rd = 3.14159 / 180
puts "    x       mycos(x)        cos(x)"
x = 0
0.step(180, 10) do |x|
  printf "%5.1f%14.6g%14.6g\n"%[x, mycos(x * rd), Math.cos(x * rd)]
  x += 10
end

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

[Ruby][アルゴリズム入門]数値積分

第二章「数値計算」 目次

総合目次

2-1 乱数
2-2 数値積分
2-3 テイラー展開
2-4 非線形方程式の解法
2-5 補間
2-6 多桁計算
2-7 長いπ
2-8 連立方程式の解法
2-9 線形計画法
2-10 最小2乗法

台形則による定積分

関数f(x)の定積分∫f(x)dxを台形則により求める。

# encoding: cp932

# 被積分関数
def func (x)
  return Math.sqrt(4- x * x)
end

print "積分区間 A?"
a = gets.chomp.to_i
print "積分区間 B?"
b = gets.chomp.to_i

N = 50.0
H = (b - a) / N
x = a
s = 0
1.upto(N - 1) do |i|
  x += H
  s += func(x)
end

sum = H * ((func(a) + func(b)) / 2 + s)
puts "  /#{b}"
puts "  |  sqrt(4-x^2) = #{sum}"
puts "  /#{a}"


シンプソン則による定積分

関数f(x)の定積分∫f(x)dxをシンプソン則により求める。

# encoding: cp932

# 被積分関数
def func (x)
  return Math.sqrt(4- x * x)
end

print "積分区間 A?"
a = gets.chomp.to_i
print "積分区間 B?"
b = gets.chomp.to_i

N = 50.0
H = (b - a) /(2 * N)
x = a
o = 0
e = 0
1.upto((N - 1) * 2) do |i|
  x += H
  if i % 2 == 0
    o += func(x)
  else
    e += func(x)
  end
end

sum = H * (func(a) + func(b) + 4 *(o + func(b - H)) + 2 * e) / 3
puts "  /#{b}"
puts "  |  sqrt(4-x^2) = #{sum}"
puts "  /#{a}"


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

[Ruby][アルゴリズム入門]乱数

第二章「数値計算」 目次

総合目次

2-1 乱数
2-2 数値積分
2-3 テイラー展開
2-4 非線形方程式の解法
2-5 補間
2-6 多桁計算
2-7 長いπ
2-8 連立方程式の解法
2-9 線形計画法
2-10 最小2乗法

一様乱数(線形合同法)

線形合同法を用いて、一様乱数を発生させる。

線形合同法は、適当なX0から初めて、
Xn=(Ax_(n-1) + C) % M
という式を使って、次々に0~Mの範囲の値を発生させる。

今回、A=109, C=1021, M=32768, X0=13を用いた。
$rndnum = 13 # X0の値

def irand
  $rndnum = ($rndnum * 109 + 1021) % 32768
  return $rndnum
end

100.times do |i|
  puts irand
end


一様性の検定

上記で作った乱数が、どのくらい均一にばらまかれているかをX^2(カイ2乗)検定の手法で計算する。

乱数が1~Mの範囲で発生するとき、iという値の発生回数をfi、iという値の発生期待値をFiとすると、
一様性の検定式
という値を計算する。このX^2の値が小さいほど均一にばらまかれていることを示す。
N = 1000
M = 10
F = N / M
SCALE = 40.0 / F

$rndnum = 13

def irnd
  $rndnum = ($rndnum * 109 + 1021) % 32768
  return $rndnum
end

def rnd
  return irnd / 32767.1
end

e = 0.0
hist = Array.new(M + 1, 0)
N.times do
  rank = (M * rnd).to_i + 1
  hist[rank] += 1
end

1.upto(M) do |i|
  printf "%3d:%3d"%[i, hist[i]]
  ((hist[i] * SCALE).to_i).times do |j|
    print "*"
  end
  puts

  e += (hist[i] - F) * (hist[i] - F) / F.to_f
end

puts " X2 = #{e}"


正規乱数(ボックス・ミュラー法)

正規乱数をボックス・ミュラー法により発生する。

def brnd (sig, m, rn)
  r1 = rand
  r2 = rand
  rn.x = sig * Math.sqrt(-2 * Math.log(r1)) * Math.cos(2 * 3.14159 * r2) + m
  rn.y = sig * Math.sqrt(-2 * Math.log(r1)) * Math.sin(2 * 3.14159 * r2) + m
end

st = Struct.new(:x, :y)
rn = st.new(0, 0)
hist = Array.new(100, 0)
1000.times do |i|
  brnd(2.5, 10.0, rn)
  hist[rn.x.to_i] += 1
  hist[rn.y.to_i] += 1
end

0.upto(20) do |i|
  printf "%3d : I "%[i]
  1.upto(hist[i] / 10) do |j|
    print "*"
  end
  puts
end

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

[Ruby]アルゴリズム入門をRubyで書いてみる・目次

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

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

第二章「数値計算」 目次

2-1 乱数
2-2 数値積分
2-3 テイラー展開
2-4 非線形方程式の解法
2-5 補間
2-6 多桁計算
2-7 長いπ
2-8 連立方程式の解法
2-9 線形計画法
2-10 最小2乗法

参考書籍

参考にした本はこちら。
C言語によるはじめてのアルゴリズム入門C言語によるはじめてのアルゴリズム入門
(1992/05)
河西 朝雄

商品詳細を見る

この本は三版まで出ています。今回参考にしたのは初版の方なので、目次や内容が違う可能性があります。
C言語によるはじめてのアルゴリズム入門 改訂第3版C言語によるはじめてのアルゴリズム入門 改訂第3版
(2008/10/02)
河西 朝雄

商品詳細を見る

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

[Ruby][アルゴリズム入門]エラトステネスのふるい

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

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

素数の判定

nが素数か否か判定する。

ルートn以上の数字は調べる必要はない。
# encoding: cp932

while (print "data? "; n = gets.chomp; n != "")
  prime = true
  if (n = n.to_i) >= 2
    limit = Math.sqrt(n).to_i
    limit.downto(2) do |i|
      if (n % i) == 0
        prime = false
        break
      end
      prime = true
    end
    if prime
      puts "素数"
    else
      puts "素数じゃない"
    end
  end
end


2~Nの全ての素数

2~Nまでの整数の中から全ての整数を求める。
# encoding: cp932

NUM = 1000
pri = Array.new(NUM / 2 + 1)
m = 0

2.upto(NUM) do |n|
  prime = true
  if n >= 2
    limit = Math.sqrt(n).to_i
    limit.downto(2) do |i|
      if (n % i) == 0
        prime = false
        break
      end
    end
    if prime
      pri[m] = n
      m += 1
    end
  end
end

m.times do |i|
  puts pri[i]
end


エラトステネスのふるい

上記素数の判定アルゴリズムでは、繰り返し回数がn√n/2 (平均値)となる。効率的に素数を求める方法として「エラトステネスのふるい」がある。この方法を用いて2~Nの中から素数を全て求める。
1:2~Nの数をすべて「ふるい」に入れる
2:「ふるい」の中で最小値を素数とする。(この場合2)
3:今求めた素数の倍数をすべて「ふるい」から外す。
4:2~3をnまで繰り返し「ふるい」に残った数が素数である。
# encoding: cp932

NUM = 1000
pri = Array.new(NUM + 1)
2.upto(NUM){|i| pri[i] = 1 }

limit = Math.sqrt(NUM).to_i

2.upto(limit) do |i|
  if pri[i] == 1
    2.upto(NUM) do |j|
      pri[j] = 0 if j % i == 0
    end
  end
end

2.upto(NUM) do |i|
  puts i if pri[i] == 1
end


素因数分解

nを素因数分解する。

1:まず、nを2で割り切れなくなるまで繰り返し割っていく。その際、割り切れなくなる度に2を表示する。
2:悪数を3として同じことを繰り返し、以降4,5,6,……と続けて行く。実際は素数について調べればいいのだが、素数表がないため手当たり次第に調べている。しかし、素数以外の物で割る場合は、それ以前にその数を素因数分解した時の素数ですでに割られているので、割り切れることはない。
3:割る数をαとしたとき、√n>=α(n>=α×α)の間が2を繰り返す条件である。nの値も割られる度に小さくなっている。
# encoding: cp932

while (print "data? "; n = gets.chomp; n != "")
  a = 2
  n = n.to_i
  while n >= (a * a)
    if n % a == 0
      print "#{a}*"
      n /= a
    else
      a += 1
    end
  end
  puts n
end

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

[Ruby][アルゴリズム入門]ユークリッドの互除法

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

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

ユークリッドの互除法(その1)

2つの整数m、nの最大公約数をユークリッド(Euclid)の互除法を用いて求める。

2つ以上の正の整数に共通な約数(公約数)のうち最大のものを最大公約数といいます. 例 12 と 18 の公約数は,1,2,3,6 で, 6 が最大公約数

最大公約数と最小公倍数
# encoding: cp932

puts "1つ目の整数を入力してください"
m = gets.chomp.to_i
puts "2つ目の整数を入力してください"
n = gets.chomp.to_i

while m != n
  if m > n
    m = m - n
  else
    n = n - m
  end
end

puts "最大公約数=#{m}"


ユークリッドの互除法(その2)

mとnの差が大きいときは減算(m-n)の代わりに剰余(m%n)を用いた方が効率がよい。この方法でmとnの最大公約数を求める。

1:mをnで割った余りをkとする。
2:mにnを、nにkを入れる。
3:kが0でなければ1に戻る。
4:mが求める最大公約数である。
# encoding: cp932

print "一つ目の整数を入力してください:"
m = gets.chomp.to_i
print "二つ目の整数を入力してください"
n = gets.chomp.to_i

begin
  k = m % n
  m = n
  n = k
end while k != 0

print "最大公約数=#{m}"

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

[Ruby][アルゴリズム入門]モンテカルロ法

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

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

パイを求める

モンテカルロ法を用いて、π(パイ)の値を求める。

# encoding: cp932
NUM = 1000

circle_in = 0
NUM.times do |i|
  x = rand
  y = rand
  circle_in += 1 if (x * x + y * y <= 1)
end

pai = Float(4) * circle_in / NUM
puts "πの値=#{pai}" #=>3.175

乱数の回数を増やせば3.14に近づいていく。

楕円の面積を求める

# encoding: cp932

NUM = 10000

circle_in = 0

NUM.times do |i|
  x = 2 * rand
  y = rand
  circle_in += 1 if (x * x / 4 + y) <= 1
end

s = 4.0 * (2.0 * circle_in / NUM)
puts "楕円の面積=#{s}"

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

[Ruby][アルゴリズム入門]ランダムな順列

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

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

ランダムな順列

1~Nの値を1回使って出来るランダムな順列を作る。

トランプをシャッフルしたりするのに便利そう。
# encoding: cp932
N = 20

# 1~引数nの乱数を返す
def irand(n)
  return (rand(n) + 1)
end

a = Array.new(N + 1, 0)

a[1] = irand(N)
2..N.times do |i|
  begin
    a[i] = irand(N)
    flag = false
    for j in 1..(i - 1)
      if (a[i] == a[j])
        flag = true
        break
      end
    end
  end while flag
end

1..N.times do |i|
  print "#{a[i]} "
end


上記の改良

上記のアルゴリズムを改良した効率のよいアルゴリズムを考える。

# encoding: cp932
N = 20

# 1~引数nの乱数を返す
def irand(n)
  return (rand(n) + 1)
end

a = Array.new(N + 1){|i| i}

N.downto(2) do |i|
  j = irand(i - 1)
  a[j], a[i] = a[i], a[j]
end

a.each_with_index do |n, i|
  next if i == 0
  print "#{n} "
end

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

[Ruby][アルゴリズム入門]順位付け

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

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

単純な順位付け

テストの点数のデータがあったとき、その特典の順位を求める。

# coding: cp932
score = [56, 25, 67, 88, 100, 61, 55, 67, 76, 56]
juni = Array.new(score.size, 0)

score.each_with_index do |num, i|
  juni[i] = 1
  score.each_with_index do |num2, j|
    if num2 > num
      juni[i] += 1
    end
  end
end

puts "   得点  順位"
score.each_index do |i|
  printf "%6d%6d\n"%[score[i], juni[i]]
end


上記の改良

上記の順位を求めるアルゴリズムではデータがn個の場合、繰り返し回数はn^2となるため、データ数が増えると処理に時間がかかってしまう。そこで、繰り返し回数を減らすようにした順位付けアルゴリズムを考える。

# coding: cp932
score = [56, 25, 67, 88, 100, 61, 55, 67, 76, 56]
juni = Array.new(102, 0)

10.times do |i|
  juni[score[i]] += 1
end

juni[101] = 1
100.downto(0) do |i|
  juni[i] = juni[i] + juni[i + 1]
end

puts "   得点  順位"
score.each_index do |i|
  printf "%6d%6d\n"%[score[i], juni[score[i]+1]]
end


負のデータ版

ゴルフ(Golf)のscoreのように小さい値の方が順位が高い場合の順位付けについて考える。

# encoding: cp932
NUM = 10
MAX = 36
MIN = -20
BIAS = 1 - (MIN) # 最小値を配列要素の1に対応させる

score = [-3, 2, 3, -1, -2, -6, 2, -1, 1, 5]
juni = Array.new(MAX + BIAS + 1, 0)

score.each do |a|
  juni[a + BIAS] += 1
end

juni[0] = 1
((MIN + BIAS) + (MAX + BIAS)).times do |i|
  juni[i] = juni[i] + juni[i - 1]
end

puts " 得点 順位"
NUM.times do |i|
  printf "%6d%6d\n"%[score[i], juni[score[i] + BIAS - 1]]
end

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

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