だるまのエクセルVBA トップ > 情報処理技術者試験対策 > 応用情報H25春　問1の解説
作成日　2013/10/27
最終更新日　2013/10/27

応用情報H25春　問1の解説

　応用情報H25春　問1の解説をします。


分野：テクノロジ系
大分類：基礎理論
中分類：基礎理論
小分類：離散数学

1.問題
2.解説


1.問題

　aを正の整数とし，b=a2とする。aを2進数で表現するとnビットであるとき，bを2進数で表現すると高々何ビットになるか。


ア　n＋1　　　イ　2n　　　ウ　n2　　　エ　2n
このページのトップへ

2.解説

　注：問題文にある「高々」というのは、「最高で」という意味です。

　これといった、うまい方法が無いですね。ただ、一部で、「公式を導き出す」-「2.簡単な例で考えてみる」が使えるようです。

◆普通に解く
　実際に、n桁で最大となる数値を2乗して桁数がどうなるか計算します。

　2進数でnビットの最大値は、1111...112ですね（1がn個）。
　これを式変形します。
　　1111...112（※1がn個） = 1000...002（※(n+1)桁。1の後ろに0がn個） - 12
　これを、10進数に直すと、
　　2n - 1
　となります。
　※注：簡単に導出しているように見えますが、実際には簡単な例（n=2のときとか）で確認しています。

　そうしたら、2乗しましょう。
　　(2n - 1)2
　　　　= 22n - 2 * 2n + 1

　これを2進数に直すと、
　　　　= 1000...0002(※(2n+1)桁。1の後ろに0が2n個)
　　　　　- 100..002(※(n+1)桁。1の後ろに0がn個)
　　　　　+ 12
となります。
計算後は、(2n+1)桁よりも小さな値になりますから、2n桁になります。

よって、答えはイです。


◆対数を使って解く（※注：要高校数学）
　高校数学で、10進数の場合ですが、対数と桁数の関係を勉強したと思います。それを使って解きます。

　aを2進数にするとn桁ということは、
　　n > log2 a ≧ n-1
　が成り立ちます（※意味がわからない人は対数を外して考えてください。対数を外すと、「2n > a ≧ 2n-1」です。）。
　※注：簡単に導出しているように見えますが、実際には簡単な例（n=2のときとか）で確認しています。ちゃんとした不等式を出すのに苦労しました。
　　log2 aをlog2 a2とするとどうなるか考えます。
　　log2 a2 = 2 * log2 a
ですから、
　　2n > log2 a2 ≧ 2(n-1)
となることが分かります。

よって、最大は2n桁であり、答えはイです。
Prev Up Next  Top
このページのトップへ

このページの利用によって発生した、いかなる損害について、このホームページの作成者は責任を負いません。
このページの間違いや嘘を見つけた方、このページに書いて欲しい情報がある方はメールをお願いします。

Microsoft 、Windows 、Visual Basic および Excel は米国Microsoft Corporationの米国およびその他の国における登録商標または商標です。
ここではExcel® をエクセル、Visual Basic® for Applications をVBAと表記する場合があります。
Mac 、Mac OS 、Mac OS X は米国Apple Computer,Inc.の登録商標または商標です。
その他、社名および商品名、システム名称などは、一般に各社の商標または登録商標です。

このホームページの作成者はこれらの会社とはいっさい関係がありません。