VPF::найти пересечение массивов - Форум программистов

Sparco

Дата 25.1.2006, 13:44 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 25.1.2006

Репутация: нет
Всего: нет

Помогите с нахождением пересечения массивов... Я вот попробовал, но препод говорит что неправильно! Надо найти одинаковые числа в двух массивах и записать эти одинаковые в третий,перебирать числа надо попорядку, если совпадает то переносим в третий, если не возвращаем 0....

Earnest

Дата 25.1.2006, 19:22 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 53
Всего: 183

Массивы упорядоченные?
если да (или можно предварительно отсортировать), то:
Вариант 1:
Ptr1 = адрес первого массива, Ptr2 = адрес второго
ЦИКЛ (пока один из указателей не вышел за пределы своего массива)
IF *Ptr1 == *Ptr2,
копируем в третий массив,
Ptr1++, Ptr2++
ELSE IF *Ptr1 < *Ptr2
Ptr1++
ELSE Ptr2++;

Если массивы не упорядочены, и сортировать нельзя, то остается только
Вариант 2:
Для каждого элемента первого массива
Ищем его во втором массиве...

--------------------

...

Fighter

Дата 29.1.2006, 02:25 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 810
Регистрация: 5.1.2005

Репутация: нет
Всего: 2

А значения в массивах повторяются?

nikitao

Дата 29.1.2006, 11:33 (ссылка)

(нет голосов)

Загрузка ...

Кот-программист

Профиль
Группа: Завсегдатай
Сообщений: 1206
Регистрация: 30.8.2005
Где: Спб

Репутация: 1
Всего: 26

Sparco,покажи тот код ,что преподу показавал.Его переделовать будем smile

--------------------

Жизнь - печальная штука.

Chaos A.D.

Дата 29.1.2006, 15:59 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 172
Регистрация: 16.1.2005
Где: 09 RUS

Репутация: 6
Всего: 7

Есть пара стандартных алгоритмов из STL, можно заюзать их. На память название не помню, но по-моему это adjacent_difference из <numeric>. Посмотри этот алгоритм.

--------------------

Надо смеяться над тем, что тебя мучит, иначе не сохранишь равновесия, иначе мир сведет тебя с ума...Ken Kesey - One Flew Over The Cocoo's Nest

Sparco

Дата 30.1.2006, 15:23 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 25.1.2006

Репутация: нет
Всего: нет

Цитата

Mnogestva Mnogestva::operator *(const Mnogestva & a)
{
int i,j,k;
bool flag;
Mnogestva c(0);
for (i=0; i<size; i++) {
for (j=0; j<a.size; j++)
if (m_a[i]==a.m_a[j]) {
flag=false;
for (k=0; k<c.size; k++)
if (c.m_a[k]==m_a[i]) flag=true;
if (!flag) c.Add(m_a[i]);
}
}
c.Sort();
return c;
}

Вот что я пытался сделать. Использовать библиотеку нельзя....

threef

Дата 30.1.2006, 18:41 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 375
Регистрация: 27.10.2005
Где: Запорожье

Репутация: 9
Всего: 10

Возможно, в множествах у тебя не может быть повторяющихся элементов, тогда нет смысла в поиске совпадений в новом массиве. Возможно, они сразу отсортированы, тогда задача еще упрощается.
Есть ли у тебя конструктор копирования, чтобы возвращать "с" по значению ?
Могут ли твои множества сортироваться в принципе ?

вот два варианта, второй - это твой без флага

Код



#define WITH_SORT

#ifdef WITH_SORT

Mnogestva Mnogestva::operator *(const Mnogestva & a)
{
  Sort();
  a.Sort();
  int i=0,j=0,k=0;
  Mnogestva c(0);
  while(i<size && j< a.size )
  {
      m_a[i]<a.m_a[j] ?  i++ :
               m_a[i]>a.m_a[j] ? j++ :
               //проверяем с последним вставленным элементом,
               // т.к. множества отсортированы
               (m_a[i]!=c.m_a[c.size-1] ? c.Add(m_a[i]) : 0)
                ,i++,j++ ;
  }
   //  c already sortet
   return c;
}

#else

Mnogestva Mnogestva::operator *(const Mnogestva & a)
{
  int i,j,k;
  Mnogestva c(0);
 
  for (i=0; i<size; i++) {
      for (j=0; j<a.size; j++)
        if (m_a[i]==a.m_a[j]) 
        {
            for (k=0; k<c.size; k++)
              if (c.m_a[k]==m_a[i]) break;
            if (k==c.size) c.Add(m_a[i]);
        }
}
c.Sort();
return c;
}

#endif

если нет конструктора копирования, то "с" лучше сделать динамическим

Mnogestva *c=new Mnogestva (0);

и возвращать указатель...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »