コンピューターサイエンスに関して学習してみた(アルゴリズム編)

始めに

Udemyがセールをしていたので，最近興味があったコンピューターサイエンスの講義を購入してみました．
講義はかなりかみ砕かれている内容で僕でも理解できるくらいわかりやすかったです．
(データベースなどは元々知っている内容だったりはしたのですが)
講義はPythonをベースに進むのですが，せっかくなのでいくつかJuliaで書き直して記録しておきたいと思います．

以下が僕が受講した講義になります．
コンピュータサイエンス講座 -PythonとGoogle Colaboratoryで学ぶ計算機科学の基礎

ユークリッドの互助法

アルゴリズムの説明でユーグリッドの互助法が例に出されました．
ユーグリッドの互助法とは以下になります．

2 つの自然数の最大公約数を求める手法の一つである。
2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。
wikipedia より https://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95

上述した通り，講義ではPythonで書かれていたのですが自分なりにJuliaで書いたのが以下になります．

function euclideanAlgorithm(a, b)
    m = a
    n = b
    # 与えられた２つの整数の大小比較
    if a < b
        m = b
        n = a
    end
    
    while 1 == 1
        r = m%n
        if r != 0
            m = n
            n = r
            # 計算過程をprint
            println("m=$m, n= $n, r = $r")
        else
            print(string(a) * "と" * string(b) * "の最大公約数は" * string(n) * "である")
            break
        end
    end
end

２進数から10進数への変換

講義では当然，２進数・16進数に関しても触れられていました．
ここでは２進数から10進数への変換の関数記述したいと思います．
Pythonではデフォルトで変換の関数が用意されているみたいなので，Juliaにもあるのかもしれません．
(普通にありそうですね)

２進数から10進数への変換は与えられた２進数の各桁の値に2^{(桁数 – 1)}を掛け合わせて最後にそれらを合算するんですね．
具体的には，以下のイメージです．
(例)２進数，1101が与えられた場合．
１桁目：１ × 2⁰ (= 2^(1-1)) = 1
２桁目：０ × 2¹ (= 2^(2-1)) = 0
３桁目：１ × 2² (= 2^(3-1)) = 4
４桁目：１ × 2³ (= 2^(4-1)) = 8
従って，１ + ０ + ４ + ８ = 13 になります．

# 2進数から10進数への変換
function binary2decimal(b)
    ans = 0
    cnt = 1
    与えられた引数を１文字ループ
    for i in string(b)
        ans = ans + parse(Int, i) * 2^(length(string(b)) - cnt)
        cnt = cnt + 1
    end 
    println(string(b) * "は十進数で" * string(ans) * "です")
end

フィボナッチ数列

再帰の説明の際にフィボナッチ数列が例題に出されました．
再帰とは自分で自分で自分を呼び出すって感じでしょうか．僕はTwitterのBotなどを作成しているのですが，何らかの原因でTweetが失敗した際もう一度自分を呼び出しTweetさせるようにしています．
イメージは以下となります．

Tweet()

function Tweet()
    t = "Tweetしたい内容を取得"
    res = excute(t)
    if res.statuscode != 200
        # 自分で自分をもう一度呼び出す(ステータスコード200が返ってくるまで)
        Tweet()
    end
end

実際のフィボナッチ数列のコードは以下になります．
(フィボナッチ数列の説明は割愛します)

# フィボナッチ数列
# n：n番目
function fib(n)
    if n <= 1 
        return 0
    elseif n == 2
        return n = 1
    else
        return fib(n-1) + fib(n-2)
    end
end

最後に

せっかく受講したので，講義で扱われていた，ソート，探索，セル・オートマトン，ライフゲームなども記事にしたいと思います．
取り急ぎ形にしたかったので，間違いありましたら優しくご指摘いただけましたら幸いです．

Julia言語で奏でる詩