#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;
}
词法分析程序中的起始状态（start state），是一种捕获对上下文敏感信息的方法。用起始状态标记规则，是通知词法分析程序只有在起始状态有效的情况下才识别该规则。
下面的示例统计C源文件中不同类型的行的数目，这些行有些包含代码，有些只包含注释或者空白。
%{
int nCommentLine, nCodeLine, nWhiteLine;
%}
%x COMMENT
%%
^[ \t]*"/*" { BEGIN COMMENT; }
^[ \t]*"/*".*"*/"[ \t]*\n { ++nCommentLine; }
<COMMENT>"*/"[ \t]*\n { BEGIN 0; ++nCommentLine; }
<COMMENT>"*/" { BEGIN 0; }
<COMMENT>\n { ++nCommentLine; }
<COMMENT>.\n { ++nCommentLine; }
^[ \t]*\n { ++nWhiteLine; }
.+"/*".*"*/".*\n { ++nCodeLine; }
.*"/*".*"*/".+\n { ++nCodeLine; }
.+"/*".*\n { ++nCodeLine; BEGIN COMMENT; }
.\n { ++nCodeLine; }
. ;
%%
main()
{
yylex();
printf("code line: %d, comment line: %d, whitespace %d\n",
nCodeLine, nCommentLine, nWhiteLine);
}空白行的正则表达式描述：
^[ \t]*\n“^”表示这种模式必须起始于行首。允许空格和制表符，但没有其他东西。以换行符“\n”结尾。
代码行或注释行被描述为任何不完全是空白的行。
^[ \t]*\n
\n /* 空白行被前一条规则匹配 */
. /* 其他东西 */使用新的规则“\n”来统计不全是空白的行的数目，“.”用来丢弃无关字符。
下面的规则描述了处于一行的单个、自包含的注释，注释文本位于“/*”和“*/”之间：
^[ \t]*"/*".*"*/"[ \t]*\n由于注释可以跨越多行，在定义部分，添加
%x COMMENT它在词法分析程序中创建新的起始状态。在规则部分，添加以“<COMMENT>”开始的规则。这些规则只有在词法分析程序处于COMMENT状态时被识别。当看到注释的开头时，进入起始状态：
^[ \t]*"/*" { BEGIN COMMENT; }动作中的BEGIN语句切换到COMMENT状态。这条规则要求注释始于行首，可以避免遇到下述情况时的计数错误：
int counter; /* this is
a strange comment */第一行并不是单独的一行。我们需要将第一行计为代码行，第二行作为注释行计算。下面是实现规则：
.+"/*".*"*/".*\n
.*"/*".*"*/".+\n上述两个表达式描述的字符串集合有重叠，但并不完全相同。下面的表达式匹配第一条规则，但不符合第二个：
int counter; /* comment */因为第二条规则要求注释后面有文字。同样，下面的表达式符合第二个规则，但不匹配第一条：
/* comment */ int counter;它们都匹配下面的表达式：
/* comment #1 */ int counter; /* comment #2 */下面来完成检测注释的正则表达式。我们采用起始状态，当处于COMMENT状态时，仅需要寻找换行符：
<COMMENT>\n
<COMMENT>.\n并进行计数。第一条规则处理注释中的空行，第二条则处理注释中有文本的行。当检测到注释结尾时，如果后面没有其他东西，就把它作为注释行计数，否则就继续处理：
<COMMENT>"*/"[ \t]*\n { BEGIN 0; ++nCommentLine; }
<COMMENT>"*/" { BEGIN 0; }第一条规则计为注释行，第二条继续处理。动作中的“BEGIN 0”回到默认状态，退出COMMENT状态。