ここから本文です

0以上の整数nに対して、f(n)は次を満たすもとのする。 f(0)=0 f(n)=f(n/2) (...

matsu100521さん

2016/6/1221:32:10

0以上の整数nに対して、f(n)は次を満たすもとのする。
f(0)=0
f(n)=f(n/2) (nが偶数)
f((n-1)/2)+1 (nが奇数)
(1)0以上の整数kに対して、f(2^k)、f((2^k)-1)を求めよ


(2)f(69)を求めよ。
(3)f(n)=3となるnを小さいものから順に4つ求めよ。
(4)2^2004≦n≦(2^2005)-1とするとき、f(n)=4となるnのうち3番目に大きいものを求め、n=a×2^bの形で表せ
という問題です。解答は、(1)1、k (2)3 (3)7、11、13、14 (4)57×(2^1999)です。解答がお分かりになる方は教えてください。よろしくお願いいたします。

閲覧数:
86
回答数:
1

違反報告

ベストアンサーに選ばれた回答

tar0_puzzleさん

2016/6/1221:53:37

二進数を考えると分かりやすいです
nを二進法で表すとき各桁が上から順に
b[k] b[k-1] ... b[1] b[0]
と並ぶとします
一の位b[0]が0のときnは偶数, 1のときnは奇数です
よって
f(n)は
f(b[k] b[k-1] ... b[1] 0) = f(b[k] b[k-1] ... b[1])
f(b[k] b[k-1] ... b[1] 1) = f(b[k] b[k-1] ... b[1]) + 1
です
これをさらに
f(b[k] b[k-1] ... b[1] 0) = f(b[k] b[k-1] ... b[1]) + 0
f(b[k] b[k-1] ... b[1] 1) = f(b[k] b[k-1] ... b[1]) + 1
と表してみれば
これは結局
f(b[k] b[k-1] ... b[1] b[0]) = f(b[k] b[k-1] ... b[1]) + b[0]
とまとめられます

したがって
f(n) = (nを二進数で表したときの1の個数)
です

(1)
2^kは一番上の桁が1で他は全て0だからf(2^k)=1
(2^k)-1は1がk個並ぶからf((2^k)-1)=k

(2)
69=64+4+1=(2^6)+(2^2)+1は二進法で表すと1が3個並ぶから
f(69)=3

(3)
f(n)=3となるn
つまり, 1が3個含む二進数を小さい順に並べればよいです
二進法で111のn=7
二進法で1011のn=11
二進法で1101のn=13
二進法で1110のn=14

(4)
2^2004≦n≦(2^2005)-1とするとき、f(n)=4となるnのうち3番目に大きいものを求め、n=a×2^b

二進法で表して1を4個含むものは同じ桁なら
1111000...0の形が一番大きい
1110100...0の形が二番目に大きい
1110010...0の形が三番目に大きい

(2^2005)-1は1が2005個並ぶ数だから
1110010...0は11001の後ろに0が1999個並ぶ数です
二進法で111001は十進法で57
二進法では2倍するごとに0が1つ増えるから
求めるnは
n = 57×2^1999
です

  • tar0_puzzleさん

    2016/06/1221:54:45

    最後の下から6行目を訂正します

    訂正前
    1110010...0は11001の後ろに0が1999個並ぶ数です

    訂正後
    1110010...0は111001の後ろに0が1999個並ぶ数です

返信を取り消しますが
よろしいですか?

  • 取り消す
  • キャンセル

質問した人からのコメント

2016/6/18 22:01:17

解答ありがとうございました。

この質問につけられたタグ

タグランキングを見る

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問や知恵ノートは選択されたID/ニックネームのMy知恵袋で確認できます。