摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 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 ;
若還是不懂就從二進制的銜接上面去理解吧 !