Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.72/25: Рейтинг темы: голосов - 25, средняя оценка - 4.72
3 / 3 / 1
Регистрация: 02.03.2013
Сообщений: 231

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

16.07.2013, 22:32. Показов 5152. Ответов 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)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
16.07.2013, 22:32
Ответы с готовыми решениями:

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

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

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

19
4 / 4 / 0
Регистрация: 11.10.2011
Сообщений: 16
16.07.2013, 23:46
Цитата Сообщение от schoolboy_ Посмотреть сообщение
Пытался вот так, но работает неправильно. Знаю, где ошибка
В 8 строке
C++
1
2
while(i < 6 && j < 6)
...
0
106 / 87 / 13
Регистрация: 29.08.2012
Сообщений: 538
17.07.2013, 08:20
можно 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
Эксперт С++
 Аватар для Thinker
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
17.07.2013, 11:00
Лучший ответ Сообщение было отмечено как решение

Решение

Цитата Сообщение от 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
106 / 87 / 13
Регистрация: 29.08.2012
Сообщений: 538
17.07.2013, 11:20
stl все равно быстрее
0
Почетный модератор
Эксперт С++
 Аватар для SatanaXIII
5851 / 2862 / 392
Регистрация: 01.11.2011
Сообщений: 6,906
17.07.2013, 11:30
Цитата Сообщение от Kukurudza Посмотреть сообщение
stl все равно быстрее
Какие ваши доказательства?
0
106 / 87 / 13
Регистрация: 29.08.2012
Сообщений: 538
17.07.2013, 11:32
аааа, пардон, погодите. intersection находит именно множество а не количество. следует воспользоваться их алгоритмом, но не строить множество а вычислять количество. на счет доказательств быстроты их алгоритма: через часика три взгляну че у них там.
0
Эксперт С++
 Аватар для Thinker
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
17.07.2013, 12:27
Цитата Сообщение от 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
106 / 87 / 13
Регистрация: 29.08.2012
Сообщений: 538
17.07.2013, 15:58
Thinker, хитрец. взял алгоритм из msdnки
0
Эксперт С++
 Аватар для Thinker
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
17.07.2013, 16:17
Цитата Сообщение от Kukurudza Посмотреть сообщение
Thinker, хитрец. взял алгоритм из msdnки
в смысле? вообще-то сам придумал, это и не трудно.
0
106 / 87 / 13
Регистрация: 29.08.2012
Сообщений: 538
17.07.2013, 16:24
там один в один:
http://www.cplusplus.com/refer... ersection/
ну или сам
0
Эксперт С++
 Аватар для Thinker
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
17.07.2013, 16:32
Цитата Сообщение от Kukurudza Посмотреть сообщение
там один в один

Не по теме:

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

1
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
17.07.2013, 17:41
Цитата Сообщение от Kukurudza Посмотреть сообщение
static const size_t MASSIV_SIZE = 6;
это офигительно...)
0
106 / 87 / 13
Регистрация: 29.08.2012
Сообщений: 538
17.07.2013, 17:45
Цитата Сообщение от salam Посмотреть сообщение
это офигительно...)
что не так? это константа - размер массива. он постоянный.
0
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
17.07.2013, 17:46
Цитата Сообщение от Kukurudza Посмотреть сообщение
stl все равно быстрее
в данном случае она очевидно медленнее...
0
106 / 87 / 13
Регистрация: 29.08.2012
Сообщений: 538
17.07.2013, 17:50
Цитата Сообщение от salam Посмотреть сообщение
в данном случае она очевидно медленнее...
в данном случае, если с построением пересечения - да, медленнее. а так, алгоритмы одинаковы. если без построения, то одинаково.
0
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
18.07.2013, 14:18
Цитата Сообщение от Kukurudza Посмотреть сообщение
в данном случае, если с построением пересечения - да, медленнее. а так, алгоритмы одинаковы. если без построения, то одинаково.
я не увидел здесь алгоритма с использованием stl, а котором пересечения множеств... покажите, будьте добры.
0
106 / 87 / 13
Регистрация: 29.08.2012
Сообщений: 538
18.07.2013, 14:20
Цитата Сообщение от Kukurudza Посмотреть сообщение
std::set_intersection(a, a + MASSIV_SIZE, b, b + MASSIV_SIZE, back_inserter(intersection));
вуаля
1
Эксперт С++
 Аватар для Thinker
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
18.07.2013, 14:26
Цитата Сообщение от Kukurudza Посмотреть сообщение
вуаля
да, но судя по нику, ТС - школьник
0
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
18.07.2013, 15:20
прошу прощения, я хотел увидеть алгоритм, с использованием stl, в котором нет пересечения множеств...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
18.07.2013, 15:20
Помогаю со студенческими работами здесь

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
http://iceja.net/ сервер решения полиномов
iceja 18.01.2026
Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Первый деплой
lagorue 16.01.2026
Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .
Расчёт переходных процессов в цепи постоянного тока
igorrr37 16.01.2026
/ * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит: токи, напряжения и их 1 и 2 производные при t = 0;. . .
Восстановить юзерскрипты Greasemonkey из бэкапа браузера
damix 15.01.2026
Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Изучаю kubernetes
lagorue 13.01.2026
А пригодятся-ли мне знания kubernetes в России?
Сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11
Jel 10.01.2026
Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru