乙Py先生のプログラミング教室
初学者のためのプログラミング学習サイト

Python

プログラミング未経験の方のための
プログラミング学習講座を作成しました

その名も
「1時間で学べるPythonプログラミング」


講義動画はこちら




この講座は初学者の方が
短時間でPython言語を学ぶことのできる
プログラミング学習用の講座です

プログラミングが分からないない方は
Python言語を通じて
プログラミングの基礎を学習できます

講座は動画に加えてGoogle Colabを用いて
手元でコードを動かすことのできます
コードがどう動くのかを確認をしながら
進めていってください

資料はここ:
Google Colabの資料


00:00 1.はじめに
02:13 2.導入方法
02:55 3.GoogleColaboratoryの操作方法
06:19 4.Pythonの計算の基礎
27:27 5.Pythonの制御文
42:14 6.Pythonのクラス
49:11 7.Pythonのその他構文
64:30 8.まとめ

なおPythonチートシートを作成しています。

コーディングに迷った際に役に立ち

WEB検索する時間を無くして

作業時間を効率化できます。

note
Pythonチートシート


 

今回は水曜日のダウンタウン企画
電気椅子ゲームのシミュレーションです。


解説動画はこちら

 

電気椅子ゲームとは

水曜日のダウンタウンのネタ
結構色々やっていますが
今回は電気椅子ゲームの
シミュレーションです。

ゲームのルールはこうです。


1~12などの番号が書かれたイス
プレイヤー二人は交互に以下を行う
相手が座るイスを予想し、電流を仕掛ける
電気イスでなければ得点獲得し、イスは撤去される
電流イスに座ると得点没収され、イスはそのまま

最終的にポイントが高い方が勝利
3回電流を喰らうか、40点先取されたら負け

このルールでシミュレーション用の
コードを作ってみました。
import random

headers = ["ターン数", "選択プレイヤー", "選択数字", "電気プレイヤー", "仕掛数字", "結果", "P1得点", "P2得点", "P1電気回数", "P2電気回数", "残り椅子"]

class ElectricChairGame:
    def __init__(self):
        self.chairs = {i: i for i in range(1, 13)}
        self.player_scores = [0, 0]
        self.electric_fails = [0, 0]
        self.current_player = 0
        self.electrified_chair = None

    def choose_chair(self, chair_number):
        # 選択した数字と電気椅子の数字が一致する場合のみ電気椅子確定
        if chair_number == self.electrified_chair:
            self.electric_fails[self.current_player] += 1
            self.player_scores[self.current_player] = 0
            return "電気椅子"
        else:
            points = self.chairs[chair_number]
            self.player_scores[self.current_player] += points
            del self.chairs[chair_number]
            return "得点獲得"

    def set_electric(self, chair_number):
        self.electrified_chair = chair_number
        return True

    def check_game_end(self):
        message = ["", ""]
        for player in range(2):
            if self.electric_fails[player] >= 3:
                winner = 2 if player == 0 else 1
                message = [winner, "電気椅子3回"]
                return True, message
            if self.player_scores[player] >= 40:
                winner = player + 1
                message = [winner, "スコア40"]
                return True, message

        if len(self.chairs) == 1:
            winner = 1 if self.player_scores[0] > self.player_scores[1] else 2
            message = [winner, "スコア差"]
            return True, message

        return False, message

def simulate_game(echo=False):
    game = ElectricChairGame()
    turn,selecting_player = 1,1
    results = []
    while True:
        # 電気椅子設置
        electric_player = 2 if selecting_player == 1 else 1
        electric_choice = random.choice(list(game.chairs.keys()))
        game.set_electric(electric_choice)

        # 椅子選択
        chair_choice = random.choice(list(game.chairs.keys()))
        game.current_player = selecting_player - 1
        result = game.choose_chair(chair_choice)

        # ログ出力
        log_line = [
            turn,
            selecting_player,
            chair_choice,
            electric_player,
            electric_choice,
            result,
            game.player_scores[0],
            game.player_scores[1],
            game.electric_fails[0],
            game.electric_fails[1],
            sorted(list(game.chairs.keys()))
        ]
        results.append(log_line)
        # ゲーム終了判定
        game_end, message = game.check_game_end()
        if game_end:
          if message[0]==1:
              win_score = game.player_scores[0]
          else:
              win_score = game.player_scores[1]
          message+=[turn ,
            win_score,
            game.player_scores[0],
            game.player_scores[1],
            game.electric_fails[0],
            game.electric_fails[1],
            len(list(game.chairs.keys()))]
          if echo:
            print(", ".join(headers))
            for log_line in results:
              print(log_line)
            print(f"ゲーム終了: 勝利プレイヤー : {message[0]}, 勝因 : {message[1]}")
          return message, results

        # プレイヤー交代
        selecting_player = 2 if selecting_player == 1 else 1
        turn += 1

ゲームを実行する場合はこうです
message, log_line = simulate_game(True)
ターン数, 選択プレイヤー, 選択数字, 電気プレイヤー,
仕掛数字, 結果, P1得点, P2得点, P1電気回数, P2電気回数, 残り椅子
[1, 1, 2, 2, 3, '得点獲得', 2, 0, 0, 0, [1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]]
[2, 2, 11, 1, 5, '得点獲得', 2, 11, 0, 0, [1, 3, 4, 5, 6, 7, 8, 9, 10, 12]]
[3, 1, 6, 2, 7, '得点獲得', 8, 11, 0, 0, [1, 3, 4, 5, 7, 8, 9, 10, 12]]
[4, 2, 1, 1, 8, '得点獲得', 8, 12, 0, 0, [3, 4, 5, 7, 8, 9, 10, 12]]
[5, 1, 3, 2, 10, '得点獲得', 11, 12, 0, 0, [4, 5, 7, 8, 9, 10, 12]]
[6, 2, 12, 1, 7, '得点獲得', 11, 24, 0, 0, [4, 5, 7, 8, 9, 10]]
[7, 1, 8, 2, 4, '得点獲得', 19, 24, 0, 0, [4, 5, 7, 9, 10]]
[8, 2, 9, 1, 7, '得点獲得', 19, 33, 0, 0, [4, 5, 7, 10]]
[9, 1, 10, 2, 7, '得点獲得', 29, 33, 0, 0, [4, 5, 7]]
[10, 2, 7, 1, 5, '得点獲得', 29, 40, 0, 0, [4, 5]]
ゲーム終了: 勝利プレイヤー : 2, 勝因 : スコア40





これで1万回やる場合は
こんな感じのコードで
データフレームにできます。
game_result, game_los = [], []
for i in range(10000):
  message, log_line = simulate_game()
  game_result.append([i+1] + message)
  for log in log_line:
    game_los.append([i+1] + log)

import pandas as pd
cols = ["ゲーム数", "勝利プレイヤー", "勝因","ターン数","獲得点数","P1得点", "P2得点", "P1電気回数", "P2電気回数", "残椅子個数"]
game_result_df = pd.DataFrame(game_result, columns=cols)
game_log_df = pd.DataFrame(game_los, columns=["ゲーム数"] + headers)

game_result_df.head()


シミュレーションの結果は
ぜひ動画を見てみてくださいませ


今回は電気椅子ゲームのシミュレーションコードについてでした
それでは!!

今回は映画サマーウォーズの
なつき先輩の誕生日から曜日求める
小ネタです


解説動画はこちら




モジュロ演算

今回はあの映画
「サマーウォーズ」に出てきた
なつき先輩の誕生日から
曜日を求めていたシーンのやつです

あのシーンでは、いわゆる
余り(剰余)を求める計算を行っていました

モジュロ演算とは
単に余りを求める計算のことです。

これとツェラーの公式
がつながります。


ツェラーの公式

西暦(YYYYMMDD)から
曜日を求める公式です。
h=(d+[26(m+1)/10]+Y+[Y/4]-2[y/100]+[y/400])mod 7

こんな感じの計算式ですが

これを使うと余りが
0-6の範囲になり、これが曜日に対応する
ということになります。

0=土曜日
1=日曜日
2=月曜日
3=火曜日
4=水曜日
5=木曜日
6=金曜日


誕生日から曜日を求めるコード


コードはこんな感じです
年月日の変数を変えて貰えば
どの年月日にも対応されます
# モジュロ演算で曜日を求めるコード
def zeller(year, month, day):
    # 1月と2月は前年の13月、14月として扱う
    if month < 3:
        month += 12
        year -= 1

    y = year % 100
    century = year // 100
    
    # ツェラーの公式より
    h = (day + (26 * (month + 1)) // 10 + y + (y // 4) - (2 * century) + (century // 4)) % 7
    
    # 曜日
    # 0=土曜日, 1=日曜日, 2=月曜日, 3=火曜日, 4=水曜日, 5=木曜日, 6=金曜日
    return h

weekdays = ["土曜日", "日曜日", "月曜日", "火曜日", "水曜日", "木曜日", "金曜日"]

# 使用例
year, month, day = 2025, 2, 1

h = zeller(year, month, day)
weekday_name = weekdays[h]
print(f"{year}年{month}月{day}日は{weekday_name}です。")
2025年2月1日は土曜日です。


なつき先輩の誕生日の曜日はなんだったか?

なつき先輩の誕生日は
1992年7月19日
となっています

コードを使って求めると

日曜日

だそうです。

当たっていましたかね?



余り使う機会のない
小ネタですが
どこかで使われることがあったら
嬉しいかもしれないですね

今日はここまでです

それでは
 

今回はベンフォードの法則と
カイ二乗検定による不正の検出方法についてです。

解説動画はこちら



ベンフォードの法則

今回はベンフォードの法則のお話です

この法則は、自然界に出てくる多くの数値の最初の桁の分布が
「一様ではなくある特定の分布になっている」という法則のことです。

電気料金の請求書、住所の番地、株価、人口の数値、死亡率、川の長さなど...
特定の範囲に限定されたものは当てはまらないですが
これに当てはまるデータが世の中にはたくさんあります。

この法則によると
大きな数値ほど最初の桁に現れる確率は小さくなり
ベンフォードの法則に従った最初の桁の理論的確率は
Pythonコードでは以下の式で表せます

math.log10((d+1)/d)



ここから先のコードをGoogle Colabで試す場合は
以下をインストールしてください
pip install japanize_matplotlib


import math
import numpy as np
import scipy.stats as stats
import japanize_matplotlib
import matplotlib.pyplot as plt

# ベンフォードの理論的な確率分布
def benford_distribution():
    return [math.log10(1 + 1 / d) for d in range(1, 10)]

benford_probs = benford_distribution()

# 棒グラフの描画
labels = [1, 2, 3, 4, 5, 6, 7, 8, 9]
bar_width = 0.35
x = np.arange(len(labels))
plt.bar(x - bar_width/2, benford_probs, width=bar_width, label='理論的確率', color='blue')
plt.xlabel('最初の桁')
plt.ylabel('確率')
plt.title('ベンフォードの法則の比較')
plt.xticks(x, labels)
plt.legend()
plt.tight_layout()
plt.show()
download


ベンフォードの法則は何に使えるのか

次のような不正の調査などで利用されているらしいです
会計データ
選挙データ
化学データ
経済データ

ここから先はどのように不正を発見するのかを
見てみましょう。



ベンフォードの法則に従うかを調査する方法

・カイ二乗検定を用いる方法

カイ二乗検定は観察されたデータと期待される
データの間の差を評価するための統計的手法のことです

データの分布が特定の比率に従っているかどうかを
検定するために使用されます

検定統計量(カイ二乗統計量)を求め、カイ二乗分布を用いて
統計量と自由度からp値(確率)を求めます

P値が一定の水準以下の場合(確率が低い)
あり得ないことが起きているとし
観察された比率が期待される比率と異なると
結論づける事ができます。


カイ二乗検定を用いたベンフォードの法則比率との比較


ここでは理論値と
観測値として、操作した比率のデータで検証していきます。

以下のコードで描画させる事ができます。
import numpy as np
import scipy.stats as stats
import japanize_matplotlib
import matplotlib.pyplot as plt

# サンプルサイズを設定
n_samples = 1000  # 適宜変更

# ベンフォードの法則に従った最初の桁の理論的確率
benford_probs = [0.301, 0.176, 0.125, 0.097, 0.079, 0.067, 0.058, 0.051, 0.046]

# 観測された出現確率を設定
observed_probs = [0.295, 0.172, 0.166, 0.092, 0.074, 0.062, 0.053, 0.046, 0.040]

# 最初の桁のラベル
labels = [1, 2, 3, 4, 5, 6, 7, 8, 9]

# 棒グラフの幅
bar_width = 0.35
x = np.arange(len(labels))

# 棒グラフの描画
plt.bar(x - bar_width/2, benford_probs, width=bar_width, label='理論的確率', color='blue')
plt.bar(x + bar_width/2, observed_probs, width=bar_width, label='観測された確率', color='orange')

# グラフの設定
plt.xlabel('最初の桁')
plt.ylabel('確率')
plt.title('ベンフォードの法則の比較')
plt.xticks(x, labels)
plt.legend()
plt.tight_layout()
plt.show()
download-1

数字の3が出てくる確率を多くしました。
これが理論上の比率と合うのかを検定します。


# 出現数を計算
observed_counts = [int(p * n_samples) for p in observed_probs]
expected_counts = [int(p * n_samples) for p in benford_probs]

print("観測数 : ",observed_counts)
print("期待値 : ",expected_counts)

# カイ二乗検定を実施
chi2_stat, p_value = stats.chisquare(f_obs=observed_counts, f_exp=expected_counts)

# 結果を表示
print("カイ二乗統計量:", chi2_stat)
print("p値:", p_value)

# 結論
alpha = 0.05  # 有意水準
if p_value < alpha:
    print("ベンフォードの法則に従わないと判断される")
else:
    print("ベンフォードの法則に従うと判断される")
観測数 :  [295, 172, 166, 92, 74, 62, 53, 46, 40]
期待値 :  [301, 176, 125, 97, 79, 67, 58, 51, 46]
カイ二乗統計量: 16.30967165997854
p値: 0.03815623468852384
ベンフォードの法則に従わないと判断される


この操作された比率の場合は
ベンフォードの法則に従わないと判断されるようです。




カイ二乗検定の仕組み



ここからはカイ二乗検定の仕組みを
説明していきます。


まずは前提として何を検定するのかを定めます。
通常は仮説を置く、ということをしています。

仮説の設定:
帰無仮説 : 観察された比率は期待される比率と等しい
対立仮説 : 観察された比率は期待される比率と異なる

理論上の比率と観測された比率が正しいのか
異なるのかを仮説に置き
一般的には帰無仮説 には差がない(比率と等しい)とします。


1.カイ二乗値を求める

仮説を置いたら
まず初めにカイ二乗値を求めていきます。

カイ二乗値は下記の式で求められます。

(観測結果 - 理論値)**2 / 理論値 の合計値

観測結果と理論値の差が大きいと
大きくなる値になります。


2.自由度を求める

次に自由度ですが、この場合は
カテゴリ数 - 1
という値になります。

この場合、1-9までの数値の比率の個数だとすると
9-1 = 8になります。


3.カイ二乗の検定統計量と比べて大きいか小さいかを見る

自由度と有意水準から
カイ二乗分布を用いて、カイ二乗検定統計量の
閾値を求めていきます。

この閾値と先ほど求めたカイ二乗値を比較します。
その結果

閾値より小さい : よく有ること
閾値より大きい : よく有ることではない

となり、閾値より大きくなった場合は
P値(確率)が低くなり

あり得ない事が起きているとして帰無仮説を棄却し
対立仮説 : 観察された比率は期待される比率と異なる
を採択することになります。


カイ二乗分布の検定統計量の表を作ってみましょう
import numpy as np
import pandas as pd
from scipy.stats import chi2

# 有意水準
alpha_levels = [0.99, 0.975, 0.95, 0.9, 0.1, 0.05, 0.025, 0.01]
# 自由度
degrees_of_freedom = range(1, 10)

# カイ二乗分布の臨界値を計算
chi_square_table = {'自由度/有意水準': degrees_of_freedom}

for alpha in alpha_levels:
    chi_square_table[f'α = {alpha}'] = [chi2.ppf(1 - alpha, df) for df in degrees_of_freedom]

# カイ二乗値のDataFrameを作成
chi_square_df = pd.DataFrame(chi_square_table)
chi_square_df
スクリーンショット 2025-01-11 17.37.20

こんな感じで、有意水準と自由度で
閾値を求められます。

紙で行う場合は、この表を見て行いますが
Pythonプログラミングでは、これを使わず
直接確率を求められます。

import numpy as np
import matplotlib.pyplot as plt
from scipy.stats import chi2

# 自由度
df = 8
# 有意水準
alpha = 0.05
# カイ二乗の臨界値を計算
critical_value = chi2.ppf(1 - alpha, df)

# 観測したカイ二乗値
observed_chi_squared = sum([(o*1000-b*1000)**2/(b*1000) for b,o in zip(benford_probs,observed_probs)])

# xの範囲を設定
x = np.linspace(0, 30, 1000)
# カイ二乗分布の確率密度関数を計算
y = chi2.pdf(x, df)

# グラフを描画
plt.figure(figsize=(10, 6))
plt.plot(x, y, label=f'Chi-squared Distribution (df={df})', color='blue')
plt.fill_between(x, y, where=(x >= critical_value), color='red', alpha=0.5, label='Rejection Region (p < 0.05)')
plt.axvline(critical_value, color='red', linestyle='--', label=f'Critical Value = {critical_value:.2f}')
plt.axvline(observed_chi_squared, color='green', linestyle='--', label=f'Observed Chi-squared = {observed_chi_squared:.2f}')
plt.title('Chi-squared Distribution with 5% Significance Level')
plt.xlabel('Chi-squared Value')
plt.ylabel('Probability Density')
plt.legend()
plt.grid()
plt.show()
download-2


この場合は求めたカイ二乗値は
閾値を超える値になるため
P値は低くなり、対立仮説の採択、となります。




実際のデータで比較するとどうなるか?

統計データを読み込みしてやってみましょう
e-statのデータを読み込みしてみます
(令和2年 都道府県・市区町村別の主な結果)

データのリンク先

こちらをColabで行う場合は
ファイル置き場においてください。


データを読み込むコードはこれです。
import pandas as pd
import numpy as np

file_path = "major_results_2020.xlsx"
  # 8行目をヘッダーとして指定(0-indexed)
df = pd.read_excel(file_path, header=8)

df.iloc[0:2, 35:]

これを集計して最初の数値のカウントと
比率を求めます。
data = df.iloc[:, 35:]

# 先頭の数字をカウントするための関数
def count_leading_digits(series):
    leading_digits = series.astype(str).str[0]
    return leading_digits.value_counts()

# 全列のデータを結合して先頭の数字をカウント
all_leading_digits = data.astype(str).stack().str[0]
digit_counts = all_leading_digits.value_counts().sort_index()
digit_counts = digit_counts[~digit_counts.index.str.contains('-')]

# 結果を表示
print(digit_counts)

# 比率を計算
total_count = digit_counts.sum()
leading_digit_ratios = digit_counts / total_count
print(leading_digit_ratios)
1    8324
2    4726
3    3465
4    2592
5    2240
6    1891
7    1594
8    1302
9    1330
Name: count, dtype: int64
1    0.303088
2    0.172080
3    0.126165
4    0.094378
5    0.081561
6    0.068854
7    0.058040
8    0.047408
9    0.048427
Name: count, dtype: float64


import numpy as np
import math
import matplotlib.pyplot as plt
from scipy.stats import norm
from collections import Counter

# ベンフォードの法則による理論的な確率分布
def benford_distribution():
    return [math.log10(1 + 1 / d) for d in range(1, 10)]

# ベンフォードの理論的分布
benford_dist = benford_distribution()

# サンプルデータの分布
sample_distribution = list(leading_digit_ratios.values)

# グラフ描画
x = range(1, 10)
fig, ax = plt.subplots(figsize=(10, 6))
ax.bar(x, sample_distribution, width=0.4, label="Sample Distribution", align="center", alpha=0.7)
ax.bar([xi + 0.4 for xi in x], benford_dist, width=0.4, label="Benford Distribution", color="orange", alpha=0.7)

# グラフの設定
ax.set_xticks(x)
ax.set_xticklabels([str(d) for d in x])
ax.set_xlabel("Leading Digit")
ax.set_ylabel("Frequency")
ax.set_title("Comparison of Sample Distribution and Benford's Law")
ax.legend()
plt.show()
download-3


カイ二乗検定を行うと
# カイ二乗検定の実施
import scipy.stats as stats

# サンプルの頻度を期待値に基づいて計算
expected_frequencies = [sum(sample_distribution) * p for p in benford_dist]
observed_frequencies = sample_distribution

# カイ二乗検定を実行
chi2_stat, p_value = stats.chisquare(observed_frequencies, f_exp=expected_frequencies)

# 結果を表示
print("カイ二乗統計量:", chi2_stat)
print("p値:", p_value)

# 有意水準を設定
alpha = 0.05
if p_value < alpha:
    print("帰無仮説を棄却します。サンプルデータはベンフォードの法則に従っていない可能性があります。")
else:
    print("帰無仮説を棄却できません。サンプルデータはベンフォードの法則に従っている可能性があります。")
カイ二乗統計量: 0.000739463432140538
p値: 0.9999999999999992
帰無仮説を棄却できません。
サンプルデータはベンフォードの法則に従っている可能性があります。


このデータの場合は
ベンフォードの法則に従っていないとは言えないようですね

正しいデータである可能性が高いです。



まとめ

ベンフォードの法則を用いると無作為に抽出したデータの場合
操作された数値を発見できる可能性はあります。

ただし、必ずしも当てはまる訳ではないので
見極めは重要です。

もしお手持ちに
会計データなどがある場合は
これで比率が正しいかを試してみると
面白いかもしれませんね。

今日はこれまでです
それでは



2つのバケツを使って水の量を測るっていう
古典的なパズル問題ありますよね

今回はそれをプログラムで解いてみました。

解説動画はこちら



二つのバケツで指定の水量を測るやつ

問題

5リットル入るバケツと3リットル入るバケツがある
この2つだけを使って4リットルの水を測りたい
どうすれば良いでしょうか

ヒント : 水は捨てたり移動したりして良い





プログラムでの解法

幅優先探索(breadth-first search, BFS)を
用いて手順の探索を行っていきます。

バケツをA, B、測りたい水量をXとし
A,Bの水量を記録していきます

途中、以下の6つの状態でうまく切り替えて手順を記録し
どこかが水量Xになったら終了になります。

1. Aを満たす
2. Bを満たす
3. Aを空にする
4. Bを空にする
5. AからBに移す
6. BからAに移す

プログラム上ではキューというデータ構造のものを使って
手順を記録していく形になります。


手順を解くコード


手順を算出するコードは次のようになります。

from collections import deque
from math import gcd

# 幅優先探索(breadth-first search, BFS)を用いて手順の探索を行う
def min_steps_to_measure(A, B, X):
    # 目標の水量がAとBの最大公約数で割り切れない場合は終了
    if X > max(A, B) or X % gcd(A, B) != 0:
        return []

    # キューとSETと状態の親を初期化
    queue, visited, parent = deque(), set(), {}

    # 初期状態をキューに追加
    queue.append((0, 0))  # (容器Aの水量, 容器Bの水量)
    parent[(0, 0)] = None  # 初期状態の親はNone

    while queue:
        a, b = queue.popleft()

        # 目標の水量に達した場合
        if a == X or b == X:
            # 結果を表示
            steps = []
            while (a, b) is not None:
                steps.append((a, b))
                # 親が存在する場合のみアンパック
                if parent[(a, b)] is not None:
                    a, b = parent[(a, b)]
                else:
                    break
            steps.reverse()
            return steps

        # 訪れた状態を記録
        if (a, b) in visited:
            continue
        visited.add((a, b))

        # 次の状態をキューに追加
        # 1. 容器Aを満たす
        if (A, b) not in visited:
            queue.append((A, b))
            parent[(A, b)] = (a, b)
        # 2. 容器Bを満たす
        if (a, B) not in visited:
            queue.append((a, B))
            parent[(a, B)] = (a, b)
        # 3. 容器Aを空にする
        if (0, b) not in visited:
            queue.append((0, b))
            parent[(0, b)] = (a, b)
        # 4. 容器Bを空にする
        if (a, 0) not in visited:
            queue.append((a, 0))
            parent[(a, 0)] = (a, b)
        # 5. 容器Aから容器Bに移す
        transfer_to_B = min(a, B - b)
        if (a - transfer_to_B, b + transfer_to_B) not in visited:
            queue.append((a - transfer_to_B, b + transfer_to_B))
            parent[(a - transfer_to_B, b + transfer_to_B)] = (a, b)
        # 6. 容器Bから容器Aに移す
        transfer_to_A = min(b, A - a)
        if (a + transfer_to_A, b - transfer_to_A) not in visited:
            queue.append((a + transfer_to_A, b - transfer_to_A))
            parent[(a + transfer_to_A, b - transfer_to_A)] = (a, b)

    return []  # 目標の水量を測ることができない場合





早速実行して見てみましょう。

バケツA,Bの値と
ターゲットの水量Xを指定すると
その手順が表示されます。

# 容器の容量と目標の水量を指定
A = 5  # 容器Aの容量
B = 3  # 容器Bの容量
X = 4  # 測りたい水量

# 最小手数を計算
steps = min_steps_to_measure(A, B, X)

# 結果を表示
if steps:
    print("途中の過程:")
    for step in steps:
        print(f"容器A: {step[0]}L, 容器B: {step[1]}L")
else:
    print("目標の水量を測ることができませんでした。")

途中の過程:
容器A: 0L, 容器B: 0L
容器A: 5L, 容器B: 0L
容器A: 2L, 容器B: 3L
容器A: 2L, 容器B: 0L
容器A: 0L, 容器B: 2L
容器A: 5L, 容器B: 2L
容器A: 4L, 容器B: 3L



このように探索の結果が表示されます。

文字だけだと分かりづらいので
描画してみることにしましょう。



手順を描画するコード

ipywidgetsでスライダーを作り
stepを可変で描画できます。

A,B,Xを色々な設定に変えて
色々遊んでみてください。

import matplotlib.pyplot as plt
import matplotlib.patches as patches
import numpy as np
import ipywidgets as widgets
from IPython.display import display
%matplotlib inline

A = 5  # 容器Aの容量
B = 3  # 容器Bの容量
X = 4  # 測りたい水量

steps = min_steps_to_measure(A, B, X)

# 描画関数
def draw_graph(step):
    a_value = steps[step][0]
    b_value = steps[step][1]
    a_frame_height = A - a_value
    b_frame_height = B - b_value

    # 描画
    fig, ax = plt.subplots(figsize=(8, 4))
    ax.bar(0, a_value, width=0.4, label='Container A Volume (L)', color='blue', linewidth=2, edgecolor='black')
    rect_a = patches.Rectangle((-0.2, a_value), 0.4, a_frame_height, linewidth=2, edgecolor='black', facecolor='none')
    ax.add_patch(rect_a)
    ax.text(0, max(A,B)+1, str(a_value), ha='center', va='bottom', fontsize=12, color='green')
    ax.bar(1, b_value, width=0.4, label='Container B Volume (L)', color='red', linewidth=2, edgecolor='black')
    rect_b = patches.Rectangle((0.8, b_value), 0.4, b_frame_height, linewidth=2, edgecolor='black', facecolor='none')
    ax.add_patch(rect_b)
    ax.text(1, max(A,B)+1, str(b_value), ha='center', va='bottom', fontsize=12, color='green')

    # タイトルとラベルの設定
    ax.set_title(f'Container A : {A} and B: {B} Target Volume : {X} with Frames step : {step}')
    ax.set_xlabel('Containers')
    ax.set_ylabel('Volume (L)')
    ax.set_xticks([0, 1])
    ax.set_xticklabels(['Container A', 'Container B'])
    ax.set_ylim(0, max(A,B)+3)
    plt.show()

# スライダーの作成
step_slider = widgets.IntSlider(value=0, min=0, max=len(steps)-1, step=1, description='Step:')
interactive_plot = widgets.interactive(draw_graph, step=step_slider)
display(interactive_plot)
step06


今回は2つのバケツを使って水量を測るやつを
プログラムにしてみました。

動画ではもう少し手順のかかるやつもやっているので
興味がある場合は見てみてください。

今回はここまでです
それでは


 

このページのトップヘ