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

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

22.12.2012, 17:35. Показов 2223. Ответов 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
//Курсовая работа(вариант с массивом)
#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?
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
22.12.2012, 17:35
Ответы с готовыми решениями:

Ошбика в алгоритме нахождения разности множеств
Set&amp; Set::operator-(const Set &amp;set) { Set *raznost = new Set; if (this-&gt;size != 0 &amp;&amp; set.size != 0) { for (int i = 0; i &lt;...

Реализовать функцию вычисления симметричной разности множеств
Помогите пожалуйста, не знаю как симметрическую разность сделать. Должно вывести 0 1 7 8 9 15 40 #include &lt;iostream&gt; int...

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

5
~ Эврика! ~
 Аватар для OhMyGodSoLong
1258 / 1007 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
22.12.2012, 17:51
Вы не с той стороны подошли к задаче. Главный вопрос: как за один проход определить количество различных элементов. Хинт: 1) последовательности в файлах, их можно читать независимо друг от друга и поэлементно, а не последовательно и всё сразу; 2) последовательности упорядочены.
Code
1
2
3
4
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
0
0 / 0 / 0
Регистрация: 22.12.2012
Сообщений: 3
22.12.2012, 18:29  [ТС]
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Вы не с той стороны подошли к задаче. Главный вопрос: как за один проход определить количество различных элементов. Хинт: 1) последовательности в файлах, их можно читать независимо друг от друга и поэлементно, а не последовательно и всё сразу; 2) последовательности упорядочены.
Code
1
2
3
4
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 минут
Таки как же реализовать, если даже учитывать эти хинты?
0
~ Эврика! ~
 Аватар для OhMyGodSoLong
1258 / 1007 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
22.12.2012, 18:30
К тому, что здесь массивы не нужны, равно как и повторное чтение файлов.

Вот именно поэтому это подсказки, а не пошаговое руководство. Внимательно смотрите на последовательности A и B слева направо и придумайте, как узнать нижнюю оценку количества элементов A, которых точно нет в B, если вы видите, что наименьший элемент B равен 3.
0
 Аватар для igorrr37
2869 / 2016 / 991
Регистрация: 21.12.2010
Сообщений: 3,722
Записей в блоге: 15
22.12.2012, 21:02
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;
}
0
0 / 0 / 0
Регистрация: 22.12.2012
Сообщений: 3
23.12.2012, 22:23  [ТС]
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;
}
Вот что пока что вышло. Единственное что - я так и не смог выдумать условие выхода из цикла.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
23.12.2012, 22:23
Помогаю со студенческими работами здесь

сравнить мощности множеств А и В. Под мощностью множеств понимается количество его элементов не считая повторов.
помогите срочно!!! сравнить мощности множеств А и В. Под мощностью множеств понимается количество его элементов не считая повторов. ...

Доказать свойства разности множеств
Доказать следующие свойства разности множеств: (А\В)\С = (А\С)\В; ( А υ В )\С =( А \ С) υ (В \ С) ; ( А \ В) ∩ С = ( А...

Написать функцию разности множеств
Привет всем! Задача: По началу было понятно, что при вызове функции (f '(1 2 1 2 1 3) '(5 3 3 1 2 2)), первый элемент 1-го...

Операции объединения, пересечения и разности множеств
Здравствуйте,помогите записать этот код в Delphi и скиньте архивом эту программу,пожалуйста. Вот условие задачи этой:Даны три поля TEdit...

Определить количество элементов последовательности, кратных разности текущего и предыдущего
Дана последовательность целых чисел. Определить количество чисел, кратных разности текущего и предыдущего чисел.


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru