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

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 155 / コンデンサー回路

静電容量が等しい理想的なコンデンサーのみを使った電気回路がある。複数のコンデンサーを直列または並列に接続してサブユニットを形成し,そのサブユニットを他のコンデンサーやサブユニットと直列または並列に接続してより大きなサブユニットを形成……のようにして最終的な回路を形成する。

この単純な手続きを n 個以下の理想的なコンデンサーに適用し,全体の静電容量が異なる複数の回路を構成することができる。たとえば 60μF のコンデンサーで n=3 の場合は以下のように7通りの異なる静電容量を得ることができる。

f:id:variee:20170330201824g:plain

n 個以下の等価なコンデンサーと上で述べた単純な手続きから得られる全体の静電容量が異なる組み合わせの数を D(n) と書くとすると,D(1)=1, D(2)=3, D(3)=7, ... となる。

D(18)を求めよ。

Problem 155 - Project Euler


題意がわかれば難しくないかな。ただ,最初は間違えてしまいました。

容量 x, y のコンデンサーを並列接続したときの容量は f(x, y)=x+y,直列接続したときの容量は g(x, y)=(1/x+1/y)^(-1) です。n 個のときの容量の集合を C(n) として

C(n+1) = f(C(n), 60) ∪ g(C(n), 60)

で計算すると不正解。すでにある n 個のコンデンサー群の外に1個つけたすだけではなく,中につけたす場合も考えないといけません。たとえば n=4 のとき,「2個を並列接続したものを2つ直列接続する」というケースもありますよね。

C(k) と C(l) の並列接続,直列接続を f(k, l), g(k, l) のようにあらわすと,C(4) は次のようになります。

C(4) = f(1, 3)+f(2, 2)+g(1, 3)+g(2, 2)

実装にあたって Outer が役立ちました。Outer[f, list1, list2] は list1, list2 のすべての組合せについての f を返します。


残る注意点は Flatten (多重リストの平滑化)の位置を間違えないことですね。 はじめは1つの Table で済ませようとしたのですが,Flatten の位置をどういじってもうまくいかなかったので,2つの Table にわけてしのぎました。