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

Проверить, является ли один массив подмножеством другого - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.79
juliette250
0 / 0 / 0
Регистрация: 26.03.2013
Сообщений: 5
15.04.2013, 18:36     Проверить, является ли один массив подмножеством другого #1
Здравствуйте!

Опять нужна помощь. Задание: Написать функцию, принимающую в качестве аргумента, указатели на два массива (А и В) и размеры массивов. Функция проверяет, является ли массив В подмножество массива А и возвращает указатель на начало найденного фрагмент, если элемента нет, возвращает 0.
Помогите, пожалуйста, найти ошибку!

Вот примерный код
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream>
#include<time.h>
using namespace std;
 
void Init(int*ptr,int size)
{
    for(int i=0;i<size;i++)
    {
        ptr[i]=rand()%3;
    }
}
 
void Show(int*ptr,int size)
{
    for(int i=0;i<size;i++,ptr++)
    {
        cout<<*ptr<<"\t";
    }
    cout<<endl;
}
 
int*Search(int A[], int size1, int B[], int size2)
{
    int*result=NULL;
    for(int i=0;i<size1;i++)
    {
        if(A[i]==B[0])
        {
            result=&A[i];
            int j;
            i++;
            for(j=1;j<size2&&i<size1;j++,i++)
            {
                if(A[i]!=B[j])
                {
                    return NULL;
                }
            }
            if(j<size2)
            {
                return NULL;
            }
        }
    }
    return result;
}
 
 
void main()
{
    setlocale(0, "");
    srand(time(NULL));
    int const size1=30;
    int const size2=3;
    int A[size1], B[size2];
    int count=0;
    
    
    Init(A,size1);
    Init(B,size2);
    Show(A,size1);
    Show(B,size2);
 
    int *result=A;
    int offset=0;
 
    while(result=Search(result+1,size1-offset,B,size2))
    {
        count++;
        offset=result-A;
        cout<<"Позиция найденного: "<<offset<<endl;
    }
    if(count==0)
    {
        cout<<"Вхождений не найдено!\n";
    }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.04.2013, 18:36     Проверить, является ли один массив подмножеством другого
Посмотрите здесь:

C++ Си является подмножеством С++?
C++ Сформировать один массив из другого
Один массив по основанию другого C++
C++ Проверить лежит ли один из многоугольников строго внутри другого и определить площади многоугольников
Проверить является ли одномерный числовой массив упорядоченным по убыванию C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
juliette250
0 / 0 / 0
Регистрация: 26.03.2013
Сообщений: 5
19.04.2013, 21:04  [ТС]     Проверить, является ли один массив подмножеством другого #2
Может быть, если не получается сделать на основе этого кода - то полностью переделать. Очень нужна помощь!
fedynyshyn
0 / 0 / 0
Регистрация: 14.09.2016
Сообщений: 1
14.09.2016, 22:32     Проверить, является ли один массив подмножеством другого #3
если честно сказать, то я само задание не понял)))
Байт
 Аватар для Байт
13988 / 8819 / 1230
Регистрация: 24.12.2010
Сообщений: 15,975
14.09.2016, 23:49     Проверить, является ли один массив подмножеством другого #4
juliette250, Я понял так. Есть 2 множества. Их элементы представлены в массивах целыми числами. Видимо, в каждом массиве числа должны быть несовпадающими (массив 0 1 2 1 не представляет множества) Посему совершенно непонятно, почему в функции Init вы заполняете числами 0 1 2. Вам нужно заполнить массивы разными числами из некоторого диапазона. Как это сделать - смотрите в одной из прикрепленных тем раздела Си. Хотя, наверное, в плюсах есть уже готовая std-функция.
Дальше вам надо просто перебрать элементы одного массива и выяснить для каждого элемента, есть ли он в другом массиве.
_stanislav
26 / 26 / 8
Регистрация: 16.08.2014
Сообщений: 246
Завершенные тесты: 2
14.09.2016, 23:52     Проверить, является ли один массив подмножеством другого #5
juliette250, Вот может пригодиться.
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
26
27
28
29
30
31
32
33
34
35
int* search(int* a1, int s1, int* a2, int s2)
{
    int* ret;
    int i;
 
    for (i = 0; i < s1; i++)
    {
        int j = i, k = 0;
 
        while (j < s1 && k < s2 && (a1[j] == a2[k]) )
        {
            j++;
            k++;
        }
 
        if (k == s2)
            return ret = a1 + i;
    }
 
    return nullptr;
}
 
int main(int argc, char* argv[] )
{
    int a1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    int a2[] = { 3, 4, 5, 6, 7 }; const int size = 5;
 
    int* p = search(a1, 10, a2, size);
 
    int a3[size];
    for (int i = 0; i < size && p; i++)
        a3[i] = p[i];
 
    return 0;
}
SamBars
 Аватар для SamBars
13 / 13 / 8
Регистрация: 06.10.2015
Сообщений: 88
14.09.2016, 23:54     Проверить, является ли один массив подмножеством другого #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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
using namespace std;
 
void add(int*, int);
void print(int*, int);
int* Search(int*, int*, int, int);
 
const int size_s = 3;
const int size_b = 10;
 
int main()
{
    int* small = new int[size_s];
    int* big = new int[size_b];
 
    add(small, size_s);
    add(big, size_b);
 
    print(small, size_s);
    print(big, size_b);
 
    cout << Search(small, big, size_s, size_b) << endl;
 
    return 0;
}
 
int* Search (int* small, int* big, int size_s, int size_b)
{
    vector<int*> v;
    for (size_t i = 0; i < size_s; i++)
    {
        for(size_t j = 0; j < size_b; j++)
        {
            if (small[i] == big[j])
            {
                v.push_back(&big[j]);
                i++;
                continue;
            }
            
            else if (v.size() == size_s)
            {
                break;
            }
 
            else
            {
                v.resize(0);
                continue;
            }
            
        }
        
    }
    if (v.size() == size_s)
    {
        return v[0];
    }
 
    else
    {
        return NULL;
    }
}
 
void add(int* small, int size_s)
{
    srand(time(NULL));
 
    for (size_t i = 0; i < size_s; i++)
    {
        small[i] = rand() % 4;
    }
 
 
}
 
void print(int* small, int size_s)
{
    for (size_t i = 0; i < size_s; i++)
    {
        cout << small[i] << " ";
    }
 
    cout << endl;
}
Mr.X
Эксперт С++
 Аватар для Mr.X
2803 / 1579 / 247
Регистрация: 03.05.2010
Сообщений: 3,672
15.09.2016, 01:13     Проверить, является ли один массив подмножеством другого #7
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
//Написать функцию, принимающую в качестве аргумента указатели
//на два массива (А и В) и размеры массивов. Функция проверяет,
//является ли массив В подмножество массива А и возвращает
//указатель на начало найденного фрагмент, если элемента нет,
//возвращает 0.
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
///////////////////////////////////////////////////////////////////////////////
int     *   may_serch
    (
        int     *   A_ptr,
        int         A_size,
        int     *   B_ptr,
        int         B_size
    )
{
    auto    res     =   std::search
                            (
                                A_ptr,
                                A_ptr   +   A_size,
                                B_ptr,
                                B_ptr   +   B_size
                            );
 
    return  res     ==  A_ptr   +   A_size
                ?   nullptr
                :   res;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    int     A[]     {1, 2, 3, 4, 5};
    int     B[]     {1, 2};
 
    srand(unsigned(time(0)));
 
    for(;;)
    {
        std::generate
            (
                std::begin  (B),
                std::end    (B),
 
                []
                {
                    return  rand() % 5 + 1;
                }
            );
 
        for( auto   a_elem  :   A )
        {
            std::cout   <<  a_elem
                        <<  '\t';
        }
        std::cout   <<  std::endl;
 
        for( auto   b_elem  :   B )
        {
            std::cout   <<  b_elem
                        <<  '\t';
        }
        std::cout   <<  std::endl;
 
        auto    pos     =   may_serch
                                (
                                    A,
                                    sizeof(A) / sizeof(*A),
                                    B,
                                    sizeof(B) / sizeof(*B)
                                );
 
        if( !pos )
        {
            std::cout   <<  "NOT"
                        <<  std::endl;
        }
        else
        {
            std::cout   <<  pos - A
                        <<  std::endl
                        <<  std::endl;
        }//else
 
        system("pause");
    }//for
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.09.2016, 07:13     Проверить, является ли один массив подмножеством другого
Еще ссылки по теме:

C++ Определить, является ли множество X подмножеством множества Y
Проверить является ли массив знакочередующимся C++
Проверить является ли массив В подпоследовательностью массива А C++

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

Или воспользуйтесь поиском по форуму:
_stanislav
26 / 26 / 8
Регистрация: 16.08.2014
Сообщений: 246
Завершенные тесты: 2
15.09.2016, 07:13     Проверить, является ли один массив подмножеством другого #8
juliette250, Лучше шаблон, что бы обрабатывать массивы любого типа.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<typename T, typename SizeT>
T* Search(T* a1, SizeT s1, T* a2, SizeT s2)
{
    SizeT i;
    for (i = 0; i < s1; i++)
    {
        SizeT j = i, k = 0;
        while (j < s1 && k < s2 && (a1[j] == a2[k]) )
        {
            j++;
            k++;
        }
 
        if (k == s2)
            return a1 + i;
    }
 
    return 0;
}
Yandex
Объявления
15.09.2016, 07:13     Проверить, является ли один массив подмножеством другого
Ответ Создать тему
Опции темы

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