［Ruby/Python/Java/Swift/JS］アルゴリズムとは？ #Python

この記事を書く理由

アルゴリズムに関する知識を自分なりにまとめる（かなりざっくり）
忘れた時に確認する

アルゴリズム（algorithm）とは？

広義の定義

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

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

問題：玄米（新米）²を、おいしく炊きたい。

おいしい玄米の炊き方（=これが「アルゴリズム」）
　1. 玄米を洗ったあと、12時間〜24時間吸水させる　
　2. 玄米と同カップの水と塩・日本酒を入れる。
　3. 10分で沸騰するような火加減で加熱、沸騰したら弱火で15分加熱。
　4. 火を消し15分蒸らす。

▲ の炊き方を守れば、ガスでも電気コンロでもIHでも美味しく炊ける。
▲ そもそも、鍋で炊かなくても炊飯器で炊いてもOK

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

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

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

・当時ギリシャ政府の債務不履行に陥る危機感が世界中にあり、それが現実になると世界的な金融恐慌に陥る恐れだった
・とあるファンドマネージャーが使っていたアルゴリズムが４０億ドル分の株式先物を売却するスピードが早すぎ、他のアルゴリズムが呼応した
・複数のトレーダーが結託して、複数のアルゴリズムを使いマーケットを暴落させようとした

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

再帰

再帰を利用して、階乗を求めるアルゴリズムを書く（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）

「アルゴリズムの基本」 p15 ↩
自宅に炊飯器がないのと出来るだけモノを増やしたくないため、鍋で米を炊いている。 ↩
「アルゴリズムが世界を支配する」 pp.5-10 ↩

［Ruby/Python/Java/Swift/JS］アルゴリズムとは？