- ベストアンサー
binary decision treeの証明
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
左の子の内部節数をm、右の子の内部節数をnとして新しい木を作ると、 左の外部節数≦m+1 右の外部節数≦n+1 だから、 (新しい木の外部節数)≦m+n+2=(m+n+1)+1=(新しい木の内部節数)+1
その他の回答 (2)
- arrysthmia
- ベストアンサー率38% (442/1154)
普通に考えると、外部節の最大数は、n+2。 n=1 の場合を図示して御覧。
- Tacosan
- ベストアンサー率23% (3656/15482)
decision は全然関係なくて binary tree の話ですね. どのように binary (decision) tree を定義しているのか分かりませんが, 普通の定義に従って帰納法を使うと #1 の通り. ただしこれではもちろん完答ではありません. ところで「上記にも記載してますが」ってなんだ.
関連するQ&A
- 数学の証明問題（数学的帰納法）
数学の証明問題の質問です。 以下の２つを数学的帰納法を使い証明するのですが 成り立つ時と成り立たないときがあり どういう風に書けばいいのかわかりません。 わかる方、回答、解説をお願いします。 Use Mathematical Induction to prove 3＾n < n! for integers n >= 7. n^3 > n^2 + 3 for all n >= 2. ※アメリカで授業をとっているため問題文が英語です。
- ベストアンサー
- 数学・算数
- 「e」が絡んだ不等式証明
「自然数nについて、次の不等式が成り立つことを求めよ。 n・log(n)-n+1 ≦ log(n!) ≦ (n+1)log(n+1)-n 」 という問題で、最初は素直に左辺-右辺≧0を使って示しました。 その後、別解として数学的帰納法を用いた証明に挑みました。 n=1のときは楽勝ですが、n=kで成り立つことを仮定した後の「n=k+1」のときに、式変形でつまずきました。今回の質問は、その最後の大小関係の評価についてです。（以下、式はn=k+1のときのもの） log{(k+1)!}-(k+1)log(k+1)+(k+1)-1 =log(k+1)+log(k!)-(k+1)log(k+1)+k ≧k・logk-k+1-k・log(k+1)+k =1-log(1+1/k)^k ・・・・・・・・・・・・(1) (1)をみた時、「あ、これってeの定義式に似てるな」と思い、もしかして (1)≧1-log(e)=0 ・・・・・・・・・・・・・(2) でも言えるのかと思ったのですが、 疑問I： だからといって果たして(2)で等号が言えるのか？ 疑問II：そもそも、lim[x→∞](1+1/x)^x=e は、eより大きい数からeに近付くのか？eより小さい数からeに近付くのか？そしてlim[x→-∞](1+1/x)^x=e では？ 上の疑問について、答が出せる方、宜しくお願いします。
- ベストアンサー
- 数学・算数
- Linuxルータの構築
CentOS5.4にて、Linuxルータを構築しようと考えています。 そこで、NICを新たに１枚購入して構築を進めているのですが、うまくいきません。 ネットワークの構成は、 外部 ------ ルータ(192.168.1.1)--(192.168.1.5)linuxルータ(192.168.2.1)--クライアント(192.168.2.3) 設定方法は、CentOSのGUIで行ったもので、外部側 (eth0)は 上記のipとデフォルトゲートウェイ(192.168.1.1)を設定し、内部側(eth1)は、上記のipとデフォルトゲートウェイに(192.168.1.5)を設定しています。 そして、iptablesには、 ----- setiptables.sh ----- external_ip='192.168.1.0/24' internal_ip='192.168.2.0/24' my_external_ip='192.168.1.5' my_internal_ip='192.168.2.1' eth_external='eth0' eth_internal='eth1' iptables -t filter -F iptables -t nat -F iptables -t mangle -F iptables -t filter -X iptables -t nat -X iptables -t mangle -X iptables -t nat -A POSTROUTING -o $eth_external -s $internal_ip -j MASQUERADE iptables -t nat -A POSTROUTING -o $eth_internal -s $external_ip -j MASQUERADE --------- このように設定しています。 この環境でクライアントからpingしてみたところ、192.168.1.5には到達できるのですが、外部には到達することができません。 つたない説明で申し訳ありませんが、アドバイス頂ければ幸いです。 分かりにくいところがあれば言っていただければ、補足説明させていただきます。 よろしくお願いします。
- ベストアンサー
- Linux系OS
- クロックの同期について
伝送装置とルータでクロック同期をとりたいと考えています。 伝送装置はexternal、ルータはinternalでクロック同期を取っているため、同期がとれていないといわれました。 この場合、同期をとるためには、ルータが伝送装置へクロック同期、もしくは伝送装置がルータへクロック同期を取りに行けば同期がとれるのでしょうか。 クロック同期のintenl(内部クロック)、external(外部クロック)、Line抽出の概要についてもよくわかっていないため、ご教授いただkれば幸いです。また、クロック同期についての説明したいるURLがありましたら、併せて教えていただければ幸いです。
- 締切済み
- ネットワーク
- 数学の証明問題
数学の論証問題の解き方を教えてください。『次のような条件を満たす集合Aがある。 (i)Aの要素は正の実数である。 (ii)Aは少なくとも2つの要素をもつ。 (iii)p∈A、q∈Aでp≠qならば、 p/q∈Aである。 このとき、次の(1)、(2)の問いに答えるという問題です。 (1)Aは無数に多くの要素をもつことを示す。 (2)1 ∈A、2 ∈Aであるとき、全ての整数nに対して、2^n ∈Aであることを示す。』 以下に自分の解いた過程を書いておきます。 間違っている箇所などのご指摘をお願いします。 (1)Aの要素の個数が有限個であると仮定する。この時、最大の要素をa、最小の要素をbとする。a>1のとき、b/a∈Aなのでbより小さい要素がある。a<1のとき、b/a∈Aなのでaより大きい要素がある。これは最大をa、最小をbとしたことと矛盾する。したがって、Aは無数に多くに要素を持つ。(証明終) (2)数学的帰納法で示す。n=1のとき、2∈Aで成立する。n=kのときに成立すると仮定すると、2^k∈A、2∈Aより、2^k/2=2^(k－1)∈A k→∞で考えていいので全ての整数nについて2^n∈Aが成立する。(証明終)
- ベストアンサー
- 数学・算数
- 【問題】箱に2個の赤いボールとn-2個の白いボールが入っている。(n=
【問題】箱に2個の赤いボールとn-2個の白いボールが入っている。(n=3,4,5,・・・) （１）略 （２）箱から3個のボールを取り出すとき、2個が白、1個が赤となる確率をP(n)とおく。このとき、P(n)={6(n-3)}/{n(n-1)}であることを証明せよ。ただし、どのボールも取り出される確率は等しいとする。 （３）P(n)-P(n+1)を求めよ。 （４）p(n)が最大になる確率を求めよ。 （２）からわかりません＾＾； 数学的帰納法を使おうとしてn=3のとき成り立つ。として、次にn=kのとき成り立つと仮定して、n=k+3のとき成り立つことを示そうとしたのですが。。。できません＾＾； どなたかよろしくお願いします。
- ベストアンサー
- 数学・算数
- 分数の和の最大値について
次の問題（(2)から）が分かりません。解答をよろしくお願いします。 n個の正の整数x(1)，x(2)，……，x(n)が不等式 u=1/x(1)+1/x(2)+……+1/x(n)<1 を満たしているとき，次の問いに答えよ。 (1)n=2,3,4に対して，uの最大値を求めよ。 (2)一般のnに対して，uの最大値を与える数列x(n)の一般項を類推せよ。 (3)数学的帰納法により，(2)の類推が正しいことを示せ。 合っているかどうか少し不安ですが，(1)の答えは次のようになりました。 (1)n=2のとき，5/6 n=3のとき，41/42 n=4のとき，1805/1806
- 締切済み
- 数学・算数
