PKU : 2116 - Death to Binary?

実装問題

問題概要

http://poj.org/problem?id=2116

二進数における'1'の重みが, フィボナッチ数列の値に変化した値(フィボナッチ進数(?))が２つ入力されます.
これらの足し算を行い, canonical representationで出力してください.
canonical representationとは, フィボナッチ進数で表すように, 大きい値から優先して変換した数値です.

アルゴリズム

単純に実装するだけです.
ちなみに, フィボナッチ数列の40番目までなら, 整数値9ケタほどなので, int型で十分です.

プログラム

int fib[44];

int toInt(string s){
  int res = 0;
  int n = s.length();
  for(int i=n-1;i>=0;i--){
    if(s[i] == '1'){
      res += fib[n-i-1];
    }
  }
  return res;
}

string toCano(int x){
  string res;
  bool flg = false;

  for(int i=43;i>=0;i--){
    if(fib[i] <= x){
      x -= fib[i];
      flg = true;
      res += "1";
    }
    else if(flg){
      res += "0";
    }
  }

  if(!flg) res = "0";

  return res;
}

int main(void){
  fib[0] = 1;
  fib[1] = 2;

  for(int i=2;i<45;i++){
    fib[i] = fib[i-1] + fib[i-2];
  }

  string a,b;
  while(cin>>a>>b){
    int ai = toInt(a);
    int bi = toInt(b);
    string ans = toCano(ai + bi);
    int n = ans.length();

    a = toCano(ai);
    b = toCano(bi);

    cout<<"  ";
    rep(i,n-a.length()) cout<<" ";
    cout<<a<<endl;

    cout<<"+ ";
    rep(i,n-b.length()) cout<<" ";
    cout<<b<<endl;

    cout<<"  ";
    rep(i,n) cout<<"-";
    cout<<endl;

    cout<<"  ";
    cout<<ans<<endl<<endl;
  }
}