2024.05.13 2024.05.16

プログラミング日記①

palm

こんにちは、Palmです！
今回はプログラミングノートを書こうと思います

前回東京通信大学のプログラミングワークショップに参加して
「アルゴリズムへの理解をもっと深めたいな」
とおもい、とある本に挑戦してみました！

それがこちらです！

もっとプログラマ脳を鍛える数学パズルアルゴリズムが脳にしみ込む70問 [ 増井敏克 ]

楽天ブックス

¥2,838 （2024/05/13 13:05時点 | 楽天市場調べ）

楽天市場

ポチップ

実家から発掘してきました！
「もっとプログラマ脳を鍛える数学パズルアルゴリズムが脳にしみ込む70問」という本です。
2018年に発行された本で少し古いです。

CodeIQ（https://codeiq.jp）※サイト終了
にある「今週のアルゴリズム」として、
毎週出題していた問題を一部改変して掲載している本です。

掲載されている解答例は、
RubyとJavaScriptにしか対応しておらず
Pythonで解くのは大変でした。

これは簡単そうな表紙に騙されて買いましたが、
「とても難しい問題」しか載ってないです！
文系の著者は一回挫折しています。

それでは挑戦していきましょう！

この記事の目次

【Q01】一発で決まる多数決
【Q02】山手線でスタンプラリー
【Q03】ローマ数字の変換規則
まとめ

【Q01】一発で決まる多数決

【問題】
じゃんけんで100人が参加する場合、「一度で」勝つ手が決まるような人数の組み合わせが何通りあるかを求めてください。

【考え方】
出せる手はグー、チョキ、パーの３通りなので、それぞれの手を出した人数を数えてみます。一度で決まるのは、その人数が最多となる手が１通りに決まる場合だと考えてみます。

それではパズルを解いてみましょう！
グーだった場合、チョキだった場合、パーだった場合を求めればので簡単ですね！

【解説①】
最初にグーとチョキを比べて、その大きいほうとパーの数を比べている。こうすると、最大の人数になっている手がいくつあるか求められる。

１.人数の設定 (変数 N ) :総人数（ここでは100人）

2.カウンタの初期化 (変数 cnt) :
　cntというカウンタを0で初期化し、条件を満たす数を数えます。

3.ループ処理 :
　・rock (グーの人数)に対して
　　0人から100人までループします
　・scissors (チョキの人数)は、
　　残りの人数内でループします（rock 人数を引いた残り）
　・paper (パーの人数)は自動的に計算され、
　　rock と scissors の人数を100から引いたものになります

4.条件のチェック:
　・各ループで、rock, scissors, paper のどれが
　　最も多いかを確認します。
　・最も人数が多い手が他の２つの手よりも多ければ、
　　カウンタ cnt を1増やします。
　　ただし、最も多い手は他の２つの手よりも多い必要があります。

5. 結果の出力：5,100通り

N = 100
cnt = 0

# グー、チョキ、パーの人数に対してループ
for rock in range(N + 1):  # グーの人数
    for scissors in range(N + 1 - rock):  # チョキの人数
        paper = N - rock - scissors  # パーの人数

        # グーが最も多い場合
        if rock > scissors and rock > paper:
            cnt += 1
        # チョキが最も多い場合
        elif scissors > rock and scissors > paper:
            cnt += 1
        # パーが最も多い場合
        elif paper > rock and paper > scissors:
            cnt += 1

print(cnt)

これは数式を用いたプログラムです。
著者はアルゴリズムを学ぶ上で数式は重要だよねとおもっていて、
興味があって載せてみました！

【解説②】重複の組み合わせ

１.変数や人数の設定
　・(変数 N ): 総人数（ここでは100人）
　・(変数 l ): 最初の境界点
　　（例えば「グー」の人数を指定します）
　　0人から100人まで変化します。
　・(変数 r ): 第二の境界点
　　（「グー」と「チョキ」の合計人数を指定します）
　　l から100人まで変化します。

2.カウンタの初期化 (変数 cnt) :
　cntというカウンタを0で初期化し、
　条件を満たす数を数えます。

3.配列の設定(配列 all : [l, r-l, N-r]):
　配列 all を使ってどのグループが最も人数が多いかを判断します
　・l : 「グー」の人数
　・r-l : 「チョキ」の人数
　・N-r : 「パー」の人数

4.条件のチェック:
　・all.count(max(all)) == 1 で、
　最大値が配列 all 内で1回だけ出現するかどうかをチェックします。
　この条件は、最も多い手がちょうど1つだけ存在するという意味です。
　・条件が正しければcnt を1増やします。

5. 結果の出力：5,100通り

【数式】
N種類から重複を許してr個選ぶ方法
$$cnt=\sum_{l=0}^{N}\sum_{r=l}^{N}1 all.count(max(all)) = 1$$

ブログに数式を載せてみたくて載せてみたけどあってるかわからない（笑）

N = 100
cnt = 0

for l in range(N + 1):
    for r in range(l, N + 1):
        all = [l, r - l, N - r]
        if all.count(max(all)) == 1:  # 最大値が1つだけである場合をカウント
            cnt += 1

print(cnt)

【Q02】山手線でスタンプラリー

【問題】
山手線は、全部で29個の駅があります。スタンプカードはすべての駅のスタンプを押すことができ、山手線の各駅には1～29の番号が付与されているとします。
1番の駅から入場し、17番の駅から出場するとき、スタンプを押す順番として考えられるパターンが何通りありますか。（途中で逆行すると違反になります）

【考え方】
問題を簡単にするには、一列に並んだ駅を考えてみます。
例えば１，２，３，４という４つの駅があった場合
・１→２→３→４
・１→２→４
・１→3→４
・１→４
の４通りです。

最初の駅にとまるので「２」に止まるかどうかか
「３」かと考えられ２×２で求められます！！
なので、「間にある駅の数」をnとすると、
2^{n}通りとなります！

それではパズルを解いてみましょう！
この本では２^{n}を求めるのに
「＜＜」というようなシフト演算を使用されていました。

シフト演算とは数値のビット列を左または右に移動させる操作です。

「<<」とは「左シフト」と呼ばれ、
「１＜＜３」であれば、
２進数の「１」を左に３ビットシフト（移動）します。

例）
0001（１）→0001000→1000（８）
0011（３）→0011000→11000（24）

【解説】
N = 29：線路上の駅の数です。

a, b = 1, 17：入場駅を1番、出場駅を17番です。

n = abs(a - b)：
　絶対値（入場駅から出場駅までの間にある駅の数）です。
　「入場した駅の番号」のほうが大きい可能性があるので、
　絶対値を使うと簡単に求められます。
　・n = 16（間にある駅の数）

patterns =
(1 << (n - 1)) + (1 << (N - n - 1)) - 1:
ビット演算を用いて、内回りと外回りの経路の数を計算します！
　・(1 << (n - 1))：
　　入場駅から出場駅まで内回りで進む経路の数です。
　・(1 << (N - n - 1))：
　　外回りでの経路の数です。
　・- 1：
　　内回りと外回りの経路が重複して計算される場合の除去です。

print(patterns)：
　patternsを出力します。
　36863通りでした！

N = 29

a,b = 1, 17 #入場と出場の駅番号をセット

n = abs(a - b)#[間にある駅の数]を求める

patterns = (1 << (n - 1)) + (1 << (N - n - 1)) - 1 #内回りと外回りを足して、重複を除外

print(patterns)

【Q03】ローマ数字の変換規則

【設問】
ローマ数字とは数字が大きい順に左から並べていきます。
27であれば10＋10＋5＋1＋1で表現できるので「XXVII」です。

「同じ数字を4つ連続で並べることができない」というルールもあります。
4「IIII」→「IV」
9「VIII」→「IX」

ここで使う記号は「M（1000）」までのため、
ローマ数字では最大3,999まで表現できます。

【問題】
ローマ数字の記号を12個並べたとき、ローマ数字として認識できる数が何通りあるかを求めてください。
1個の記号で表現できるのは、I、V、X、L、C、D、Mの7通り、15個の記号で表現できるのは「MMMDCCCLXXXVIII」(3,888)の1通りです。

【考え方】
それぞれの数をローマ数字に変換できれば、
あとはその文文字数を数えるだけです。
アラビア数字からローマ字にどのように変換するかを考えてみます。

まずは、１、１０、１００、１０００という桁で区切るため、
それを割り算して、その余りを求めます。
この余りが４、９、４０、９０、、、のようになる場合は
無条件にローマ数字が決まります。

一方、余りがその他の場合は、
さらに５、５０、５００で割った余りを考えてみます。

【解説】
conv 関数

　パラメータ
　　・n: 0から9までの数字
　　・i: 1の位に相当するローマ数字の文字
　　・v: 5の位に相当するローマ数字の文字
　　・x: 10の位に相当するローマ数字の文字

　機能:
　　・9 の場合は ix 形式（例: IX）
　　・4 の場合は iv 形式（例: IV）
　　・それ以外の場合、
　　まず v を n // 5 の回数だけ追加し（5以上の場合）、
　　残りを i で表現します。

roman 関数

　パラメータ
　　・n: 1から3999までの整数

　機能:
　　・数値 n をローマ数字に変換します。
　　・最初に1000の位 (m)、
　　次に100の位 (c)、
　　次に10の位 (x)、
　　最後に1の位の計算を行います。
　　・それぞれの桁について、
　　conv 関数を使ってローマ数字に変換し、
　　最終的なローマ数字を組み立てます。

メインプログラム

　機能:
　　・1から3999までのすべての整数に対してローマ数字に変換し、
　　　その長さを計算します。
　　・各長さのローマ数字が何回出現するかを
　　　辞書 cnt に記録します。
　　・与えられた数値 N（12）に対応するローマ数字の長さが
　　　何回出現するかを出力します。

N = 12

#1桁分の変換
def conv(n, i, v, x):
    result = ''
    if n == 9:
        result += i + x
    elif n == 4:
        result += i + v
    else:
        result += v * (n // 5)
        n = n % 5
        result += i * n
    return result

#ローマ字への変換
def roman(n):
    m, n = divmod(n, 1000)
    c, n = divmod(n, 100)
    x, n = divmod(n, 10)
    result = 'M' * m
    result += conv(c, 'C', 'D', 'M')
    result += conv(x, 'X', 'L', 'C')
    result += conv(n, 'I', 'V', 'X')
    return result

cnt = {}
for n in range(1, 4000):
    r = roman(n)
    cnt[len(r)] = cnt.get(len(r), 0) + 1

print(cnt[N])