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

Найти количество общих элементов в массивах. - C++

Восстановить пароль Регистрация
 
schoolboy_
1 / 1 / 0
Регистрация: 02.03.2013
Сообщений: 59
16.07.2013, 22:32     Найти количество общих элементов в массивах. #1
Даны два возрастающих массива x: array[1..k] of integer
и y: array[1..l] of integer. Найти количество общих элементов в этих массивах.
Вот решение:
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
#include "stdafx.h"
#include "iostream"
 
using namespace std;
 
int i = 0, j = 0, n =  0;
 
int array[6] = {1, 2, 3, 4, 5, 6};
int array1[6] = {3, 4, 5, 6, 7, 8};
 
int main()
{
    for(i = 0; i != 6; i++)
    {
        for(j = 0; j != 6; j++)
        {   
            if(array[i] == array1[j])
                n++;
        }
    }
    cout<<n<<endl;
    system("pause");
    return 0;
}
Но, хотелось бы за меньшее кол-во действий. Например так:
Кликните здесь для просмотра всего текста

Pascal
1
2
3
4
5
6
7
8
9
while (k1<> k) and (l1 <> l) do begin
if [k1 ] < [l1+1] then begin
k1 := k1 + 1;
end else if [k1] > y[l1] then begin
l1 := l1 + 1;
 else begin 
k1 := k1 + 1;
l1 := l1 + 1;
n := n + 1;

Пытался вот так, но работает неправильно. Знаю, где ошибка
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int i = 0, j = 0, n =  0;
 
int array[6] = {1, 2, 3, 4, 5, 6};
int array1[6] = {3, 4, 5, 6, 7, 8};
 
int main()
{
    while(i != 6 && j != 6)
    {
        array[i] < array1[j] ? i++ : j++;
 
        if(array[i] == array1[j])
        {
            n++;
            i++;
            j++;
        }
    }
 
cout<<n<<endl;
 
    system("pause");
    return 0;
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.07.2013, 22:32     Найти количество общих элементов в массивах.
Посмотрите здесь:

C++ Подсчитать в 2-x массивах количество элементов, меньших значения t
C++ Найти количество общих точек окружности и прямой
C++ Даны два возрастающих массива x[k] и y[l]. Найти количество общих элементов
C++ в массивах С(28) и М(12) определить количество элементов до последнего максимального
Сформировать массивы А[15] и B[10]. Вывести их на экран. Подсчитать количество ненулевых элементов и максимальные значения в обоих массивах C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
maks_b
4 / 4 / 0
Регистрация: 11.10.2011
Сообщений: 15
16.07.2013, 23:46     Найти количество общих элементов в массивах. #2
Цитата Сообщение от schoolboy_ Посмотреть сообщение
Пытался вот так, но работает неправильно. Знаю, где ошибка
В 8 строке
C++
1
2
while(i < 6 && j < 6)
...
Kukurudza
104 / 85 / 6
Регистрация: 29.08.2012
Сообщений: 539
17.07.2013, 08:20     Найти количество общих элементов в массивах. #3
можно stl'ем попользоваться, и быстрее и код короче и над алгоритмом заморачиваться не надо:
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
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
 
void massiv() {
    std::cout << "massiv() :\n";
 
    static const size_t MASSIV_SIZE = 6;
 
    int a[MASSIV_SIZE] = {3,1,6,4,5,2};
    int b[MASSIV_SIZE] = {8,4,5,9,7,6};
    std::sort(a, a + MASSIV_SIZE);
    std::sort(b, b + MASSIV_SIZE);
 
    std::copy(a, a + MASSIV_SIZE, std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
 
    std::copy(b, b + MASSIV_SIZE, std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
 
    std::vector<int> intersection;
    std::set_intersection(a, a + MASSIV_SIZE, b, b + MASSIV_SIZE, back_inserter(intersection));
 
    std::copy(intersection.begin(), intersection.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
}
 
void set() {
    std::cout << "set() :\n";
 
    std::set<int> set1;
    set1.insert(3);
    set1.insert(1);
    set1.insert(6);
    set1.insert(4);
    set1.insert(5);
    set1.insert(2);
 
    std::set<int> set2;
    set2.insert(8);
    set2.insert(4);
    set2.insert(5);
    set2.insert(9);
    set2.insert(7);
    set2.insert(6);
 
    std::copy(set1.begin(), set1.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
 
    std::copy(set2.begin(), set2.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
 
    std::vector<int> intersection;
    std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), back_inserter(intersection));
 
    std::copy(intersection.begin(), intersection.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
}
 
int main() {
    massiv();
    set();
 
    return 0;
}
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
17.07.2013, 11:00     Найти количество общих элементов в массивах. #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от schoolboy_ Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
    for(i = 0; i != 6; i++)
    {
        for(j = 0; j != 6; j++)
        {   
            if(array[i] == array1[j])
                n++;
        }
    }
алгоритмы квадратичной сложности для таких задач нелепо использовать. Алгоритм с одним проходом по исходным массивам:

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
#include<iostream>
const int NA = 5;
const int NB = 7;
 
int Count(int *a, int *b, int na, int nb)
{
    int i = 0, j = 0, count = 0;
    while(i < na && j < nb)
    {
        while(a[i] < b[j])
            ++i;
        while(b[j] < a[i])
            ++j;
        if (i < na && j < nb  && a[i] == b[j])
        {
            ++i, ++j, ++count;
        }
    }
    return count;
}
 
int main()
{
   int a[NA] = {1, 2, 5, 7, 10}, b[NC] = {0, 1, 2, 3, 7, 10 ,11};
   std::cout << Count(a, b, NA, NB);
   return 0;
}
Kukurudza
104 / 85 / 6
Регистрация: 29.08.2012
Сообщений: 539
17.07.2013, 11:20     Найти количество общих элементов в массивах. #5
stl все равно быстрее
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5547 / 2561 / 233
Регистрация: 01.11.2011
Сообщений: 6,330
Завершенные тесты: 1
17.07.2013, 11:30     Найти количество общих элементов в массивах. #6
Цитата Сообщение от Kukurudza Посмотреть сообщение
stl все равно быстрее
Какие ваши доказательства?
Kukurudza
104 / 85 / 6
Регистрация: 29.08.2012
Сообщений: 539
17.07.2013, 11:32     Найти количество общих элементов в массивах. #7
аааа, пардон, погодите. intersection находит именно множество а не количество. следует воспользоваться их алгоритмом, но не строить множество а вычислять количество. на счет доказательств быстроты их алгоритма: через часика три взгляну че у них там.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
17.07.2013, 12:27     Найти количество общих элементов в массивах. #8
Цитата Сообщение от Kukurudza Посмотреть сообщение
stl все равно быстрее
да, она же волшебная немного переделал свой прежний алгоритм:

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
#include<iostream>
const int NA = 5;
const int NB = 7;
 
int Count(int *a, int *b, int na, int nb)
{
    int i = 0, j = 0, count = 0;
    while(i < na && j < nb)
    {
        if(a[i] < b[j])
            ++i;
        else if(b[j] < a[i])
            ++j;
        else
        {
            ++i, ++j, ++count;
        }
    }
    return count;
}
 
int main()
{
   int a[NA] = {1, 2, 3, 7, 10}, b[NC] = {0, 1, 2, 3, 7, 10 ,11};
   std::cout << Count(a, b, NA, NB);
   return 0;
}
Kukurudza
104 / 85 / 6
Регистрация: 29.08.2012
Сообщений: 539
17.07.2013, 15:58     Найти количество общих элементов в массивах. #9
Thinker, хитрец. взял алгоритм из msdnки
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
17.07.2013, 16:17     Найти количество общих элементов в массивах. #10
Цитата Сообщение от Kukurudza Посмотреть сообщение
Thinker, хитрец. взял алгоритм из msdnки
в смысле? вообще-то сам придумал, это и не трудно.
Kukurudza
104 / 85 / 6
Регистрация: 29.08.2012
Сообщений: 539
17.07.2013, 16:24     Найти количество общих элементов в массивах. #11
там один в один:
http://www.cplusplus.com/reference/a..._intersection/
ну или сам
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
17.07.2013, 16:32     Найти количество общих элементов в массивах. #12
Цитата Сообщение от Kukurudza Посмотреть сообщение
там один в один

Не по теме:

так логика построения очевидна. глупо строить навороты, если понятно как задача решается. думайте как хотите, а писал без msdn

salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
17.07.2013, 17:41     Найти количество общих элементов в массивах. #13
Цитата Сообщение от Kukurudza Посмотреть сообщение
static const size_t MASSIV_SIZE = 6;
это офигительно...)
Kukurudza
104 / 85 / 6
Регистрация: 29.08.2012
Сообщений: 539
17.07.2013, 17:45     Найти количество общих элементов в массивах. #14
Цитата Сообщение от salam Посмотреть сообщение
это офигительно...)
что не так? это константа - размер массива. он постоянный.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
17.07.2013, 17:46     Найти количество общих элементов в массивах. #15
Цитата Сообщение от Kukurudza Посмотреть сообщение
stl все равно быстрее
в данном случае она очевидно медленнее...
Kukurudza
104 / 85 / 6
Регистрация: 29.08.2012
Сообщений: 539
17.07.2013, 17:50     Найти количество общих элементов в массивах. #16
Цитата Сообщение от salam Посмотреть сообщение
в данном случае она очевидно медленнее...
в данном случае, если с построением пересечения - да, медленнее. а так, алгоритмы одинаковы. если без построения, то одинаково.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
18.07.2013, 14:18     Найти количество общих элементов в массивах. #17
Цитата Сообщение от Kukurudza Посмотреть сообщение
в данном случае, если с построением пересечения - да, медленнее. а так, алгоритмы одинаковы. если без построения, то одинаково.
я не увидел здесь алгоритма с использованием stl, а котором пересечения множеств... покажите, будьте добры.
Kukurudza
104 / 85 / 6
Регистрация: 29.08.2012
Сообщений: 539
18.07.2013, 14:20     Найти количество общих элементов в массивах. #18
Цитата Сообщение от Kukurudza Посмотреть сообщение
std::set_intersection(a, a + MASSIV_SIZE, b, b + MASSIV_SIZE, back_inserter(intersection));
вуаля
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
18.07.2013, 14:26     Найти количество общих элементов в массивах. #19
Цитата Сообщение от Kukurudza Посмотреть сообщение
вуаля
да, но судя по нику, ТС - школьник
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.07.2013, 15:20     Найти количество общих элементов в массивах.
Еще ссылки по теме:

Функции. Подсчитать в массивах количество элементов, больших значения t C++
C++ Найти количество элементов, встречающихся в обоих массивах
C++ Подсчитать в массивах количество отрицательных элементов

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

Или воспользуйтесь поиском по форуму:
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
18.07.2013, 15:20     Найти количество общих элементов в массивах. #20
прошу прощения, я хотел увидеть алгоритм, с использованием stl, в котором нет пересечения множеств...
Yandex
Объявления
18.07.2013, 15:20     Найти количество общих элементов в массивах.
Ответ Создать тему

Метки
количество общих элементов, массивы
Опции темы

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