Yaowei的小小杂货铺

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 $

2007年12月4日星期二

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

下面再扩展计算器的功能，使它能够处理名字为单个字母的变量。先只考虑26个小写字母为变量名，我们将这26个变量储存在数组vbltable中。为了使计算器更有用，我们还进一步扩展，使它能处理多条表达式，每行一条，并且使用浮点数作为数值。

拥有变量和实数数值的计算器语法分析程序calc3.y：

%{
double vbltable[26];
%}

%union {
  double dval;
  int vblno;
}

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

%type <dval> expression

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

statement : NAME '=' expression { vbltable[$1] = $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                      { $$ = vbltable[$1]; }
 ;

拥有变量和实数数值的计算器词法分析程序calc3.l：

%{
#include "y.tab.h"
#include <math.h>
extern double vbltable[26];
%}

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

[ \t]  ;

[a-z]  { yylval.vblno = yytext[0] - 'a'; return NAME; }

"$"     { return 0; }

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

%%

在这个程序中，符号值有多种数据类型：表达式的值是double，变量引用和符号NAME的值是对应于vbltable的从0到25之间的整数。为了定义可能的符号类型，在定义部分加入了%union声明：

%union {
  double dval;
  int vblno;
}

声明中的内容将被逐字拷贝到输出文件y.tab.h中，作为C类型定义YYSTYPE的联合声明的内容：

#define NAME 257
#define NUMBER 258
#define UMINUS 259
typedef union {
  double dval;
  int vblno;
} YYSTYPE;
extern YYSTYPE yylval;

生成的头文件中还声明了变量yylval，并且定义了语法中使用的的符号标记的标记号。

在语法分析程序中的定义部分的符号定义行，由尖括号扩住的联合声明中的字段名指定了符号值的类型。

%token <vblno> NAME
%token <dval> NUMBER

%type <dval> expression

非终结符不需要声明，除非需要通过声明%type指定其类型。也可以在%left、%right或%nonassoc通过尖括号指定类型。在动作代码中，yacc对于符号值引用将自动添加合适的字段名，例如，如果第三个字符是NUMBER，对$3的引用就等于$3.dval。

在这个扩展的语法分析程序中还加入了一个新的起始符号statement_list，因此它能处理一系列而不仅仅是一条语句，每条语句以换行结尾。还为设置变量的规则增加了一个动作，并在最后添加了一条将NAME转换成expression的新规则，它获取变量的值。

词法分析程序也必须进行一些修改。yylval已经在y.tab.h中声明，所以不需要再次声明。词法分析程序并不能自动识别符号的类型，所以设置yylval时必须显式地添加字段引用。动作代码调用atof()读入数字，然后将值赋给yylval.dval。对于变量，在yylval.vblno中返回变量表中变量的下标。最后，使“\n”成为了一个普通标记，并使用“$”标志输入的结束。

下面是运行实例：

% calc3 2/3 = 0.666667 a = 2/7 a = 0.285714 z = a+1 z = 1.28571 a/z = 0.222222 $

2007年12月3日星期一

HTML常用特殊字符

-	ID	代码	描述
	160	nbsp	non-break space
&	38	amp	ampersand
¦	166	brvbar	broken bar
>	62	gt	greater-than sign
<	60	lt	less-than sign
¢	162	cent	cent sign
£	163	pound	pound sign
©	169	copy	copyright sign
®	174	reg	registered sign
™	8482	trade	trade mark sign
°	176	deg	degree sign
±	177	plusmn	plus-minus sign
×	215	times	multiplication sign
÷	247	divide	division sign
¹	185	sup1	superscript one
²	178	sup2	superscript two
³	179	sup3	superscript three
½	189	frac12	valgar fraction one half
¼	188	frac14	valgar fraction one quarter
¾	190	frac34	valgar fraction three quarters
µ	181	micro	micro sign
↑	8593	uarr	upwards arrow
←	8592	larr	leftards arrow
↓	8595	darr	downwards arrow
→	8594	rarr	rightwards arrow
↔	8596	harr	left right arrow
↵	8629	crarr	downwards arrow with corner leftwards
⇑	8657	uArr	upwards double arrow
⇐	8656	lArr	leftwards double arrow
⇓	8659	dArr	downwards double arrow
⇒	8658	rArr	rightwards double arrow
⇔	8660	hArr	left right double arrow

订阅：博文 (Atom)