关于《微软的面试试题的c语言算法》的讨论

本章中有二个问题：  
   
  一、《微软的面试试题的c语言算法》  
  先前有人给出了一道：  
   
  这是csdn的一个帖子：  
   
  求第1500个只有2,3,5因子的数          
  数是从小到大排列          
  第一个数是1,1=2^0*3^0*5^0          
  要求用C实现,至少要讲清楚算法思路    
  如：1，2，3，4，5，6，8，9，10，12，15，18，20，24，25......  
   
  我用了1个下午，编了一个非常秒的程序（程序见下），只花1秒钟就（有时要不了，看机性能）能搞定，   不知有人能用更简单的算法解决出来么？我向高手请教！！  
   
  程序1：  
   
  #include   <stdio.h>  
  #include   <time.h>  
   
  #define   M   1500  
   
  /*   M   ，   第M个   */  
   
  void   main()  
  {  
          double   a[M]={1.0};  
          int   x[3]={0};  
          int   y[3]={2,3,5};  
          int   count=1;  
          time_t   tm;  
   
          tm=time(0);  
          printf("%d   count,   result:       %lf\n",count,a[count-1]);  
          while(count<M)  
          {  
          register   int   min;  
                  if(a[x[0]]<1.5*a[x[1]])  
                          if(a[x[0]]<2.5*a[x[2]])  
                                  min=0;  
                          else  
                                  min=2;  
                  else  
                          if(3*a[x[1]]<5*a[x[2]])  
                                  min=1;  
                          else  
                                  min=2;  
                  if(y[min]*a[x[min]]>a[count-1])  
                  {  
                          a[count]=y[min]*a[x[min]];  
                          count++;  
                          printf("%d   count,   result:       %lf\n",count,a[count-1]);  
                  }  
                  x[min]++;  
          }  
   
          printf("*****************\n");  
          printf("%d   count,   LastResult:       %lf\n",count,a[count-1]);  
   
          printf("%d\n",(int)(time(0)-tm));   /*   计算时间（好机子，根本用不了1秒！）   */  
          getch();  
  }  
   
  答案：859963392  
  *********************************************************************************  
   
  二、由微软题联想到的  
   
  还有一个类似的题，题目是这样的：  
   
  求第1500个含有2,3,5因子的数（至少含有其中一个）          
  数是从小到大排列          
  第一个数是1,1=2^0*3^0*5^0*other...    
  （如14=   2^1*3^0*5^0*7）        
  要求用C实现,至少要讲清楚算法思路    
  如：1，2，3，4，5，6，8，9，10，12，14，15，16，18，20，22，24，25，26......  
   
  我也做出来了，比较复杂，请高手指教有更简单的方法没（也是1秒钟搞定）  
   
  程序2：  
   
  #include   <stdio.h>  
  #include   <time.h>  
   
  #define   M   1500  
   
  /*   M   ，   第M个   */  
   
  void   main()  
  {  
          double   a[M]={1.0};  
          int   x[3]={0};  
          int   y[3]={2,3,5};  
          int   count=1;  
          time_t   tm;  
   
          tm=time(0);  
          printf("%d   count,   result:       %lf\n",count,a[count-1]);  
          while(count<M)  
          {  
          register   int   min;  
                  if(a[x[0]]<1.5*a[x[1]])  
                          if(a[x[0]]<2.5*a[x[2]])  
                                  min=0;  
                          else  
                                  min=2;  
                  else  
                          if(3*a[x[1]]<5*a[x[2]])  
                                  min=1;  
                          else  
                                  min=2;  
                  if(y[min]*a[x[min]]>a[count-1])  
                  {  
                          a[count]=y[min]*a[x[min]];  
                          count++;  
                          printf("%d   count,   result:       %lf\n",count,a[count-1]);  
                  }  
                  x[min]++;  
          }  
   
          printf("*****************\n");  
          printf("%d   count,   LastResult:       %lf\n",count,a[count-1]);  
   
          printf("%d\n",(int)(time(0)-tm));   /*   计算时间（好机子，根本用不了1秒！）   */  
          getch();  
  }  
   
   
  答案：   2044  
   
  *************************************************************************************  
  附送N皇后经对称式修改后比较快的一种解法（引用与最快的八皇后问题一文中，我稍做了些修改）：  
   
  /*     N   Queens   Problem   */  
  /*     试探-回溯算法，递归实现   */  
   
  /*     sum用来记录皇后放置成功的不同布局数；upperlim用来标记所有列都已经放置好了皇后。   */  
   
  #include   <time.h>  
   
  long   sum   =   0,   upperlim   =   1,half=0;  
   
  /*     试探算法从最右边的列开始。   */  
  void   test(long   row,   long   ld,   long   rd)  
  {  
        if   (row   !=   upperlim)  
        {  
   
      /*     row，ld，rd进行“或”运算，求得所有可以放置皇后的列,对应位为0，   */  
                      /*     然后再取反后“与”上全1的数，来求得当前所有可以放置皇后的位置，对应列改为1。   */  
                      /*     也就是求取当前哪些列可以放置皇后。   */  
        long   pos   =   upperlim   &   ~(row   |   ld   |   rd);  
      while   (pos)   /*     0   --   皇后没有地方可放，回溯。   */  
      {  
   
          /*     拷贝pos最右边为1的bit，其余bit置0。   */  
          /*     也就是取得可以放皇后的最右边的列。   */  
          {  
                            long   p   =   pos   &   -pos;  
   
                    /*     将pos最右边为1的bit清零。   */  
                                    /*     也就是为获取下一次的最右可用列使用做准备，   */  
                                    /*     程序将来会回溯到这个位置继续试探。   */  
                          pos   -=   p;                                                          
   
                    /*     row   +   p，将当前列置1，表示记录这次皇后放置的列。   */  
                    /*     (ld   +   p)   <<   1，标记当前皇后左边相邻的列不允许下一个皇后放置。   */  
                    /*     (ld   +   p)   >>   1，标记当前皇后右边相邻的列不允许下一个皇后放置。   */  
                                            /*     此处的移位操作实际上是记录对角线上的限制，只是因为问题都化归   */  
                                            /*     到一行网格上来解决，所以表示为列的限制就可以了。显然，随着移位   */  
                                            /*     在每次选择列之前进行，原来N×N网格中某个已放置的皇后针对其对角线   */  
                                            /*     上产生的限制都被记录下来了。     */  
   
                          if(row==0&&p>half)  
                                continue;  
                          else  
                                test(row   +   p,   (ld   +   p)   <<   1,   (rd   +   p)   >>   1);  
          }  
      }  
        }    
        else          
        {  
    /*     row的所有位都为1，即找到了一个成功的布局，回溯。   */  
      sum++;  
   
        }  
  }  
   
  int   main(int   argc,   char   *argv[])  
  {  
        time_t   tm;  
        int   n   =   16;  
   
        if   (argc   !=   1)  
      n   =   atoi(argv[1]);  
        tm   =   time(0);  
   
        /*     因为整型数的限制，最大只能32位，   */  
        /*     如果想处理N大于32的皇后问题，需要   */  
        /*     用bitset数据结构进行存储。   */  
        if   ((n   <   1)   ||   (n   >   32))                                      
        {  
      printf("   只能计算1-32之间\n");  
      exit(-1);  
        }  
        printf("%d   皇后\n",   n);  
   
        /*   采用对称式算法计算，增加全局变量half   */  
        half=(n-1)/2;  
        half=upperlim<<half;  
        /*     N个皇后只需N位存储，N列中某列有皇后则对应bit置1。   */  
        upperlim   =   (upperlim   <<   n)   -   1;  
   
   
        test(0,   0,   0);  
        printf("all   %ld   counts,   ji   suan   time   %d   miao   \n",   sum*2,   (int)   (time(0)   -   tm));  
        getch();  
        /*   78秒   1.8G   632M   */  
  }