import java.util.*;
import java.io.*;
class Formula {
public Formula(List<Term> termList) {
this.termList = termList;
}
public String toString() {
String result = "";
result += termList.size() + " terms, " + termList.get(0).getNumVars() + " variables\n";
for(int i=0; i<termList.size(); i++) {
result += termList.get(i).toString() + "\n";
}
return result;
}
public void reduceToPrimeImplicants() {
originalTermList = new ArrayList<Term>(termList);
int numVars = termList.get(0).getNumVars();
ArrayList[][] table = new ArrayList[numVars + 1][numVars + 1];
for(int dontKnows=0; dontKnows <= numVars; dontKnows++) {
for(int ones=0; ones <= numVars; ones++) {
table[dontKnows][ones] = new ArrayList();
}
}
for(int i=0; i<termList.size(); i++) {
int dontCares = termList.get(i).countValues(Term.DontCare);
int ones = termList.get(i).countValues((byte)1);
table[dontCares][ones].add(termList.get(i));
}
for(int dontKnows=0; dontKnows <= numVars - 1; dontKnows++) {
for(int ones=0; ones <= numVars - 1; ones++) {
ArrayList<Term> left = table[dontKnows][ones];
ArrayList<Term> right = table[dontKnows][ones + 1];
ArrayList<Term> out = table[dontKnows+1][ones];
for(int leftIdx = 0; leftIdx < left.size(); leftIdx++) {
for(int rightIdx = 0; rightIdx < right.size(); rightIdx++) {
Term combined = left.get(leftIdx).combine(right.get(rightIdx));
if (combined != null) {
if (!out.contains(combined)) {
out.add(combined);
}
termList.remove(left.get(leftIdx));
termList.remove(right.get(rightIdx));
if (!termList.contains(combined)) {
termList.add(combined);
}
}
}
}
}
}
}
public void reducePrimeImplicantsToSubset() {
int numPrimeImplicants = termList.size();
int numOriginalTerms = originalTermList.size();
boolean[][] table = new boolean[numPrimeImplicants][numOriginalTerms];
for (int impl=0; impl < numPrimeImplicants; impl++) {
for (int term=0; term < numOriginalTerms; term++) {
table[impl][term] = termList.get(impl).implies(originalTermList.get(term));
}
}
ArrayList<Term> newTermList = new ArrayList<Term>();
boolean done = false;
int impl;
while (!done) {
impl = extractEssentialImplicant(table);
if (impl != -1) {
newTermList.add(termList.get(impl));
} else {
impl = extractLargestImplicant(table);
if (impl != -1) {
newTermList.add(termList.get(impl));
} else {
done = true;
}
}
}
termList = newTermList;
originalTermList = null;
}
public static Formula read(Reader reader) throws IOException {
ArrayList<Term> terms = new ArrayList<Term>();
Term term;
while ((term = Term.read(reader)) != null) {
terms.add(term);
}
return new Formula(terms);
}
private int extractEssentialImplicant(boolean[][] table) {
for (int term=0; term < table[0].length; term++) {
int lastImplFound = -1;
for (int impl=0; impl < table.length; impl++) {
if (table[impl][term]) {
if (lastImplFound == -1) {
lastImplFound = impl;
} else {
// This term has multiple implications
lastImplFound = -1;
break;
}
}
}
if (lastImplFound != -1) {
extractImplicant(table, lastImplFound);
return lastImplFound;
}
}
return -1;
}
private void extractImplicant(boolean[][] table, int impl) {
for (int term=0; term < table[0].length; term++) {
if (table[impl][term]) {
for (int impl2=0; impl2 < table.length; impl2++) {
table[impl2][term] = false;
}
}
}
}
private int extractLargestImplicant(boolean[][] table) {
int maxNumTerms = 0;
int maxNumTermsImpl = -1;
for (int impl=0; impl < table.length; impl++) {
int numTerms = 0;
for (int term=0; term < table[0].length; term++) {
if (table[impl][term]) {
numTerms++;
}
}
if (numTerms > maxNumTerms) {
maxNumTerms = numTerms;
maxNumTermsImpl = impl;
}
}
if (maxNumTermsImpl != -1) {
extractImplicant(table, maxNumTermsImpl);
return maxNumTermsImpl;
}
return -1;
}
private List<Term> termList;
private List<Term> originalTermList;
public static void main(String[] args) {
try {
Formula f = Formula.read(new BufferedReader(new FileReader(args[0])));
f.reduceToPrimeImplicants();
System.out.println(f.toString());
f.reducePrimeImplicantsToSubset();
System.out.println(f.toString());
}
catch(IOException e) {
}
}
}
https://www.zhihu.com/question/19625397
著作权归作者所有。
商业转载请联系作者获得授权,非商业转载请注明出处。
作者:wu vvilp
链接:https://www.zhihu.com/question/19625397/answer/46837477
来源:知乎
#define aSet c
#define BufferedReader(x)1
#define byte Y[I][_^1]?do(:):_&1?do(.):do(`):8;++y;}
#define class int N=0,_,O=328,l=192,y=4,Y[80][64]={0},I;struct
#define do(c)a(#c "\b")
#define err c,c
#define getAllStrings(x));q()
#define if(x)b(#x)
#define IOException
#define line c
#define main(a)b(char*x){write(1,"\033[",2),null}main()
#define new
#define null a(x);}a(char*x){write(1,x,strlen(x));try;try;try;try;
#define out c,c
#define println(x)c
#define private int d(int
#define public short c;}c;typedef int BufferedReader;char*F="JF>:>FB;;BII";
#define return {return
#define static f(x){N=(N+x)%6,y--?f(0),f(1),f(4),f(1):++Y[(I=O+N[F]-66)
#define String
#define System c
#define this if(D):1,O=I,I/=16,l<_/32?if(B):l>/32?if(A):2,l=,_/=16,byte
#define throws
#define toArray(x)c
#define try for(;--c.c;)
#define void /16][(_=l+N[6+F]-66)/16]?O/=16,l/=32,OI/16?this
#define while(k)if(2J),if(7;21H),f(0),f(4),f(4),if(H),/*
import java.io.*;
import java.util.*;
/**
@author J. Random Worker
*/
class LameJavaApp
{
/** The infamous Long-Winded Signature From Hell. /
public static void main(String[] args)
throws IOException
{
/ Don't get me started on this. */
BufferedReader reader =
new BufferedReader(new FileReader(args[0]));
/* What, this long incantation just to print a string? */
System.err.println("Hello world!");
/* At least this is sane. */
String line;
while ((line = reader.readLine()) != null)
System.out.println(line.length());
}
/**
}
著作权归作者所有。
商业转载请联系作者获得授权,非商业转载请注明出处。
作者:wu vvilp
链接:https://www.zhihu.com/question/19625397/answer/46837477
来源:知乎
#define aSet c
#define BufferedReader(x)1
#define byte Y[I][_^1]?do(:):_&1?do(.):do(`):8;++y;}
#define class int N=0,_,O=328,l=192,y=4,Y[80][64]={0},I;struct
#define do(c)a(#c "\b")
#define err c,c
#define getAllStrings(x));q()
#define if(x)b(#x)
#define IOException
#define line c
#define main(a)b(char*x){write(1,"\033[",2),null}main()
#define new
#define null a(x);}a(char*x){write(1,x,strlen(x));try;try;try;try;
#define out c,c
#define println(x)c
#define private int d(int
#define public short c;}c;typedef int BufferedReader;char*F="JF>:>FB;;BII";
#define return {return
#define static f(x){N=(N+x)%6,y--?f(0),f(1),f(4),f(1):++Y[(I=O+N[F]-66)
#define String
#define System c
#define this if(D):1,O=I,I/=16,l<_/32?if(B):l>/32?if(A):2,l=,_/=16,byte
#define throws
#define toArray(x)c
#define try for(;--c.c;)
#define void /16][(_=l+N[6+F]-66)/16]?O/=16,l/=32,OI/16?this
#define while(k)if(2J),if(7;21H),f(0),f(4),f(4),if(H),/*
import java.io.*;
import java.util.*;
/**
@author J. Random Worker
*/
class LameJavaApp
{
/** The infamous Long-Winded Signature From Hell. /
public static void main(String[] args)
throws IOException
{
/ Don't get me started on this. */
BufferedReader reader =
new BufferedReader(new FileReader(args[0]));
/* What, this long incantation just to print a string? */
System.err.println("Hello world!");
/* At least this is sane. */
String line;
while ((line = reader.readLine()) != null)
System.out.println(line.length());
}
/**
}