フィボナッチ数列：「プログラマ脳を鍛える数学パズル」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
このプログラム、理論上は正しい筈なのだが答えを出すのにやたらと時間がかかる。何かがおかしい。４つ目の答えまでは待ったけど、５つ目の答えは待ちきれずプログラムを強制終了した。
続きを読むルーレットの最大値：「プログラマ脳を鍛える数学パズル」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を参考に。
わたしのオリジナル解答
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回で切り分けることができます。
問１．n=20, m=3のときの回数を求めてください。
問２．n=100, m=5のときの回数を求めてください。
元ネタ：
第8回「今週のアルゴリズム：棒の切り分け」正解者発表｜CodeIQ MAGAZINE
わたしの考え方
- 棒を１回切るごとに断片が1個増える。
- n[cm]の棒を1[cm]単位に切り分ける＝n個の断片にすればよい。
- 切ることが出来る人数が１人ずつ増えて行き、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)
続きを読む
