Программа на C++ (пересечение множеств)

[Legioner93]

Здравствуйте! Посмотрите, пожалуйста, программу. Выдает ошибку, пересекать множества отказывается.
"Пересечение множеств

Time limit = 5 секунд(ы)

Memory limit = 33000 Kb

Вход — два множества натуральных чисел.

Выход — их пересечение (перечисление элементов через пробел в любом порядке без повторений) или слово empty, если пересечение пусто.

Множества $A={a_1, a_2, ..., a_n}$ и $B={b_1, b_2, ..., b_k}$ на входе представлены как последовательности натуральных чисел, разделенных пробелом, и завершающиеся числом $-1$ — идентификатором конца. Возможны повторения элементов, которые надо исключить. Размеры множеств меньше $1000$. Сами числа меньше $10^6$. "

// Пересечение множеств.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"

#include <stdio.h>
int _tmain(int argc, _TCHAR* argv[])
{
int a[1001], b[1001], c[1001];
int x,y,i,k,p,z,m;
x=0; y=0;
do
{
x=x+1; scanf("%d", &a[x]);
}while(a[x]>0); x=x-1;
do
{
y=y+1; scanf("%d", &b[y]);
}while(b[y]>0); y=y-1;
p=0;
for(i=1; i<x+y+1; y++)
{
c[i]=0;
}
for(i=1; i<x+1; i++)
{
for (k=1; k<y+1; k++)
{
if (b[k]==a[i])
{
m=1;
for (z=1; z<p+1; z++)
{
if (c[z]==b[k])
{
m=0;
}

}
if (m==1)
{
p=p+1;
c[p]=b[k];
}
}
}
}
for (i=1; i<p+1; i++);
{
printf("%d", c[i]); printf(" ");
}
getchar(); getchar();
return 0;
}

Программа простая, даже обидно:) Видимо, еще не разобрался в тонкостях языка. Спасибо!

[lim0n]

Очистка массива c: переменная i - инвариант цикла, а инкрементируете почему-то y?

Просто небольшое замечание: чем Вам не нравится использовать массивы "по полной", т.е. начиная с нулевого элемента. Это позволило бы избавиться от множества "...+1", которые просто засоряют программу.

Для оформления хорошо использовать тэги "[code]" и "[syntax]".

[creative]

Немного переделал Вашу программу в процессе выравнивания отступов (обязательно используйте отступы и подсветку синтаксиса), проверил, теперь работает (т.е. нерабочий вариант я не запускал). Проверьте на разных входных данных.
Я компилировал под *nix. Если Вы компилируете под Windows, то возможно Вам нужно добавить какие-то заголовочные файлы или изменить пару строк, но работа алгоритма принципиально не изменится.

Так же вижу, что сейчас его время работы составляет $O(ABC)$, где $A$ - длинна первого входного массива, $B$ - длинна второго, $C$ - длинна выходного.
Тут обсуждаются более эффективные алгоритмы решения этой задачи.

Используется синтаксис C

#include <stdio.h>

int main()
{
    //init data
    int a[1000] = {0};
    int b[1000] = {0};
    int c[1000] = {0};
    int x = 0, y = 0, p = 0;
    int i, k, z, m, v;

    //input data
    do {
        scanf("%d", &v);
        if (x < 1000) a[x++] = v;
    } while(v >= 0);
    x--;

    do {
        scanf("%d", &v);
        if (y < 1000) b[y++] = v;
    } while(v >= 0);
    y--;

    //compute intersection
    for(i = 0; i < x; i++) {
        for (k = 0; k < y; k++) {

            if (b[k] == a[i]) {
                m = 1;

                for (z = 1; z < p + 1; z++) {
                    if (c[z] == b[k]) {
                        m = 0;
                    }
                }

                if (m == 1) {
                    p++;
                    c[p] = b[k];
                }
            }
        }
    }

    //output result
    for (i = 1; i < p + 1; i++) {
        printf("%d", c[i]);
        printf(" ");
    }
    printf("\n");

    return 0;
}
 

[lim0n]

creative в сообщении #354323 писал(а):

Немного переделал Вашу программу

После ввода чисел в массив уменьшается их количество (переменные $x$ и $y$, проверьте при $A=\{a_1\}$ и $B=\{b_1\}$).
Можно поправить работу с результирующим массивом ($c[0]$ не используется).
После присваивания $m=0$ цикл проверки на повторение можно покинуть (break).

[creative]

lim0n в сообщении #354343 писал(а):

После ввода чисел в массив уменьшается их количество (переменные $x$ и $y$, проверьте при $A=\{a_1\}$ и $B=\{b_1\}$).
Можно поправить работу с результирующим массивом ($c[0]$ не используется).
После присваивания $m=0$ цикл проверки на повторение можно покинуть (break).

Поправил:

-                for (z = 1; z < p + 1; z++) {
+                for (z = 0; z < p; z++) {
                     if (c[z] == b[k]) {
                         m = 0;
+                        break;


                 if (m == 1) {
-                    p++;
                     c[p] = b[k];
+                    p++;
                 }


-    for (i = 1; i < p + 1; i++) {
+    for (i = 0; i < p; i++) {

С $A=\{a_1\}$ и $B=\{b_1\}$ работает, так как x и y успевают инкрементироваться на единицу (тем самым x, y указывают на следующий за -1 элемент в массиве) в последней итерации цикла, когда считано отрицательное число:

# echo "4 -1 4 -1" | ./a.out
4 

# echo "4 -1 3 -1" | ./a.out

[Legioner93]

lim0n в сообщении #354306 писал(а):

Очистка массива c: переменная i - инвариант цикла, а инкрементируете почему-то y?

Просто небольшое замечание: чем Вам не нравится использовать массивы "по полной", т.е. начиная с нулевого элемента. Это позволило бы избавиться от множества "...+1", которые просто засоряют программу.

Для оформления хорошо использовать тэги "[code]" и "[syntax]".

Да, в этом дело! Большое спасибо:) Про теги понял.

creative в сообщении #354323 писал(а):

обязательно используйте отступы и подсветку синтаксиса

Хорошо, разберусь!

[lim0n]

В заголовке темы упомянут язык программирования C++, но всё обсуждение прошло вокруг программы на "чистом" C. В качестве бонуса автору темы:

Используется синтаксис C++

#include <iostream>
#include <set>
#include <algorithm>

using namespace std;

void main()
{
    set<long int> A, B;
    long int v;

    while (cin >> v, v != -1)
        A.insert(v);

    while (cin >> v, v != -1)
        B.insert(v);

    set_intersection(A.begin(), A.end(), B.begin(), B.end(),
                    ostream_iterator<long int>(cout, " "));
    cout << endl;
}
 

Используется Standart Template Library (STL), проверено на VC++ v6.0, компилировать с опцией "-GX".