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

methaneのブログ

このブログに乗せているサンプルコードはすべてNYSLです。

亀の子算の他人の回答

http://sfuhiro.seesaa.net/article/22247501.html
で同じ問題をこんな計算式で解いていた。

答えは 56 + (56-11)/(6-1) = 65 で65匹でしょうね.

僕の計算式では

(56 - 11) * 6 / (6 - 1) + 11

さらに一般化されていた。

一般化すると,「d分木が N 個与えられたとき,葉の総数がpとする.このときの総節点数は?」で,答えは p+(p-N)/(d-1) ということでしょうか.

僕の計算式を、同じ文字を使って一般化するとこうなる。

(p - N) * d / (d - 1) + N

もちろん、この計算式は等価で、変形すれば同じになる。

# 僕の式を単項式にまとめる。
(p - N) * d / (d - 1) + N
   = ((p - N) * d + Nd - N) / (d - 1)
   = (pd - Nd + Nd - N) / (d - 1)
   = (pd - N) / (d - 1)

# 少爺さんの式を単項式にまとめる。
p+(p-N)/(d-1)
   = (pd - p + p - N) / (d - 1)
   = (pd - N) / (d - 1)

さて、数学的に正しければもちろん等価な式になるのだが、最初の式の形を見て、どうやって問題を解いたかを考えると面白い。
残念ながら少爺さんはこの式をどうやって導いたかは書かれていないのだが、式を分解するとこうなる。

全nodeの数 := leafの数+leaf以外のnodeの数
leafの数 = p
leaf以外のnodeの数 := leafとrootの数の差 / leaf以外のnode1つあたりの枝増加数
leafとrootの数の差 = p - N
leaf以外のnode1つあたりの枝増加数 = d - 1

と言うことで、葉の数に、葉の数が合うに至る分岐の数を加えている。

分岐の数に着目した少爺さん式の方が正攻法っぽくて、兄弟(親が同じnode)に着目した僕の式の方が裏技かな。でも、僕の考え方の方が、小学生が納得するのにかかる時間が短い気もする。実は少爺さんはもっと簡単な考え方であの式を導いたという可能性もあるけど。