uva 763 Fibinary Numbers

本文主要是介绍uva 763 Fibinary Numbers，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题：
The standard interpretation of the binary number 1010 is 8 + 2 = 10. An alternate way to view the sequence “1010” is to use Fibonacci numbers as bases instead of powers of two. For this problem, the terms of the Fibonacci sequence are:
1, 2, 3, 5, 8, 13, 21, …
Where each term is the sum of the two preceding terms (note that there is only one 1 in the sequence as defined here). Using this scheme, the sequence “1010” could be interpreted as 1·5+0·3+1·2+0·1 = 7.
This representation is called a Fibinary number.
Note that there is not always a unique Fibinary representation of every number. For example the number 10 could be represented as either 8 + 2 (10010) or as 5 + 3 + 2 (1110). To make the Fibinary
representations unique, larger Fibonacci terms must always be used whenever possible (i.e. disallow 2 adjacent 1’s). Applying this rule to the number 10, means that 10 would be represented as 8+2 (10010).
Write a program that takes two valid Fibinary numbers and prints the sum in Fibinary form.
Input
The input file contains several test cases with a blank line between two consecutive.
Each test case consists in two lines with Fibinary numbers. These numbers will have at most 100 digits.
Output
For each test case, print the sum of the two input numbers in Fibinary form. It must be a blank line between two consecutive outputs.
Sample Input
10010
1
10000
1000
10000
10000
Sample Output
10100
100000
100100

中文：
给你两个斐波那契进制序列，让你求这个数的和，结果也用斐波那契序列表示，要求不能有两个1相邻。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1000;/*精度位数*/
/*(必选)类与基础功能定义，用法类似于unsigned(非负)*/
class bign
{friend istream& operator>>(istream&,bign&);/*输入运算符友元*/friend ostream& operator<<(ostream&,const bign&);/*输出运算符友元*/friend bign operator+(const bign&,const bign&);/*加号运算符友元*/friend bign operator*(const bign&,const bign&);/*乘号运算符友元*/friend bign operator*(const bign&,int);/*高精度乘以低精度乘法友元*/friend bign operator-(const bign&,const bign&);/*减号运算符友元*/friend bign operator/(const bign&,const bign&);/*除法运算符友元*/friend bign operator%(const bign&,const bign&);/*模运算符友元*/friend bool operator<(const bign&,const bign&);/*逻辑小于符友元*/friend bool operator>(const bign&,const bign&);/*逻辑大于符友元*/friend bool operator<=(const bign&,const bign&);/*逻辑小于等于符友元*/friend bool operator>=(const bign&,const bign&);/*逻辑大于等于符友元*/friend bool operator==(const bign&,const bign&);/*逻辑等符友元*/friend bool operator!=(const bign&,const bign&);/*逻辑不等符友元*/private:int len,s[maxn];public:bign(){memset(s,0,sizeof(s));len=1;}bign operator=(const char* num){int i=0,ol;ol=len=strlen(num);while(num[i++]=='0'&&len>1)len--;memset(s,0,sizeof(s));for(i=0;i<len;i++)s[i]=num[ol-i-1]-'0';return *this;}bign operator=(int num){char s[maxn];sprintf(s,"%d",num);*this=s;return *this;}bign(int num){*this=num;}bign(const char* num){*this=num;}string str() const{int i;string res="";for(i=0;i<len;i++)res=char(s[i]+'0')+res;if(res=="")res="0";return res;}};
/*(可选)基本逻辑运算符重载*/
bool operator<(const bign& a,const bign& b)
{int i;if(a.len!=b.len)return a.len<b.len;for(i=a.len-1;i>=0;i--)if(a.s[i]!=b.s[i])return a.s[i]<b.s[i];return false;}
bool operator>(const bign& a,const bign& b){return b<a;}
bool operator<=(const bign& a,const bign& b){return !(a>b);}
bool operator>=(const bign& a,const bign& b){return !(a<b);}
bool operator!=(const bign& a,const bign& b){return a<b||a>b;}
bool operator==(const bign& a,const bign& b){return !(a<b||a>b);}
/*(可选)加法运算符重载*/
bign operator+(const bign& a,const bign& b)
{int i,max=(a.len>b.len?a.len:b.len),t,c;bign sum;sum.len=0;for(i=0,c=0;c||i<max;i++){t=c;if(i<a.len)t+=a.s[i];if(i<b.len)t+=b.s[i];sum.s[sum.len++]=t%10;c=t/10;}return sum;}
/*(可选)乘法运算符重载(高精度乘高精度)*/
bign operator*(const bign& a,const bign& b)
{int i,j;bign res;for(i=0;i<a.len;i++){for(j=0;j<b.len;j++){res.s[i+j]+=(a.s[i]*b.s[j]);res.s[i+j+1]+=res.s[i+j]/10;res.s[i+j]%=10;}}res.len=a.len+b.len;while(res.s[res.len-1]==0&&res.len>1)res.len--;if(res.s[res.len])res.len++;return res;}
/*高精度乘以低精度(注意:必须是bign*int顺序不能颠倒,要么会与高精度乘高精度发生冲突*/
bign operator*(const bign& a,int b)
{int i,t,c=0;bign res;for(i=0;i<a.len;i++){t=a.s[i]*b+c;res.s[i]=t%10;c=t/10;}res.len=a.len;while(c!=0){res.s[i++]=c%10;c/=10;res.len++;}return res;}
/*(可选)减法运算符重载*/
bign operator-(const bign& a,const bign& b)
{bign res;int i,len=(a.len>b.len)?a.len:b.len;for(i=0;i<len;i++){res.s[i]+=a.s[i]-b.s[i];if(res.s[i]<0){res.s[i]+=10;res.s[i+1]--;}}while(res.s[len-1]==0&&len>1)len--;res.len=len;return res;}
/*(可选)除法运算符重载(注意:减法和乘法运算和>=运算符必选)*/
bign operator/(const bign& a,const bign& b)
{int i,len=a.len;bign res,f;for(i=len-1;i>=0;i--){f=f*10;f.s[0]=a.s[i];while(f>=b){f=f-b;res.s[i]++;}}while(res.s[len-1]==0&&len>1)len--;res.len=len;return res;}
/*(可选)模运算符重载(注意:减法和乘法运算和>=运算符必选)*/
bign operator%(const bign& a,const bign& b)
{int i,len=a.len;bign res,f;for(i=len-1;i>=0;i--){f=f*10;f.s[0]=a.s[i];while(f>=b){f=f-b;res.s[i]++;}}return f;}
/*(可选)X等运算符重载(注意:X法必选)*/
bign& operator+=(bign& a,const bign& b)
{a=a+b;return a;}
bign& operator-=(bign& a,const bign& b)
{a=a-b;return a;}
bign& operator*=(bign& a,const bign& b)
{a=a*b;return a;}
bign& operator/=(bign& a,const bign& b)
{a=a/b;return a;}
/*可选前缀++/--与后缀++/--(注意:加法必选)*/
bign& operator++(bign& a)
{a=a+1;return a;}
bign& operator++(bign& a,int)
{bign t=a;a=a+1;return t;}
bign& operator--(bign& a)
{a=a-1;return a;}
bign& operator--(bign& a,int)
{bign t=a;a=a-1;return t;}
istream& operator>>(istream &in,bign& x)
{string s;in>>s;x=s.c_str();return in;}
ostream& operator<<(ostream &out,const bign& x)
{out<<x.str();return out;}
bign fib[130];
bign get_num(string a)
{bign tmp=0;for(int j=1,i=a.size()-1;i>=0;i--,j++){if(a[i]=='1')tmp+=fib[j];}return tmp;
}
fstream in,out;
int find_max(int s,int e,bign tar)
{for(int i=e;i>=s;i--){if(fib[i]<=tar)return i;}
}
int main()
{ios::sync_with_stdio(false);
//    in.open("in.txt");
//    out.open("out.txt");fib[1]=1,fib[2]=2;for(int i=3;i<=120;i++)fib[i]=fib[i-2]+fib[i-1];bign a,b,tmp;string s1,s2;vector<int> ans;int t=0;while(cin>>s1>>s2){if(t++)cout<<endl;ans.clear();tmp=0;tmp+=get_num(s1);tmp+=get_num(s2);int inx=120;while(true){int ind=lower_bound(fib+1,fib+inx,tmp)-fib;if(fib[ind]==tmp){tmp-=fib[ind];ans.push_back(ind);break;}else{tmp-=fib[ind-1];ans.push_back(ind-1);if(tmp==0)break;}}/*while(true){int ind=find_max(1,inx,tmp);tmp-=fib[ind];ans.push_back(ind);if(tmp==0)break;inx=ind;}*/bool mark[501];int ter=-1;memset(mark,0,sizeof(mark));for(auto x:ans){if(x>ter)ter=x;mark[x]=1;}for(int i=ter;i>=1;i--)cout<<mark[i];if(ans.size()==1&&ans.back()==0)cout<<0;cout<<endl;}
//    in.close();
//    out.close();return 0;
}