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

   正整数序列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;i<N;i++)
    {
      if(a*count_a < b*count_b)
       {
          Q[i] = a*count_a;
          count_a++;
       }
      else
       {
         Q[i] = 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;i<N;i++)
    {
      if(a*count_a < b*count_b)
       {
          Q[i] = a*count_a;
          count_a++;
       }
      else
       {
         Q[i] = 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;i<N;i++)
   printf("%d\t",Q[i]);
   
  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;i<2;i++)
  {
   Q = (int*)malloc(sizeof(int)*(num[i][2]));
   generate( num[i][0], num[i][1], num[i][2], Q);
   printf("array Q is:\n");
   print_array(Q, num[i][2]);
   free(Q);
   Q = NULL;
  }
   
  system("PAUSE");    
  return 0;
}


 

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