プログラマ脳を鍛える数学パズルQ05いまだに現金払い？

問題概要

1000円を500円玉、100円玉、50円玉、10円玉の組み合わせに両替する。ただし硬貨の枚数の合計は15枚以下。

Code

何も考えずに解く

#Q05いまだに現金払い？

combinations = [] #組み合わせのリスト
for c500 in range(3):
    for c100 in range(11):
        for c50 in range(16):
            for c10 in range(16):
                if c500 + c100 + c50 + c10 <= 15:
                    if c500 * 500 + c100 * 100 + c50 * 50 + c10 *10 == 1000:
                        combinations.append((c500, c100, c50, c10))

print(combinations)
print(len(combinations))

Codeその2

なるべくfor文の繰り返しを減らして書く

import itertools
import numpy as np

combinations = []
for c in list(itertools.product(list(range(16)), repeat=4)):
    m = np.array(list(c)) * np.array([500, 100, 50, 10])
    if np.sum(c) <= 15 and np.sum(m) == 1000:
        combinations.append(c)

print(combinations)
print(len(combinations))

コードが短くなったが、べつに処理速度が速くなったようは思えないし、可読性も低くなったので参考程度で。。。

言いたいことは、配列回りの処理をするときには、

• itertools
• numpy

あたりを漁ると、実装が楽になるツールが見つかる、ということ。

以下、今回使ったツールの補足。

itertools.product

配列の直積を求める。repeatオプションを使うと、自分自身との直積を求めることができる。itertoolsオブジェクトを返すが、listにキャストできる。以下使用例。

import itertools

x = ['a', 'b']
y = ['c', 'd']
z = list(range(3)) #[0, 1, 2]

print(list(itertools.product(x, y))) 
#[('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd')]

print(list(itertools.product(x, repeat=2)))
#[('a', 'a'), ('a', 'b'), ('b', 'a'), ('b', 'b')]

print(list(itertools.product(z, repeat=2)))
#[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]

numpyでのリストの四則演算

通常のリストでは、+記号はリストの連結を表す。それ以外の演算記号はエラー。
numpyでは、リストを演算記号でつなぐと、同じ位置にある要素を演算した結果のリストを返す。

import numpy as np

x = [1, 3, 5]
y = [2, 4, 6]

print(x + y) #[1, 3, 5, 2, 4, 6]
print(x - y) #error
print(x * y) #error
print(x / y) #error

print(np.array(x) + np.array(y)) # [ 3  7 11]
print(np.array(x) - np.array(y)) # [-1 -1 -1]
print(np.array(x) * np.array(y)) # [ 2 12 30]
print(np.array(x) / np.array(y)) # [0.5 0.75 0.83333333]