离散数学anyview答案.doc

1.00 试设计一算法，判断元素与集合之间的关系。Boolean IsInSet(SetElem elem, pSet pA) /Add your code here SetElem *pAElems; for(pAElems=outToBuffer(pA);*pAElems!=n;pAElems+) if(elem=*pAElems) return true; return false;1.01 试设计一算法，实现集合的并运算。pSet SetUnion(pSet pA, pSet pB) pSet pS; pS=createNullSet(); SetElem *pBElems; SetElem *pAElems; for(pAElems=outToBuffer(pA);*pAElems!=n;pAElems+) directInsertSetElem(pS,*pAElems); for(pBElems=outToBuffer(pB);*pBElems!=n;pBElems+) if(!isInSet(pA,*pBElems) directInsertSetElem(pS,*pBElems); return pS;1.02 试设计一算法，实现集合的交运算。pSet SetIntersection(pSet pA, pSet pB) pSet pS; pS=createNullSet(); SetElem *pBElems; for(pBElems=outToBuffer(pB);*pBElems!=n;pBElems+) if(isInSet(pA,*pBElems) directInsertSetElem(pS,*pBElems); return pS;1.03 试设计一算法，实现集合的差运算。pSet SetSubtraction(pSet pA, pSet pB) pSet pS; pS=createNullSet(); SetElem *pAElems; for(pAElems=outToBuffer(pA);*pAElems!=n;pAElems+) if(!isInSet(pB,*pAElems) directInsertSetElem(pS,*pAElems); return pS;1.04 试设计一算法，实现集合的求补集运算。pSet SetComplement(pSet pA, pSet pI) pSet pS; pS=createNullSet(); SetElem *pAElems; SetElem *pIElems; for(pAElems=outToBuffer(pA);*pAElems!=n;pAElems+)/PA不是PI的子集的情况判断 if(!isInSet(pI,*pAElems) return NULL;break; for(pIElems=outToBuffer(pI);*pIElems!=n;pIElems+) if(!(isInSet(pA,*pIElems) directInsertSetElem(pS,*pIElems); return pS;1.05 试设计一算法，实现集合的对称差运算。pSet SetSysmmetricDifference(pSet pA, pSet pB) /Add your code here pSet pS; pS=createNullSet(); SetElem *pAElems; SetElem *pBElems; for(pAElems=outToBuffer(pA);*pAElems!=n;pAElems+) if(!isInSet(pB,*pAElems) directInsertSetElem(pS,*pAElems); for(pBElems=outToBuffer(pB);*pBElems!=n;pBElems+) if(!isInSet(pA,*pBElems) directInsertSetElem(pS,*pBElems); return pS;1.05 试设计一算法，判断两个集合之间的包含关系。SetRelationshipStatus SetRelationship(pSet pA, pSet pB) /Add your code here pSet pS; pS=createNullSet(); SetElem *pAElems; SetElem *pBElems; pAElems=outToBuffer(pA); pBElems=outToBuffer(pB); pS=pB;/假定pS为pB的相等集合 if(isNullSet(pA)&!isNullSet(pB)/pA为空集，pB不为空集时 return REALINCLUDED; if(!isNullSet(pA)&isNullSet(pB)/pB为空集，pA不为空集时 return REALINCLUDING; if(isNullSet(pA)&isNullSet(pB)/pA,PB都为空集时 return EQUAL; if(!isNullSet(pA)&!isNullSet(pB)/pA,PB都不为空集时 while(*pAElems!=n) if(isInSet(pS,*pAElems) pAElems+; else while(*pBElems!=n) if(isInSet(pA,*pBElems) pBElems+; else return NOT_INCLUSIVE;/若集合pB中有一个元素不属于pB if(*pBElems=n) return REALINCLUDING;/若集合pB中的所有元素已遍历完 if(*pAElems=n) while(*pBElems!=n) if(isInSet(pA,*pBElems) pBElems+; else return REALINCLUDED;/若集合pB中有一个元素不属于pA if(*pBElems=n)/若集合pB元素已遍历完 return EQUAL; 1.07 试设计一个非递归算法，实现集合的求幂集运算。pSet miji(pSet pB,pSet pC) SetElem *pBElems; SetElem *pCElems; pSet pS; pS=createNullSet(); for(pBElems=outToBuffer(pB);*pBElems!=n;pBElems+) directInsertSetElem(pS,*pBElems); for(pCElems=outToBuffer(pC);*pCElems!=n;pCElems+) if(!isInSet(pB,*pCElems) directInsertSetElem(pS,*pCElems); return pS; pFamilyOfSet PowerSet(pSet pA) /Add your code here int i; pSet pI=createNullSet(); pFamilyOfSet pF=createNullFamilyOfSet(); SetElem *pAElems=outToBuffer(pA); insertToFamilyOfSet(pF,pI); if(!isNullSet(pA)/pA不为空集时 while(*pAElems!=n) pSet pK=createNullSet(); directInsertSetElem(pK,*pAElems); pSet *pS=outFamilyOfSetToBuffer(pF); for(i=0;*(pS+i)!=NULL;i+) insertToFamilyOfSet(pF,miji(pK,*(pS+i); pAElems+; return pF;1.08 试设计一个递归算法，实现集合的求幂集运算。void myFunction(long k, SetElem *pAElems,pFamilyOfSet pFamSetA,pSet pB) long i=k,j=0; pB=createNullSet(); while(*(pAElems+j)!=n) if(i%2=1) /表示二进制最后一位是1 directInsertSetElem(pB,*(pAElems+j);/执行插入步骤 j+; i=1; insertToFamilyOfSet(pFamSetA,pB); /把集合加入到集族 k-;/插入一个集合到集族后，对应k的值（即剩下的未插入集族的个数）减去一 if(k=0) /2n-1个子集 myFunction(k,pAElems,pFamSetA,pB);pFamilyOfSet PowerSet(pSet pA) /Add your code here pFamilyOfSet pFamSetA=createNullFamilyOfSet(); long i,k=1;/设置循环变量 i SetElem *pAElems=outToBuffer(pA); pSet pB=createNullSet(); for(i=0;*(pAElems+i)!=n;)/利用循环得出集合pA的个数 i+;/不可将i放到for语句中，否则当pA为空集时，i的值不为零 k=i;/k利用左移位运算表示集合pA集族的个数 k=2i myFunction(k,pAElems,pFamSetA,pB); return pFamSetA;3.01 试设计一个非递归算法，验证一个表达式是不是命题公式(statement formula)。Boolean IsStatementFormula(pStatementFormula pFormula) /Add your code here StatementFormulaSymbles preS,currS,nextS; int leftNum = 0,rightNum = 0; preS = getCurrentSymbleType(pFormula); switch(preS) case Exception:return false;/若取得了公式外的字符，则不是合法的命题公式 case Conjunction:return false; case Disjunction:return false; case Implication:return false; case Equivalence:return false; case LeftParenthesis:leftNum+;break;/若为左括号，则leftNum的值自增一 case RightParenthesis:return false; case EndOfFormula:return true;/若命题公式只有结束符号#，则为合法的命题公式 nextPos(pFormula);/指示器指向下一个字符 currS = getCurrentSymbleType(pFormula); switch(currS) case LeftParenthesis:leftNum+;break;/若为左括号，则leftNum的值自增一 case RightParenthesis:rightNum+;break;/若为有括号，则RightNum的值自增一 case PropositionalVariable: if(preS = PropositionalVariable)/当currS为命题变元时，若preS也为命题变元 return false; while (nextS != EndOfFormula) nextPos(pFormula); nextS = getCurrentSymbleType(pFormula); if(nextS = LeftParenthesis)/若为左括号，则leftNum的值自增一 leftNum+; if(nextS = RightParenthesis)/若为有括号，则RightNum的值自增一 rightNum+; if(preS = Exception|currS = Exception|nextS = Exception)/若读取到一个公式歪的字符，则为不合法的命题公式 return false; if(currS = PropositionalVariable)/若currS字符为命题变元 if(nextS = PropositionalVariable|preS = PropositionalVariable)/且nextS或者preS也为命题变元时，则为不合法的命题公式 return false; if(currS = Conjunction|currS = Disjunction|currS = Implication|currS = Equivalence)/若currS为联结词 if(preS != PropositionalVariable & preS != RightParenthesis) | (nextS != PropositionalVariable & nextS != LeftParenthesis & nextS != Negation)/前后字符既不为命题变元，也不相应为右，左括号 ，并且后一个字符不为否定号，则为不合法的命题公式 return false; if(nextS = Negation)/若nextS为否定号 if(currS = PropositionalVariable|currS = RightParenthesis)/且currS为命题变元或者右括号时 return false; preS = currS;/为下个字符的判断进行移位 currS = nextS; if(leftNum != rightNum)/若左右括号的数目不相等，则必定为不合法的命题公式 return false; return true;3.02 试设计一个递归算法，验证一个表达式是不是命题公式(statement formula)。Boolean Function(int leftNum,int rightNum,StatementFormulaSymbles preS,StatementFormulaSymbles currS,StatementFormulaSymbles nextS,pStatementFormula pFormula) nextPos(pFormula);/解释同上题所示 nextS = getCurrentSymbleType(pFormula); if(nextS = LeftParenthesis) leftNum+; if(nextS = RightParenthesis) rightNum+; if(preS = Exception|currS = Exception|nextS = Exception) return false; if(currS = PropositionalVariable) if(nextS = PropositionalVariable|preS = PropositionalVariable) return false; if(currS = Conjunction|currS = Disjunction|currS = Implication|currS = Equivalence) if(preS != PropositionalVariable & preS != RightParenthesis) | (nextS != PropositionalVariable & nextS != LeftParenthesis & nextS != Negation) return false; if(nextS = Negation) if(currS = PropositionalVariable|currS = RightParenthesis) return false; preS = currS; currS = nextS; if(nextS != EndOfFormula) return Function(leftNum,rightNum,preS,currS,nextS,pFormula); if(leftNum != rightNum) return false; return true;Boolean IsStatementFormula(pStatementFormula pFormula) /Add your code here StatementFormulaSymbles preS,currS,nextS; int leftNum = 0,rightNum = 0; preS = getCurrentSymbleType(pFormula); switch(preS) case Exception:return false;/若取得了公式外的字符，则不是合法的命题公式 case Conjunction:return false; case Disjunction:return false; case Implication:return false; case Equivalence:return false; case LeftParenthesis:leftNum+;break;/若为左括号，则leftNum的值自增一 case RightParenthesis:return false; case EndOfFormula:return true;/若命题公式只有结束符号#，则为合法的命题公式 nextPos(pFormula);/指示器指向下一个字符 currS = getCurrentSymbleType(pFormula); switch(currS) case LeftParenthesis:leftNum+;break;/若为左括号，则leftNum的值自增一 case RightParenthesis:rightNum+;break;/若为有括号，则RightNum的值自增一 case PropositionalVariable: if(preS = PropositionalVariable)/当currS为命题变元时，若preS也为命题变元 return false; return Function(leftNum,rightNum,preS,currS,nextS,pFormula); /返回值的真假，同时调用函数Function6.01 试设计一算法，实现集合的卡氏积运算。pCartersianSet CartesianProduct(pOriginalSet pA, pOriginalSet pB) pCartersianSet pC=createNullCartersianSet(); for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA) for(resetOriginalSet(pB);!isEndOfOriginalSet(pB);nextOriginalSetPos(pB) OrderedCoupleInsertToCartersianSet(pC,createOrderedCouple(getCurrentOriginalSetElem(pA),getCurrentOriginalSetElem(pB); return pC;6.02 试设计一算法，给定集合A、集合B和集合C，判断集合C是否为A到B的一个二元关系。boolean isBinaryRelation(pOriginalSet pA, pOriginalSet pB, pCartersianSet pC) pCartersianSet pD=createNullCartersianSet(); for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA) for(resetOriginalSet(pB);!isEndOfOriginalSet(pB);nextOriginalSetPos(pB) OrderedCoupleInsertToCartersianSet(pD,createOrderedCouple(getCurrentOriginalSetElem(pA),getCurrentOriginalSetElem(pB); for(getCurrentCartersianSetElem(pC);!isEndOfCartersianSet(pC);nextCartersianSetPos(pC) while(!isEndOfCartersianSet(pD) if(getCurrentCartersianSetElem(pD)=getCurrentCartersianSetElem(pC) nextCartersianSetPos(pD); else return false; if(isEndOfCartersianSet(pC) return true;6.03 试设计一算法，求集合A上的恒等关系。pCartersianSet IdentityRelation(pOriginalSet pSet) pCartersianSet pC=createNullCartersianSet(); for(resetOriginalSet(pSet);!isEndOfOriginalSet(pSet);nextOriginalSetPos(pSet) OrderedCoupleInsertToCartersianSet(pC,createOrderedCouple(getCurrentOriginalSetElem(pSet),getCurrentOriginalSetElem(pSet); return pC;6.04 试设计一算法，求两个卡氏积集合的复合运算。pCartersianSet CompositeOperation(pCartersianSet pA, pCartersianSet pB) pCartersianSet pC=createNullCartersianSet(); for(resetCartersianSet(pA);!isEndOfCartersianSet(pA);nextCartersianSetPos(pA) for(resetCartersianSet(pB);!isEndOfCartersianSet(pB);nextCartersianSetPos(pB) if(getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pA)=getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pB) OrderedCoupleInsertToCartersianSet(pC,createOrderedCouple(getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pA),getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pB); return pC;6.05 试设计一算法，求一个关系的逆运算。pCartersianSet InverseOperation(pCartersianSet pA) pCartersianSet pC=createNullCartersianSet(); for(resetCartersianSet(pA);!isEndOfCartersianSet(pA);nextCartersianSetPos(pA) OrderedCoupleInsertToCartersianSet(pC,createOrderedCouple(getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pA),getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pA); return pC;6.06 试设计一算法，对某集合A上的一个二元关系，求该关系的幂运算。pCartersianSet PowOperation(pOriginalSet pA, pCartersianSet pBinaryRelationR, int n) pCartersianSet pC=createNullCartersianSet(); pC=copyCartersianSet(pBinaryRelationR); if(n=0) for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA) OrderedCoupleInsertToCartersianSet(pC,createOrderedCouple(getCurrentOriginalSetElem(pA),getCurrentOriginalSetElem(pA); if(n=1)return pC; pCartersianSet pD=createNullCartersianSet(); int i; for(i=2;i=n;i+) pD=copyCartersianSet(pC); pC=compositeOperation(pD,pBinaryRelationR); return pC;6.07 试设计一算法，对某集合A上的一个二元关系R，判断R是否具有自反性。boolean IsReflexivity(pOriginalSet pA, pCartersianSet pBinaryRelationR) pCartersianSet pC=createNullCartersianSet(); pC=copyCartersianSet(pBinaryRelationR); if(isNullOriginalSet(pA) return true; else for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);) if(isInCartersianSet(pC,createOrderedCouple(getCurrentOriginalSetElem(pA),getCurrentOriginalSetElem(pA) nextOriginalSetPos(pA); else break; if(isEndOfOriginalSet(pA) return true; else return false;6.08 试设计一算法，对某集合A上的一个二元关系R，判断R是否具有反自反性。boolean IsAntiReflexivity(pOriginalSet pA, pCartersianSet pBinaryRelationR) pCartersianSet pC=createNullCartersianSet(); pC=copyCartersianSet(pBinaryRelationR); if(isNullOriginalSet(pA) return true; else for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);) if(!isInCartersianSet(pC,createOrderedCouple(getCurrentOriginalSetElem(pA),getCurrentOriginalSetElem(pA) nextOriginalSetPos(pA); else break; if(isEndOfOriginalSet(pA) return true; else return false;6.09 试设计一算法，对某集合A上的一个二元关系R，判断R是否具有自反性或者反自反性。Reflexivity_Type DetermineReflexivity(pOriginalSet pA, pCartersianSet pBinaryRelationR) pCartersianSet pC=createNullCartersianSet(); pC=copyCartersianSet(pBinaryRelationR); if(isNullOriginalSet(pA)/空集既有自反性又有反自反性 return REFLEXIVITY_AND_ANTI_REFLEXIVITY; else for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);) if(isInCartersianSet(pC,createOrderedCouple(getCurrentOriginalSetElem(pA),getCurrentOriginalSetElem(pA) nextOriginalSetPos(pA); else break; if(isEndOfOriginalSet(pA) return REFLEXIVITY; else for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);) if(!isInCartersianSet(pC,createOrderedCouple(getCurrentOriginalSetElem(pA),getCurrentOriginalSetElem(pA) nextOriginalSetPos(pA); else break; if(isEndOfOriginalSet(pA) return ANTI_REFLEXIVITY; else return NOT_REFLEXIVITY_AND_NOT_ANTI_REFLEXIVITY;6.10 试设计一算法，对某集合A上的一个二元关系R，判断R是否具有对称性或者反对称性。boolean IsSymmetry(pCartersianSet pA)/判断是否具有对称性 if(!isNullCartersianSet(pA) for(resetCartersianSet(pA);!isEndOfCartersianSet(pA);nextCartersianSetPos(pA) pOrderedCouple pCouple = createOrderedCouple( getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pA), getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pA); if(!isInCartersianSet(pA,pCouple) return false; return true;boolean IsAntiSymmetry(pCartersianSet pA)/判断是否具有反自反性 if(!isNullCartersianSet(pA) for(resetCartersianSet(pA);!isEndOfCartersianSet(pA);nextCartersianSetPos(pA) pOriginalSetElem pFirstElem = getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pA); pOriginalSetElem pSecondElem = getSecondElemOfOr