「プロジェクトオイラー解説問199」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー解説問199 - (2013/12/11 (水) 12:52:37) のソース

*Problem 199 「反復円充填」 †
----
**問題
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20199
3つの半径の等しい円が, 1つのもっと大きい円の中にあり, 各円は他の円とお互い接している. ただし中の円はお互いが重ならない. 4つのすき間があり, これを繰り返し接する円で埋めていく.

#ref(e199.gif)
各ステップで, 全てのすき間にそれぞれ最大の円を置いていき, 結果として次のステップにはさらにすき間が増えていく. 3ステップ後には上の図のようになる. 108のすき間ができ, 円で埋められていない面積の比率は10進8桁に四捨五入して 0.06790342 となる.

10ステップ後に円で埋まっていない面積の比率はいくらか？
10進数8桁に四捨五入し, x.xxxxxxxx という形で回答を入力せよ.


----
用語定義
円のサイズ＝円の半径や大きさと考えてください。
----
解法
まず答えの式を立てます。
(一番大きな円の面積-描かれる円の面積の合計)/一番大きな円の面積が答えなので、

計算するために描かれる円の面積の合計を考えてみます。

この問題は図をよく見て規則性を探すことで綺麗に解くことができます。
まず最初の３つの円の面積は幾何計算で簡単に求まります。
つぎにそれ以外の円の面積を求めましょう。


例として示された図を色分けしてみます。
#ref(e199_2.gif)
少し配色センスを疑われるかもしれませんがわかりやすさ重視で塗りました。
-A ピンクは一番大きな円に内接し、２つの互いに外接する円の間にその２つの円と外接する形で新しい小さな円が描かれています。
-B 水色は３つの互いに外接した円の間にそれら３つと外接する形でより小さな円が描かれています。
そして図は最初の３つの円を除きこの２種類しかなく、これ以後小さな円を派生(生成)させていっても２種類以外派生しません。
Aをoutな円。
Bをinな円とします。
outな円もinな円も&bold(){３つの親となる円から生まれる}（形や位置）が決定されることを確認してください。


次に生成される円の生成パターンを考えてみます。
outの円が描かれた場合そのoutから派生して描かれる円はoutな円がその左右に、円の中心方向にinな円が新しく派生します。
またinの円はinの円の周りに3つinな円が描かれます。



**outな円の派生。
#ref(e199_3.gif)
一番大きな円をＲ0としＲ1とＲ２の間にＲ３が描かれたとします。
R3から派生する円はR4、R6、R7となります。
次の円のサイズを計算する再帰関数を考えます。
実はoutな円もinな円も親となる３つの円のサイズだけから次の円のサイズが決まり座標は無視できます。(このことはあとで説明します)
３つの親となる円から周りの隙間に描かれる小さな円のサイズを決定する関数を
Ru=inR(Ri,Rj,Rk)
Ru=outR(Ri,Rj,Rk)
どちらも親となる３つの円のサイズを受け取りinRはinタイプの円をoutRはoutタイプの円のサイズを返す関数です。


ここの図では
R7=inR(R1,R2,R3)
R4=outR(R1,R2,R3)
R6=outR(R1,R3,R2)
と次の円のサイズが決定されます。


少し手順が前後しましたがR1,R2,R3の円が決定された場合、Ｒ３から派生する円は
R4=outR(R0,R1,R3)
R6=outR(R0,R3,R2)
R7=inR(R1,R2,R3)
と計算されます。


Ｒ３は円Ｒ0Ｒ1Ｒ２の３つからoutR(R0,R1,R2)と派生します。
Ｒ4やＲ6でもＲ３と同様の派生パターンを繰り返します。

R4の周りは
outR(R0,R1,R4)
outR(R0,R4,R3)
inR(R1,R4,R3)の３つの円が派生しますし。

R6の周りでは
outR(R0,R3,R6)
outR(R0,R6,R2)
inR(R2,R3,R6)
と円が派生していきます。
外周ではこの派生パターンが連続して続き、３つに分岐する単純な再帰関数で表現できます。


----
***outRを一般化すると
Rk=outR(R0,Ri,Rj)
ならRkの周りで生成する円は
outR(R0,Ri,Rk)
outR(R0,Rk,Rj)
inR(Ri,Rj,Rk)
となりこの単純な漸化式がどこまでも続きます。
outＲは一番外側の外周にできる円でinは内側にできる円です。


----
***３つの円の間にできるinな円の派生

#ref(e199_4.gif)
また３つの円に囲まれたinな円からの派生は。
（これは例なので円には適当な番号を割り振っています）

円R4は円Ｒ1，Ｒ２，Ｒ３から派生し。
円Ｒ4からは
R5=inR(R1,R4,R3)
R6=inR(R2,R4,R3)
R7=inR(R2,R1,R4)
と派生しこれ以後も同じパターンでより小さな円が派生します。

これも再帰関数で表現できます。

これによって全円の派生パターンを網羅したことになります。
----
***小纏め
inな円からはinな円が３つ周りには派生して描かれ。
outな円からはoutな円が２つとinな円が一つ描かれることが判明し。
その規則性はとても単純で再帰関数で表現可能なことが判明しました。

----
***描かれていくより小さな円のサイズの決定
次に描かれていく小さな円は親となる３つの円の半径だけから決まることを書いてみます。
inR関数を考えてみます。
#ref(e199_5.gif)
inRでは３つの外接する円の隙間に新しい円の半径が決定されます。
A,C,Eの３つの円の隙間に新しい円Ｈが派生する場合のＨの半径を計算する方法を考えてみましょう。

計算しやすいよう
一つの円Ａを原点にＣをＸ軸にとるとＥの位置を反時計回りな位置に決めると描かれる図は一意に決まります。
隙間に円Ｈが描かれますが、円Ｈはサイズが一意となります。
この図から派生する小さな円のサイズを計算するには大きな三つの円のサイズだけからいえることがわかります。
さてＨを求める場合ですが
円ＡＣＥの座標円のサイズからＨのサイズを決める３つの連立方程式を解けば答えが出てきます。
かなり複雑な式変形になるので式変形を自動でしてくれるソフトを使うとよいでしょう。


Ｈの周りに派生する３つの円も
inR(H,A,E)なら
-点Ｈを原点にとりＡをＸ軸にとれば次に派生する円のサイズが計算できます。
inR(H,A,C)も同様に
-点Ｈを原点にとりＡをＸ軸にとれば次に派生する円のサイズを計算できます。
inR(H,C,E)も
-点Ｈを原点にとりＣをＸ軸状にとれば次に派生する円のサイズを計算できます。

これ以後に派生するより小さな円も同じ手順でもとまります。
outな円もすこし計算方法や図が変わりますがinな円と同じ手法手順で順番に派生する円のサイズを計算できます。

----
***纏め
ここまで判明したらあとは自力で考えられることと思います。
私の解説がよくわからなかった場合。
この問題は文章で考えるより図とよくにらめっこしたほうが直感的にわかるはずです。
なので図の意味をよく考えてください。