Java
Ruby
Python
JavaScript
Swift

[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のコードを追加・タイトル変更

参考資料

・クリストファー・スタイナー(訳:永峯涼)「アルゴリズムが世界を支配する」(KADOKAWA,2013)
・トーマス・H・コルメン(訳:長尾高弘)「アルゴリズムの基本」(日経BP社,2016)
・柴田望洋「新・明解Javaで学ぶアルゴリズムとデータ構造」(SBクリエイティブ,2017)


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

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

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