饭桶精英: 算法

Showing posts with label 算法. Show all posts

Wednesday, May 13, 2009

SQL Parser

Tuesday, May 12, 2009

更多精彩请到 http://www.139ya.com

转自: http://blog.chinaunix.net/u/16292/showart_490167.html

把中缀表达式转换为后缀表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符，对于不同类型的字符按不情况进行处理。

加减运算符的优先级设定为1，乘除运算符的优先级设定为2，在栈中保存的特殊运算符’@’和’(’的优先级设定为0

1. 若遇到的是空格则认为是分隔符，不需要进行处理；
2. 若遇到的是数字或小数点，则直接写入到s2中，并在每个数值的最后写入一个空格；
3. 若遇到的是左括号，则应把它压入到运算符栈中，待以它开始的括号内的表达式转换完毕后再出栈；
4. 若遇到的是右括号，则表明括号内的中缀表达式已经扫描完毕，把从栈顶直到保存着的对应左括号之间的运算符依次退栈并写入s2串中；
5. 若遇到的是运算符，
5.1 当该运算符的优先级大于栈顶运算符的优先级时，表明该运算符的后一个运算对象还没有被扫描也没有被放入到s2串中，应把它暂存于运算符栈中，待它的后一个运算对象从s1串中读出并写入到s2串中后，再令其出栈并写入s2串中；
5.2 若遇到的运算符的优先级小于或等于栈顶运算符的优先级，这表明栈顶运算符的两个运算对象已经被保存到s2串中，应将栈顶运算符退栈并写入到s2串中，对于新的栈顶运算符仍继续进行比较和处理，直到被处理的运算符的优先级大于栈顶运算符的优先级为止，然后让该运算符进栈即可。
按照以上过程扫描到中缀表达式结束符’@’时，把栈中剩余的运算符依次退栈并写入到后缀表达式中，再向s2写入表达式结束符’@’和字符串结束符’{post.abstract}’，整个转换过程就处理完毕，在s2中就得到了转换成的后缀表达式。

下面是java源代码：

清单1：StackChar.java 栈


package zieckey.datastructure.study.stack;

public class StackChar
{
  private int        maxSize;    // size of stack array

  private char[]    stackArray;
  private int        top;        // top of stack


  public StackChar( int maxSize )
  {
      this.maxSize = maxSize;// 设置数组大小

      stackArray = new char[maxSize];// 创建数组

      top = -1;// 还没有任何元素

  }

  public void push( char ch )
  {// 入栈

      if ( isFull() )
      {
          System.out.println( "Cannot insert item " + ch + "! The stack is full." );
      } else
      {
          top++ ;
          stackArray[top] = ch;
      }
  }

  public char pop()
  {// 出栈

      if ( isEmpty() )
      {
          System.out.println( "The stack is empty." );
          return 0;
      } else
      {
          char ch = stackArray[top];
          stackArray[top] = 0;
          top-- ;
          return ch;
      }
  }

  public int size()
  {
      return top + 1;
  }

  public char peek()
  {// 返回栈顶元素

      return stackArray[top];
  }

  public char peekN( int n )
  {// 返回index为n的元素

      return stackArray[n];
  }

  public boolean isEmpty()
  {
      return ( -1 == top );
  }

  public boolean isFull()
  {
      return ( maxSize - 1 == top );
  }

  public void displayStack()
  {
      System.out.print( " Stack: " );
      for ( int i = 0; i < precedencestack =" precedence(" precedencein =" precedence("> precedenceStack )
      {
          return 1;
      } else if ( precedenceIn == precedenceStack )
      {
          return 0;
      } else
      {
          return -1;
      }
  }

  /**
   * 计算传入参数的优先级
   *
   * @param ch
   * @return
   */
  public static int precedence( char ch )
  {
      if ( '+' == ch || '-' == ch )
      {
          return PrecedenceAdd;
      } else if ( '*' == ch || '/' == ch )
      {
          return PrecedenceMultiply;
      } else if ( '(' == ch )
      {
          return PrecedenceOpenParentheses;
      } else if ( ')' == ch )
      {
          return PrecedenceCloseParentheses;
      } else
      {
          return PrecedenceOthers;
      }
  }

  private static final int    PrecedenceAdd                = 1;
  private static final int    PrecedenceMultiply            = 2;
  private static final int    PrecedenceOpenParentheses    = 0;
  private static final int    PrecedenceCloseParentheses    = 3;
  private static final int    PrecedenceOthers            = -1;
}

清单2：Infix2Postfix.java 中缀表达式转换为后缀表达式


package zieckey.datastructure.study.stack;

public class Infix2Postfix
{
   private StackChar    theStack;
   private String        input;
   private String        output    = "";

   public Infix2Postfix( String in ) // constructor

   {
       input = in;
       int stackSize = input.length( );
       theStack = new StackChar( stackSize/2 );
   }

   /**
    * A*(B+C)-D/(E+F) The opThis operator has just been read from the infix
    * input, while the opTop operator has just been popped off the stack.
    *
    * 加减运算符的优先级设定为1，乘除运算符的优先级设定为2，在栈中保存的运算符’(’的优先级设定为0
    *
    * 把中缀表达式转换为后缀表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符，对于不同类型的字符按不情况进行处理。
    *
    * 处理方法步骤：
    * 1. 若遇到的是操作数，则直接写入到s2中，并在每个数值的最后写入一个空格；
    * 2. 若遇到的是左括号，则应把它压入到运算符栈中，待以它开始的括号内的表达式转换完毕后再出栈；
    * 3. 若遇到的是右括号，则表明括号内的中缀表达式已经扫描完毕，把从栈顶直到保存着的对应左括号之间的运算符依次退栈并写入s2串中；
    * 4. 若遇到的是运算符，
    *     4.1 当该运算符的优先级大于栈顶运算符的优先级时，表明该运算符的后一个运算对象还没有被扫描也没有被放入到s2串中，
    *         应把它暂存于运算符栈中，待它的后一个运算对象从s1串中读出并写入到s2串中后，再令其出栈并写入s2串中；
    *     4.2 若遇到的运算符的优先级小于或等于栈顶运算符的优先级，这表明栈顶运算符的两个运算对象已经被保存到s2串中，
    *         应将栈顶运算符退栈并写入到s2串中，对于新的栈顶运算符仍继续进行比较和处理，
    *         直到被处理的运算符的优先级大于栈顶运算符的优先级或者栈为空时为止，然后让该运算符进栈即可。
    *
    */
   public String doTrans()
   {
       char ch;
       int len = input.length( );
       for ( int index = 0; index < ch =" input.charAt(" output =" output"> StackChar.precedence( theStack.peek( ) ) )
               {
                   theStack.push( ch );
               } else
               {
                   /**
                    * 该运算符的优先级小于或等于栈顶运算符的优先级,应将栈顶运算符退栈并写入到输出字符串中，
                    * 对于新的栈顶运算符仍继续进行比较和处理，直到被处理的运算符的优先级大于栈顶运算符的优先级或者栈为空时为止，
                    * 然后让该运算符进栈即可。
                    */
                   while ( !theStack.isEmpty( ) )
                   {
                       if ( StackChar.precedence( ch ) > StackChar.precedence( theStack.peek( ) ) )
                       {
                           break;
                       } else
                       {
                           output = output + theStack.pop( );
                       }
                   }
                   theStack.push( ch );
               }
               break;
           case '(' :// 当其他运算符与之比较时优先级为0。当'('与其它运算符比较时优先级最高，直接入栈

               theStack.push( ch );
               break;
           case ')' :// 优先级为3，为最高优先级，遇到后，对栈进行出栈操作

               while ( !theStack.isEmpty( ) )
               {
                   if ( '(' != theStack.peek( ))
                   {
                       output = output + theStack.pop( );
                   } else
                   {
                       theStack.pop( );
                       break;
                   }
               }
               break;
           case ' ':
               break;
           default : // not an operator, must be an operand

               output = output + ch;// write it into output

               break;
       }// end switch

   }
}

清单3：Postfix.java 计算后缀表示式的值


package zieckey.datastructure.study.stack;

public class Postfix
{
   private String        inPostfix;
   private StackX    theStack;
   private int            size;

   public Postfix( String a )
   {
       inPostfix = a;
       size = inPostfix.length( );
       theStack = new StackX(size);
   }
  
   /**
    * 计算数据成员 inPostfix(为后缀表达式) 的值，
    *
    * 方法：
    * 从左至右扫描后缀表达式，遇到运算数就将其压入栈内；
    * 遇到运算符就做2次出栈操作，将操作数用这个运算符进行运算，将结果压入栈中。
    * 知道扫描完，最后出栈操作就是表达式的最终计算结果。
    *
    * @return
    */
   public double calculatePostfix()
   {
       char chRead;
       for ( int i = 0; i < chread =" inPostfix.charAt(">='0'&&chRead<='9' )                     {                         theStack.push( (int)(chRead-'0') );                     }                     break;             }         }         return theStack.pop( );     }      private void disposeOperator( char chRead )     {         double num1;         double num2;         double interAns = 0;         num2 = theStack.pop( );         num1 = theStack.pop( );         switch ( chRead )         {             case '+' :                 interAns = num1 + num2;                 break;             case '-' :                 interAns = num1 - num2;                 break;             case '*' :                 interAns = num1 * num2;                 break;             case '/' :                 interAns = num1 / num2;                 break;             default :                 break;         }         theStack.push( interAns );     }  }

清单4：InfixCalcApp.java 测试程序main


package zieckey.datastructure.study.stack;

public class InfixCalcApp
{

   /**
    * @param args
    */
   public static void main( String[] args )
   {
       // TODO Auto-generated method stub

       String input = "5-(8+9-5*6)/3*(5+8-9)+6/(3+5-9-8+1)";
       String output;
       Infix2Postfix in2post = new Infix2Postfix( input );
       Postfix postfix;
       output = in2post.doTrans( );
       postfix = new Postfix( output );
       double ans = postfix.calculatePostfix( );
       System.out.println( "Postfix is : " + output );
       System.out.println( "The answer is : " + ans );

   }

}

运行结果：

For 5 : Stack: 5
For - : Stack: 5
For ( : Stack: - 5
For 8 : Stack: -( 58
For + : Stack: -( 58
For 9 : Stack: -(+ 589
For - : Stack: -(+ 589+
For 5 : Stack: -(- 589+5
For * : Stack: -(- 589+5
For 6 : Stack: -(-* 589+56
For ) : Stack: -(-* 589+56*-
For / : Stack: - 589+56*-
For 3 : Stack: -/ 589+56*-3
For * : Stack: -/ 589+56*-3/
For ( : Stack: -* 589+56*-3/
For 5 : Stack: -*( 589+56*-3/5
For + : Stack: -*( 589+56*-3/5
For 8 : Stack: -*(+ 589+56*-3/58
For - : Stack: -*(+ 589+56*-3/58+
For 9 : Stack: -*(- 589+56*-3/58+9
For ) : Stack: -*(- 589+56*-3/58+9-
For + : Stack: -* 589+56*-3/58+9-*-
For 6 : Stack: + 589+56*-3/58+9-*-6
For / : Stack: + 589+56*-3/58+9-*-6
For ( : Stack: +/ 589+56*-3/58+9-*-6
For 3 : Stack: +/( 589+56*-3/58+9-*-63
For + : Stack: +/( 589+56*-3/58+9-*-63
For 5 : Stack: +/(+ 589+56*-3/58+9-*-635
For - : Stack: +/(+ 589+56*-3/58+9-*-635+
For 9 : Stack: +/(- 589+56*-3/58+9-*-635+9
For - : Stack: +/(- 589+56*-3/58+9-*-635+9-
For 8 : Stack: +/(- 589+56*-3/58+9-*-635+9-8
For + : Stack: +/(- 589+56*-3/58+9-*-635+9-8-
For 1 : Stack: +/(+ 589+56*-3/58+9-*-635+9-8-1
For ) : Stack: +/(+ 589+56*-3/58+9-*-635+9-8-1+
Postfix is : 589+56*-3/58+9-*-635+9-8-1+/+
The answer is : 21.583333333333332

Wednesday, April 1, 2009

Cache替换算法［转]

更多精彩请到 http://www.139ya.com

转自: http://www.cnblogs.com/greatqn/archive/2007/02/05/640376.html

Cache替换算法是影响代理缓存系统性能的一个重要因素，一个好的Cache替换算法可以产生较高的命中率。目前已经提出的算法可以划分为以下三类：

（1）传统替换算法及其直接演化，其代表算法有：①LRU（Least Recently Used）算法：将最近最少使用的内容替换出Cache；②LFU（Lease Frequently Used）算法：将访问次数最少的内容替换出Cache；③Pitkow/Recker[10]提出了一种替换算法：如果Cache中所有内容都是同一天被缓存的，则将最大的文档替换出Cache，否则按LRU算法进行替换。

（2）基于缓存内容关键特征的替换算法，其代表算法有：①Size[10]替换算法：将最大的内容替换出Cache；②LRU— MIN[11]替换算法：该算法力图使被替换的文档个数最少。设待缓存文档的大小为S，对Cache中缓存的大小至少是S的文档，根据LRU算法进行替换；如果没有大小至少为S的对象，则从大小至少为S/2的文档中按照LRU算法进行替换；③LRU—Threshold[11] 替换算法：和LRU算法一致，只是大小超过一定阈值的文档不能被缓存；④Lowest Lacency First[12]替换算法：将访问延迟最小的文档替换出Cache。

（3）基于代价的替换算法，该类算法使用一个代价函数对Cache中的对象进行评估，最后根据代价值的大小决定替换对象。其代表算法有：①Hybrid[12] 算法：算法对Cache中的每一个对象赋予一个效用函数，将效用最小的对象替换出Cache；②Lowest Relative Value[13] 算法：将效用值最低的对象替换出Cache；③Least Normalized Cost Replacement（LCNR）[14]算法：该算法使用一个关于文档访问频次、传输时间和大小的推理函数来确定替换文档；④Bolot等人 [15]提出了一种基于文档传输时间代价、大小、和上次访问时间的权重推理函数来确定文档替换；⑤Size—Adjust LRU（SLRU）[16] 算法：对缓存的对象按代价与大小的比率进行排序，并选取比率最小的对象进行替换。

总之，为了使Cache命中率最大化，围绕Cache替换算法已经开展了大量的工作，但是替换算法的性能很大程度上取决于WWW访问的特性，还没有哪一种替换算法能够对所有Web访问模式都优于其它算法。

Saturday, February 7, 2009

十进制数转换为二进制,八进制,十六进制数的算法


# using System;
# using System.Collections.Generic;
# using System.ComponentModel;
# using System.Data;
# using System.Drawing;
# using System.Text;
# using System.Windows.Forms;
# 
# namespace ExDtoB
# {
#     public partial class Form1 : Form
#     {
#         public Form1()
#         {
#             InitializeComponent();
#         }
# 
#         //十进制转二制
#         public string DtoB(int d)
#         {
#             string b = "";
#             //判断该数如果小于2，则直接输出
#             if (d < b =" d.ToString();" s =" 0;" n =" d;">= 2)
#                 {
#                     s++;
#                     n = n / 2;
#                 }
#                 int[] m = new int[s];
#                 int i = 0;
#                 do
#                 {
#                     c = d / 2;
#                     m[i++] = d % 2;
#                     d = c;
#                 } while (c >= 2);
#                 b = d.ToString();
#                 for (int j = m.Length - 1; j >=0; j--)
#                 {
#                     b += m[j].ToString ();
#                 }
#             }
#             return b;
#         }
# 
# 
#         //十进制转八进制
#         public string DtoO(int d)
#         {
#             string o = "";
#             if (d < o =" d.ToString();" s="0;" n="d;" temp =" d;">= 8)
#                 {
#                     s++;
#                     n = n / 8;
#                 }
#                 int[] m = new int[s];
#                 int i = 0;
#                 do
#                 {
#                     c = d / 8;
#                     m[i++] = d % 8;
#                     d = c;
#                 } while (c >= 8);
#                 o = d.ToString();
#                 for (int j = m.Length - 1; j >= 0; j--)
#                 {
#                     o += m[j];
#                 }
#             }
#             return o;
#         }
# 
# 
#         //十进制转十六进制
#         public string DtoX(int d)
#         {
#             string x = "";
#             if (d < x =" chang(d);" s =" 0;" n =" d;" temp =" d;">= 16)
#                 {
#                     s++;
#                     n = n / 16;
#                 }
#                 string [] m = new string[s];
#                 int i = 0;
#                 do
#                 {
#                     c = d / 16;
#                     m[i++] = chang(d % 16);//判断是否大于10，如果大于10，则转换为A~F的格式
#                     d = c;
#                 } while (c >= 16);
#                 x = chang(d);
#                 for (int j = m.Length - 1; j >= 0; j--)
#                 {
#                     x += m[j];
#                 }
#             }
#             return x;
#         }
# 
# 
#         //判断是否为10~15之间的数，如果是则进行转换
#         public string chang(int d)
#         {
#             string x = "";
#             switch (d)
#             {
#                 case 10:
#                     x = "A";
#                     break;
#                 case 11:
#                     x = "B";
#                     break;
#                 case 12:
#                     x = "C";
#                     break;
#                 case 13:
#                     x = "D";
#                     break;
#                 case 14:
#                     x = "E";
#                     break;
#                 case 15:
#                     x = "F";
#                     break;
#                 default:
#                     x = d.ToString();
#                     break;
#             }
#             return x;
#         }
# 
#         private void button1_Click(object sender, EventArgs e)
#         {
#             textBox2.Text = DtoB(Convert.ToInt32(textBox1.Text));//十转二进制
#         }
# 
#         private void button2_Click(object sender, EventArgs e)
#         {
#             textBox2.Text = DtoO(Convert.ToInt32(textBox1.Text));//十转八进制
#         }
# 
#         private void button3_Click(object sender, EventArgs e)
#         {
#             textBox2.Text = DtoX(Convert.ToInt32(textBox1.Text));//十转十六进制
#         }
#     }
# }

车牌识别及验证码识别的一般思路

Wednesday, January 21, 2009

中缀到后缀表达式的转换

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   postfix.cpp
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-6 16:00:54
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

// 算法：
// 1)检查输入的下一元素。
// 2)假如是个操作数，输出。
// 3)假如是个开括号，将其压栈。
// 4)假如是个运算符，则
//   i) 假如栈为空，将此运算符压栈。
//   ii) 假如栈顶是开括号，将此运算符压栈。
//   iii) 假如此运算符比栈顶运算符优先级高，将此运算符压入栈中。
//   iv) 否则栈顶运算符出栈并输出，重复步骤4。
// 5)假如是个闭括号，栈中运算符逐个出栈并输出，直到遇到开括号。开括号出栈并丢弃。
// 6)假如输入还未完毕，跳转到步骤1。
// 7)假如输入完毕，栈中剩余的所有操作符出栈并输出它们。

#include <stdio.h>
#include "stack.h"

// 返回操作符的优先级
// +和-的优先级是一样的，*和/的优先级也是一样的，但+和-的优先级要比*和/的低。
static int GetPRI(const char optr)
{
   switch (optr)
   {
   case '+': return 1;
   case '-': return 1;
   case '*': return 2;
   case '/': return 2;
   default : return 0;
   }
}

// 在这个函数中完成对栈顶的操作符和当前操作符的优先级对比，
// 并决定是输出当前的操作符还是对当前的操作符进行入栈处理。
static void ProcessStackPRI(
   CStack<char> &stack,
   const char optr,
   char **szPostfix
)
{
   ASSERT(*szPostfix);

   int i;
   int nRetCode;
   char chStackOptr;
   int nCount = stack.GetCount();

   for (i = 0; i <= nCount; ++i)
   {
       nRetCode = stack.top(&chStackOptr);
       if (
           (0 == nRetCode) ||                  // 栈顶为空，新操作符添加到栈顶
           (GetPRI(chStackOptr) < GetPRI(optr))// 栈顶操作符优先级比当前的要低
       )
       {
           stack.push(optr);
           break;
       }
       else
       {
           // 如果栈顶操作符优先级不低于当前的，则栈顶元素出栈并输出：
           stack.pop();
           *(*szPostfix)++ = chStackOptr;
       }
   }
}

static void Infix2Postfix(
   const char *szInfix,
   char *szPostfix
)
{
   ASSERT(szPostfix);

   char chOptr;
   int nRetCode;
   CStack<char> stack;

   while (*szInfix)
   {
       switch (*szInfix)
       {
       // 忽略空格和TAB：
       case ' ':
       case '\t':
           break;

       // 对操作符进行优先级判断，以便决定是入栈还是输出：
       case '+':
       case '-':
       case '*':
       case '/':
           nRetCode = stack.IsEmpty();
           if (!nRetCode)
               ProcessStackPRI(stack, *szInfix, &szPostfix);
           else
               stack.push(*szInfix);   // 当栈为空时，毫无疑问操作符应该入栈
           break;

       // 遇到左括号时，无条件入栈，因为它的优先级是最高的
       case '(':
           stack.push(*szInfix);
           break;

       // 遇到右括号时，逐个把栈中的操作符出栈，直到遇到左括号为止
       case ')':
           do
           {
               nRetCode = stack.pop(&chOptr);
               if (nRetCode && ('(' != chOptr))            // 左括号本身不输出
                   *szPostfix++ = chOptr;
           } while (!stack.IsEmpty() && ('(' != chOptr));  // 遇到左括号为止
           break;

       // 其余的情况，直接输出即可
       default:
           *szPostfix++ = *szInfix;
           break;
       }
       ++szInfix;
   }
   // 如果输入的内容已经分析完毕，那么就把栈中剩余的操作符全部出栈
   while (!stack.IsEmpty())
   {
       nRetCode = stack.pop(&chOptr);
       *szPostfix++ = chOptr;
   }
   *szPostfix = '\0';
}

int main()
{
   char *szInfix = "a+b*c+(d*e+f)*g";
   char szPostfix[255];

#ifdef _DEBUG
   _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif

   Infix2Postfix(szInfix, szPostfix);

   printf("Infix   : %s\n", szInfix);
   printf("Postfix : %s\n", szPostfix);
}

算法的时间复杂度（计算实例）

更多精彩请到 http://www.139ya.com

转自: http://blog.chinaunix.net/u/26481/showart_479537.html

算法的时间复杂度

2007年12月02日星期日 01:17
定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数 T(n)称为这一算法的“时间复杂性”。

当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。

我们常用大O表示法表示时间复杂性，注意它是某一个算法的时间复杂性。大O表示只是说有上界，由定义如果f(n)=O(n)，那显然成立f(n)=O(n^2)，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。

此外，一个问题本身也有它的复杂性，如果某个算法的复杂性到达了这个问题复杂性的下界，那就称这样的算法是最佳算法。

“ 大O记法”：在这种描述中使用的基本参数是 n，即问题实例的规模，把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order)，比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时，运行时间至多将以正比于 f(n)的速度增长。

这种渐进估计对算法的理论分析和大致比较是非常有价值的，但在实践中细节也可能造成差异。例如，一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然，随着n足够大以后，具有较慢上升函数的算法必然工作得更快。

O(1)

Temp=i;i=j;j=temp;

以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

O(n^2)

2.1. 交换i和j的内容
sum=0；（一次）
for(i=1;i<=n;i++) （n次）
for(j=1;j<=n;j++) （n^2次）
sum++；（n^2次）
解：T(n)=2n^2+n+1 =O(n^2)

2.2.
for (i=1;i
{
y=y+1; ①
for (j=0;j<=(2*n);j++)
x++; ②
}
解：语句1的频度是n-1
语句2的频度是(n-1)*(2n+1)=2n^2-n-1
f(n)=2n^2-n-1+(n-1)=2n^2-2
该程序的时间复杂度T(n)=O(n^2).

O(n)

2.3.
a=0;
b=1; ①
for (i=1;i<=n;i++) ②
{
s=a+b;　　　　③
b=a;　　　　　④
a=s;　　　　　⑤
}
解：语句1的频度：2,
语句2的频度： n,
语句3的频度： n-1,
语句4的频度：n-1,
语句5的频度：n-1,
T(n)=2+n+3(n-1)=4n-1=O(n).

O(log2n )

2.4.
i=1; ①
while (i<=n)
i=i*2; ②
解：语句1的频度是1,
设语句2的频度是f(n), 则：2^f(n)<=n;f(n)<=log2n
取最大值f(n)= log2n,
T(n)=O(log2n )

O(n^3)

2.5.
for(i=0;i
{
for(j=0;j
{
for(k=0;k
x=x+2;
}
}
解：当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n^3).

我们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最坏情况运行时间是 O(n^2)，但期望时间是 O(nlogn)。通过每次都仔细地选择基准值，我们有可能把平方情况 (即O(n^2)情况)的概率减小到几乎等于 0。在实际中，精心实现的快速排序一般都能以 (O(nlogn)时间运行。
下面是一些常用的记法：

访问数组中的元素是常数时间操作，或说O(1)操作。一个算法如果能在每个步骤去掉一半数据元素，如二分检索，通常它就取 O(logn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间。常规的矩阵乘算法是O(n^3)，因为算出每个元素都需要将n对元素相乘并加到一起，所有元素的个数是n^2。
指数时间算法通常来源于需要求出所有可能结果。例如，n个元素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的。指数算法一般说来是太复杂了，除非n的值非常小，因为，在这个问题中增加一个元素就导致运行时间加倍。不幸的是，确实有许多问题 (如著名的“巡回售货员问题” )，到目前为止找到的算法都是指数的。如果我们真的遇到这种情况，通常应该用寻找近似最佳结果的算法替代之。

时间复杂度

更多精彩请到 http://www.139ya.com

时间复杂度

　　（1）时间频度
　　一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
　　（2）时间复杂度
　　在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。
　　一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作 T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
　　在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n^2+3n+4与T(n)=4n^2+2n+1它们的频度不同，但时间复杂度相同，都为O(n^2)。
　　按数量级递增排列，常见的时间复杂度有：
　　常数阶O(1),对数阶O(log(2)n),线性阶O(n),
　　线性对数阶O(nlog(2)n),平方阶O(n^2)，立方阶O(n^3),...，
　　k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
　　（3）算法的时间复杂度
　　若要比较不同的算法的时间效率，首先要确定一个度量标准，最直接的办法就是将计算法转化为程序，在计算机上运行，通过计算机内部的计时
　　功能获得精确的时间，然后进行比较。但该方法受计算机的硬件、软件等因素的影响，会掩盖算法本身的优劣，所以一般采用事先分析估算的算法，
　　即撇开计算机软硬件等因素，只考虑问题的规模（一般用用自然数n表示），认为一个特定的算法的时间复杂度，只采取于问题的规模，或者说它是
　　问题的规模的函数。
　　为了方便比较，通常的做法是，从算法选取一种对于所研究的问题（或算法模型）来说是基本运算的操作，以其重复执行的次数作为评价算法时间
　　复杂度的标准。该基本操作多数情况下是由算法最深层环内的语句表示的，基本操作的执行次数实际上就是相应语句的执行次数。

一般 T（n）=O(f(n))
　　O(1)<O(log2n)<O(n)<O(n log2 n)<O(n^2)<O(n^3)<O(2^n)所以要选择时间复杂度量级低的算法。

Saturday, January 17, 2009

24点数字游戏题解

更多精彩请到 http://www.139ya.com

转自: http://blogger.org.cn/blog/more.asp?name=njucs&id=3772

24点游戏

数字游戏题解
by starfish

[说明：此文改编自我写的一篇解题报告，原题是某年国家集训队组队赛题目]

问题描述

80年代全世界流行一种数字游戏，在中国我们把这种游戏称为“24点”。现在我们
把这个有趣的游戏推广一下：您作为游戏者将得到6个不同的自然数作为操作数，
以及另外一个自然数作为理想目标数，而您的任务是对这6个操作数进行适当的算
术运算，要求运算结果小于或等于理想目标数，并且我们希望所得结果是最优的，
即结果要最接近理想目标数。
您可以使用的运算只有：+，-，*，/，您还可以使用（）来改变运算顺序。注意：
所有的中间结果必须是整数，所以一些除法运算是不允许的（例如，（2*2）/4是
合法的，2*（2/4）是不合法的）
下面我们给出一个游戏的具体例子：
若给出的6个操作数是：1，2，3，4，7和25，理想目标数是573；
则最优结果是573：（（（4*25-1）*2）-7）*3。

输入：

输入文件名为game.in。输入文件仅一行，包含7个整数，前6个整数Mi,
1<=Mi<=100，表示操作数，最后一个整数T, 1<=T<=1000,表示理想目标数。输出：输出文件名为game.out。输出文件有两行，第一行仅一个整数，表示您的程序计算得到的最优结果；第二行是一个表达式，即您得到的最优结果的运算方案。输入输出示例：输入文件 1 2 3 4 7 25 573 输出文件 573 ((4*25-1)*2)-7)*3 算法分析首先我们要对这个问题进行数学抽象。定义1：对于有理数组成的多重集合S ， f(S) 定义如下：如果 S 是空集或只包含一个元素，则 f(S)=S ；否则 f(S)=∪ f( ( S-{r1, r2}) ∪ {r} ) ，对于每一个 r=r1+r2 , r1-r2 , r1×r2 ，r1÷r2(r2≠0)，且r1, r2取遍 S 中所有元素的组成的二元组。定义1说明：要计算集合S中的元素通过四则混合运算所能得到的所有值，我们只需要任取 S 中的两个元素 r1 , r2 ，分别计算 r1 , r2 的加减乘除运算，然后用所得的结果与 S 中剩下的其他数字进行四则混合运算。只要取遍所有的 r1 , r2 ，最后得到的所有结果的并集就是 S 中的元素通过四则混合运算所能得到的所有值的集合。根据上述定义，在本问题中，集合 S 就是由输入中给定的6个正整数组成的集合，题目所求就是找出 f(S) 中小于或等于目标数的最大数。定义2：给定两个多重集合 S1 , S2，定义 comb( S1, S2 ) = ∪ { r1+r2 , r1-r2, r1×r2, r1÷r2(r2≠0) } (1.1) 其中 ( r1 , r2 ) ∈ S1 × S2。定义2实际上定义了两个集合中的元素两两进行加减乘除运算所能得到的结果集合。定理1：对于有理数组成的多重集合 S ，如果 S 至少有两个元素，则 f(S)=∪ comb( f(S1), f(S - S1) ) (1.2) 其中 S1 取遍 S 的所有非空真子集。定理1的含义是：要计算 S 中的元素通过四则混合运算所能得到的所有值，可以先将 S 分解为两个子集 S1 和 S- S1 ，分别计算 S1 和 S-S1 中的元素进行四则混合运算所能得到的结果集合，即 f(S1) 和 f(S-S1) ，然后对这两个集合中的元素进行加减乘除运算，即 comb( f(S1), f(S-S1) ) ，最后得到的所有集合的并集就是 f(S) 。限于篇幅，定理1的正确性易用数学归纳法证明。定义1和定理1实际上分别给出了计算f(S)的两种不同的方法。根据定义1，可以递归地计算f(S) ，其算法伪代码如下：算法1 function f(S) begin 1. if |S| <> 0) and (r1 mod r2 = 0) then
14. begin
15. r ← r1 / r2;
16. T ← T + f(S – {r1, r2} + {r});
17. end
18. end
19. return T;
20. end
end

上述伪代码中使用了+, - 来分别表示集合的并和差运算。算法1每次选择两个数字
进行某种运算，然后将结果与剩下的数字递归地进行运算，最后求得所有数字进行
四则混合运算的结果。当然，在具体实现该算法的过程中有很多可以优化的地方，
比如根据加法交换律， a+b+c=a+c+b ，因此我们可以规定：如果上一层递归作了
加法运算，这一层仅当满足当前的操作数大于上一层的两个操作数的时候才进行加
法运算，以确保 a+b+c 这样的式子中的操作数总是从小到大排列，这样就可以避
免重复进行等价的加法计算。类似地我们可以对乘法也作此规定。在进行减法的时
候，我们可以规定只能计算大数减小数，因为最后所需计算得到的目标数是一个正
数，如果计算过程中出现负数，肯定有另外一个较大的正数与其作加法或者有另外
一个负数与其做乘除法以消除负号。因此我们总可以调整运算次序使得四则混合运
算的每一步的中间结果都是正数。在作除法的时候，因为题目规定中间结果只能是
整数，所以也只需要用大数除小数，且仅当能除尽的时候才进行除法。对于本题而
言，初始的集合 S 中一共有6个操作数，每次递归都可以合并两个操作数，所以递
归到第5层的时候集合 S 中只剩下一个数，这个数就是原先的6个操作数进行四则
混合运算所能得到的结果。本题只要求最接近目标值的结果，所以实现上述算法的
时候可以只记录当前最优的结果。对于本题也可以利用递归回溯构造出所有的四则
混合运算的语法树，但本质上与算法1是没有区别的。

定理1则给出了另一种计算f(S)的方法。我们当然也可以根据(1.2)式直接地递归计
算f(S)，但那样的话会有很多冗余计算。例如对于S={1,2,3,4}，
f(S) = comb( f({ 1 }), f({ 2,3,4}) )∪ ... ∪ comb( f({ 1,2 }), f({
3,4 }) ) ∪ ...;
计算f(S)的时候需要计算 f({ 2,3,4 })和f({ 3,4 }) ，又因为
f({2,3,4}) = comb(f({ 2 }), f({3,4})) ∪ ...;
在计算 f({ 2,3,4}) 的时候又要重复地计算 f({ 3,4 }) ，这就产生了冗余的计
算。这种情况下直接地递归就不适用。必须按照一定的顺序，递推地进行计算。这
种将递归改为递推，以解决冗余的算法设计策略，就叫做动态规划。

下面我们具体阐述一下该算法的步骤。设初始时集合 S 中的 n 个数字分别为
x[0], x[1],...,x[n-1] ，我们可以用一个二进制数k来表示S 的子集 S[k] ，
x[i] ∈ S[k] 当且仅当二进制数k的第i位为1。于是我们用一个数组 F[0..2^n-1]
就可以保存函数f对于S的所有子集的函数值（注意，函数f的函数值是一个集合）
，且 F[2^n-1]=f(S) 就是所求。

算法2
1. for i ← 0 to 2^n-1
2. do F[i]←Φ;
3. for i ← 0 to n-1
4. do F[2^i]← {x[i]};
5. for x ← 1 to 2^n-1 do
6. begin
7. for i ← 1to x-1 do
8. begin
9. if x∧i=i then
10. begin
11. j ← x – i;
12. if i < i="i" i="i" 15="" 3="" function="" s1="" for="" each="" y="" in="" s2="" do="" begin="" t="" if="" x=""> y then
9. begin
10. T ← T + {(x – y)};
11. if (y <> 0) and (x mod y = 0)
12. then T ← T + {(x / y)};
13. end
14. else begin
15. T ← T + {(y – x)};
16. if (x <> 0) and (y mod x = 0)
17. then T ← T + {(y / x)};
18. end;
19. end;
20. end;
21. return T;

comp在进行计算的时候不考虑参数集合S1和S2的顺序，进行减法的时候始终用大
数减小数，这样保证运算过程中不出现负数（这样做的理由前文已经阐明）。

因为我们只关心最后的f(S)中最接近目标值的数字，并且题目只要求求出任何一组
最优解，所以算法2中的集合不需要是多重集合，只要是一般的集合即可。换句话
说，集合F[i]中所有的元素互不相同，重复出现元素的我们只保留其中一个。这样
可以大大减少计算中的冗余。做了这样的处理后，算法2的效率至少不会比算法1差
，因为算法1中所能采用的主要剪枝手段是排除等价的表达式，但因为等价的两个
表达式计算出的结果也一定相同，而算法2排除了所有结果相同的表达式，所以算
法2的效率至少不会比算法1差，算法2中所进行的计算基本上都是得到最优解所必
需的计算。

在实现算法2的过程中，集合可以用一个链表加上一个哈希表来实现。链表中保存
每个表达式及其值，哈希表用来记录该集合中是否存在某个特定值的表达式。当向
集合中插入一个新的表达式的时候，首先检查哈希表，看看该集合是否已经有和新
表达式值相同的表达式，如果有的话就不插入，否则将新的表达式追加到链表末尾
。采用这种数据结构，可以在常数时间内完成集合的插入和删除操作。利用链表，
集合的并操作也很容易高效地实现。

在实现算法2的过程中，可以不必保存表达式的字符串，只需要记录下当前的值是
由哪两个集合中的元素通过哪种运算得到的，最后再根据最优解递归地计算出最优
解的表达式。这样只在最后构造最优解的表达式时才进行字符串操作，程序运行效
率能提高7～8倍左右。另外，在comb函数中进行乘法运算的时候要注意考虑运算结
果超出整数范围的情况。

经过以上优化，利用算法2实现的程序对于100个随机生成的测试数据总共只需要5
秒左右就可以出解，平均每个数据只需要50毫秒即可出解（测试用的CPU为赛扬
1GB）。这样的效率已经非常令人满意了。

附录：

1。根据算法1计算24点的代码

#include
#include
#include

using namespace std;

const double PRECISION = 1E-6;
const int COUNT_OF_NUMBER = 4;
const int NUMBER_TO_CAL = 24;

double number[COUNT_OF_NUMBER];
string expression[COUNT_OF_NUMBER];

bool Search(int n)
{
if (n == 1) {
if ( fabs(number[0] - NUMBER_TO_CAL) < i =" 0;" j =" i" a =" number[i];" b =" number[j];" expa =" expression[i];" expb =" expression[j];" i =" 0;">> x;
number[i] = x;
itoa(x, buffer, 10);
expression[i] = buffer;
}

if ( Search(COUNT_OF_NUMBER) ) {
cout << "Success." <<>
#include
#include
#include
#include
#include
#include
#include
using namespace std;

const char* INPUT_FILE = "game.in";
const char* OUTPUT_FILE = "game.out";
const int NUMBER_COUNT = 6;
const int STATE_COUNT = (1 << max_number =" 100;" max_expection =" 1000;" max_value =" MAX_EXPECTION"> NodeList;

struct State {
bitset exist;
NodeList nodelist;
};

int number[NUMBER_COUNT], expection;
State state[STATE_COUNT];

void ReadData()
{
ifstream fin(INPUT_FILE);

for (int i = 0; i <>> number[i];
}
fin >> expection;
}

void Init()
{
Node node ;
for (int i = 0; i < value =" number[i];" left =" node.right" i =" state[a].nodelist.begin();" j =" state[b].nodelist.begin();" value =" (*i).value" left =" a;" right =" b;" leftvalue =" (*i).value;" rightvalue =" (*j).value;" opr =" '+';" tmp =" double((*i).value)" value =" (*i).value" left =" a;" right =" b;" leftvalue =" (*i).value;" rightvalue =" (*j).value;" opr =" '*';">= (*j).value) {
node.value = (*i).value - (*j).value;
node.left = a;
node.right = b;
node.leftvalue = (*i).value;
node.rightvalue = (*j).value;
node.opr = '-';
} else {
node.value = (*j).value - (*i).value;
node.left = b;
node.right = a;
node.leftvalue = (*j).value;
node.rightvalue = (*i).value;
node.opr = '-';
}

if ( (node.value <= MAX_VALUE) && (!state[x].exist[no de.value]) ) { state[x].nodelist.push_back(node); state[x].exist[node.value] = true; } ///////////////////////////////////////////////////// if ( ((*j).value != 0) && ((*i).value >= (*j).value) &
&
((*i).value % (*j).value == 0) )
{
node.value = (*i).value / (*j).value;
node.left = a;
node.right = b;
node.leftvalue = (*i).value;
node.rightvalue = (*j).value;
node.opr = '/';
} else if ( ((*i).value != 0) && ((*j).value >= (*i).

value) &&
((*j).value % (*i).value == 0) )
{
node.value = (*j).value / (*i).value;
node.left = b;
node.right = a;
node.leftvalue = (*j).value;
node.rightvalue = (*i).value;
node.opr = '/';
}

if ( (node.value <= MAX_VALUE) && (!state[x].exist[no

de.value]) )
{
state[x].nodelist.push_back(node);
state[x].exist[node.value] = true;
}
/////////////////////////////////////////////////////

}
}
}

void Solve()
{
Init();

for (int x = 2; x < STATE_COUNT; x++) {
for (int i = 1; i < x; i++) {
if ( (x & i) == i ) {
int j = x - i;
if (i <= j) {
Merge(i, j, x);
}
}
}
}
}

void PrintExpression(ostream& out, Node node)
{
if (node.left == -1) {
out << node.value;
} else {
NodeList::const_iterator iter;

out << "(";

for (iter = state[node.left].nodelist.begin();
iter != state[node.left].nodelist.end();
iter++)
{
if ((*iter).value == node.leftvalue) {
PrintExpression(out, *iter);
break;
}
}

out << node.opr;

for (iter = state[node.right].nodelist.begin();
iter != state[node.right].nodelist.end();
iter++)
{
if ((*iter).value == node.rightvalue) {
PrintExpression(out, *iter);
break;
}
}

out << ")";
}
}

void Output()
{
ofstream fout(OUTPUT_FILE);

int bestValue = -INT_MAX;
NodeList::const_iterator iter, bestIter;

NodeList& nodelist = state[STATE_COUNT-1].nodelist;

for (iter = nodelist.begin(); iter != nodelist.end(); iter++)
{
if ( ((*iter).value <= expection) && (bestValue < (*iter).val

ue) ) {
bestValue = (*iter).value;
bestIter = iter;
}
}
fout << bestValue << endl;
PrintExpression(fout, *bestIter );
fout << endl;
}

int main()
{
ReadData();
Solve();
Output();
return 0;
}

Tuesday, November 11, 2008

算法链接

Thursday, September 25, 2008

如何能中500万？

更多精彩请到 http://www.139ya.com

http://www.cctv.com/program/jjyf/20080923/104103.shtml

从上面这个新闻里看到一个哈尔滨的幸运儿两年内买双色球连中两个500万的消息，他真是太幸运了，但他也是不幸的，因为接下来他沉迷于彩票，又输光了所赢得的一切...

抛开他的幸运与不幸不谈，作为一个普通人如何能中500万呢？我这儿倒是有一个办法

每次都坚持买同一个号码的蓝球，比如蓝球7，不中的话下次追加一倍继续买蓝球7号，这就是一个简单的等比数列求和，以第一次投入2元为例，中奖后盈利：

total = 2^(n - 1) * 5 - (2^n * 2 - 2) = 2^(n - 1) * (2^2 + 1) - 2^(n + 1) + 2 = 2^(n + 1) + 2^(n - 1) - 2^(n + 1) + 2 = 2^(n - 1) + 2

只有没有后台操控，而且资金足够，同时中奖时n不能太大（比如不超过12，超过了奖池里的钱可能就不够发奖了^_^），结果肯定是赚的

Wednesday, September 10, 2008

一道google笔试题以及解答

更多精彩请到http://www.139ya.com

来源:http://simplesource.blog.163.com/

转自:http://blog.csdn.net/simplecoding/archive/2007/05/16/1611500.aspx

一道google笔试题以及解答

我的一个好朋友参加了一次google招聘的笔试，遇到一道算法题不会做。我思考了一下，初步给出了以下解答，可能有纰漏和错误，仅供大家参考，高手也可以给出自己的算法进行解答，看看哪种算法最优。

问题：写一个算法，求一个有n个节点的二叉树中有m个节点的连通图的个数，分析算法复杂度。

解决方法(分治法)

1、将每个节点以及这个节点的所有子节点看作是一棵子树

2、设每棵子树有一组属性：n, N[n + 1] M[n + 1]

n: 组大小

N[0~n]: 含有树根节点的连通图个数(N[i]表示节点数为i的连通图个数)

M[0~n]: 不含树根节点的连通图个数(M[i]表示节点数为i的连通图个数)

注意：N和M数组下标为0~n，大小为n + 1

（实际上组的大小必定为这棵树的子节点数目 + 1）

3、从叶子节点开始遍历

举例说明：

a) 对于一棵没有子节点的树：n = 1,N[0] = 0, N[1] = 1, M[0] = 0, M[1] = 0

b) 对于一棵只有一边子树的树：

因为B的属性已经求得，假设为：

N[0, NB1, NB2…NBn]

M[0, MB1, MB2…MBn]

则A的属性为：

nB + 1

N[0, 1, NB1 , NB2 , …, NBn ]

M[0, NB1 + MB1, NB2 + MB2, …, NBn + MBn, 0]

c) 对于一棵有两边子树的树：

因为B, C的属性已经求得，假设为：

N[0, NB1, NB2…NBn]

M[0, [MB1, MB2…MBn]

N[0, NC1, NC2…NCn]

M[0, MC1, MC2…MCn]

则A的属性为：

n = nB + nC + 1

N[i] 的计算:

N[] = [0](清零)

N[1] = 1

for(j = 0; j <= nB; j++)

{

for(k = 0; k <= nC; k++)

{

N[ j + k + 1] += NBj + NCk;

}

M[0, NB1 + MB1 + NC1 + MC1, NB2 + MB2 + NC2 + MC2, …, NBn + MBn + NCn - 1 + MCn - 1, 0]

4、最后求出根节点的属性后

取N[m] + M[m]即所求连通图的个数

算法复杂度分析：

整个算法中最复杂的是第三步中的两重循环，如果二叉树为完全二叉树T(n)(n表示节点数)，则 T(1) 需要计算0次

T(3) 需要计算(1 + 1) * (1 + 1) = 4次

T(7) 需要计算(1 + 1) * (1 + 1) * 2 + (3 + 1) * (3 + 1) = 24次

T(15) 需要计算(1 + 1) * (1 + 1) * 2^2 + (3 + 1) * (3 + 1) * 2^1 + (7 + 1) * (7 + 1) * 2^0 = 112次

T(2^n – 1) 需要计算T(2^(n – 1) - 1) * 2 + (2^(n - 1)) * (2^(n - 1)) 次

= (1 + 1) * (1 + 1) * 2^(n - 2) + (3 + 1) * (3 + 1) * 2^(n - 3) + (7 + 1) * (7 + 1) * 2^(n - 4) +… + (2^(n - 1)) * (2^(n - 1)) * (2^0) = 2^n * (2^(n - 1) - 1) = (2^n - 1 + 1) * (2^n - 1 - 1) = (N + 1) *（N - 1）/ 2 = (N * N - 1) / 2

即对于一棵节点数为N的完全二叉树需要计算约N*N/2次

所以算法复杂度为O(n^2)

饭桶精英

Wednesday, May 13, 2009

SQL Parser

Tuesday, May 12, 2009

数据结构——栈的应用，中缀表达式转换为后缀表达式

Wednesday, April 1, 2009

Cache替换算法［转]

Saturday, February 7, 2009

十进制数转换为二进制,八进制,十六进制数的算法

车牌识别及验证码识别的一般思路

Wednesday, January 21, 2009

中缀到后缀表达式的转换

算法的时间复杂度（计算实例）

时间复杂度

Saturday, January 17, 2009

24点数字游戏题解

Tuesday, November 11, 2008

算法链接

Thursday, September 25, 2008

如何能中500万？

Wednesday, September 10, 2008

一道google笔试题以及解答

Soyez bienvenu

Libellés

Archive de blog

Ma liste de blogs

Qui êtes-vous ?

Wednesday, May 13, 2009

Tuesday, May 12, 2009

Wednesday, April 1, 2009

Saturday, February 7, 2009

Wednesday, January 21, 2009

Saturday, January 17, 2009

Tuesday, November 11, 2008

Thursday, September 25, 2008

Wednesday, September 10, 2008

Soyez bienvenu

S’abonner à

Libellés

Archive de blog

Ma liste de blogs

Qui êtes-vous ?