読者です 読者をやめる 読者になる 読者になる

Pythonで解く数学パズル

「プログラマ脳を鍛える数学パズル」をPythonで解きます。

フィボナッチ数列:「プログラマ脳を鍛える数学パズル」Q11の答え

問題

フィボナッチ数列のうち、各桁の数字を足した数で割り切れる数を以下の例に続けて 小さい方から5個求めてください。

例)
2 : 2 ÷ 2
3 : 3 ÷ 3
5 : 5 ÷ 5
8 : 8 ÷ 8
21 : 21 ÷ 3 ← (2 + 1 = 3で割る)
144 : 144 ÷ 9 ← (1 + 4 + 4 = 9で割る)

元ネタ:
第3回「今週のアルゴリズム:フィボナッチ数列」正解者発表|CodeIQ MAGAZINE

わたしの考え方

わたしのオリジナル解答

def fibonacci(n):
    if n == 0: return 1
    if n == 1: return 1
    return fibonacci(n-1) + fibonacci(n-2)

def sum_each_fig(m):
    sum_each = 0
    m = str(m)
    for x in m[0:]:
        sum_each += int(x)
    return sum_each

cnt = 0
n = 13
while cnt <5:
    if fibonacci(n) % sum_each_fig(fibonacci(n)) == 0:
        print fibonacci(n)
        cnt += 1
    n += 1

このプログラム、理論上は正しい筈なのだが答えを出すのにやたらと時間がかかる。何かがおかしい。4つ目の答えまでは待ったけど、5つ目の答えは待ちきれずプログラムを強制終了した。

続きを読む

ルーレットの最大値:「プログラマ脳を鍛える数学パズル」Q10の答え

問題

この問題もCodeIQで見つからなかったので書籍版オリジナル問題と思われる。

ルーレットの目の配列にはヨーロピアンスタイルとアメリカンスタイルがある。連続するn個の目の和の最大値がヨーロピアンスタイル<アメリカンスタイルとなるような2以上36以下のnはいくつあるか?と言う問題。

わたしの考え方

  • 任意の目から順にn個のルーレットの目を合算する関数を定義する
  • n個の目の数の和の最大値を求める関数を定義する
  • さいごにヨーロピアンスタイルとアメリカンスタイルで比較する

わたしのオリジナル解答

European = [0,32,15,19,4,21,2,25,17,34,6,27,13,36,11,30,8,23,10,5,24,16,33,1,20,14,31,9,22,18,29,7,28,12,35,3,26]
American = [0,28,9,26,30,11,7,20,32,17,5,22,34,15,3,24,36,13,1,00,27,10,25,29,12,8,19,31,18,6,21,33,16,4,23,35,14,2]

def European_Sum(m, n):
    Sum = 0
    for s in range (m, m + n):
        if s >= 37:
            s -= 37
        Sum += European[s]
    return Sum

def European_Max(n):
    Max_sum = 0
    for m in range(0,37):
        if Max_sum < European_Sum(m, n):
            Max_sum = European_Sum(m, n)
    return Max_sum

def American_Sum(m, n):
    Sum = 0
    for s in range (m, m + n):
        if s >= 38:
            s -= 38
        Sum += American[s]
    return Sum

def American_Max(n):
    Max_sum = 0
    for m in range(0,38):
        if Max_sum < American_Sum(m, n):
            Max_sum = American_Sum(m, n)
    return Max_sum

cnt = 0
for n in range(2,36):
    if European_Max(n) < American_Max(n):
        cnt += 1
print cnt
続きを読む

つりあわない男女:「プログラマ脳を鍛える数学パズル」Q09の答え

問題

男性20人、女性10人がランダムに到着して行列を作る。ある位置で区切って行列を2つのグループに分ける時、どこで区切っても2つのグループのいずれかで男女の数が異なってしまうような到着順は何通りあるか。

この問題の元ネタをCode IQのサイトで探したけど見つからなかったので、書籍版のオリジナル問題なのだろうか。

わたしの考え方

  • まずは男性20名、女性10名の並び替えの組み合わせを全て吐きだす。
  • 最初の2名のところで区切るところから初めて、28名で区切るところまで全ての場合を検証して、男女の数が等しくならない組み合わせを数え上げて行く。

わたしのオリジナル解答

import itertools

p = list('MMMMMMMMMMMMMMMMMMMMFFFFFFFFFF')
r=30
cnt = 0

for q in set(itertools.permutations(p,r)):
    for n in range (2, 28):
        former = q[:n]
        latter = q[n:]
        if former.count('M') != former.count('F') or latter.count('M') != latter.count('F'):
            cnt += 1
print cnt

このプログラム、理論的には正しいはずなのだが検証すべき場合の数が多すぎて走らせるといつまでたっても終わらない・・・

続きを読む

日付の2進数変換:「プログラマ脳を鍛える数学パズル」Q07の答え

問題

年月日をYYYYMMDDの8桁の整数で表したとき、これを2進数に変換して逆から並べ さらに10進数に戻したとき、元の日付と同じ日付になるものを探してください。
期間は、前回の東京オリンピック(1964年10月10日)から、次回の東京オリンピック(2020年7月24日予定)とします。

例)1966年7年13日の場合
● YYYYMMDDのフォーマット:
 19660713
● 2進数に変換:
 1001010111111111110101001
● 2進数を逆から並べる:
 1001010111111111110101001
● 逆から並べた2進数を10進数に戻す:
 19660713
 ↓
 1966年7月13日になる

元ネタ:
第2回「今週のアルゴリズム:日付の2進数変換」正解者発表|CodeIQ MAGAZINE

わたしの考え方

  • Pythonで日付を扱う場合はdatetimeモジュールをimportすればよい。
  • 日付の加算を行うにはtimedeltaを使う。
  • 2進数変換した時の回文判定はQ01を参考に。

pythonista.hateblo.jp

わたしのオリジナル解答

import datetime

def ispalindrome(x):
    y = x.year
    m = x.month
    d = x.day
    YMD = y * 10000 + m * 100 + d
    YMD = format(YMD, 'b')
    return str(YMD) == str(YMD)[::-1]

sDate = datetime.date(1964, 10, 10)
eDate = datetime.date(2020, 07, 24)

x = sDate

while x != eDate:
    if ispalindrome(x):
        print x
    x = x + datetime.timedelta(days=1)
続きを読む

(改造版)コラッツの予想:「プログラマ脳を鍛える数学パズル」Q06の答え

問題

数学の未解決問題のひとつに「コラッツの予想」があります。
自然数nについて、

・nが偶数の場合、nを2で割る
・nが奇数の場合、nに3をかけて1を足す

という操作を繰り返すとき、初期値がどんな数であっても必ず1に到達する(1→4→2→1を繰り返す)というものです。
この問題を少し変えて、初期値が偶数の場合、初回のみnに3をかけて1を足すことから始めることとし、「最初の数」に戻るものを考えます。

例えば、2で始めた場合、
2→7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2
となります。

同様に、4で始めると、 4→13→40→20→10→5→16→8→4 となります。

しかし、6で始めると、
6→19→58→29→88→44→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1→4→…
となり、6には戻ってくることはありません。

10,000以下の偶数のうち、上記の2や4のような「最初の数に戻る数」がいくつあるか、その個数を求めてください。

元ネタ:
第20回「今週のアルゴリズム:(改造版)コラッツの予想」正解者発表|CodeIQ MAGAZINE

わたしの考え方

  • コラッツのルールを関数Collatz(x)として定義する。
  • Collatz(x)をループして繰り返し、元の数字に戻ればカウンタを1増やす。1に等しくなった場合はループをbreakする。

わたしのオリジナル解答

cnt = 0

def Collatz(x):
    if x % 2 == 0:
        x = x/2
    else:
        x = x * 3 + 1
    return x

for m in range(2, 10001, 2):
    n = m * 3 + 1
    while n != m:
        n = Collatz(n)
        if n == 1:
            break
        if n == m:
            cnt += 1
print cnt
続きを読む

いまだに現金払い?:「プログラマ脳を鍛える数学パズル」Q05の答え

問題

最近は電車もバスも電子マネーが当たり前。
でも、いまだに現金で払う人も意外と多いもの。

今回はバスに設置されている両替機を考えます。
この機械では、10円玉、50円玉、100円玉、500円玉の組み合わせに両替することができ、いずれの硬貨も十分な枚数がセットされています。
(バスの運賃は現金の場合は10円単位になっているため、1円玉、5円玉は取り扱っていません)

両替する際に、使われない硬貨はあっても構いませんが、バスの中でたくさんの小銭が出ると困るため、最大で15枚になるように両替します。
例えば、10円玉を100枚、という両替はできません。

このとき、1000円札を入れたときに出てくる硬貨の組み合わせは何通りあるかを求めてください。
なお、硬貨の順番は区別しないものとします。

元ネタ:
第40回「今週のアルゴリズム:いまだに現金払い?」正解者発表|CodeIQ MAGAZINE

わたしの考え方

  • 総当たり式でループを作り、合計額が1000円かつ合計枚数が15枚以下の組み合わせを抽出する。
  • 500円玉は0枚から2枚、100円玉なら0枚から10枚までとループの数は調整できる。

わたしのオリジナル解答

#coding: UTF-8
a = 0
for m in range (0, 3): #500円玉は0から2枚
    for n in range (0, 11): #100円玉は0から10枚
        for o in range (0, 16): #50円玉は0から15枚
            for p in range (0, 16): #10円玉は0から15枚
                if 500 * m + 100 * n + 50 * o + 10 * p == 1000 and m + n + o + p < 16:
                    a += 1
                    print [m, n, o, p]
print a
続きを読む

棒の切り分け:「プログラマ脳を鍛える数学パズル」Q04の答え

問題

長さn[cm]の一本の棒を1[cm]単位に切り分けることを考えます。 一本の棒を一度に切ることができるのは一人だけです。(切り分けられた棒が三本あれば、同時に三人で切ることができます。)
最大m人の人がいるとき、最短何回で切り分けることができるかを求めてください。
例えば、n=8, m=3のときは次の図のようになり、4回で切り分けることができます。

問1.n=20, m=3のときの回数を求めてください。
問2.n=100, m=5のときの回数を求めてください。

元ネタ:
第8回「今週のアルゴリズム:棒の切り分け」正解者発表|CodeIQ MAGAZINE

わたしの考え方

  • 棒を1回切るごとに断片が1個増える。
  • n[cm]の棒を1[cm]単位に切り分ける=n個の断片にすればよい。
  • 切ることが出来る人数が1人ずつ増えて行き、m[人]で打ち止めになる。

わたしのオリジナル解答

def Cut_Tree(m, n):
    stick = 1
    t = 0
    c = 1
    while stick < n:
        if c < m:
            stick = stick + c
            t += 1
            c += 1
        else:
            stick = stick + m
            t += 1
    return t

print Cut_Tree(3, 20)
print Cut_Tree(5, 100)
続きを読む