一个 C++ 卡诺图最小化器（无限变量）

• 下载源代码   
• 下载可执行文件 

引言

此代码提供了一个 C++ 程序，它实现了一个卡诺图 (k-map) 最小项生成器，该生成器包含一个可以解决所有类型卡诺图的算法，即适用于任意数量变量的卡诺图，但在本程序中仅为 26 个变量实现，与英文字母的数量相同。 

背景  

为了从本文中获益最多，读者应具备布尔代数和卡诺图使用的基础知识。

要使用此程序，您需要按照以下步骤操作

1. 输入卡诺图类型 (变量数量)
2. 输入 1 的位置 (-1 停止)
3. 输入无关紧要的位置 (-1 停止)
4. 选择结果类型 (SOP 或 POS)
5. 获取卡诺图的解决方案 

算法 

该算法有 3 个步骤。每个步骤都使用一个特殊的类来实现： 

1. 通过从用户那里获取信息（类型、1 的位置和无关紧要的位置）来设置卡诺图，并保存 1 和无关紧要的位置及其二进制值。 
2. 比较 1 和无关紧要的位置以获得所有可能的最小项。
3. 过滤比较结果以消除非必需项，选取必需项并提供所有可能的解决方案。 

第 1 步 

在这一步中，卡诺图的类型由用户输入（1 的位置和无关紧要的位置）。然后将其转换为等效的二进制值，即根据卡诺图类型进行二进制表示。然后将其保存在向量中。因此，如果我们有一个 4 变量卡诺图，其 1 的位置是 0,1,3,4 和 11，无关紧要的位置是 5，这将导致： 

• 类型将是：4 
• 1 的位置将保存为：0000 , 0001, 0011, 0100 和 1011
• 无关紧要的位置将保存为：0101

第 2 步 

在这一步中，1 和无关紧要的项将按其等效的二进制值逐一进行比较

1. 如果两个二进制值在类型 - 1 位匹配，则保存此值并将不同条件视为 -1。 
2. 将所有这些半匹配值视为虚线值。
3. 以类型次数的次数执行此过程，如果我们有一个 n 变量卡诺图且该卡诺图是满的，我们需要进行 n 次比较，以便在每个圆中将 1 个变量视为 -1，最后用一个满的卡诺图解决此卡诺图。 

因此，如果我们遵循第一步示例中的方法，处理的数据将是： 

•  开始：            0000, 0001, 0011, 0100, 0101 和 1011  
•  第一个圆：         000(-1), 0(-1)00, 00(-1)1,0(-1)01,(-1)011 和 010(-1) 
•  第二个圆：     0(-1)0(-1), 0(-1)0(-1), 00(-1)1 和 (-1)011  
•   第三个圆：       0(-1)0(-1), 0(-1)0(-1), 00(-1)1 和 (-1)011    
•  最后一个圆：          0(-1)0(-1), 0(-1)0(-1), 00(-1)1 和 (-1)011      

比较后，删除重复项以确保后续过程的简便性。因此，然后处理的数据是：0(-1)0(-1), 00(-1)1 和 (-1)011。 

删除后，二进制项根据以下说明转换为等效的字母：    

1. 这些数字项用等于其类型值的字母表示，从 A 开始，然后是 B, C... 等。 
2. 从左边的第一位代表 A，第二位代表 B，第三位代表 C... 等。
3. 如果数字等于 0，其等效字母将是虚线。如果等于 1，则不会是虚线，如果等于 (-1)，则将被跳过。 

因此，最后的二进制值将由以下方式表示：A'C', A'B'D 和 B'CD。

注意：如果一个项的所有最小项都为 -1，这意味着一个完整的图，其解为 1；如果没有 1，则意味着一个空图，其解为 0。在这些情况下，将跳过下一步（过滤）。

步骤 3

在这一步中，来自比较的结果被过滤，因为这些结果并非都是必需的。并尝试使用以下说明找到所有可能的解决方案

1. 计算所有项的最小项数，并确定最大项的最小项数。
2. 将所有较小子项的最小项视为必需项。
3. 将必需项与其他项进行组合并进行检查。如果它们接受卡诺图，则保存它们，否则不保存它们，直到保存所有卡诺图的可能解决方案为止。

注意：所有可能的解决方案都应具有相同的项数。

实现

步骤 1

在第 1 步中，使用了 setKmap 类。此类通过从用户那里获取信息（类型、1 的位置和无关紧要的位置）来设置卡诺图，并以如下方式保存 1 和无关紧要的位置及其二进制值：

1. guidewin 方法通过演示其处理步骤来指导用户使用该程序。
2. readInt 方法是用于读取整数值和 -1（如果需要）并防止不必要输入的函数。
3. getPos 方法是使用 readInt 方法读取 1 和无关紧要的位置的函数。
4. setTerms 方法是保存 1 和无关紧要的位置及其二进制等效值的函数。

//this class is used for prompting k-map details from user
//and setting k-map in order to solveing itclass setKmap 
{ 
protected: 
		int	type,	            //k-map type 2,3, ....
			termCount,          //term's count
			saverCount;			//saving savers
		vector<int>ones;          //Saving ones position
 		vector<int>dCare;        //Saving dont care position
		bool hasEnteredType,      //check entering type of not
			SOP;			      // ture for some of product
		                          // false for product of some
	void guideWin (short cursor);
	int readInt (int &count, bool negative ); 
	void getPos (vector<int> &pos, string name);
	void setTerms (vector<int> ones, vector<vector<int> > &terms);  
	
	setKmap(): hasEnteredType(false) {}
};//end kmap 

第二步

在这一步中，使用了 CompareKmapTerms 类。此类继承了 setKmap 类，以比较 1 的位置和无关紧要的位置，从而获得所有可能的最小化，例如：

1. Minimize 方法是通过以下方式执行比较的方法：
   • 使用 setTerms 方法将卡诺图中的 1 的位置设置为值。
   • 使用 setTerms 方法将卡诺图中的无关紧要的位置设置为值。
   • 使用 compare 方法成对比较所有项。
   • 使用 unrepeat 方法删除重复的项。
   • 使用 posToTerm 方法将二进制项转换为字母符号。
2. compare 方法逐一比较所有项，如果两个项在数字上匹配且等于类型值 - 1，则使用 saveValue 方法保存它们，并将不同的数字视为 -1，并将此项视为虚线项。
3. saveValue 是 compare 方法之后保存半匹配项的方法。
4. addOther 是保存未被虚线化的项的方法。
5. unRepeat 是保存后删除重复项的方法。
6. posToTerm 是将二进制项转换为字母项的方法。

//This class is used to compare inputs results and provides
// minmizing terms in order to filter them and get results
class   CompareKmapTerms : public setKmap 
{
protected:
		int	temp, temp1, temp2, temp3; //temperature variables
		int resultTerms;
	vector<char> minimize (vector<int> &ones, vector<int> &dCare);
	void compare (vector < vector< int >> &terms); // comparelify
	void saveValue(vector<int> &tempSave, vector<vector<int>> 
	&saver, vector<bool> &hascompare, vector<vector<int>> &terms);
	void addOther (vector<vector<int>> &saver,vector<bool> 
	&hascompare, int &saverCount, vector<vector<int>> &terms);
	void unRepeat (vector<vector<int> > &terms);
	vector<char> posToTerm(vector<vector<int>> 
	&terms); //convert position to its terms
		
};//end kmap 

步骤 3

在这一步中，使用了 FilterKmapTerms 类。此类继承了 CompareKmapTerms、ConverteTerms 和 Combination 类，以过滤比较结果，防止非必需项，获取必需项并提供所有可能的解决方案，例如：

1. getTerm 是可以从包含某些项的字符数组中读取一个项的函数。
2. getMintermCount 是可以计算一个项的最小项数的函数。
3. getLargestTermSize 是可以确定具有最小项数的最大项的函数。
4. checkResult 是检查某个结果是否覆盖了所有 1 的方法的函数。
5. getFilterResult 是将非必需项进行组合并添加到必需项的方法。然后它使用 checkResult 方法检查此结果，例如，如果此结果覆盖了所有 1，它将保存它，直到获得所有可能的解决方案。
6. Filter 是组织此类处理的方法，方法是：
   • 使用 getLargestTermSize 方法确定最小项中的最大项。
   • 与项的最小项数进行比较，确定必需项和非必需项。
   • 将非必需项进行组合并将其添加到必需项中以创建结果。
   • 使用 chechResult 方法检查某个结果，以确定此结果是否覆盖了所有 1，如果覆盖了，则保存此结果。

//this class is used for filtering results and giving
//all possible results
class FilterKmapTerms : public CompareKmapTerms, public ConverteTerms, public Combination
{
protected:
	int	temp, temp1, temp2, temp3; //temperature variables
	vector<char> getTerm (vector<char> 
	&result, int pos); //getting a term form an array
	int getMintermCount(vector<char> &term);
	int getLargestTermSize(vector<char> &result);
	bool checkResult (vector<char> someResult, vector<int> ones );	
vector <vector<char>> getFilterResult(vector<vector 
< char>> &results, vector<char> &essentialTerms);	
	vector <vector<char>> filter 
	(vector<char> &result, vector<int> ones);	
};//end filterKmapTerms 

最后，打印结果。

关注点

1. 此代码处理所有类型的卡诺图，即任意数量的变量，这是最新的（26 个变量，与英文字母的数量相同）。
2. 此代码在工作上依赖于向量模板，因此与依赖数组的代码相比，它节省了内存，因为向量是内置的。
3. 它可以处理大多数不规则情况（如果不是全部的话）。

参考

• 数字设计第 4 版，作者 M. Morris Mano 和 Michael D. Ciletti