Yaowei的小小杂货铺

2009年1月30日星期五

2009年1月27日星期二

听歌 01/27/2009

一个人浪漫林心如新如主义 2008年11月擎天娱乐
无缘周旭风无缘(大陆) 2009年01月亮傲文化传媒

2008年12月4日星期四

2008年3月12日星期三

整数在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;
}

2007年12月20日星期四

lex/yacc系列：lex中的起始状态

词法分析程序中的起始状态（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状态。

2007年12月7日星期五

2007年12月5日星期三

lex/yacc系列：yacc进阶（三）

下面我们使用符号表——一种用来跟踪使用中的名字的结构，来增加使用长变量名的能力。每次语法分析程序读取输入中的名字，它都在符号表中查找这个名字，并且得到一个对应于符号表条目的指针。因为符号表要求词法分析程序和语法分析程序之间共享数据结构，所以我们创建一个头文件calc4.h：

#define NSYMS 20 /* 允许的符号个数 */

struct symtab {
  char *name;
  double value;
} symtab[NSYMS];

struct symtab *symlook();

在这个实现中，符号表是一个结构数组（也可以使用其他类型的数据结构，例如链表），每个结构包含变量的名字和它的值。还声明了一个函数symlook()，它以文本字符串形式的名字为参数，返回对应的符号表条目的指针，如果不存在，就添加。

语法分析程序只需要少许修改，以使用符号表：

%{
#include "calc4.h"
#include 

int nsym = 0;
%}

%union {
  double dval;
  struct symtab *symp;
}

%token <symp> NAME
%token <dval> NUMBER
%left '+' '-'
%left '*' '/'
%nonassoc UMINUS

%type <dval> expression

%%
statement_list : statement '\n'
 ¦   statement_list statement '\n'
 ;

statement : NAME '=' expression { $1->value = $3; }
 ¦   expression    { printf("= %g\n", $1); }
 ;

expression : expression '+' expression { $$ = $1 + $3; }
 ¦   expression '-' expression { $$ = $1 - $3; }
 ¦   expression '*' expression { $$ = $1 * $3; }
 ¦   expression '/' expression
      { if ($3 == 0.0)
          yyerror("divide by zero");
        else
          $$ = $1 / $3;
      }
 ¦   '-' expression %prec UMINUS { $$ = -$2; }
 ¦   '(' expression ')'        { $$ = $2; }
 ¦   NUMBER
 ¦   NAME                      { $$ = $1->value; }
 ;

%%
struct symtab *
symlook(char *s)
{
 int i;

 for (i = 0; i < nsym; ++i) {
  if (!strcmp(symtab[i].name, s))
   return &symtab[i];
 }

 if (nsym < NSYMS) {
  symtab[nsym].name = strdup(s);
  ++nsym;
  return &symtab[nsym-1];
 }

 yyerror("Too many symbols");
 exit(1);
}

NAME标记的值是指向符号表的指针，%union和NAME的%token声明适当地有所改变，而且给变量赋值和读取变量的动作现在将标记值作为指针来使用，读写符号表条目的value字段。函数symlook()被定义在用户子例程部分，它顺序地搜索符号表来寻找与作为参数传入的名字对应的条目，并返回其指针；如果没有找到，就把它保存在符号表中。顺序搜索对于这个简单示例是合适的，但对于大尺寸的符号表来说太慢了，需要使用散列表或者其他的快速搜索方法。

词法分析程序也需要稍加修改以适应符号表。识别变量名的规则匹配“[A-Za-z][A-Za-z0-9]*”，任何以字母开头的包含
字母和数字的字符串被认为是变量名。它的动作调用symlook()得到指向符号表条目的指针，并将它存储在标记的值yylval.symp中。

%{
#include "y.tab.h"
#include "calc4.h"
#include 
%}

%%
([0-9]+|([0-9]*\.[0-9]+)([eE][-+]?[0-9]+)?) {
  yylval.dval = atof(yytext);
  return NUMBER;
 }

[ \t] ;

[A-Za-z][A-Za-z0-9]* {
  yylval.symp = symlook(yytext);
  return NAME;
 }

"$"   { return 0; }

\n    ¦
.     { return yytext[0]; }

%%

因为字符串动态分配，所以对于变量名的长度没有限制。下面是运行实例：

% calc4 foo = 12 foo /5 = 2.4 thisisanextremelylongvariablenamewhichnobodywouldwanttotype = 42 3 * thisisanextremelylongvariablenamewhichnobodywouldwanttotype = 126 thisisanextremelylongvariablenamewhichnobodywouldwanttotype / foo = 3.5 $

订阅：博文 (Atom)