Edited at

[Ruby/Python/Java/Swift/JS]アルゴリズムとは?


この記事を書く理由


  1. アルゴリズムに関する知識を自分なりにまとめる(かなりざっくり)

  2. 忘れた時に確認する


アルゴリズム(algorithm)とは?


広義の定義


「仕事をやり遂げるための一連の手順」1



日常生活にも「アルゴリズム」がある。

問題: 玄米(新米)2を、おいしく炊きたい。

おいしい玄米の炊き方(=これが「アルゴリズム」

 1. 玄米を洗ったあと、12時間〜24時間吸水させる 

 2. 玄米と同カップの水と塩・日本酒を入れる。

 3. 10分で沸騰するような火加減で加熱、沸騰したら弱火で15分加熱。

 4. 火を消し15分蒸らす。

▲ の炊き方を守れば、ガスでも電気コンロでもIHでも美味しく炊ける。

▲ そもそも、鍋で炊かなくても炊飯器で炊いてもOK


「アルゴリズム」が、マーケットを動揺させた事例3

2010年5月6日 14時47分(アメリカ東部時間) ダウ平均が3分間の間に1000ドル下落(=フラッシュクラッシュ

この現象が発生した考えられる理由:詳細は未だ不明

・当時ギリシャ政府の債務不履行に陥る危機感が世界中にあり、それが現実になると世界的な金融恐慌に陥る恐れだった

・とあるファンドマネージャーが使っていたアルゴリズムが40億ドル分の株式先物を売却するスピードが早すぎ、他のアルゴリズムが呼応した

・複数のトレーダーが結託して、複数のアルゴリズムを使いマーケットを暴落させようとした


コンピュータの世界の「アルゴリズム」


再帰

再帰を利用して、階乗を求めるアルゴリズムを書く(Ruby/Python/Java/Swift)


factiorial.rb

def factorial(number)

if number == 0
1
else
number * factorial(number - 1)
end
end

(0..20).each do |i|
puts "#{i}! = #{factorial(i)}"
end



factiorial.py

def factorial(number):

if(number==0):
return 1
else:
return number * factorial(number-1)

for i in range(1,20+1):
print(str(i) + "! = " + str(factorial(i)))



Factorial.java

class Factorial{

public static int factorial(int number){
if (number == 0){
return 1;
} else {
return number * factorial(number - 1);
}
}

public static void main(String[] args){
for(int i=1; i<=20; i++){
System.out.println(i + "! = " + (factorial(i)));
}
}
}



factorial.swift

func factiorial(_ number:Int) -> Int{

if(number==0){
return 1
} else {
return number * factiorial(number-1)
}
}

for i in 0...20 {
print("\(i)! = \(factiorial(i))")
}



factorial.js

const factorial = (number)=>{

if(number===0){
return 1;
} else {
return number * sample(number-1);
}
}

for(let i=1; i<=20; i++){
console.log(`${i}! = ${factorial(i)}`);
}



Ruby/Python/Swift/JS出力結果

0! = 1

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000


Java出力結果

1! = 1

2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 1932053504
14! = 1278945280
15! = 2004310016
16! = 2004189184
17! = -288522240
18! = -898433024
19! = 109641728
20! = -2102132736


その他のアルゴリズム

線形探索

二分探索

ハッシュ探索


編集履歴

2018/11/03 投稿

2018/11/19 JSのコードを追加・タイトル変更

2018/12/01 線形探索のリンクを追加

2018/12/02 二分探索・ハッシュ探索のリンクを追加


参考資料

・クリストファー・スタイナー(訳:永峯涼)「アルゴリズムが世界を支配する」(KADOKAWA,2013)

・トーマス・H・コルメン(訳:長尾高弘)「アルゴリズムの基本」(日経BP社,2016)

・柴田望洋「新・明解Javaで学ぶアルゴリズムとデータ構造」(SBクリエイティブ,2017)





  1. 「アルゴリズムの基本」 p15 



  2. 自宅に炊飯器がないのと出来るだけモノを増やしたくないため、鍋で米を炊いている。 



  3. 「アルゴリズムが世界を支配する」 pp.5-10