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

Количество элементов в разности множеств - C++

Восстановить пароль Регистрация
 
alex_creed
0 / 0 / 0
Регистрация: 22.12.2012
Сообщений: 3
22.12.2012, 17:35     Количество элементов в разности множеств #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
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
//Курсовая работа(вариант с массивом)
#include <iostream>
using namespace std;
 
const int AMAX = 100;
 
int main()
{
    setlocale(0, "");
    //Объявление переменных
    int F[AMAX], //Множество F
        G[AMAX], //Множество G
        i,       //Счетчики циклов 
        j,
        n,       //Размерность массивов 
        razn=0;    //Количество элементов в разности
    bool flag;   //"Флаг" несовпадения элементов
    //Ввод данных в массивы
    cout << "Введите размерность множеств: ";
    cin >> n;
    cout << "Введите элементы множества F: ";
    for(i=1; i<=n; i++)
        cin >> F[i];
    cout << "Введите элементы множества G: ";
    for(j=1; j<=n; j++)
        cin >> G[j];
    cout << endl;   
    //Цикл вычисление разности
    for(i=1; i<=n; i++)
    {
        flag=1;
        cout << endl << "<" << i << ">" << endl;
        for(j=1; j<=n; j++)
        {
            if (F[i]==G[j])
            {
                flag=0;
                break;
            }
            cout << "<" << i << "." << j << "> " << F[i] << " vs " << G[j] << endl;
        }
        if (flag) 
            razn++;
        else
            cout << "<" << i << "." << j << "> " << F[i] << " vs " << G[j] << " Совпадение!" << endl;
        cout << "<" << i << ">" << "Количество элементов в разности равно: " << razn << endl;
    }
    
    cout << endl << "Количество элементов в разности равно " << razn;
    
    return 0;
}
Можно ли ее как-то оптимизировать или и так все в порядке? Просто меня смущает то, что каждый раз приходится во вложенном цикле прогонять второй массив.

И второй вопрос(собственно почему я пока сделал все с массивами).
Вот фрагмент программы с файлами:
C++
1
2
3
4
5
6
7
8
9
10
11
while (inF >> f) //Цикл вычисления razn (inF - оператор ввода из файла F.txt)
    { 
        flag=1;
        while (inG >> g) 
                if (g==f) 
            { 
                flag=0;
                break;
            }
        if (flag) razn++;
    }
Как видите, у меня цикл продолжается, пока идет ввод из файла(в основном цикле F.txt, во вложенном - G.txt). Если с основным циклом все в порядке(по очереди вводит элементы из f.txt), то во вложенном проблема. Программа считывает его только один раз, а дальше перескакивает через цикл(т.к. из G.txt уже ввод не идет, он уже прошел). Как сделать, чтобы каждый шаг цикла она снова вводила элементы из G.txt?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.12.2012, 17:35     Количество элементов в разности множеств
Посмотрите здесь:

C++ Дана матрица целых чисел. Подсчитать количество элементов, предшествующих максимуму и количество элементов, следующих за минимумом
Найти номера двух ближайших элементов из этого массива, т. е. элементов с наименьшим модулем разности C++
C++ Ошбика в алгоритме нахождения разности множеств
C++ Определить количество чисел, кратных разности текущего и предыдущего чисел
Дан массив целых чисел. Определить количество четных элементов и количество элементов, оканчивающихся на цифру 5 C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
22.12.2012, 17:51     Количество элементов в разности множеств #2
Вы не с той стороны подошли к задаче. Главный вопрос: как за один проход определить количество различных элементов. Хинт: 1) последовательности в файлах, их можно читать независимо друг от друга и поэлементно, а не последовательно и всё сразу; 2) последовательности упорядочены.
Код
A:      1, 2, 3, 4, 5, 6, 7
B:            3, 4,       7, 9, 10, 11
A & B:        3, 4,       7
A / B:  1, 2,       5, 6
alex_creed
0 / 0 / 0
Регистрация: 22.12.2012
Сообщений: 3
22.12.2012, 18:29  [ТС]     Количество элементов в разности множеств #3
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Вы не с той стороны подошли к задаче. Главный вопрос: как за один проход определить количество различных элементов. Хинт: 1) последовательности в файлах, их можно читать независимо друг от друга и поэлементно, а не последовательно и всё сразу; 2) последовательности упорядочены.
Код
A:      1, 2, 3, 4, 5, 6, 7
B:            3, 4,       7, 9, 10, 11
A & B:        3, 4,       7
A / B:  1, 2,       5, 6
Я не понимаю к чему вы ведете.

Добавлено через 27 минут
Таки как же реализовать, если даже учитывать эти хинты?
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
22.12.2012, 18:30     Количество элементов в разности множеств #4
К тому, что здесь массивы не нужны, равно как и повторное чтение файлов.

Вот именно поэтому это подсказки, а не пошаговое руководство. Внимательно смотрите на последовательности A и B слева направо и придумайте, как узнать нижнюю оценку количества элементов A, которых точно нет в B, если вы видите, что наименьший элемент B равен 3.
igorrr37
 Аватар для igorrr37
1594 / 1222 / 118
Регистрация: 21.12.2010
Сообщений: 1,868
Записей в блоге: 7
22.12.2012, 21:02     Количество элементов в разности множеств #5
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
#include <iostream>
#include <fstream>
#include <iterator>
 
template<typename InputIterator>
size_t count_symmetric_difference(InputIterator __first1, InputIterator __last1,
                                InputIterator __first2, InputIterator __last2)
{
    size_t counter = 0;
    while (__first1 != __last1 && __first2 != __last2)
    if (*__first1 < *__first2)
      {
        ++counter;
        ++__first1;
      }
    else if (*__first2 < *__first1)
      {
        ++counter;
        ++__first2;
      }
    else
      {
        ++__first1;
        ++__first2;
      }
      while(__first1 != __last1)
      {
          ++__first1;
          ++counter;
      }
      while(__first2 != __last2)
      {
          ++__first2;
          ++counter;
      }
    return counter;
}
 
int main ()
{
    std::ifstream ifs1("in1.txt"), ifs2("in2.txt");
    if(ifs1.is_open() && ifs2.is_open())
    {
        std::cout << count_symmetric_difference
        (
            std::istream_iterator<int>(ifs1), std::istream_iterator<int>(),
            std::istream_iterator<int>(ifs2), std::istream_iterator<int>()
        ) << std::endl;
        ifs1.close();
        ifs2.close();
    }
    else
        std::cerr << "Unable to open input file(s)" << std::endl;
    return 0;
}
alex_creed
0 / 0 / 0
Регистрация: 22.12.2012
Сообщений: 3
23.12.2012, 22:23  [ТС]     Количество элементов в разности множеств #6
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
#include <iostream>
#include <fstream>
#include <stdio.h>
 
using namespace std;
 
int main()
{
    setlocale(0, "");
    //Открытие файлов
    ifstream fin("f.txt");
    ifstream gin("g.txt");
//  ofstream fout("kursout.txt");
    //Объявление переменных
    int f,      //Текущий элемент множества F
        g,      //Текущий элемент множества G
        lenF=0, //Длина множества F
        sim=0//Количество одинаковых элементов
        razn=0; //Количество элементов в разности F и G
    //Вычисление razn
    fin >> f;
    gin >> g;
    while (f!=EOF)
    {
        if (f==g)
        {
            fin >> f;
            gin >> g;
            lenF++;
            sim++;
        }
        else if (f<g)
        {
            fin >> f;
            lenF++;
        }
        else if (f>g)
            gin >> g;
        
        razn=lenF-sim;
        cout << razn << endl ;
    }
    cout << endl << razn;
    
    system("pause");
    return 0;
}
Вот что пока что вышло. Единственное что - я так и не смог выдумать условие выхода из цикла.
Yandex
Объявления
23.12.2012, 22:23     Количество элементов в разности множеств
Ответ Создать тему
Опции темы

Текущее время: 00:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru