在有效時間內寫入正整數的方法總數爲2的冪的總和

Question

我一直在尋找Number of ways to write n as a sum of powers of 2，它工作得很好，但我想知道如何提高該算法的運行時效率。它在任何合理的時間內（10秒以內）都不能計算超過〜1000的任何東西。

我假設它與分解成子問題有關，但不知道如何去做。我在想像O（n）或O（nlogn）運行時 - 我確信它可能以某種方式。我只是不知道如何有效地分工。通過Chasefornone

代碼

#include<iostream> 
using namespace std; 

int log2(int n) 
{ 
    int ret = 0; 
    while (n>>=1) 
    { 
     ++ret;  
    } 
    return ret; 
} 

int power(int x,int y) 
{ 
    int ret=1,i=0; 
    while(i<y) 
    { 
     ret*=x; 
     i++; 
    } 
    return ret; 
} 

int getcount(int m,int k) 
{ 
    if(m==0)return 1; 
    if(k<0)return 0; 
    if(k==0)return 1; 
    if(m>=power(2,k))return getcount(m-power(2,k),k)+getcount(m,k-1); 
    else return getcount(m,k-1); 

} 

int main() 
{ 
    int m=0; 
    while(cin>>m) 
    { 
     int k=log2(m); 
     cout<<getcount(m,k)<<endl; 
    } 
    return 0; 
} 

Answer 1

因爲我們正在處理一些基本的權力（在這種情況下2），我們可以很容易地做到這一點在O(n)時間（和空間，如果我們考慮的固定計數尺寸）。

關鍵是分區的生成功能。假設p(n)是寫作n作爲基數b的權力總和的方式的數量。

然後考慮

 ∞ 
f(X) = ∑ p(n)*X^n 
     n=0 

可以寫f爲無限的產品，

 ∞ 
f(X) = ∏ 1/(1 - X^(b^k)) 
     k=0 

，如果一個只想係數達到一定極限l，只需要考慮b^k <= l的因素。

以正確的順序（降序）將它們相乘，在每個步驟中一個都知道，只有係數索引爲整除b^i是非零，等需要僅n/b^k + n/b^(k-1) + ... + n/b + n加法系數的，在總O(n)。

代碼（不是防範溢出較大參數）：

#include <stdio.h> 

unsigned long long partitionCount(unsigned n); 

int main(void) { 
    unsigned m; 
    while(scanf("%u", &m) == 1) { 
     printf("%llu\n", partitionCount(m)); 
    } 
    return 0; 
} 

unsigned long long partitionCount(unsigned n) { 
    if (n < 2) return 1; 
    unsigned h = n /2, k = 1; 
    // find largest power of two not exceeding n 
    while(k <= h) k <<= 1; 
    // coefficient array 
    unsigned long long arr[n+1]; 
    arr[0] = 1; 
    for(unsigned i = 1; i <= n; ++i) { 
     arr[i] = 0; 
    } 
    while(k) { 
     for(unsigned i = k; i <= n; i += k) { 
      arr[i] += arr[i-k]; 
     } 
     k /= 2; 
    } 
    return arr[n]; 
} 

工作速度不夠快：

$ echo "1000 end" | time ./a.out 
1981471878 
0.00user 0.00system 0:00.00elapsed 

Answer 2

一個普遍適用的方法問題，像這樣的緩存中間結果，例如如下：

#include <iostream> 
#include <map> 

using namespace std; 

map<pair<int,int>,int> cache; 

/* 
The log2() and power() functions remain unchanged and so are omitted for brevity 
*/ 
int getcount(int m,int k) 
{ 
    map<pair<int,int>, int>::const_iterator it = cache.find(make_pair(m,k)); 
    if (it != cache.end()) { 
     return it->second; 
    } 
    int count = -1; 
    if(m==0) { 
     count = 1; 
    } else if (k<0) { 
     count = 0; 
    } else if (k==0) { 
     count = 1; 
    } else if(m>=power(2,k)) { 
     count = getcount(m-power(2,k),k)+getcount(m,k-1); 
    } else { 
     count = getcount(m,k-1); 
    } 
    cache[make_pair(m,k)] = count; 
    return count; 
} 

/* 
The main() function remains unchanged and so is omitted for brevity 
*/ 

原始程序（我已經叫nAsSum0）的結果是：

$ echo 1000 | time ./nAsSum0 
1981471878 
59.40user 0.00system 0:59.48elapsed 99%CPU (0avgtext+0avgdata 467200maxresident)k 
0inputs+0outputs (1935major+0minor)pagefaults 0swaps 

對於版本緩存：

$ echo 1000 | time ./nAsSum 
1981471878 
0.01user 0.01system 0:00.09elapsed 32%CPU (0avgtext+0avgdata 466176maxresident)k 
0inputs+0outputs (1873major+0minor)pagefaults 0swaps 

...都在Cygwin下的Windows 7 PC上運行。因此，帶有緩存的版本對於time來說太準確，而原始版本需要大約1分鐘才能運行。