作者weiyucsie (选择那刻 才算开始)
站内Prob_Solve
标题Re: [问题] 面试遇到的程式问题，现在还想不出来(MTK)
时间Mon Dec 15 15:48:08 2008
稍微有点用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
1F：→ weiyucsie:for(s=0,i=0;t=n>>i;i++) {s+=(t&1?t/2+1:-t/2)<<(i*2)} 12/18 02:29
2F：→ weiyucsie:如果要用回圈的话 加个暂存变数t 大概上面的式子可用 12/18 02:31
3F：→ weiyucsie:s是总和 0加到n (忘了加分号了:p) 12/18 02:33