Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.54/13: Рейтинг темы: голосов - 13, средняя оценка - 4.54
1 / 1 / 1
Регистрация: 02.03.2013
Сообщений: 151
1

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

16.07.2013, 22:32. Просмотров 2401. Ответов 19

Даны два возрастающих массива 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;
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.07.2013, 22:32
Ответы с готовыми решениями:

Даны два возрастающих массива x[k] и y[l]. Найти количество общих элементов
Даны два возрастающих массива x и y. Найти количество общих элементов в этих ...

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

Найти количество общих элементов в массивах. Исправить ошибки в коде
static void Main(string args) { Console.Write(&quot;Enter k: &quot;); int...

Количество общих элементов в двух массивах
Ребята, Помогите Пожалуйста написать программу на Java: Даны два возрастающих массива, содержащие...

19
4 / 4 / 0
Регистрация: 11.10.2011
Сообщений: 16
16.07.2013, 23:46 2
Цитата Сообщение от schoolboy_ Посмотреть сообщение
Пытался вот так, но работает неправильно. Знаю, где ошибка
В 8 строке
C++
1
2
while(i < 6 && j < 6)
...
0
105 / 86 / 13
Регистрация: 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;
}
0
Эксперт С++
4254 / 2228 / 203
Регистрация: 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;
}
3
105 / 86 / 13
Регистрация: 29.08.2012
Сообщений: 539
17.07.2013, 11:20 5
stl все равно быстрее
0
Почетный модератор
Эксперт С++
5836 / 2843 / 390
Регистрация: 01.11.2011
Сообщений: 6,881
17.07.2013, 11:30 6
Цитата Сообщение от Kukurudza Посмотреть сообщение
stl все равно быстрее
Какие ваши доказательства?
0
105 / 86 / 13
Регистрация: 29.08.2012
Сообщений: 539
17.07.2013, 11:32 7
аааа, пардон, погодите. intersection находит именно множество а не количество. следует воспользоваться их алгоритмом, но не строить множество а вычислять количество. на счет доказательств быстроты их алгоритма: через часика три взгляну че у них там.
0
Эксперт С++
4254 / 2228 / 203
Регистрация: 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;
}
2
105 / 86 / 13
Регистрация: 29.08.2012
Сообщений: 539
17.07.2013, 15:58 9
Thinker, хитрец. взял алгоритм из msdnки
0
Эксперт С++
4254 / 2228 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
17.07.2013, 16:17 10
Цитата Сообщение от Kukurudza Посмотреть сообщение
Thinker, хитрец. взял алгоритм из msdnки
в смысле? вообще-то сам придумал, это и не трудно.
0
105 / 86 / 13
Регистрация: 29.08.2012
Сообщений: 539
17.07.2013, 16:24 11
там один в один:
http://www.cplusplus.com/refer... ersection/
ну или сам
0
Эксперт С++
4254 / 2228 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
17.07.2013, 16:32 12
Цитата Сообщение от Kukurudza Посмотреть сообщение
там один в один

Не по теме:

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

1
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 800
17.07.2013, 17:41 13
Цитата Сообщение от Kukurudza Посмотреть сообщение
static const size_t MASSIV_SIZE = 6;
это офигительно...)
0
105 / 86 / 13
Регистрация: 29.08.2012
Сообщений: 539
17.07.2013, 17:45 14
Цитата Сообщение от salam Посмотреть сообщение
это офигительно...)
что не так? это константа - размер массива. он постоянный.
0
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 800
17.07.2013, 17:46 15
Цитата Сообщение от Kukurudza Посмотреть сообщение
stl все равно быстрее
в данном случае она очевидно медленнее...
0
105 / 86 / 13
Регистрация: 29.08.2012
Сообщений: 539
17.07.2013, 17:50 16
Цитата Сообщение от salam Посмотреть сообщение
в данном случае она очевидно медленнее...
в данном случае, если с построением пересечения - да, медленнее. а так, алгоритмы одинаковы. если без построения, то одинаково.
0
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 800
18.07.2013, 14:18 17
Цитата Сообщение от Kukurudza Посмотреть сообщение
в данном случае, если с построением пересечения - да, медленнее. а так, алгоритмы одинаковы. если без построения, то одинаково.
я не увидел здесь алгоритма с использованием stl, а котором пересечения множеств... покажите, будьте добры.
0
105 / 86 / 13
Регистрация: 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));
вуаля
1
Эксперт С++
4254 / 2228 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
18.07.2013, 14:26 19
Цитата Сообщение от Kukurudza Посмотреть сообщение
вуаля
да, но судя по нику, ТС - школьник
0
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 800
18.07.2013, 15:20 20
прошу прощения, я хотел увидеть алгоритм, с использованием stl, в котором нет пересечения множеств...
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
18.07.2013, 15:20

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Найти количество элементов в массивах
Даны целочисленные массивы S и T с разным количеством элементов. Найти количество элементов в этих...

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

Найти количество одинаковых элементов в 2 массивах
Собственно вот задание Проинициализировать два массива произвольной длины, в каждом из которых нет...

Функции. Найти среднее арифметическое всех элементов с четными номерами и количество нулевых элементов в трех массивах.
Заданы три одномерных массива R, U, W. Количество элементов каждого массива не превышает 25. Для...

Найти количество одинаковых элементов в двух массивах
2) Даны два массива x и y. Найти количество одинаковых элементов в этих массивах, т. е....

Найти общее количество элементов в заданных массивах
Даны два возрастающих целочисленных массива: x длиной k и y длиной m. Найти количество общих...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.