Страница 1 из 1
C++ - Объединить два упорядоченных массива в один
Добавлено: 25 апр 2015, 19:23
miros_0571
Заданы два упорядоченных массива А и В, состоящих из N и M вещественных элементов соответственно. Соединить их в один массив С, так чтобы его элементы были упорядочены.
Помогите разобраться и найти ошибку. работает....надо исключить одинаковые элементы
Код: Выделить всё
#include<iostream.h>
#include<conio.h>
const int N= 6;
const int M= 7;
int main()
{
int A[N]={0,2,4,6,8,11};
int B[M]={1,4,5,7,9,10,12};
int*C=new int[N+M];
int i=0;
int j=0;
for (int k=0;k<N+M;k++)
{
if (A[i]<B[j] && i!=N)
C[k]=A[i++];
else if(j!=M)
C[k]=B[j++];
else
break;
}
for (int k=0; k<N+M; k++)
cout <<C[k]<<" ";
delete [] C;
getch();
return 0;
}
Re: C++ - Объединить два упорядоченных массива в один
Добавлено: 27 апр 2015, 11:47
Decoder
Наверно лучше сделать так...
Код: Выделить всё
int i = 0; // A[i]
int j = 0; // B[j]
int k = 0; // C[k]
while (i < N || j < M)
{
int v = 0;
if (i < N && j < M)
{
v = (A[i] < B[j])? A[i++] : B[j++];
} else
{
v = (N < M)? B[j++] : A[i++];
}
if (k > 0 && C[k-1] == v)
continue;
C[k++] = v;
}
// Вывод результата...
for (int m = 0; m < k; m++)
std::cout << C[m] << " ";
Re: C++ - Объединить два упорядоченных массива в один
Добавлено: 27 апр 2015, 12:16
Romeo
Следует рассматривать не два случая (A меньше B[j], иначе), а три случая (A меньше B[j], A больше B[j], иначе). В третьем случае (когда они равны), следует C[k] присваивать любой из A или B[j] (ведь они равны), но после этого увеличивать ОБА индекса i и j.
Re: C++ - Объединить два упорядоченных массива в один
Добавлено: 27 апр 2015, 12:18
Romeo
Ну можно и так, как Decoder написал. Но твой вариант тоже доработать можно, он рабочий.
Re: C++ - Объединить два упорядоченных массива в один
Добавлено: 27 апр 2015, 13:33
WinMain
В алгоритме у
Decodera есть один косяк. Если оба массива будут иметь одинаковый размер (M = N), то программа может свалиться из-за выхода индекса за границы массива в зависимости от значений элементов массива.
Вот как будет правильно:
Код: Выделить всё
while (i < N || j < M)
{
int v = 0;
if (i < N && j < M)
{
v = (A[i] < B[j])? A[i++] : B[j++];
} else
{
v = (N == i)? B[j++] : A[i++];
}
if (k > 0 && C[k-1] == v)
continue;
C[k++] = v;
}
Re: C++ - Объединить два упорядоченных массива в один
Добавлено: 27 апр 2015, 16:18
miros_0571
Romeo писал(а):Ну можно и так, как Decoder написал. Но твой вариант тоже доработать можно, он рабочий.
Теперь убирает повторение,но в конце массива надо убрать лишний элемент....Как?
Код: Выделить всё
#include<iostream.h>
#include<conio.h>
const int N= 6;
const int M= 7;
int main()
{
int A[N]={0,3,4,6,8,11};
int B[M]={1,3,5,7,9,10,12};
int*C=new int[N+M];
int i=0;
int j=0;
for (int k=0;k<N+M;k++)
{
if (( A[i]<B[j] || j>=M) && i<N)
{
C[k]=A[i];i++;
}
else if ( A[i]==B[j])
{
C[k]=B[j];i++;j++;
}
else { C[k]=B[j];j++;
}
}
for (int k=0; k<N+M; k++)
cout <<C[k]<<" ";
delete [] C;
getch();
return 0;
}
Re: C++ - Объединить два упорядоченных массива в один
Добавлено: 27 апр 2015, 16:31
WinMain
Теперь убирает повторение,но в конце массива надо убрать лишний элемент....Как?
Нужно считать, какое количество элементов было реально записано в массив с учётом исключения повторяющихся значений. При выводе массива на экран в цикле использовать получившееся число элементов. У
Decodera в алгоритме именно так и происходит.