Re: [問題] 面試遇到的程式問題，現在還想不出來(MTK)
稍微有點用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
→
12/18 02:29, , 1F
12/18 02:29, 1F
→
12/18 02:31, , 2F
12/18 02:31, 2F
→
12/18 02:33, , 3F
12/18 02:33, 3F
討論串 (同標題文章)
完整討論串 (本文為第 15 之 16 篇)：