→ weiyucsie:for(s=0,i=0;t=n>>i;i++) {s+=(t&1?t/2+1:-t/2)<<(i*2)} 12/18 02:29
→ weiyucsie:如果要用迴圈的話 加個暫存變數t 大概上面的式子可用 12/18 02:31
→ weiyucsie:s是總和 0加到n (忘了加分號了:p) 12/18 02:33
稍微有點用divide and conquer的寫法
int tc3(int n) {
if (n == 1) {
return 1;
} else if (n == 0) {
return 0;
} else if (n % 2 == 1) {
return tc3(n/2)*4 + n/2 + 1;
} else {
return tc3(n-1) + n;
}
}
雖然用到遞迴
不過速度好像還不錯
(偶數懶得想 所以就tc3(n-1)+n直接下去)
例如
0 + 1 + 2 + 3 + 4 +5
看成
0 + 2 + 4
1 + 3 + 5
這兩個分別除以2(無條件捨去)
變成
0 + 1 + 2
0 + 1 + 2
然後只要算0 + 1 + 2就可以了
接著就是
(0 + 1 + 2) * 2 = 0 + 2 + 4
(0 + 1 + 2) * 2 = 0 + 2 + 4
考慮奇數的部分級數
每個都要加1
可是5/2如果無條件捨去 會是2 最後一個數字不會加到
所以就n/2完之後 再+1
就變成
(0 + 1 + 2) * 2 = 0 + 2 + 4
(0 + 1 + 2) * 2 + (5/2 + 1) = 1 + 3 + 5
所以就是
tc3(n/2) * 4 + n/2 + 1
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.203.6