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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
schoolboy_
1 / 1 / 0
Регистрация: 02.03.2013
Сообщений: 59
#1

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

16.07.2013, 22:32. Просмотров 1010. Ответов 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;
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.07.2013, 22:32
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти количество общих элементов в массивах. (C++):

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

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

В заданных массивах найти количество элементов равных нулю и заменить их на -100 в случае выполнения условия - C++
Помогите пожалуйста. В массивах Х1..Х5, Y1..Y7, Z1..Z14 определить количество равных нулю элементов. Если их больше половины, то первый и...

Найти количество общих точек окружности и прямой - C++
Решить задачу в С++ Помогите пожалуйста =) Дана окружность и прямая. Окружность задается уранвением r²=x²+y². Уравнение прямой y=ax+b....

Подсчитать в массивах количество отрицательных элементов - C++
Разработать программу, содержащую две функции: 1. Заданы два массива А(N) и В(M). Подсчитать в них количество отрицательных элементов и...

Подсчитать количество отрицательных элементов в массивах - C++
1. Заданы два массива А(N) и В(M). Подсчитать в них количество отрицательных элементов и первым на печать вывести массив, имеющий...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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
105 / 86 / 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++
4225 / 2199 / 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
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
17.07.2013, 11:20 #5
stl все равно быстрее
SatanaXIII
Супер-модератор
Эксперт С++
5609 / 2643 / 244
Регистрация: 01.11.2011
Сообщений: 6,502
Завершенные тесты: 1
17.07.2013, 11:30 #6
Цитата Сообщение от Kukurudza Посмотреть сообщение
stl все равно быстрее
Какие ваши доказательства?
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
17.07.2013, 11:32 #7
аааа, пардон, погодите. intersection находит именно множество а не количество. следует воспользоваться их алгоритмом, но не строить множество а вычислять количество. на счет доказательств быстроты их алгоритма: через часика три взгляну че у них там.
Thinker
Эксперт C++
4225 / 2199 / 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
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
17.07.2013, 15:58 #9
Thinker, хитрец. взял алгоритм из msdnки
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
17.07.2013, 16:17 #10
Цитата Сообщение от Kukurudza Посмотреть сообщение
Thinker, хитрец. взял алгоритм из msdnки
в смысле? вообще-то сам придумал, это и не трудно.
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
17.07.2013, 16:24 #11
там один в один:
http://www.cplusplus.com/reference/a..._intersection/
ну или сам
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
17.07.2013, 16:32 #12
Цитата Сообщение от Kukurudza Посмотреть сообщение
там один в один

Не по теме:

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

salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 726
17.07.2013, 17:41 #13
Цитата Сообщение от Kukurudza Посмотреть сообщение
static const size_t MASSIV_SIZE = 6;
это офигительно...)
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
17.07.2013, 17:45 #14
Цитата Сообщение от salam Посмотреть сообщение
это офигительно...)
что не так? это константа - размер массива. он постоянный.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 726
17.07.2013, 17:46 #15
Цитата Сообщение от Kukurudza Посмотреть сообщение
stl все равно быстрее
в данном случае она очевидно медленнее...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.07.2013, 17:46
Привет! Вот еще темы с ответами:

Подсчитать в массивах количество отрицательных элементов - C++
Заданы два массива А(5) и В(5). Подсчитать в них количество отрицательных элементов и первым на печать вывести массив, имеющий наименьшее...

Подсчитать в 2-x массивах количество элементов, меньших значения t - C++
Заданы два массива А(5) и В(5). Подсчитать в них количество элементов, меньших значения t, и первым на печать вывести массив, имеющий...

в массивах С(28) и М(12) определить количество элементов до последнего максимального - C++
в массивах С(28) и М(12) определить количество элементов до последнего максимального

Посчитать количество одинаковых элементов в двух массивах - C++
#include &lt;cstdio&gt; #include &lt;map&gt; #include &lt;iostream&gt; using namespace std; map &lt;bool, int&gt; a; int n, m, year, i, k;////k -...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
17.07.2013, 17:46
Ответ Создать тему
Опции темы

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