奇摩知識+ 找出1~N分別轉成二進制會有多少個1
如果你瞧不起我,請自離
不准看
1->1
2->10
3->11
4->100
5->101
6->110
7->111
8->1000
9->1001
10->1010
11->1011
12->1100
13->1101
14->1110
15->1111
16->10000
17->10001
18->10010
....
發現到一個新的2^K,只是接續上一次的尾巴而已
先定義A(k)是1~2^k轉成2進制的1總和個數 (1<= <=2^k)
a(n)是1~n 轉成2進制的1總和個數 (1<= <=n)
C(M,N)是M抓N的個數(組合)
若只是A的數列,這方面是排列組合以及二項式定理的部份,這方面很好算
首先找出A(k)的快速方法
方法1: 是以下的証明
A(k)= C(k,1)*1+C(k,2)*2+C(k,3)*3...+C(k,k-1)*(k-1)+C(k,k)*k+1
+)C(k,k)*k+C(k,k-1)*(k-1)... +C(k,1)*1
A(k)= (1/2)*k*( C(k,0)+C(k,1)+C(k,2)...+C(k,k) ) +1
A(k)= (1/2)* k * 2^k +1
A(k)= k * 2^(k-1) +1 <= 這樣就能快速算出1~2^k有多少個1了
方法2: 導出遞迴式
A(1)=2 , A(2)=5 , A(3)=13 , A(4)=33 ,A(5)=81
遞洄的找法,就是利用2^k之後頭會多一個 1
個數 個數-1
1->1 1
2->10 1
3->11 2
4->100 1
5->101 2
6->110 2
7->111 3
8->1000 1
9->1001 2 1
10->1010 2 1
11->1011 3 2
12->1100 2 1
13->1101 3 2
14->1110 3 2
15->1111 4 3
16->10000 1 0
是不是重新重複了? 對吧
所以A(k)=2 * A(k-1) + 2^(k-1) +1;
既然遞迴式的找法,已經能夠理解了,那麼看來整個遞迴條件就能看清楚了
假設要求a(n)
a(n)= A(k) + (n-2^k) + a(n-2^k) (在這裡找出2^k<=n,最大的k)
在遞迴求a(n-2^k)
定義a(0)=0 ;
若還是不懂就從二進制的銜接上面去理解吧 !