本文主要是介绍POJ2116题解（1.低阶：贪心 2.高阶：利用斐波那契的规律），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.题目分析：
我这里介绍一种最简单的方法：就是将字符串转换成整数并将整数转换成字符串。将整数转换为字符串的时候有一个技巧就是从大往小去减权重，这样可以避免连续的1。这里说一下为什么：
为了避免前导零的情况，我们需要一直找权值小于等于整数的，找到一个就减去，那么无可非议它前面的那个权值是大于整数的，这个权值小于等于整数，说明下一个权值一定是大于整数减去当前的权重，所以一定不会出现连续1的情况。附上代码！
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int f[41];
void init()
{f[0]=1;f[1]=2;for(int i=2;i<41;i++){f[i]=f[i-1]+f[i-2];}return;
}
long long sum(string s)
{ long long ans=0;reverse(s.begin(),s.end());for(int i=0;i<s.size();i++){ans+=(s[i]-'0')*f[i];}return ans;
}
string get(long long a)
{string ans;int i=40;while(i>=0&&f[i]>a){i--;}if(i==-1)ans+='0';while(i>=0&&a>=0){if(a>=f[i]){ans+='1';a-=f[i];}elseans+='0';i--;}return ans;
}
int main()
{ init();string temp1,temp2;while(cin>>temp1>>temp2){long long tmp1,tmp2,tmp3;tmp1=sum(temp1);temp1=get(tmp1);tmp2=sum(temp2);temp2=get(tmp2);tmp3=tmp1+tmp2;string temp3=get(tmp3);for(int i=0;i<2+temp3.size()-temp1.size();i++){cout<<" ";}cout<<get(tmp1)<<endl;cout<<"+ ";for(int i=0;i<temp3.size()-temp2.size();i++)cout<<" ";cout<<get(tmp2)<<endl;cout<<" ";for(int i=0;i<temp3.size();i++)cout<<"-";cout<<endl;cout<<" ";cout<<get(tmp3)<<endl<<endl;}
}
2.额外的方法：（进阶）
其实大部分题解都是以上的这种方法，其实不好，除了贪心的观念用到了斐波那契的技巧，避免连续1的出现。其实仔细观察斐波那契数列，每一项都等于前一项和前两项的和，由此你有什么启发呢？
对的，也就是两个1可以合并成一个1的情况。由此又分为了多种情况，连续的两个一合并，如果前两项有1怎么办呢，我们可以假设当前位置是‘2’，我们仔细观察斐波那契数列，一个数的二倍等于什么呢？除了F[1]=2F[0],其余各项是不是都是2F[n]=F[n+1]+F[n-2];这里留下小小的思考，希望读者不要依赖转换的代码，去通过斐波那契的规律去解题。
这篇关于POJ2116题解（1.低阶：贪心 2.高阶：利用斐波那契的规律）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
