一个文件里有10万个随机正整数,按照以下规则能组合出一份新的数据:
A. 如果当前数字能被3整除,那么它和文件中所有数字(包括自己)两两相加后生成一组数字替代自己的位置。
B. 如果不能被3整除,则它只需要乘以二,生成一个数字替代自己的位置。
例如:[3,7,6] 会组合出[6,10,9,14,9,13,12]
再如:[5,12,9,6,2]会组合出[10,17,24,21,18,14,14,21,18,15,11,11,18,15,12,8,4]
写一个程序找出并打印出新数据的最小的前200个数字。请考虑优化算法复杂度。
void print(int *a, int len)
{
int i = 0;
for (; i {
printf("%d ", a[i]);
}
printf("\n");
}
int * process(int *a, int len, int &k)
{
int i = 0;
int j = 0;
int *b = new int[len*len];
int *p = b;
for (; i {
if (a[i] % 3 == 0)
{
for (j = 0; j {
*(p+k) = a[i] + a[j];
k++;
}
}
else
{
*(p + k) = 2 * a[i];
k++;
}
}
for (i = 0; i printf("%d ", b[i]);
printf("\n");
return b;
}
void adjust(int *a, int beg, int end)
{
int i;
int temp = a[beg];
for (i = 2 * beg+1; i <=end; i = 2 * i+1)
{
if (i {
i++;
}
if (temp >= a[i])
{
break;
}
a[beg] = a[i];
beg = i;
}
a[beg] = temp;
}
void creatHead(int *a, int len)
{
int i;
for (i = (len-1) / 2; i >= 0; i--)
{
adjust(a, i, len - 1);
}
}
void sort(int *a, int len, int min)
{
int i;
int j;
for (i = min; i {
if (a[0] > a[i])
{
a[0] = a[i];
}
adjust(a, 0, min - 1);
print(a, 5);
}
}
int main()
{
//int a[3] = { 3, 7, 6 };
//int num = 0;
//int *b = process(a, 3, num);
//creatHead(b, 4);
//print(b, 4);
//sort(b, num, 4);
//print(b, 4);
int a[5] = { 5, 12, 9, 6, 2 };
int num = 0;
int *b = process(a, 5, num);
creatHead(b, 5);
print(b, 5);
sort(b, num, 5);
print(b, 5);
}