整数在Fibonacci序列的二进制表示

（在买买提看到的MS面试题）
Fibonacci序列：1,2,3,5,8,13,...
F(n)=F(n-1)+F(n-2),F(0)=1,F(1)=2
任意正整数n，可以表示为Fibonacci序列的和，例如：10=8+2，记为10010；17=13+3+1，记为100101；同时10=5+3+2，记为01110。试给出所有可能的序列组合。

下面为我的代码实现：

#include
#include
#include

using namespace std;

// construct Fibonacci series
void
construct_fibonacci(vector &set, int num)
{
  int f0 = 1;
  int f1 = 2;

  set.push_back(f0);
  set.push_back(f1);

  int f2;
  do {
    f2 = f0 + f1;
    set.push_back(f2);

    f0 = f1;
    f1 = f2;
  } while (num > f2);

  if (f2 > num)
    set.pop_back();
}

inline void
clear_bit(int *bit, size_t n)
{
  for (size_t i = 0; i < n; ++i)
    bit[i] = 0;
}

bool
rec_find_fib(int num, size_t pos, const vector &set, int *bit)
{
  if (1 == num) {
    bit[0] = 1;
    return true;
  }
  if (2 == num) {
    bit[1] = 1;
    return true;
  }

  size_t tpos = pos;
  while (set[tpos] > num)
    --tpos;
  bit[tpos] = 1;
  if (num == set[tpos])
    return true;
  else {
    num -= set[tpos];
    if (num == set[tpos])
      return false;
    return rec_find_fib(num, tpos, set, bit);
  }
}

void
output_fib(size_t nset, int *bit)
{
  for (int i = (int)nset - 1; i >= 0; --i)
    cout << (bit[i] ? "1" : "0");
  cout << endl;
}

// use pos for remove duplicate output
void
rec_pos_fib(int *bit, size_t nset, size_t pos)
{
  int pos_1 = -1;
  int num_0 = 0;
  bool count = false;

  for (int i = (int)pos; i >= 0; --i) {
    if (bit[i]) {
      count = true;
      pos_1 = i;
      num_0 = 0;
    } else if (count) {
      ++num_0;

      if (2 == num_0) {
        // two zero encountered, convert "100" to "011"
        bit[pos_1] = 0;
        bit[pos_1-1] = 1;
        bit[pos_1-2] = 1;

        output_fib(nset, bit);

        // recursively try
        rec_pos_fib(bit, nset, (size_t)i);

        // restore
        bit[pos_1] = 1;
        bit[pos_1-1] = 0;
        bit[pos_1-2] = 0;

        count = false;
        num_0 = 0;
      }
    }
  }
}

void
find_fib(const vector &set, int num, size_t nset, int *bit)
{
  clear_bit(bit, nset);

  bool res = rec_find_fib(num, nset - 1, set, bit);
  if (res)
    output_fib(nset, bit);

  rec_pos_fib(bit, nset, nset - 1);
}

main()
{
  int num;
  cin >> num;
  if (num < 3)
    exit(1);

  // construct Fibonacci set
  vector set;
  construct_fibonacci(set, num);

  size_t nset = set.size();
  int *bit = new int[nset];

  find_fib(set, num, nset, bit);

  delete [] bit;
}