C++编程之美-C#自底向上的解法

static bool nim(int x, int y)
{
     // speical case
     if(x == y)
     {
          return true;		// I win
     }

     // swap the number
     if(x > y)
     {
          int t = x; x = y; y = t; 
     }

     // basic cases
     if(x == 1 && y == 2)
     {
          return false;		// I lose
     }

     ArrayList al = new ArrayList();
     al.Add(2); 

     int n = 1; 

     int delta = 1;
     int addition = 0; 

     while(x > n)
     {
          // find the next n;
          while(al.IndexOf(++n) != -1);
          delta++; 
          al.Add(n + delta); 
          addition++;

          if(al.Count > 2 && addition > 100)
          {
               // 因为数组al中保存着n从1开始的不安全局面，所以在
               // 数组元素个数超过100时删除无用的不安全局面，使数组
               // 保持在一个较小的规模，以降低后面IndexOf()函数调用
               // 的时间复杂度。 
               ShrinkArray(al, n); 
               addition = 0; 
          }
     }

     if((x != n) || (al.IndexOf(y) == -1))
     {
          return true;		// I win
     }

     else
     {
          return false;		// I lose
     }
}

static void ShrinkArray(ArrayList al, int n)
{
     for(int i = 0; i < al.Count; i++)
     {
          if((int)al[i] > n)
          {
               al.RemoveRange(0, i);
               return; 
          }
     }
}