به نقل از mazoolagh :
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
static int num;
/* This forms a linked list of nodes. Yummy. */
struct imp {
int value; /* Algorithm relies on value having 0-bit where mask is zero */
int mask; /* 0 where the value does not matter */
int used; /* This is marked true when an implicant is combined with another */
struct imp *next; /* This points to the next implicant in the linked list */
};
static void printImp(struct imp *imp);
static int countBits(int n);
static int numVars(int X[]);
static void addImp(struct imp *imp, int value, int mask);
static void mungeList(struct imp **imp_list, struct imp **imp_list2, int i);
static void erase_list(struct imp *imp_list);
static void printHeader();
static int is_one_bit(const int n);
int PI(int X[]) {
int i,j;
struct imp **imp_list;
struct imp **imp_list2; // Used for temp list of combined implicants
struct imp needed_imps; // Final list of implicants in compiled into here.
struct imp *i1; // Used as an iterator in various places.
struct imp **i2; // Used as an iterator in various places.
printHeader();
if(X[0] == 0) {
printf("0\n");
return 0;
}
num = numVars(X);
/* Initialize the imp_lists */
imp_list = (struct imp**)malloc(sizeof(void*)*(num+1));
imp_list2 = (struct imp**)malloc(sizeof(void*)*(num+1));
for(i=0;i<num+1;i++) {
imp_list[i] = (struct imp*)malloc(sizeof(struct imp));
imp_list2[i] = (struct imp*)malloc(sizeof(struct imp));
}
needed_imps.next = NULL;
for(i=0;i<=num;i++) {
i1 = imp_list[i];
i1->value = 0xBEEF;
i1->next = NULL;
i1 = imp_list2[i];
i1->value = 0xBEEF;
i1->next = NULL;
}
/* Sort implicants into linked lists based on the number of one-bits
in the binary representation of their value */
for(i=1;i<=X[0];i++) {
addImp(imp_list[countBits(X[i])], X[i], -1);
}
/***************************************************************************/
/* Loop over the different numbers of zero bits in the masks */
for(j=0;j<=num;j++) { /* num+1 times since we have to take in account if all of the cells are true. */
/* Combine all of the terms into a second set of lists */
for(i=0;i<num;i++)
mungeList(imp_list, imp_list2, i);
/* Look for the items that were not used and add them to needed_imps */
for(i=0;i<=num;i++) {
for(i1 = imp_list[i]->next; i1; i1 = i1->next) {
if (!(i1->used)) {
addImp(&needed_imps, i1->value, i1->mask);
}
}
}
/* Remove the old list1 */
for(i=0;i<=num;i++)
erase_list(imp_list[i]);
/* swap the two lists */
i2 = imp_list;
imp_list = imp_list2;
imp_list2 = i2;
} /* . . . . rinse and repeat. */
/***************************************************************************/
j=0;
for(i1 = needed_imps.next; i1; i1 = i1->next) {
printImp(i1);
printf("\n");
j++;
}
// Free all of the dynamicly allocated memory
for(i=0;i<=num;i++)
erase_list(imp_list[i]);
for(i=0;i<=num;i++)
erase_list(imp_list2[i]);
erase_list(&needed_imps);
free(imp_list);
free(imp_list2);
return j;
}
/* If an implicant with value and mask is in imp, this function will
return 1. Otherwise, it returns 0. */
static int search(struct imp *imp, const int value, const int mask) {
while((imp = imp->next))
if (imp->value == value && imp->mask == mask)
return 1;
return 0;
}
/* This prints out an implicant to stdout */
static void printImp(struct imp *imp) {
int i;
int outs=0;
for(i=num-1;i>=0;i--)
if ((imp->mask & (1<<i))) {
if(imp->value & (1<<i))
printf("%c",num-i+'a'-1);
else
printf("%c'",num-i+'a'-1);
outs++;
}
if (outs==0)
printf("1");
}
/* This frees all the nodes in a list (except for the head node )*/
static void erase_list(struct imp *imp_list) {
struct imp *i;
while(imp_list->next) {
i = imp_list->next->next;
free(imp_list->next);
imp_list->next = i;
}
}
/* This attempts to combine terms of imp_list[i] and imp_list[i+1] and
stores the combined terms in imp_list2[num_bits(combined term)] */
static void mungeList(struct imp **imp_list, struct imp **imp_list2, int i) {
int d;
struct imp *i1, *i2;
for(i1 = imp_list[i]->next; i1; i1 = i1->next) {
for(i2 = imp_list[i+1]->next;i2; i2 = i2->next) {
d = i1->value ^ i2->value;
if ((i1->mask == i2->mask)
&& (is_one_bit(d))) {
i1->used = 1;
i2->used = 1;
addImp(imp_list2[i],i1->value,i1->mask-d);
}
}
}
}
/* Prepends an implicant to a implicant list that has a specified
value and mask only if it has not already been added. */
static void addImp(struct imp *imp, int value, int mask) {
struct imp *new_imp;
if (!search(imp,value,mask)) {
new_imp= (struct imp*)malloc(sizeof(struct imp));
new_imp->value = value;
new_imp->mask = mask;
new_imp->next = imp->next;
new_imp->used = 0;
imp->next = new_imp;
}
}
/* Returns 1 is argument contains only one true bit */
static int is_one_bit(int n) {
if(n==0)
return 0;
if(n==1)
return 1;
while (((n >>=1) &1)==0)
;
if(n==1)
return 1;
return 0;
}
/* Returns the number of 1 bits in a number */
static int countBits(int n) {
int total=0;
while(n) {
total += n & 1;
n >>=1;
}
return total;
}
/* Returns the number of variables needed to represent the maximum
term of X */
static int numVars(int X[]) {
int i;
int max = 0;
int num=1;
for(i=1;i<=X[0];i++)
if(X[i]>max)
max = X[i];
while(max/=2)
num++;
return num;
}
static void printHeader() {
printf("Nathan Conrad\n");
printf("ITCS2181 Programming assignment 1\n");
printf("Due 3/27/03, 10pm\n");
}#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main(void)
{ int b[200][200],c[200][200],n,*m,*ones,*primes,i,j,k,e,f,t;
int a1,b1,index,min = 0,order=0,cnt=0;
char cr;
/* comment : allocating memory space for variables */
printf(" Ain Shams University Faculty of Engineering \n");
printf(" Year : 2nd Year of Computer and Systems Eng. \n");
printf(" Student Name : Mahmoud Reda Hussien Seireg \n");
printf(" Section : 4 \n");
printf(" Bench No. : 23777 \n");
printf("\n enter # of variables in boolean expr. : ");
scanf("%d",&n);
if (n<=0) { printf(" error : not valid no. of variables \n"); goto end; }
m=(int *)calloc(n,sizeof(int));
ones=(int *)calloc(n,sizeof(int));
primes=(int *)calloc(n,sizeof(int));
/* comment : receiving minterms */
printf("\n enter minterms seperated by space");
printf("\n note : enter last minterm -1");
printf("\n for example F(x1,x2,x3)=(0,1,2,7) is entered as ");
printf("\n 0 1 2 7 -1 ");
printf("\n enter data : ");
for (i=0;i<pow(2,n);++i)
{ scanf("%d",&m[i]);
if (m[i]==-1)
break;
if ((m[i]>=pow(2,n)) || (m[i]<0))
{
printf("\n error : %d not a valid minterm.\n",m[i]);
printf(" please re-run the program \n ");
goto end;
}
/* comment : obtaining binary representation of minterm */
for (j=n-1;j>=0;--j)
{ b[i][j]=((m[i]%2)==1); m[i]/=2; }
}
/* comment : printing binary value of each minterm of the function */
printf("\n\n Displaying minterm's binary values of entered function\n");
for (k=0;k<i;++k)
{ printf(" | ");
for (j=0;j<n;++j)
printf("%d",b[k][j]);
}
printf("\n press enter to continue ");
cr=getchar();
cr=getchar();
/* comment : diplaying the function before simplification */
printf("\n\n Displaying the function before simplification : ");
printf(" \n F(");
for (k=1;k<=n;++k)
printf("x%d%s",k,(k!=n)?",":")");
printf("=");
for (k=0;k<i;++k)
{ for (j=0;j<n;++j)
if (b[k][j]==0)
printf("x%d'",j+1);
else if (b[k][j]==1)
printf("x%d",j+1);
printf("%s",(k==i-1)?".\n":" + ");
}
printf("\n press enter to continue ");
cr=getchar();
/* comment : counting ones in each minterm */
for (k=0;k<i;++k)
primes[k]=0;
for (f=0;f<i;++f)
{
for (k=0;k<i;++k)
{ ones[k]=0; primes[k]=0;}
for (k=0;k<i;++k)
for (j=0;j<n;++j)
ones[k]+=(b[k][j]==1);
/* comment : sorting and simplyfing min no. of ones with those
of next level of ones. */
min=ones[0];
for (k=0;k<i;++k)
min=(ones[k]<=min)?ones[k]:min;
for (e=0;e<i;++e)
for (k=0;k<i;++k)
if (ones[k]==min+e)
for (j=0;j<i;++j)
{ if (j==k) continue;
if (ones[j]==min+e+1)
{ for (a1=0;a1<n;a1++)
if (b[k][a1]==b[j][a1])
++cnt;
else
index=a1;
if (cnt==n-1)
{ primes[k]=1;
primes[j]=1;
for (b1=0;b1<n;b1++)
if (b1==index)
c[order][b1]='-';
else
c[order][b1]=b[k][b1];
++order;
}
}
cnt=0;
}
for (k=0;k<order;k++)
for (j=0;j<n;j++)
b[k][j]=c[k][j];
}
t=0;
for (k=0;k<order;++k)
if (primes[k]==0)
{ for (j=0;j<n;++j)
c[t][j]=b[k][j];
++t;
}
/* comment : printing binary value of simplified minterms */
printf("\n Displaying the binary value of the functions prime implicants \n");
for (k=0;k<t;++k)
{ printf(" \n");
for (j=0;j<n;++j)
if (c[k][j]==45)
printf("%c",c[k][j]);
else
printf("%d",c[k][j]);
}
printf("\n press enter to continue ");
cr=getchar();
/* comment : diplaying the function after simplification */
printf("\n Displaying the function after simplification : ");
printf(" \n F(");
for (k=1;k<=n;++k)
printf("x%d%s",k,(k!=n)?",":")");
printf("=");
for (k=0;k<=t;++k)
{ for (j=0;j<n;++j)
if (c[k][j]==0)
printf("x%d'",j+1);
else if (c[k][j]==1)
printf("x%d",j+1);
printf("%s",(k==t)?".\n":" + ");
}
putchar('\n');
end:
printf("\n press enter to exit the program ");
cr=getchar();
return 0;
}به نقل از littlerabbit :
به نقل از mazoolagh :