广工Anyview离散数学第六章

发布于：2025-02-10 ⋅ 阅读:(24) ⋅ 点赞:(0)

注：网络资源整理，并非本人代码，离散数学对初学者比较抽象，希望对你有所帮助。请注意对应题目，每年题目可能有小变动。

目录

试设计一算法，实现集合的卡氏积运算

试设计一算法，给定集合A、集合B和集合C，判断集合C是否为A到B的一个二元关系

试设计一算法，求集合A上的恒等关系

试设计一算法，求两个卡氏积集合的复合运算

试设计一算法，求一个关系的逆运算

试设计一算法，对某集合A上的一个二元关系，求该关系的幂运算

试设计一算法，对某集合A上的一个二元关系R，判断R是否具有自反性

试设计一算法，对某集合A上的一个二元关系R，判断R是否具有反自反性

试设计一算法，对某集合A上的一个二元关系R，判断R是否具有自反性或者反自反性

试设计一算法，对某集合A上的一个二元关系R，判断R是否具有对称性或者反对称性

试设计一算法，对某集合A上的一个二元关系R，判断R是否具有传递性

试设计一算法，对某集合A上的一个二元关系R，求R的自反闭包

试设计一算法，对某集合A上的一个二元关系R，求R的对称闭包在实际计算中，无需给出集合A

试设计一算法，对某集合A上的一个二元关系R，求R的传递闭包

实现Warshall算法，求某关系的传递闭包

试设计一算法，实现集合的卡氏积运算

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;

}

试设计一算法，给定集合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;

}

试设计一算法，求集合A上的恒等关系

pCartersianSet IdentityRelation(pOriginalSet pSet)

{

    pCartersianSet pC=createNullCartersianSet();

    for(resetOriginalSet(pSet);!isEndOfOriginalSet(pSet);nextOriginalSetPos(pSet))  

        OrderedCoupleInsertToCartersianSet(pC,createOrderedCouple(getCurrentOriginalSetElem(pSet),getCurrentOriginalSetElem(pSet)));    

    return pC;

}

试设计一算法，求两个卡氏积集合的复合运算

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;

}

试设计一算法，求一个关系的逆运算

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;

}

试设计一算法，对某集合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;

}

试设计一算法，对某集合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;

}

试设计一算法，对某集合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;

}

试设计一算法，对某集合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;

}

试设计一算法，对某集合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 = getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pA));

                    if(!isEqualOriginalSetElem(pFirstElem,pSecondElem))

                        {

                            pOrderedCouple pCouple = createOrderedCouple(pSecondElem,pFirstElem);           

                            if(isInCartersianSet(pA,pCouple))

                                return false;           

                        }

                }

        }

    return true;

}



Symmetry_Type DetermineSymmetry(pCartersianSet pBinaryRelationR)

{

    if(IsSymmetry(pBinaryRelationR))       

            if(IsAntiSymmetry(pBinaryRelationR))

                return SYMMETRY_AND_ANTI_SYMMETRY;

            else

                return SYMMETRY;       

    else

        if(IsAntiSymmetry(pBinaryRelationR))

            return ANTI_SYMMETRY;

        else

            return NOT_SYMMETRY_AND_NOT_ANTI_SYMMETRY;    

}

试设计一算法，对某集合A上的一个二元关系R，判断R是否具有传递性

boolean IsTransitive(pOriginalSet pA, pCartersianSet pBinaryRelationR)
{
    pCartersianSet pR = createNullCartersianSet();
    if(!isNullCartersianSet(pBinaryRelationR))
        {
            for(resetCartersianSet(pBinaryRelationR);!isEndOfCartersianSet(pBinaryRelationR);nextCartersianSetPos(pBinaryRelationR))
                OrderedCoupleInsertToCartersianSet(pR,getCurrentCartersianSetElem(pBinaryRelationR));    
            for(resetCartersianSet(pBinaryRelationR);!isEndOfCartersianSet(pBinaryRelationR);nextCartersianSetPos(pBinaryRelationR))
                {
                    pOrderedCouple pC1 = getCurrentCartersianSetElem(pBinaryRelationR);
                    for(resetCartersianSet(pR);!isEndOfCartersianSet(pR);nextCartersianSetPos(pR))
                        {
                            pOrderedCouple pC2 = getCurrentCartersianSetElem(pR);
                            if(isEqualOriginalSetElem(getSecondElemOfOrderedCouple(pC1),getFirstElemOfOrderedCouple(pC2)))
                                if(!isInCartersianSet(pBinaryRelationR,createOrderedCouple(getFirstElemOfOrderedCouple(pC1),getSecondElemOfOrderedCouple(pC2))))
                                    return false;            
                        }
                }
        }
    return true;
}

试设计一算法，对某集合A上的一个二元关系R，求R的自反闭包

pCartersianSet ReflexiveClosure(pOriginalSet pA, pCartersianSet pBinaryRelationR)

{

    pCartersianSet pC=createNullCartersianSet();

    pC=copyCartersianSet(pBinaryRelationR);

    pCartersianSet pD=createNullCartersianSet();

    pD=copyCartersianSet(pBinaryRelationR);

    if(isNullCartersianSet(pC))//若卡式积集合为空集

        for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

            OrderedCoupleInsertToCartersianSet(pD,createOrderedCouple(getCurrentOriginalSetElem(pA),getCurrentOriginalSetElem(pA)));

    else  

        for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))        

           for(resetCartersianSet(pC);!isEndOfCartersianSet(pC); nextCartersianSetPos(pC))            

                if(!isInCartersianSet(pC,createOrderedCouple(getCurrentOriginalSetElem(pA),getCurrentOriginalSetElem(pA))))//若没有该序偶，则插入到pD集合中

                    OrderedCoupleInsertToCartersianSet(pD,createOrderedCouple(getCurrentOriginalSetElem(pA),getCurrentOriginalSetElem(pA)));                

    return pD;

}

试设计一算法，对某集合A上的一个二元关系R，求R的对称闭包在实际计算中，无需给出集合A

pCartersianSet SymmetricClosure(pCartersianSet pBinaryRelationR)

{

    pCartersianSet pC=createNullCartersianSet();             

    pC=copyCartersianSet(pBinaryRelationR);

    pCartersianSet pD=createNullCartersianSet();

    pD=copyCartersianSet(pBinaryRelationR);

    for(resetCartersianSet(pC);!isEndOfCartersianSet(pC); nextCartersianSetPos(pC))    

        if(!isInCartersianSet(pC,createOrderedCouple(getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pC)),getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pC)))))

            OrderedCoupleInsertToCartersianSet(pD,createOrderedCouple(getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pC)),getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pC))));     

    return pD;

}

试设计一算法，对某集合A上的一个二元关系R，求R的传递闭包

pCartersianSet TransitiveClosure(pOriginalSet pA, pCartersianSet pBinaryRelationR)

{

    pCartersianSet pC=createNullCartersianSet();             

    pC=copyCartersianSet(pBinaryRelationR);

    pCartersianSet pD=createNullCartersianSet();

    pD=copyCartersianSet(pBinaryRelationR);

    pCartersianSet pN=createNullCartersianSet();

    pN=copyCartersianSet(pBinaryRelationR);

    for(resetCartersianSet(pC);!isEndOfCartersianSet(pC);nextCartersianSetPos(pC))

        for(resetCartersianSet(pD);!isEndOfCartersianSet(pD);nextCartersianSetPos(pD))

            if(getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pC))==getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pD)))

                if(!isInCartersianSet(pC,createOrderedCouple(getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pC)),getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pD)))))

                    OrderedCoupleInsertToCartersianSet(pN,createOrderedCouple(getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pC)),getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pD))));

    return pN;

}

实现Warshall算法，求某关系的传递闭包

pMatrix Warshall(pMatrix pM)//矩阵为转置矩阵

{

    int n,i,j,k,m;

    n=getDim(pM);//获取矩阵维数

    pMatrixBase pBase;//定义缓冲区

    pBase=outToBuffer(pM);//输出矩阵中的元素到pBase

    for(m=0;m<2;m++)

        for(i=0;i<n;i++)

            for(j=0;j<n;j++)

                if(!converToInt(*(pBase+n*i+j)))//当序偶<i,j>不属于集合A，即pM对应矩阵元素为0

                    for(k=0;k<n;k++)                           

                        if(converToInt(*(pBase+n*i+k)))//若存在序偶<i,k>,<k,j>都为一，即都属于集合A时

                            if(converToInt(*(pBase+n*k+j)))

                                putValue(pBase+n*i+j,1);//则序偶<i，j>属于集合A，pM对应矩阵元素为1

    pM=createMatrix(pBase,n);//创建打印矩阵

    return pM;//返回传递包的关系矩阵

}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布