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

时间：2009-08-18 来源：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;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的想法....这些天的努力也是值得的.