Форум программистов, компьютерный форум CyberForum.ru

последовательности в массивах - C++

Восстановить пароль Регистрация
 
лизи
 Аватар для лизи
0 / 0 / 0
Регистрация: 14.11.2011
Сообщений: 104
30.11.2011, 02:36     последовательности в массивах #1
Даны натуральные числа m и n, последовательности целых чисел a1 a2...am и b1 b2...bm В каждой последовательности могут быть повторяющиеся члены. Приняв m<=20 n<=30
последовательности хранятся в массивах
верно ли что все члены последовательноти am входит в bn
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Сыроежка
Заблокирован
30.11.2011, 02:46     последовательности в массивах #2
Цитата Сообщение от лизи Посмотреть сообщение
Даны натуральные числа m и n, последовательности целых чисел a1 a2...am и b1 b2...bm В каждой последовательности могут быть повторяющиеся члены. Приняв m<=20 n<=30
последовательности хранятся в массивах
верно ли что все члены последовательноти am входит в bn
Если вам разрешено использовать стандартные агоритмы, то ваша задача решается с помощью двух алгоритмов. Первый - это std::sort, с помощью которого следует отсортировать оба массива. Второй - это std::includes, который определяет, входит ли один массив в другой.

Если вам не разрешено пользоваться стандартными алгоритмами, то вам самостоятельно придется написать сортировку одномерного массива, а затем сравнить массивы между собой.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
30.11.2011, 06:37     последовательности в массивах #3
Цитата Сообщение от Сыроежка Посмотреть сообщение
Если вам не разрешено пользоваться стандартными алгоритмами, то вам самостоятельно придется написать сортировку одномерного массива, а затем сравнить массивы между собой.
Зачем сортировка? Время сортировки пузырьком (а лучший алгоритм он вряд ли реализует, да и при таких n врядли даже qsort заметно выиграет) пропорционально n^2 всегда. У него будет две. n^2 и m^2. Время сравнения каждого с каждым с брейком при обнаружении пропорционально n*m, что при n>m уже меньше n^2, так ещё и в худшем случае. И ко всему прочему, повторы не дадут ни использовать includes на весь массив, ни избавиться от n*m.
лизи
 Аватар для лизи
0 / 0 / 0
Регистрация: 14.11.2011
Сообщений: 104
30.11.2011, 09:22  [ТС]     последовательности в массивах #4
Цитата Сообщение от Сыроежка Посмотреть сообщение
Если вам разрешено использовать стандартные агоритмы, то ваша задача решается с помощью двух алгоритмов. Первый - это std::sort, с помощью которого следует отсортировать оба массива. Второй - это std::includes, который определяет, входит ли один массив в другой.

Если вам не разрешено пользоваться стандартными алгоритмами, то вам самостоятельно придется написать сортировку одномерного массива, а затем сравнить массивы между собой.
и как сравнивать эти массивы?
Сыроежка
Заблокирован
30.11.2011, 12:36     последовательности в массивах #5
Цитата Сообщение от лизи Посмотреть сообщение
и как сравнивать эти массивы?
Сначала покажу, как это делается с помощью стандартных алгоритмов.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include   <iostream>
#include   <iomanip>
#include   <algorithm>
 
int main()
{
   int a[] = { 1, 3, 1 };
   int b[] = { 3, 0, -1, 1, 1};
 
   std::sort( a, a + 3 );
   std::sort( b, b + 5 );
 
   std::cout << std::boolalpha
                  << std::includes( b, b + 5, a, a + 3 )
                  << std::endl;
}
Попробуйте у себя запустить этот код.

Итак, возникает вопрос, разрешено ли вам пользоваться, например, стандартной фунецией сортировки std::sort. Если нет, то вам придется самой написать функцию сортировки.

Второй алгоритм, под названием std::includes можно самостоятельно реализовать седующим образом:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool includes( int b[], int n, int a[], int m )
{
   int i = 0, j = 0;
 
   while ( i < n && j < m )
   {
      if ( a[j]  < b[i] )
      {      
         return  ( false );
      }
      else if ( b[i] < a[j] )
      {
         i++;
      }
      else
      {
         i++; j++;
      }
   }
   return ( j == m );
}
Надеюсь, я ничего не напутал в этом алгоритме.
лизи
 Аватар для лизи
0 / 0 / 0
Регистрация: 14.11.2011
Сообщений: 104
17.12.2011, 16:25  [ТС]     последовательности в массивах #6
вот код должен быть примерно таким)
помогите найти ошибки
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
#include <math.h>
int main()
{int a[20];int b[30];int n,m,i,j,flag;
scanf("%d",&m);
scanf("%d",&n);
for (i=0;i<m;i++)
{printf("a[%d]=",i);
  scanf("%d",&a[i]); }
  for (i=0;i<n;i++)
{printf("b[%d]=",i);
  scanf("%d",&b[i]); }
 
flag=1;
for(i=0;i<m;i++)
 for(j=0;j<n;j++)
 {if (a[i]== b[j]) \колчиесво совпадение
 flag=0;}
 
 
 {if (flag)
 
 printf("vhodyat" "\n");
 else
 printf("ne vhodyat" "\n");}}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.03.2012, 20:13     последовательности в массивах
Еще ссылки по теме:

Индексация в массивах c++ C++
C++ Функции в массивах
Построить элементы в убывающей последовательности и вывести первоначальные индексы последовательности C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
лизи
 Аватар для лизи
0 / 0 / 0
Регистрация: 14.11.2011
Сообщений: 104
23.03.2012, 20:13  [ТС]     последовательности в массивах #7
больше не нужно
справилась сама)
Yandex
Объявления
23.03.2012, 20:13     последовательности в массивах
Ответ Создать тему
Опции темы

Текущее время: 15:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru