严格递增数组Q中的每个元素都能被a和b中的至少一个数整除，现给定a和b以及N，求数组Q的前N项，函数接口如下：void generate(int a, int b, int N, int *Q);比如：a = 3, b = 5, N = 6,则Q = {3, 5, 6, 9, 10, 12}。
分析题目可以发现，数组Q中的每个元素都是3或者5的倍数，且严格递增，所以如果确定在某一时刻，若数组中已经确定了k项，数组中已经确定的元素中是a的最大的倍数的数是a * i，是b的最大的倍数的数是b * j，那么第k + 1项必然是a * (i + 1)和b * (j + 1)中的较大者。细节处理，由于数组是严格递增的，所以对于即是a的倍数又数b的倍数的数只能出现一次，所以如果a * (i + 1) = b * (j + 1)，则需要i++, j++;否则只需要较小者自增1。
代码如下：
1 void generate(int a, int b, int N, int *Q) {
2 assert(N >= 0 && Q && a > 0 && b > 0);
3 if (N == 0) {
4 return;
5 }
6 if (N == 1) {
7 Q[0] = a > b ? b : a;
8 return;
9 }
10 int min = a > b ? b : a;
11 int max = a > b ? a : b;
12 int index_min = 1;
13 int index_max = 0;
14
15 int k = 1;
16 Q[0] = min;
17 if (min == max) {
18 index_max = 1;
19 }
20
21 while (k < N) {
22 if (min * (index_min + 1) < max * (index_max + 1)) {
23 Q[k++] = min * (++index_min);
24 } else if (min *(index_min + 1) == max * (index_max + 1)) {
25 Q[k++] = min * (++index_min);
26 index_max++;
27 } else {
28 Q[k++] = max * (++index_max);
29 }
30 }
31 }
需要注意的细节是a和b相等的情况。
posted on 2012-09-09 21:08
myjfm 阅读(344)
评论(0) 编辑 收藏 引用 所属分类:
算法基础