プロジェクトオイラー 問１２２

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問１２２「効率的なべき乗計算」
n15を求めるのに最も単純な方法では 14 回の掛け算が必要である.

n × n × ... × n = n¹⁵
しかし2進法を用いれば, 6 回の掛け算で計算できる.

n × n = n²
n² × n² = n⁴
n⁴ × n⁴ = n⁸
n⁸ × n⁴ = n¹²
n¹² × n² = n¹⁴
n¹⁴ × n = n¹⁵
ところがたった 5 回の掛け算のみでも計算できる.

n × n = n²
n² × n = n³
n³ × n³ = n⁶
n⁶ × n⁶ = n¹²
n¹² × n³ = n¹⁵
m(k)を n^k を求めるのに必要最低限な掛け算の回数と定義する.
たとえば m(15)=5 である.

1 ≦ k ≦ 200 に対し, Σ m(k) を求めよ.



注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。



私の回答例は以下の通りです。

def f(n1, n2):
	L = [[] for i in xrange(n2 + 1)]
	M = [0 for i in xrange(n2 + 1)]
	L[1].append([])
	
	for i in xrange(1, n2):
		for m in L[i]:
			s = m + [i]
			t = len(s)
			for j in s[::-1]:
				for k in s[::-1]:
					u = j + k
					if not (i < u  <= n2): break
					if 0 < M[u] < t: continue
					if s in L[u]: continue
					L[u].append(s)
					M[u] = t
	return sum(M[n1:])
	
if __name__=="__main__":
	print f(1, 200)

掛け算するときの掛ける数の指数を足していき、指定数に達するまでの最小回数を求めます。
１度掛け算して作成した累乗値の指数は再利用できます。

掛け算で使用した指数値のユニークな配列を作成し、
この要素と掛け算で到達したその指数値自身から、
値を２つ取り出し、その和の累乗値の配列として順に計算していきます。
このとき、指数値のユニークな値の配列は複数パターンできることがあり、いずれも必要です。
例えば、n=5の場合、到達するパターンは[1,2,3]と[1,2,4]の２つあり、
これを元にさらに大きな指数値について計算していくとき、
どちらの系統を使った方が最小回数になるか、この段階では判断つかないためです。

また、掛け算を実施した回数を別のリストに保存しておき、最後にその合計を求めます。

１．関数f(n1, n2)
・題意にあるm(k)について、n1≦k≦n2のときのm(k)の和を返します。

・L = [[] for i in xrange(n2 + 1)]
　M = [0 for i in xrange(n2 + 1)]
　Lは、そのインデックス位置の値の累積値を求めるときの「掛け合わせた指数値のユニークリスト」のリストです。
　Mは、そのインデックス位置の値の累積値を求めるときの最小掛け算回数のリストです。
　例えば、n=5の場合、L[5]=[[1, 2, 3], [1, 2, 4]]、M[5]=3　です。

・L[1].append([])
　初期値です。これでn**1の場合に、この指数値までに使用した指数値のリストは無いが、この指数値そのもの（つまり、1）を使用して累乗していくことが可能になります。

・for i in xrange(1, n2):
　ループ変数iは、1からn2に至るインデックスです。累乗値計算の範囲です。

・for m in L[i]:
　ループ変数mは「掛け合わせた指数値のユニークリスト」です。

・s = m + [i]
　sは「掛け合わせた指数値のユニークリスト」に、それより到達した指数値iそのものを追加したリストです。
　次の累乗値計算の元になる指数値のリストです。

・t = len(s)
　tは、リストsの次の累乗で生成できる累乗値までの掛け算回数の候補です。

・for j in s[::-1]:
　for k in s[::-1]:
　ループ変数jとループ変数kは、リストsから取り出した２つの要素です。
　大きい値から順に、次の値を計算していきます。

・u = j + k
　uは、次の掛け算で到達できる累乗値の指数です。

・if not (i < u  <= n2): break
　i < u < n2 なら書き換え対象です。
　そうでない場合は、kはそれ以下の値しかないので、条件は満たせずループは終了です。

・if 0 < M[u] < t: continue
　0 < M[u] < tの場合、今までの結果よりも掛け算回数が少ないパターンなので、次のパターンを考えます。
　そうでない場合、ここまでの処理結果よりも同じか長い掛け算回数のパターンなので処理続行です。

・if s in L[u]: continue
　リストsは指数値uのときの「掛け合わせた指数値のユニークリスト」に既にあれば、次のパターンを考えます。

・L[u].append(s)
　M[u] = t
　ここまでくれば題意の満たす初めての「掛け合わせた指数値のユニークリスト」になので、掛け算回数tとともに保存します。

・return sum(M[n1:])
　iのループが終了したところで、n1以上の掛け算回数の和を返却します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
1582