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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.79
l2ded
80 / 68 / 11
Регистрация: 10.05.2011
Сообщений: 284
#1

Метод Квайна-Мак'Класки - C++

14.11.2012, 23:40. Просмотров 3566. Ответов 4
Метки нет (Все метки)

Пишу программу для нахождения Fmin и сталкиваюсь с тем, что не знаю, как найти Fmin
У меня в программе находит все импликанты, как у меня на скрине, но я не понимаю, как находят Fmin.
0
Миниатюры
Метод Квайна-Мак'Класки  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.11.2012, 23:40
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Метод Квайна-Мак'Класки (C++):

очень тяжело,метод квайна-мак-класки - C++
Поиск минимальной конъюнктивный нормальной формы булевой функции (случай зависимости функции от 4 переменных) по методу Квайна-Мак-Класки

СЛАУ. Метод обратной матрицы, метод Гаусса, метод Крамера, метод Зейделя - C++
Помогите ребят. Не могу построить алгоритмы для этих методов Язык C++

Исправить ошибки в работе метода Квайна Мак'Класки - C++
Пишу программу по методу Квайна Мак'Класки, программа работает не верно, не могу понять почему #include "stdafx.h" #include <stdio.h> ...

Метод медиан из трех элементов VS улучшенный быстрый метод сортировки(метод Бентли-Макилроя) - C++
Здравствуйте! Дали весьма интересное задание. Сравнить два вышеуказанных метода сортировки для массива из 10000 элементов, результаты...

Мой код - метод бисекции, метод секущих (метод хорд) - C++
Всем привет!!! Изучаем в институте С++. Сделал код, и там, и там одна и та же проблема - при любых вбиваемых значениях программа делает...

Исследовать итерационный метод- метод касательных для решения нелинейных уравнений - C++
прочитал много всего , но сам пример реализовать никак не могу , кто может помогите F(x) = x5+5x+1=0 с...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Анна2405
0 / 0 / 0
Регистрация: 09.05.2013
Сообщений: 6
09.05.2013, 23:17 #2
оу)) а вы можете поделиться этой программкой? а то делаю курсовик по цифровым автоматам, а здесь такие огромные функции, что я не вывожу уже сидеть и все считать...
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.05.2013, 23:30 #3
l2ded, http://ptca.narod.ru/lec/lec4_2.html
0
Анна2405
0 / 0 / 0
Регистрация: 09.05.2013
Сообщений: 6
09.05.2013, 23:36 #4
спасибо)) но я понимаю как решать и все это делается ) просто у меня для минимизации 6 разрядных функции где количество их доходит до 32, и 32 функции 6 разрядов * 8 . и я уже вторые сутки минимизирую сижу, а завтра курсовик сдавать, и вот хотелось бы найти программку которая сделает это быстрее и без ошибок, и я уже уйду наконец от минимизации и перейду к триггерам свои и цифровому автомату ) была бы очень признательна если бы вы смогли поделиться программкой за вознаграждение )
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
10.05.2013, 18:13 #5
Анна2405, Вот он! говнокод ! но работает !! на вход подаётся список термов
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <set>
 
using namespace std;
 
void print_def(int n, char symb){
    for (int i = 0; i < n; i++) {
        cout << symb;
    }
}
 
int pos(const string &v1, const string &v2){
    int cnt = -1;
    if (v1.size() != v2.size())
        return -1;
    for (int i = 0; i < v1.size(); i++) {
        if (v1[i] != v2[i]) {
            if (cnt != -1)
                return -1;
            cnt = i;
        }
    }
    return cnt;
}
 
bool check(const string &v1, const string &v2) {
    if (v1.size() != v2.size())
        return false;
    for (int i = 0; i < v1.size(); i++) {
        if (v1[i] != v2[i] && v1[i] != '*' && v2[i] != '*')
            return false;
    }
    return true;
}
 
int main(){
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    int n = 10;
    vector <string> term;
    vector< vector < string > > d(n);
    string str;
    while (cin >> str) {
        int cnt = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str[i] == '1') {
                cnt++;
            }
        }
        term.push_back(str);
        d[cnt].push_back(str);
    }
    vector < vector <string> > scn(n);
    for (int t = 0; t < n - 1; t++) {
        printf("Board #%d\n", t); 
        if (d[t+1].size() == 0 || d[t].size() == 0)
            continue;
        print_def(d[t+1][0].size(), '-');
        for (int j = 0; j < d[t+1].size(); j++) {
            printf(" | ");
            cout << d[t+1][j];
        }
        printf(" | ");
        puts("");
        for (int i = 0; i < d[t].size(); i++) {
            cout << d[t][i]; 
            printf(" | ");
            for (int j = 0; j < d[t+1].size(); j++) {
                int k = pos(d[t][i], d[t+1][j]);
                if (k == -1)
                    print_def(d[t][i].size(), '-');
                else {
                    char tmp = d[t][i][k];
                    d[t][i][k] = '*';
                    scn[t].push_back(d[t][i]);
                    cout << d[t][i];
                    d[t][i][k] = tmp;
                }
                printf(" | ");
            }
            puts("");
        }
        puts("");
    }
    printf("---------------------\n"); 
    map <string, int> implic;
    vector <string> perv_impl;
    for (int t = 0; t < n - 1; t++) {
        printf("Board #%d\n", t); 
        if (scn[t+1].size() == 0 || scn[t].size() == 0)
            continue;
        print_def(scn[t+1][0].size(), '-');
        for (int j = 0; j < scn[t+1].size(); j++) {
            printf(" | ");
            cout << scn[t+1][j];
        }
        printf(" | ");
        puts("");
        for (int i = 0; i < scn[t].size(); i++) {
            cout << scn[t][i]; 
            printf(" | ");
            for (int j = 0; j < scn[t+1].size(); j++) {
                int k = pos(scn[t][i], scn[t+1][j]);
                if (k == -1)
                    print_def(scn[t][i].size(), '-');
                else {
                    char tmp = scn[t][i][k];
                    scn[t][i][k] = '*';
                    implic[scn[t][i]]++;
                    if (implic[scn[t][i]] == 2) { 
                        perv_impl.push_back(scn[t][i]);
                    }
                    cout << scn[t][i];
                    scn[t][i][k] = tmp;
                }
                printf(" | ");
            }
            puts("");
        }
        puts("");
    }
    map <string, int> finale;
    printf("\nimplicanti:\n");
    for (int i = 0; i < perv_impl.size(); i++) {
        finale[perv_impl[i]]++;
        cout << perv_impl[i] << "\n";
    }
    printf("---------------------\n"); 
    if (perv_impl.size() == 0 || term.size() == 0)
        return 0;
    print_def(perv_impl[0].size(), '-');
    printf(" | ");
    for (int j = 0; j < term.size(); j++) {
        cout << term[j];
        printf(" | ");
    }
    puts("");
    vector <int> flags(term.size(), -1);
    for (int i = 0; i < perv_impl.size(); i++) {
        cout << perv_impl[i] << " | ";
        for (int j = 0; j < term.size(); j++) {
            if (check(perv_impl[i], term[j])) {
                if (flags[j] == 0) { 
                    flags[j] = i;
                } else 
                    flags[j] = -2;
                print_def(perv_impl[i].size(), '*');
            }else 
                print_def(perv_impl[i].size(), '-');
            printf(" | ");
        }
        puts("");
    }
    vector <string> sim;
    for (int j = 0; j < term.size(); j++) {
        if (flags[j] > -1) {
            sim.push_back(perv_impl[flags[j]]);
            finale[perv_impl[flags[j]]]++;
        }
    }
    printf("---------------------\n"); 
    printf("\nsushestvennie implicanti:\n");
    for (int i = 0; i < sim.size(); i++) {
        cout << sim[i] << "\n";
    }
    printf("---------------------\n"); 
    printf("final answer:\n");
    for (map <string, int>::iterator it = finale.begin(); it != finale.end(); ++it) {
        if (it->second == 1) {
            cout << it->first << "\n";
        }
    }
    return 0;
}
Добавлено через 9 минут
Анна2405, если будет нужно, то я перепишу чтобы чисто было, а то я писал код, пока вы мне его объясняли

Добавлено через 16 часов 8 минут
Анна2405, Вот переписал покрасивей
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <set>
 
using namespace std;
 
void print_chars(int n, char symb){
    for (int i = 0; i < n; i++) {
        cout << symb;
    }
}
 
int pos(const string &v1, const string &v2){
    int cnt = -1;
    if (v1.size() != v2.size())
        return -1;
    for (int i = 0; i < v1.size(); i++) {
        if (v1[i] != v2[i]) {
            if (cnt != -1)
                return -1;
            cnt = i;
        }
    }
    return cnt;
}
 
bool check(const string &v1, const string &v2) {
    if (v1.size() != v2.size())
        return false;
    for (int i = 0; i < v1.size(); i++) {
        if (v1[i] != v2[i] && v1[i] != '*' && v2[i] != '*')
            return false;
    }
    return true;
}
 
vector <string> print_table(int num, vector <string> & row, const vector <string> & col) {
    vector <string> implicants;
    printf("\nTable %d - %d \n", num, num + 1);
    vector <string> ans;
    if (row.size() == 0 || col.size() == 0) {
        printf("--- Table is empty ---");
        return implicants;
    }
    int len = col[0].length();
    print_chars(len, ' ');
    printf(" | ");
    for (int i = 0; i < col.size(); i++) {
        cout << col[i] << " | ";
    }
    printf("\n");
    for (int i = 0; i < row.size(); i++) {
        cout << row[i] << " | ";
        for (int j = 0; j < col.size(); j++) {
            int k = pos(row[i], col[j]);
            if (k == -1) {
                print_chars(len, '-');
            } else {
                char tmp = row[i][k];
                row[i][k] = '*';
                implicants.push_back(row[i]);
                cout << row[i];
                row[i][k] = tmp;
            }
            printf(" | ");
        }
        printf("\n");
    }
    printf("\n");
    return implicants;
}
 
vector <string> total_board(const vector <string> & term, const vector <string> & primary_implicants) {
    vector <string> answer;
    printf("\n###Total Board###\n");
    vector <string> ans;
    if (term.size() == 0 || primary_implicants.size() == 0) {
        printf("--- Total Board is empty ---");
        return answer;
    }
    int len = term[0].length();
    print_chars(len, ' ');
    printf(" | ");
    for (int i = 0; i < term.size(); i++) {
        cout << term[i] << " | ";
    }
    printf("\n");
    vector <int> cols(term.size(), -1);
    for (int i = 0; i < primary_implicants.size(); i++) {
        cout << primary_implicants[i] << " | ";
        for (int j = 0; j < term.size(); j++) {
            if (!check(primary_implicants[i], term[j])) {
                print_chars(len, '-');
            } else {
                if (cols[j] == -1) {
                    cols[j] = i;
                } else 
                    cols[j] = -2;
                print_chars(len, '+');
            }
            printf(" | ");
        }
        printf("\n");
    }
    vector <bool> ch(primary_implicants.size(), true);
    for (int i = 0; i < term.size(); i++) {
        if (cols[i] > -1) {
            ch[cols[i]] = false;
        }
    }
    printf("\nCommited Implicants: \n");
    for (int i = 0; i < primary_implicants.size(); i++) {
        if (ch[i])
            answer.push_back(primary_implicants[i]);
        else {
            cout << primary_implicants[i] << endl;
        }
    }
    printf("\n");
    return answer;
}
 
int main(){
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    int n;
    vector <string> term;
    vector< vector < string > > d;
    string str;
    while (cin >> str) {
        if (d.size() == 0) {
            n = str.length() + 1;
            d = vector< vector < string > > (n);
        }
        int cnt = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str[i] == '1') {
                cnt++;
            }
        }
        term.push_back(str);
        d[cnt].push_back(str);
    }
    printf("Input file : \n");
    for (int i = 0; i < n; i++) {
        printf("Group number %d (%d): ", i, d[i].size());
        for (int j = 0; j < d[i].size(); j++) {
            cout << d[i][j];
            if (j != d[i].size() - 1)
                printf(", ");
        }
        printf("\n");
    }
    printf("\n");
    vector < vector <string> > scn(n);
    for (int t = 0; t < n - 1; t++) {
        scn[t] = print_table(t, d[t], d[t+1]);
    }
    printf("\n---------------------\n"); 
    vector <string> temp, primary_implicants;
    map <string, int> implicants;
    for (int t = 0; t < n - 1; t++) {
        temp = print_table(t, scn[t], scn[t+1]);
        for (int i = 0; i < temp.size(); i++) {
            implicants[temp[i]]++;
            if (implicants[temp[i]] == 2) { 
                primary_implicants.push_back(temp[i]);
            }
        }
    }
    printf("\n\nPrimary Implicants : \n");
    for (int i = 0; i < primary_implicants.size(); i++) {
        cout << primary_implicants[i] << "\n";
    }
    vector <string> ans = total_board(term, primary_implicants);
    printf("\nFinal answer:\n");
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << endl;
    }
    return 0;
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.05.2013, 18:13
Привет! Вот еще темы с ответами:

Не сходится теория и практика метод Шелла и метод простого выбора - C++
Здравствуйте! Помогите пожулуйста найти ошибке в коде, Я уже не знаю где ее искать. У меня метод простого выбора работает по показателям...

Метод деления отрезка пополам для решения нелинейных уравнений (метод дихотомии) - C++
Здравствуйте. Помогите пожалуйста дописать программу. Вот что вымучал, но на сдаче завалили, типо нет вывода корней, не рассмотрены...

Нахождения корней уравнения: метод половинного деления (бисекции) или метод хорд - C++
Разработать программу нахождения корней уравнения f(x) =0 на интервале с точностью e = 0,001 (интервал или подобрать самостоятельно). При...

Производный класс: метод возведения в произвольную степень, и метод для вычисления логарифма числа - C++
Реализовать класс-оболочку Number для числового типа float. Реализовать методы сложения и деления. Создать производный класс Real, в...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
10.05.2013, 18:13
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru