google 2009笔试题-正整数序列Q

ubuntuer

   正整数序列Q 中的每个元素都至少能被正整数a和b中的一个整除,现给定a和b, 需要计算出Q中的前几项,例如,当a=3, b=5, N=6时,序列3,5,6,9,10,12
   设计一个函数void generate(int a, int b, int N, int* Q)计算Q的前几项

   最近突发奇想看看google的笔试题,突然怎么感觉so easy!!!!呵呵...看来前段时间猛看DS,还是有收获的。
   以前要是拿到这题肯定是
    for(i=min(a,b);;i++)
     {
       if(i%a==0 || i%b == 0)
        {
          count++;
          if(count==N)
            break;
        }
     }
    当然这个也是可以的,刚把题目给小徒弟做了,怀疑她就会这么做^_^
   好了,说我的思路,其实Q就是
    a*(1,2,3,4....)
    b*(1,2,3,4....)

   知道这个就好说了
   
for(i=0;iN;i++)
    {
      if(a*count_a  b*count_b)
       {
          Q = a*count_a;
          count_a++;
       }
      else
       {
         Q = b*count_b;
                  
         if(a*count_a == b*count_b)
          count_a++;
         
          count_b++;
       }
      
    }

上面的乘法多计算了几次,可以把a*count_a和b*count_b先赋给两个变量,我就不写了

#include stdio.h>
#include stdlib.h>
void generate(int a, int b, int N, int* Q)
{
   int i;
   int count_a = 1;
   int count_b = 1;
   
   for(i=0;iN;i++)
    {
      if(a*count_a  b*count_b)
       {
          Q = a*count_a;
          count_a++;
       }
      else
       {
         Q = b*count_b;
                  
         if(a*count_a == b*count_b)
          count_a++;
         
          count_b++;
       }
      
    }
}
void print_array(int* Q, int N)
{
  int i;
  for(i=0;iN;i++)
   printf("%d\t",Q);
   
  printf("\n");
}
int main(int argc, char *argv[])
{
  int i;
  int num[2][3] = {{3,5,6},{3,15,6}};
  int* Q = NULL;
  
  for(i=0;i2;i++)
  {
   Q = (int*)malloc(sizeof(int)*(num[2]));
   generate( num[0], num[1], num[2], Q);
   printf("array Q is:\n");
   print_array(Q, num[2]);
   free(Q);
   Q = NULL;
  }
   
  system("PAUSE");   
  return 0;
}

做了这些题,我有了就笔试一把google的想法....这些天的努力也是值得的.


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/76292/showart_2030933.html