More than 1 year has passed since last update.

「Pythonではじめるアルゴリズム入門」#01 - 初歩的なアルゴリズム（FizzBuzz、お釣り計算、フィボナッチ数列）

Last updated at 2023-02-22Posted at 2023-02-21

「Pythonではじめるアルゴリズム入門」の学習記録です。学習に使ったファイルやコードなどをアップしていきます。
機械学習やデータサイエンス、統計解析を学ぶにあたって中高生レベルの数学の復習、と実践的なアルゴリズムを学習したいと考えたので学習し始めました。

アルゴリズムとは

アルゴリズムとは、問題を解決するための手順や計算方法を指す言葉です。プログラミングの場合はアルゴリズムをプログラミング言語の文法に従って実装することを指します。
機械学習や最先端の技術を使わなくても、適切なアルゴリズムを使うことで処理時間・精度を大幅に改善できるケースがあります。プログラミング、数学を用いたアルゴリズムを学ぶ際は、コードを写経しノートに数式を書くことがおすすめです。そうすることでアルゴリズムの意味に対する理解が深まります。

Pythonではじめるアルゴリズム入門」で学習できること

基礎的なアルゴリズム（FizzBuzz, フィボナッチ数列）
計算コスト、計算時間について
探索アルゴリズム（木構造）
並べ替えアルゴリズム（ソート、全6種類）
実務で使えるアルゴリズム（最短経路問題、ベルマン・フォード法）

今回は基礎的なアルゴリズムについて学習しました。

FizzBuzz

倍数・商と余りの判定、素数やフィボナッチ数など、四則演算を使った基礎的なアルゴリズムです。
FizzBuzzアルゴリズムは、3の倍数に対してFizz、5の倍数に対してBuzz、15の倍数に対してFuzzBuzzと出力する
論理的に排他的となるものの優先度を高めに設定するのがアルゴリズムの基本です。

"""
倍数・商と余りの判定、素数やフィボナッチ数など、四則演算を使った基礎的なアルゴリズム
FizzBuzz
3の倍数に対してFizz、5の倍数に対してBuzz、15の倍数に対してFuzzBuzzと出力する
#論理的に排他的となるものの優先度を高めに設定する
"""

for i in range(1,16):
    #論理的に排他的となるものの優先度を高めに設定する
    if (i%3==0 and i%5==0):
        print(str(i) + ":FizzBuzz")
    elif (i%3==0):
        print(str(i) + ":Fizz")
    elif (i%5==0):
        print(str(i) + ":Buzz")
    else:
        print(i)

1
2
3:Fizz
4
5:Buzz
6:Fizz
7
8
9:Fizz
10:Buzz
11
12:Fizz
13
14
15:FizzBuzz

おつりの計算

おつりの金額が紙幣・硬貨に換算するとそれぞれ何枚になるかを計算します。
金額の高い通貨から商・余りを計算するアルゴリズムを1円になるまで繰り返すことで、おつりの生産ができます。
アルゴリズムを実装する際は、データ型が合っているか、おつり額がマイナスでないかというフェイルセーフ・前提条件のチェックもおこないます。

"""
おつりの計算
おつりの金額が紙幣・硬貨に換算するとそれぞれ何枚になるかを計算する
金額の高い通貨から商・余りを計算するアルゴリズムを1円になるまで繰り返す
アルゴリズムを実装する際は、データ型が合っているか、おつり額がマイナスでないかというフェイルセーフ・前提条件のチェックを行う。
"""
import sys

input_price = 10111
product_price = 120
change = input_price - product_price

#フェイルセーフ開始-------------------
if change < 0:
    print("おつり額が不足しています：")
    sys.exit()

#フェイルセーフ完了-------------------

coin = [5000,1000,500,100,50,10,5,1]

for i in coin:
    #金額の高い通貨から商(枚数)・余り(次の通貨への繰り越し)を
    #計算するアルゴリズムを1円になるまで繰り返す
    r = change // i
    change %= i
    print("通貨額:" + str(i) + " | 枚数:" + str(r) + " | 残り金額:" + str(change) )

通貨額:5000 | 枚数:1 | 残り金額:4991
通貨額:1000 | 枚数:4 | 残り金額:991
通貨額:500 | 枚数:1 | 残り金額:491
通貨額:100 | 枚数:4 | 残り金額:91
通貨額:50 | 枚数:1 | 残り金額:41
通貨額:10 | 枚数:4 | 残り金額:1
通貨額:5 | 枚数:0 | 残り金額:1
通貨額:1 | 枚数:1 | 残り金額:0

10進数→2進数への変換

0進数→2進数への変換を行うには、元の数を2で割り商と余りを求める→商をさらに2で割り、余りの数を桁に足すというルーチンを繰り返します。また、割る数を変えるだけで基数から10進数への変換をするアルゴリズム全般が実装できます。

"""
10進数→2進数への変換をするアルゴリズム
10進数→2進数への変換を行うには、元の数を2で割り商と余りを求める→商をさらに2で割り、余りの数を桁に足すというルーチンを繰り返す
"""
n = 1000
result=""

while n > 0:
    result = str(n%2) + result
    n //=2

print(result)

"""
割る数を変えるだけで、基数から10進数への変換をするアルゴリズム全般が実装できる
"""
n = 1000

def convert(n, base):
    result=""
    while n > 0:
        result = str(n%base) + result
        n //=base

    return result

print(convert(n, 8))

1111101000
1750

2進数→10進数への変換

2進数→10進数への変換を行うには対応する桁の累乗部分の変換を繰り返し、その値の総和を求めます。

"""
2進数→10進数への変換をするアルゴリズム
2進数→10進数への変換を行うには対応する桁の累乗部分の変換を繰り返し、その値の総和を求める
"""
n = "101010111"
result=0

for i in range(len(n)):
    result += int(n[i])* (2**(len(n)-i-1))

整数が素数かを判定する

整数が素数化は、その整数の平方根以下の整数が約数となるかを調べます。
なぜ平方根以下かは背理法で証明できます。以下の証明を参照してください。
https://math-jp.net/2017/03/10/how-to-find-a-prime-number/

"""
整数が素数かを判定するアルゴリズム
整数が素数化は、その整数の平方根以下の整数が約数となるかを調べる。
なぜ平方根以下かは帰無法で証明できるので、様参照。
"""
import math

def isPrime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

for i in range(100):
    if isPrime(i):
        print(i, end=" | ")

2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 | 37 | 41 | 43 | 47 | 53 | 59 | 61 | 67 | 71 | 73 | 79 | 83 | 89 | 97 |

整数が素数かを判定:エラトステネスの篩

素数を判定する際、判定済みの数の倍数となる数を除外することで素数計算の効率を高めます。

"""
整数が素数かを判定するアルゴリズム:エラトステネスの篩
素数を判定する際、判定済みの数の倍数となる数を除外することで素数計算の効率を高める
"""
import math

def getPrime(n):
    if n <= 1:
        return []
    prime = [2]
    limit = int(math.sqrt(n))

    data = [i +1 for i in range(2,n,2)]
    while limit > data[0]:
        prime.append(data[0])
        #割り切れなかった値のみ追加
        data = [j for j in data if j % data[0] != 0]
    return prime + data

print(getPrime(100))

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

SymPyを使うと、素数を使ったアルゴリズムが更に簡潔に書ける

pip install sympy
from sympy import sieve

primes = [i for i in sieve.primerange(0, 100)]
print(primes)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

フィボナッチ数列を求めるアルゴリズム

"""
フィボナッチ数列を求めるアルゴリズム
再帰的に漸化式を計算し、フィボナッチ数列のような値を求める
"""
def fibonacci(n):
    if (n==1)or(n==2):
        return 1
    return fibonacci(n-2) + fibonacci(n-1)

for i in range(1, 30):
    print(str(fibonacci(i)) + " | ")

フィボナッチ数列を求めるアルゴリズムを改良

すでに算出した値をコレクションに加え、無駄な計算を削減することができます。この手法は「メモ化」と呼ばれます。

"""
フィボナッチ数列を求めるアルゴリズムを改良：
すでに算出した値をコレクションに加え、無駄な計算を削減する。この手法は「メモ化」と呼ばれる
"""
#数列のメモ化には辞書型を用いる
fibonacci_dict = {1:1, 2:1}

def fibonacci(n):
    #フィボナッチ数列の辞書にその値があれば、その値を返す
    #新しくフィボナッチ数を求めたら、その値を辞書に追加しておく
    if n in fibonacci_dict:
        return fibonacci_dict[n]

    fibonacci_dict[n] = fibonacci(n-2) + fibonacci(n-1)
    return fibonacci_dict[n]

for i in range(1, 30):
    print(str(fibonacci(i)) + " | ")

次は計算量について学習します。頑張りますね。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up