Re: [中學] 高斯無窮和
※ 引述《shingai (shingai)》之銘言：
: 題為
: 給定一個正整數 n
: inf
: Σ [(n+2^k)/2^(k+1)] 其中 inf 表正無限大 , [ ] 為高斯符號
: k=0
: ___________________________________________________________
: 想請教
: 這一題要怎麼切割分case討論
: 最後用n表示此總加
: 請高手們分享想法了...
: 推 XII :考慮 n 的二進位! 06/09 16:35
這個看法是這題的關鍵!
這個和式的每一項
其實就是在 n 的二進位右邊數來第 (k+1) 位左邊點上小數點後零捨一入到整數
也就是每一項小數點都會往左移一位二進位
考慮 n 的二進位中在 2^d 位上的 1
它對整個和的貢獻有 d+1 個地方:
k = 0 ~ d-1 時 (即小數點逐步左移的過程中) 它依序貢獻 2^(d-1), 2^(d-2), ..., 1
k = d 時 (即小數點移到這個 1 左邊那一刻) 由於零捨一入, 它貢獻 1
k > d 時這個 1 對總和就沒有貢獻了
以上的貢獻總合 2^(d-1)+2^(d-2)+...+2+1+1 恰好是 2^d
由於每一位的 1 都是如此, 所以原式總和恰為 n
舉個例子: 十進位 75 二進位 1001011
1001011 1001011
100101.1 100101 + 1
10010.11 10010 + 1
1001.011 1001
100.1011 100 + 1
10.01011 10
1.001011 1
.1001011 0 + 1
最左邊這一位的 1 在 75 中在 2^6 位
而在小數點逐步左移時, 它依序代表 2^5, 2^4, ..., 2, 1
在最後一個數當中 (k = 6) 由於零捨一入, 它也對總和貢獻了 1, 總計正好 2^6 = 64
下一個 1 在 75 中在 2^3 位
小數點逐步左移時它依序代表 2^2 = 4, 2^1 = 2, 2^0 = 1
在 k = 3 時小數點移到它左邊了, 此時零捨一入使它對和貢獻 1, 總計也是 2^3 = 8
同樣的 2^1 的 1 跟 2^0 的 1 也分別貢獻了 2^1 = 2 和 2^0 = 1
所以總和就是 75
--
LPH [acronym]
= Let Program Heal us
-- New Uncyclopedian Dictionary, Minmei Publishing Co.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.30.32
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1402312312.A.897.html
推
06/09 21:58, , 1F
06/09 21:58, 1F
討論串 (同標題文章)