Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- var R, SR, S, Rez, Flag, IndexS, IndexRez;
- function doAll(n, defArr, undefArr, minForm, def){
- var values = [];
- R = n;
- SR = Math.pow(2, n);
- S = [];
- Rez = [];
- for(var i = 0; i < defArr.length; i++) {
- var s = toBinary(defArr[i], n);
- Rez.push(s);
- S.push(s);
- values.push(s);
- }
- //if (def == 1)
- for(var i = 0; i < undefArr.length; i++) {
- var s = toBinary(undefArr[i], n);
- if (s != '0NaN'){
- Rez.push(s);
- S.push(s);
- values.push(s);}
- }
- terms = minimize();
- buildMatrix(terms, values);
- }
- function minimize(){
- //склеивание
- for(var i = 0; i < R; i++) {
- Flag = newArr(SR);
- Rez = [];
- console.log('-----------------');
- console.log(i +'-r0', Rez, S, Flag);
- for(var j=0; j < S.length-1; j++) {
- for(var k=j+1; k < S.length; k++)
- stuck(j, k);
- }
- console.log(i +'-r1', Rez, S, Flag);
- //копирование не склеившихся компонент
- for(var j=0; j < S.length; j++) {
- if (Flag[j] == 0)
- Rez.push(S[j]);
- }
- console.log(i +'-r2', Rez, S, Flag);
- clear();
- console.log(i +'-r3', Rez, S, Flag);
- }
- //удаление ****
- Rez = [];
- for(var i=0; i < S.length; i++) {
- if (del(S[i]) == false)
- Rez.push(S[i]);
- }
- return Rez;
- }
- function stuck(i1, i2){
- var s1 = S[i1];
- var s2 = S[i2];
- var k = 0;
- var n;
- for(var i=0; i < R; i++) {
- if (s1[i] != s2[i]) {
- k++;
- n=i;
- }
- }
- if (k == 0) {
- Rez.push(s1);
- Flag[i1]=1;
- Flag[i2]=1;
- }
- if (k == 1 && s1[n] != '*' && s2[n] != '*'){
- var ss = s1.substring(0, n) + '*' + s1.substring(n+1, s1.length);
- Rez.push(ss);
- Flag[i1] = 1;
- Flag[i2] = 1;
- }
- }
- function clear(){
- Flag = newArr(Rez.length);
- S = [];
- for(var i=0; i < Rez.length; i++) {
- if (Flag[i] == 0) {
- for(var j=i+1; j < Rez.length; j++) {
- if (Rez[i] == Rez[j])
- Flag[j] = 1;
- }
- }
- }
- for(var i=0; i < Rez.length; i++) {
- if (Flag[i] == 0)
- S.push(Rez[i]);
- }
- }
- function del(ss){
- var k=0;
- for(var i = 0; i < R; i++) {
- if (ss[i]=='*')
- k=k+1;
- }
- return (k==R);
- }
- /*
- Построение импликантной матрицы
- terms - массив приведенных термов, каждый терм это массив вида ['1', '0', '1', '*']
- values - массив значений на которых ф-ция принимает значение TRUE. Каждое значение задано массивом вида [1, 1, 0, 1]
- Длины каждого терма и каждого значения должны быть одинаковы (это число переменных)
- */
- function buildMatrix(terms, values) {
- // массив с существенными термами
- // если term[i] - существенный, то stongTermArr[i] = 1 (иначе 0)
- var stongTermArr = newArr(terms.length);
- // массив со значениями существенных термов для каждого набора значений
- var total = newArr(values.length);
- var finaly = true;
- console.log("Terms", terms); // отладочная печать
- console.log("Values", values); // отладочная печать
- printValuesTable(terms, values);
- var nt = 0;
- while (finaly == true){
- // ищем существенные термы
- finaly = findStrongTerms(stongTermArr, terms, values, total, finaly);
- console.log("StrongTerms: ", stongTermArr); // отладочная печать
- // Заносим значения всех существенных термов в total
- fillStrongTermsTotal(total, stongTermArr, terms, values);
- nt = 0;
- for (var i = 0; i < total.length; i++){
- if (total[i] == 1)
- nt++;
- }
- if (nt == total.length)
- finaly = false;
- if (finaly == true)
- //убираем термы входящие в другие
- finaly = mergeTerms(values, terms, total, stongTermArr);
- console.log("Total: ", total); // отладочная печать
- }
- var h = 1;
- for (var w = 0; w < stongTermArr.length; w++){
- if (stongTermArr[w] == 0) {
- fillOtherTermsTotal(total, stongTermArr, terms, values, w);
- }
- printResult(terms, stongTermArr, h);
- h++;
- }
- printResult(terms, stongTermArr, 1);
- }
- function trySetValue(total, term, values) {
- var changed = false;
- for (var i = 0; i < total.length; i++) {
- if (total[i] == 0 && value(term, values[i]) == 1) {
- total[i] = 1;
- changed = true;
- }
- }
- return changed;
- }
- function value(term, values) {
- if (term.length != values.length)
- console.log('Term or values is wrang', term, values);
- var val = 1;
- for (var i = 0; i < term.length; i++) {
- if (term[i] == '*')
- continue;
- val = val * (term[i] == values[i] ? 1 : 0);
- }
- return val;
- }
- // для каждого набора значений ищем существенный терм
- function findStrongTerms(stongTermArr, terms, values, total, finaly) {
- finaly = false;
- for (var i = 0; i < values.length; i++)
- if (total[i] == 0){
- var n = 0;
- var termIdx = -1;
- for (var j = 0; j < terms.length; j++)
- if (stongTermArr[j] != '*'){
- var val = value(terms[j], values[i]);
- if (val == 1) {
- n++;
- termIdx = j;
- }
- }
- // ура-ура нашли!
- if (n == 1){
- stongTermArr[termIdx] = 1;
- finaly = true;
- }
- }
- return finaly;
- }
- // Заносим значения всех существенных термов в total
- function fillStrongTermsTotal(total, stongTermArr, terms, values) {
- for (var i = 0; i < stongTermArr.length; i++) {
- if (stongTermArr[i] == 1) {
- for (var j = 0; j < values.length; j++) {
- var val = value(terms[i], values[j]);
- if (val == 1)
- total[j] = 1;
- }
- }
- }
- }
- //идем по всем оставшимся (несущ.) термам и пытаемся заполнить ими нули в total (если они там есть)
- function fillOtherTermsTotal(total, stongTermArr, terms, values, w) {
- for (var i = w; i < stongTermArr.length; i++) {
- if (stongTermArr[i] == 0) {
- var totalChanged = trySetValue(total, terms[i], values);
- stongTermArr[i] = (totalChanged ? 1 : 0);
- }
- }
- }
- function toBinary(str, length) {
- return parseInt(str).toString(2).padStart(length, '0');
- }
- function newArr(len, val) {
- val = (typeof val == 'undefined') ? 0 : val;
- var arr = [];
- arr.length = len;
- arr.fill(val, 0, len);
- return arr;
- }
- function mergeTerms(values, terms, total, stongTermArr) {
- mergeFound = false;
- var kv = 0;
- var k1 = 0;
- for (var i = 0; i < terms.length-1; i++) {
- if (stongTermArr[i] == '*')
- continue;
- for (var j = 0; j < terms.length; j++) {
- if (stongTermArr[i] != 0)
- continue;
- // если term[j] входит в term[i]
- if (termContains(terms[i], terms[j], values, total)) {
- stongTermArr[j] = '*'; // больше term[j] не рассматриваем
- mergeFound = true;
- }
- }
- }
- return mergeFound;
- }
- // Значения на терме t1 содержат в себе все значения на терме t2
- function termContains(t1, t2, values, total) {
- for (var i = 0; i < values.length; i++) {
- if (total[i] == 0) {
- var val1 = value(t1, values[i]);
- var val2 = value(t2, values[i]);
- if (val1 == 0 && val2 == 1)
- return false;
- }
- }
- return true;
- }
- //форматирование интерфейса
- function start() {
- var terms = parseInput(byId('inputTerms').value);
- var values = parseInput(byId('inputValues').value);
- process(terms, values);
- }
- function byId(id) {
- return document.getElementById(id);
- }
- function parseInput(txt) {
- txt = txt.split('\n');
- var arr = new Array();
- for (var i = 0; i < txt.length; i++) {
- var x = txt[i].trim();
- if (x.length > 2) {
- arr.push(x.split(''));
- }
- };
- return arr;
- }
- function printResult(terms, stongTermArr, num) {
- var html = '';
- for (var i = 0; i < stongTermArr.length; i++)
- if (stongTermArr[i] == 1)
- html += (html.length == 0 ? '' : ' + ') + terms[i];
- byId('res').innerHTML += '<small>Миним. форма:</small> ' + html + '</br>';
- }
- function printValuesTable(terms, values) {
- var html = '<tr><th></th>';
- for (var j = 0; j < values.length; j++)
- html += '<th>' + values[j] + '</th>';
- html += '</tr>';
- for (var i = 0; i < terms.length; i++) {
- html += '<tr><th>' + terms[i] + '</th>';
- for (var j = 0; j < values.length; j++)
- html += '<td>' + value(terms[i], values[j]) + '</td>';
- }
- byId('table').innerHTML = html;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement