Re: [中學] 高斯無窮和
Here is another solution that uses the identity
[x+ 1/2]=[2x]-[x], which is a variant of a special case of the so-called
Hermit's identity:
n-1
[nx]= Σ [x+ i/n].
i=0
Thus, we see that Σ [ (x+2^k)/2^(k+1)] = Σ ([x/2^k] - [x/2^(k+1)])
k>=0 k>=0
= [x].
PS. Note that x is not necessary to be an integer.
※ 引述《LPH66 (1597463007)》之銘言：
: ※ 引述《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
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.76.10
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1402327442.A.F89.html
推
06/10 01:14, , 1F
06/10 01:14, 1F
→
06/10 01:14, , 2F
06/10 01:14, 2F
推
06/10 11:51, , 3F
06/10 11:51, 3F
討論串 (同標題文章)