Функция и одномерные массивы с условием

[Андрюшатина]

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

Задача: Функция принимает два одномерных массива и выводит на экран все общие элементы. Функция должна вернуть true, в случае если общие элементы были найдены или false в противном случае

P.S.
Нужно использовать только #include <iostream>
Извините, что без исходника. Вообще не пойму, что написать((((

[FPaul]

Я не знаю C и C++, но оптимальный алгоритм здесь однозначный:
1. Ввод массивов А и В.
2. Сортировка массивов А и В.
3. Просмотр массивов в двух параллельных циклах и вывод общих элементов.
Свой Pascal-вариант приводить не буду из-за бесполезности. Но, полагаю, что плана действий уже достаточно для старта.

[Poma][a]

я бы сортировал один. А из другого брал элементы и искал бинарным поиском

[FPaul]

Лучше оба. Тогда по мере "продвижения" меньше сравнений, можно пропускать одинаковые. Но это лишь мнение...

[Андрюшатина]

Вот код, но выдает ошибки, а так вроде всё правильно, можете подправить? Но не используя оператор new

#include <iostream>
using namespace std;

bool Massive(int mas1, int mas2, int x, int y){
	bool val = false;
	for (int i = 0; i<x; i++){
		for (int j = 0; j<y; j++){
			if (mas1[i] == mas2[j]){
				cout <<"true: "<< mas1[i] << " ";
				val = true;
			}
		}
	}
	return val;
}

void main(){
	setlocale(LC_ALL, "Russian");
	int x;
	int y ;
	int A[] = { 0 };
	int B[] = { 0 };
	cout << "Введите размер массива 1" << endl;
	cin >> A[x];
	for (int i = 0; i<x; i++){
		A[i] = (rand() % 15);
		cout << A[i] << " ";
	}
	cout << endl;
	cout << "Введите размер массива 2" << endl;
	cin >> B[y];
	
	for (int i = 0; i<x; i++){
		B[i] = (rand() % 15);
		cout << B[i] << " ";
	}
	cout << endl;
	Massive(A[x], B[y], x, y);
}

[FPaul]

А ты не мог бы самостоятельно исправить ошибки? Там ведь о до компиляции не доходит. Мне просто тяжеловато бодаться с чуждым мне синтаксисом.

[Андрюшатина]

Дело в том, что тему очень плохо понял и синтаксис, тут как раз для меня последняя преграда, не могу понять, как правильно всё оформить

[FPaul]

Я могу за тебя подучить синтаксис и исправить. Этот язык для меня новый. Где-то через 3-4 часа разберусь с сообщениями компилятора и даже сделаю твою лабу. Ты позволишь приступать?

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

#include <iostream>
using namespace std;

#define MaxLen 20

void Swap(int arr[], int pos1, int pos2)
{
    int tmp;
    tmp = arr[pos1];
    arr[pos1] = arr[pos2];
    arr[pos2] = tmp;
}

void BubbleSort(int arr[], int len)
{
    int i, j;
    for(i = 0; i < len - 1; ++i)
        for(j = 0; j < len - i; ++j)
            if (arr[j] > arr[j + 1])
                Swap(arr, j , j + 1);
}

bool ProcessArray(int mas1[], int mas2[], int len1, int len2)
{
    bool val = false;
    BubbleSort(mas1, len1);
    BubbleSort(mas2, len2);
    int i=0;
    int j=0;
    while(true)
    {
        if(i==len1)
            break;
        if(j==len2)
            break;
        if(mas1[i]>mas2[j])
            j++;
        else if(mas1[i]<mas2[j])
            i++;
        else
        {
            val=true;
            cout << "a[" << i << "]=" << mas1[i] << " == " << "b[" << j << "]=" << mas2[j] << endl;
            // пропускаем дублирующиеся элементы в mas1
            while(i+1<len1)
            {
                i++;
                if(mas1[i-1]!=mas1[i])
                    break;
                else
                    i++;
            }
            // пропускаем дублирующиеся элементы в mas2
            while(j+1<len2)
            {
                j++;
                if(mas2[j-1]!=mas2[j])
                    break;
                else
                    j++;
            }
        }

    }
    if (val)
        cout << endl;
    return val;
}

int main()
{
    setlocale(LC_ALL, "Russian");
    int A_len;
    int B_len;
    int A[MaxLen] = {74, -67, -14, 74, -69, -6, -19, -14, 80, -14, -18, -52, -11, 27, 94, 19, 45, -19, -80, -9};
    int B[MaxLen] = {29, 35, 40, -75, -14, -99, -100, -64, 74, 34, 30,-14, 30, -14, 90, 27, 73, 14, -69, -4};
    A_len=10;
    B_len=15;
    if (ProcessArray(A, B, A_len, B_len))
        cout << "There is a same elements in a arrays." << endl;
    else
        cout << "There isn't a same elements in a arrays." << endl;
    return 0;
}

[Poma][a]

Лучше оба. Тогда по мере "продвижения" меньше сравнений, можно пропускать одинаковые. Но это лишь мнение...

Давай для простоты скажем, что у нас массивы одинаково размера..
Тогда сложность двух сортировок : O(2*(n*log N))
И еще проход по двум массивам..
Тоесть всего O(2*(n*log N)+2*N)
Мой вариант..
Сортировка одного O(n*log N)
Бинарный поиск O(n*log N)

Итого O(2n*logN)

Посути алгоритмы одинаково эффективны

[FPaul]

Да, более, чем согласен. Но есть два нюанса:
1. Ищем мы в отсортированном массиве A. А шаблон поиска берём из неупорядоченного B. Если в B есть дубликаты, да ещё и присутствующие в A, то они будут выведены несколько раз в хаотичном порядке.
2. Несмотря на простоту идеи бинарнрго поиска, он сложен в отладке - там есть нюансы. Помню, что долго не мог справится со строгими и нестрогими неравенствами. А наш ТС - ещё в синтаксисе "плавает".

PS ТС, наверное, на мою издёвку обиделся, ушел и не приходит. Хотя, по моему мнению, школьники и студенты-далеко-не-программисты изучают Pascal и VBA. А С (С++) - уже другой уровень знаний (слишком сложный, хотя и эффективный язык).