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

зделать задачу по дискретной математике - C++

Восстановить пароль Регистрация
 
igor myakota
 Аватар для igor myakota
58 / 58 / 15
Регистрация: 03.05.2012
Сообщений: 1,200
08.09.2013, 22:21     зделать задачу по дискретной математике #1
Пусть сгенерированные на ЭВМ множества А, В, С состоят из элементов: А = {1, 3, 4, 5, 10}, B = {3, 5, 7, 8, 9}, C = {3, 5, 6 , 9, 10}.
Тогда результат выполнения операции пересечения этих множеств имеет вид:
D = A http://www.cyberforum.ru/cgi-bin/latex.cgi?\subset B http://www.cyberforum.ru/cgi-bin/latex.cgi?\subset C = {3, 5}
написать код
Изображения
 
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.09.2013, 22:21     зделать задачу по дискретной математике
Посмотрите здесь:

как зделать функцию C++
МОжна тут такое зделать? C++
как зделать в цикле C++
C++ как зделать эту программу
помогите зделать завдание на C/C++ C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nullik
 Аватар для Nullik
43 / 12 / 1
Регистрация: 13.03.2013
Сообщений: 297
Завершенные тесты: 1
08.09.2013, 22:28     зделать задачу по дискретной математике #2
брать одно число из А и проверять его через цикл for в В и C?
igor myakota
 Аватар для igor myakota
58 / 58 / 15
Регистрация: 03.05.2012
Сообщений: 1,200
08.09.2013, 22:30  [ТС]     зделать задачу по дискретной математике #3
то можете хотя б написать код а то с++ никогда не было был тока паскаль чтобы розобратся
кстати!! Считать универсальной множеством Х все натуральные числа от 0 до 40. Расчеты выполнить используя ЭВМ.
Nullik
 Аватар для Nullik
43 / 12 / 1
Регистрация: 13.03.2013
Сообщений: 297
Завершенные тесты: 1
08.09.2013, 22:52     зделать задачу по дискретной математике #4
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
#include "stdafx.h"
#include <iostream> //обязательная библиотека
#include <ctime> //для работы рандома
#include <vector> //для работы вектора
 
using namespace std; //чтобы не прописывать всё время std:: для cout, vector, cin, например.
 
void main() 
{
    int n1,n2,n3,i=0,j=0,h=0; //ввели переменные счётчики. Группа n -- для динамических одномерных массивов
    setlocale(0,""); //русский язык
    srand (time(0)); //рандомные числа по секундам
    cout << "Введите размер первого множества:\n";
    cin >> n1;
    cout << "Введите размер второго множества:\n";
    cin >> n2;
    cout << "Введите размер третьего множества:\n";
    cin >> n3;
    cout << "\n\nD = A с B с C = {";
 
    int *a,*b,*c; //создали указали на память
    a = new int[n1]; //выделили память под эти указатели, т.е., создали динамический массив int типа под n1 размер
    b = new int[n2];
    c = new int[n3];
    vector<int> d; //сделали вектор, куда будем складывать "решение"
 
    //сначала нужно создать эти множества, заполнили их рандомом
    for (;i<n1;i++) 
    {
        a[i]=rand() %40; // от 0 до 40, только не помню - 40 включительно или нет.
    }
    for (i=0;i<n2;i++)
    {
        b[i]=rand() %40;
    }for (i=0;i<n3;i++)
    {
        c[i]=rand() %40;
    }
 
    // поэлементно проверяем содержание одинаковых элементов
    for(i=0; i<n1; i++)
    {
        for (j=0; j<n2; j++)
        {
            for (h=0; h<n3; h++)
            {
                if ((a[i]==b[j])&&(a[i]==c[h])) //если выполнилось это условие, то
                {
                    d.push_back(a[i]); //добавляем в вектор элемент-повторюшку
                }
            }
        }
    }
 
    for (i=0; i<d.size(); i++) //распечатали элементы "пересечения"
    {
        cout << d[i] << ", ";
    }
 
    cout << "}";
 
    cin.get(); //задержка экрана
    cin.get();
}
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
08.09.2013, 23:13     зделать задачу по дискретной математике #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
#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
 
 
int main() {
   std::vector<int> U(41);
   std::iota(std::begin(U), std::end(U), 0);
 
   std::vector<int> A { 1, 3, 4, 5, 10 };
   std::vector<int> B { 3, 5, 7, 8, 9  };
   std::vector<int> C { 3, 5, 6, 9, 10 };
 
   std::vector<int> AandB;
   std::set_intersection(
         std::begin(A), std::end(A)
       , std::begin(B), std::end(B)
       , std::back_inserter(AandB));
 
   std::vector<int> notAandB;
   std::set_difference(
         std::begin(U), std::end(U)
       , std::begin(AandB), std::end(AandB)
       , std::back_inserter(notAandB));
 
   std::vector<int> result;
   std::set_intersection(
         std::begin(notAandB), std::end(notAandB)
       , std::begin(C), std::end(C)
       , std::back_inserter(result));
 
   std::copy(
         std::begin(result), std::end(result)
       , std::ostream_iterator<int>(std::cout, " "));
   std::cout << std::endl;
}
http://ideone.com/E4zDw1
igor myakota
 Аватар для igor myakota
58 / 58 / 15
Регистрация: 03.05.2012
Сообщений: 1,200
08.09.2013, 23:58  [ТС]     зделать задачу по дискретной математике #6
Цитата Сообщение от Nullik Посмотреть сообщение
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
#include "stdafx.h"
#include <iostream> //обязательная библиотека
#include <ctime> //для работы рандома
#include <vector> //для работы вектора
 
using namespace std; //чтобы не прописывать всё время std:: для cout, vector, cin, например.
 
void main() 
{
    int n1,n2,n3,i=0,j=0,h=0; //ввели переменные счётчики. Группа n -- для динамических одномерных массивов
    setlocale(0,""); //русский язык
    srand (time(0)); //рандомные числа по секундам
    cout << "Введите размер первого множества:\n";
    cin >> n1;
    cout << "Введите размер второго множества:\n";
    cin >> n2;
    cout << "Введите размер третьего множества:\n";
    cin >> n3;
    cout << "\n\nD = A с B с C = {";
 
    int *a,*b,*c; //создали указали на память
    a = new int[n1]; //выделили память под эти указатели, т.е., создали динамический массив int типа под n1 размер
    b = new int[n2];
    c = new int[n3];
    vector<int> d; //сделали вектор, куда будем складывать "решение"
 
    //сначала нужно создать эти множества, заполнили их рандомом
    for (;i<n1;i++) 
    {
        a[i]=rand() %40; // от 0 до 40, только не помню - 40 включительно или нет.
    }
    for (i=0;i<n2;i++)
    {
        b[i]=rand() %40;
    }for (i=0;i<n3;i++)
    {
        c[i]=rand() %40;
    }
 
    // поэлементно проверяем содержание одинаковых элементов
    for(i=0; i<n1; i++)
    {
        for (j=0; j<n2; j++)
        {
            for (h=0; h<n3; h++)
            {
                if ((a[i]==b[j])&&(a[i]==c[h])) //если выполнилось это условие, то
                {
                    d.push_back(a[i]); //добавляем в вектор элемент-повторюшку
                }
            }
        }
    }
 
    for (i=0; i<d.size(); i++) //распечатали элементы "пересечения"
    {
        cout << d[i] << ", ";
    }
 
    cout << "}";
 
    cin.get(); //задержка экрана
    cin.get();
}
а можете сказать что ето "Введите размер первого множества"??
Nullik
 Аватар для Nullik
43 / 12 / 1
Регистрация: 13.03.2013
Сообщений: 297
Завершенные тесты: 1
09.09.2013, 06:52     зделать задачу по дискретной математике #7
Ну, например, в паскале, чтобы сделать массив, ты внутри программы пишешь/объявляешь массив, его длину. Числа груупы n нужны для трёх различных множеств, т.е., это как бы мы вводим размер массива. Это динамические массивы, и вот:

Перед cin.get();

Допиши:

delete a, b,c; //раз мы память взяли, то её должны и вернуть


cin >> - это ввод данных, тоже самое что read в паскале
cout << - тоже самое, что write
igor myakota
 Аватар для igor myakota
58 / 58 / 15
Регистрация: 03.05.2012
Сообщений: 1,200
09.09.2013, 14:48  [ТС]     зделать задачу по дискретной математике #8
тойсь розмер каждого масива нада вводить 40 ??
Миниатюры
зделать задачу по дискретной математике  
Nullik
 Аватар для Nullik
43 / 12 / 1
Регистрация: 13.03.2013
Сообщений: 297
Завершенные тесты: 1
09.09.2013, 16:37     зделать задачу по дискретной математике #9
нет, массив 40 не надо вводить, это значит что числа натуральные от 0 до 40 или 39, не помню.

Кстати, сейчас, скину доработанный вариант программы.

Добавлено через 1 час 23 минуты
так, я в коде обнаружила ошибку. Проанализировав её, пришла к такому выводу: чтобы не было случая, когда в двух из множеств по одной, например, 2, а в третьем три 2 (а программа будет три раза выводить 2), сделала следующее:

сделаем через "вектор" множества a,b,c. Когда мы встретим одинаковые элементы, то мы по одному элементу будем удалять из каждого множества, добавляя "удалённый элемент" в множество d.


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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include "stdafx.h"
#include <iostream> //обязательная библиотека
#include <ctime> //для работы рандома
#include <vector> //для работы вектора
 
using namespace std; //чтобы не прописывать всё время std:: для cout, vector, cin, например.
 
void main() 
{
    int n1,n2,n3,i=0,j=0,h=0, temp; //ввели переменные счётчики. Группа n -- для динамических одномерных массивов
    setlocale(0,""); //русский язык
    srand (time(0)); //рандомные числа по секундам
    cout << "Введите размер первого множества:\n";
    cin >> n1;
    cout << "Введите размер второго множества:\n";
    cin >> n2;
    cout << "Введите размер третьего множества:\n";
    cin >> n3;
 
 
 
    
 
    
    vector<int> d,a,b,c; //сделали вектора. Вектор d -- вектор для "ответа"
 
 
    //сначала нужно создать эти множества, заполнили их рандомом и выведем на экран
    for (;i<n1;i++) 
    {
        temp=rand() %41; // от 0 до 40 включительно => [0..40]
        a.push_back(temp);
        cout << a[i] <<" ";
    }
 
    cout << "\n";
 
    for (i=0;i<n2;i++)
    {
        temp=rand() %41;
        b.push_back(temp);
        cout << b[i] <<" ";
    }
 
    cout << "\n"; //перевод на след. строку ~ writeln();
 
    for (i=0;i<n3;i++)
    {
        temp=rand() %41;
        c.push_back(temp);
        cout << c[i] <<" ";
    }
 
    cout << "\n\nD = A с B с C = {";
    int dd_size1=0,dd_size2=0; //dd_size1 - начальный размер вектора d, dd_size2 - конечный. Нужно для сравнения, были ли изменения. 
    //так как мы будем удалять элемента, а на их место встанут другие -- надо проверять с того же места. В этом коде "сравнение размера ДО и ПОСЛЕ" поможет
 
    // поэлементно проверяем содержание одинаковых элементов
    for(i=0; i<n1; i++)
    {
        for (j=0; j<n2; j++)
        {
            for (h=0; h<n3; h++)
            {
                if ((a[i]==b[j])&&(a[i]==c[h])) //если выполнилось это условие, то
                {
                    d.push_back(a[i]); //добавляем в вектор элемент-повторюшку
                    a.erase(a.begin() + i); //удаляем элемент из ветора, "который на хочется на i" месте. 
                    //По сути, функция erase удаляет итератор, но мы сдвинули итератор на i, поэтому, тоже самое, как "удалить элемент на i-ом месте"
                    b.erase(b.begin() + j);
                    c.erase(c.begin() + h);
                    dd_size2++; //увеличили конечный размер
                    break; //вышли из этого цикла for
                }
                
            }
            if (dd_size1!=dd_size2) //если размеры поменялись, т.е., выход из цикла for выше был совершен, то
            {
                dd_size1++; //прировняли размеры ДО и ПОСЛЕ
                i--; //уменьшили переменную первого цикла, так как при начале цикла она вновь увеличится на 1 --> мы проверим ещё раз с того же места но другими элементами
                n1--; //уменьшаем размеры множеств, так как мы удаляли из них элементы. Можно было бы использовать name vector.size(); , но это длиннее. (возможно, постоянно будет проверка на размер) А так, разницы никакой. 
                n2--;
                n3--;
                break; //вышли из этого цикла for в "главный"
            }
        }
    }
 
 
    if (d.size()==0) //если в d ничего не добавили, то
    {
        cout << "пустое множество";
    }
    else //иначе
    {
 
        for (i=0; i<d.size(); i++) //распечатали элементы "пересечения"
        {
            cout << d[i] << ", ";
        }
    }
    cout << "}";
 
    cin.get(); //задержка экрана
    cin.get();
}
AlexCore
2 / 2 / 0
Регистрация: 28.08.2013
Сообщений: 26
09.09.2013, 17:52     зделать задачу по дискретной математике #10
Зачем так сложно? Если я правильно понимаю, задача сводится к тому, чтобы найти кол-во всех чисел от 0 до 40 включительно для каждого из трех множеств, и вывести минимальное количество по каждому числу

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
int main()
{
    vector <vector<int> > rep(40);
 
    for(int i = 0;i < 40; ++i)
        rep[i].assign(3, 0);
 
    int n, m, l;
    cin >> n >> m >> l;
 
    int tmp = 0;
    for(int i = 0;i < n; ++i)
        cin >> tmp, ++rep[tmp][0];
 
    for(int i = 0;i < m; ++i)
        cin >> tmp, ++rep[tmp][1];
 
    for(int i = 0;i < m; ++i)
        cin >> tmp, ++rep[tmp][2];
 
    cout << "{";
    bool fg = true;
    int min_ = 0;
    for(int i = 0;i < 40; ++i){
        if((min_ = min(min(rep[i][0], rep[i][1]), rep[i][2])) > 0){
            if(!fg)
                cout << ", ";
 
            for(int j = 1;j <= min_; ++j){
                fg = false;
                cout << i;
                if(j != min_)
                    cout << ", ";
            }
        }
    }
    cout << "}" << endl;
 
    getch();
    return 0;
}
Тест:
5 5 5
1 2 2 3 3
4 3 2 2 3
1 3 2 2 3

Вывод:
{2, 2 ,3 ,3}
Nullik
 Аватар для Nullik
43 / 12 / 1
Регистрация: 13.03.2013
Сообщений: 297
Завершенные тесты: 1
09.09.2013, 18:29     зделать задачу по дискретной математике #11
Да, всё же:

5 5 5
1 2 2 3 3
4 3 2 2 3
1 3 2 2 3
ответ: { }

Добавлено через 4 минуты
хотя, я никак не пойму смысла картинки -- из неё следует, что будет ответ:

1,4,7,8,9,10 пересечь с 3,5,6,9,10, = 6,9,10.

Добавлено через 2 минуты
и почему в коде два раза буква m в циклах фор?
Raali
572 / 276 / 12
Регистрация: 06.07.2013
Сообщений: 917
Завершенные тесты: 1
09.09.2013, 18:32     зделать задачу по дискретной математике #12
Цитата Сообщение от Nullik Посмотреть сообщение
1,4,7,8,9,10 пересечь с 3,5,6,9,10, = 6,9,10.
= 9 , 10 - только они присутствуют и там и там
AlexCore
2 / 2 / 0
Регистрация: 28.08.2013
Сообщений: 26
09.09.2013, 18:38     зделать задачу по дискретной математике #13
Про m - верно замечено
Nullik
 Аватар для Nullik
43 / 12 / 1
Регистрация: 13.03.2013
Сообщений: 297
Завершенные тесты: 1
09.09.2013, 18:44     зделать задачу по дискретной математике #14
Да, верно.

И всё же, мне кажется, я нашла способ ещё короче (ещё один вариант).

AlexCore, если вам не сложно, расскажите вкратце ещё раз: что делает ваш код?

Мой код банально перебирает и сравнивает.
AlexCore
2 / 2 / 0
Регистрация: 28.08.2013
Сообщений: 26
09.09.2013, 18:56     зделать задачу по дискретной математике #15
Диапазон чисел - от 0 до 40. Создадим вектор, который будет содержать вектор из трех элементов: число вхождений данного числа в первом множестве, второй элемент - число вхождений данного числа во втором множестве, третий - соответственно. Далее посчитаем количество вхождений чисел во всех множествах. Далее, мы выводим ответ: те числа, минимальное кол-во которых больше нуля, и столько раз, сколько составляет этот минимум...допустим, у нас множества {2, 3, 2}, {2, 1, 1}, {1, 3, 2}. для rep[0] = 0, 0, 0, rep[1](для единицы) = 0, 2, 1, rep[2] = 2, 1, 1. И так далее...потом находим минимумы, то есть для rep[0] = 0, rep[1](для единицы) = 0, rep[2] = 1, в итоге выводим {2}.

Но судя по картинке, нужно совсем другое.
Nullik
 Аватар для Nullik
43 / 12 / 1
Регистрация: 13.03.2013
Сообщений: 297
Завершенные тесты: 1
09.09.2013, 18:56     зделать задачу по дискретной математике #16
Мой вариант через 3 цикла -- самый атасный. Я думаю, он "тяжёлым" будет для большого кол-ва элементов в множестве.

Вариант AlexCore, который неплохой, не решил задачу в моменте:
1 2 2 3 3
4 3 2 2 3
1 3 2 2 3
вот выпадут вам такие числа и сидите, делайте ещё по (41 число - 0 и 40 включены в область) 37 проверок. А Вдруг будет так, что 3 множества по миллиону в каждом и в одном все 0, в другом все 1, в третьем все 2. И?

и тут меня осенило, как мне кажется.

Сначала мы сравним, какое из множеств самое маленькое.

Сначала мы "просканим" первое множество, выпишем из него все оригинальные элементы, а неоригинальные элементы запишем ниже. т.е., предположительно, можно создать двумерный вектор. (можно 4 вектора)

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

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

Т.е., если в среднем не оказалось "0", а он есть в самом маленьком множестве, то мы запишем 42 (это будет число х, которое нужно будет для сравнения).

на выходе, мы получим, например, такой двумерный массив:


1 2 3 4 5 6 7 10 23 - оригинальные элементы первого множества
2 4 5 1 1 1 6 1 5 - количество их встреч
1 1 7 1 1 2 3 42 42 - кол-во встреч в среднем
1 42 1 1 1 8 4 42 42 - кол-во встреч в большом
потом смотрим по столбцам и ищем где нет 42 (в столбце) и наименьшее:

ответ будет такой: 1, 3, 4, 5, 6, 7, 7, 7
AlexCore
2 / 2 / 0
Регистрация: 28.08.2013
Сообщений: 26
09.09.2013, 19:14     зделать задачу по дискретной математике #17
Цитата Сообщение от Nullik Посмотреть сообщение

вот выпадут вам такие числа и сидите, делайте ещё по (41 число - 0 и 40 включены в область) 37 проверок. А Вдруг будет так, что 3 множества по миллиону в каждом и в одном все 0, в другом все 1, в третьем все 2. И?
И получаем rep[0] = 1000000, 0, 0; rep[1] = 0, 1000000, 0; rep [2] = 0, 0, 1000000;...

Потом 40 проходок, которые вычисляют минимумы, а они все 0, и все...40 итераций против Ваших n1*n2*n3, при одинаковой размерности O(N^3). Пусть у нас одинаковая размерность и N = 1000000 как Вы сказали. Имеем огромную цифру 1000000000000000000, то есть 10^18...в 1 секунду компьютер обработает примерно 10^8...и сколько Вы будете тогда ждать? 10000000000 секунд?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.09.2013, 19:21     зделать задачу по дискретной математике
Еще ссылки по теме:

C++ Задача по дискретной математике (написать программу для расшифровки числового ребуса)
C++ НЕ сложная Англоязычная литература по языкам программирования, алгоритмам и дискретной математике
C++ Как зделать второе уровнение?

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

Или воспользуйтесь поиском по форуму:
Nullik
 Аватар для Nullik
43 / 12 / 1
Регистрация: 13.03.2013
Сообщений: 297
Завершенные тесты: 1
09.09.2013, 19:21     зделать задачу по дискретной математике #18
AlexCore, я сравнила с другим вариантом.
Тоже проходы, но не по всем 41 элементу.

Т.е., у вас останется потом 39 проходов, потом сравнить.
Предположим, что множества не равные. Это в одном 1 миллион, в другом 2, в третьем 3.

И я предложила 3-ий вариант, не использовать for-for-for, как это было в первом варианте, а использовать то, что ниже написано.

Или вы хотите сказать, что третий (это который буквами описан, если что, а не тот что на первой странице темы) вариант будет по мощности O(N^3) ?

Добавлено через 51 секунду
Сейчас, оформлю код, думаю, на словах плохо видно.
Yandex
Объявления
09.09.2013, 19:21     зделать задачу по дискретной математике
Ответ Создать тему
Опции темы

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