作成日 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.の登録商標または商標です。
その他、社名および商品名、システム名称などは、一般に各社の商標または登録商標です。

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