SCIP in C++11 ― 2.2.2節 その2

二進モービル：問題2.29

dについては、自分のC++11コードでは、

cons-cellと2要素のリストを区別していないので関係ない。

----

typedef int BranchLength;

typedef int BranchWeight;

typedef int Torque;

typedef List Branch;

typedef List Mobile;

// for binary mobile

const Mobile makeMobile

(const Branch& leftBranch, const Branch& rightBranch)

{return(makeList(leftBranch,rightBranch));}

// make single branch

const Branch makeBranch

(const BranchLength& length,const BranchWeight& structure)

{return(cons(length,structure));}

//make branch

const Branch makeBranch

(const BranchLength& length,const Mobile& structure)

{return(makeList(length,structure));}

const Branch leftBranch(const Mobile& mobile)

{return(car(mobile));}

const Branch rightBranch(const Mobile& mobile)

{return(cadr(mobile));}

const BranchLength branchLength(const Branch& branch)

{return(value<BranchLength>(car(branch)));}

const Mobile branchStructure(const Branch& branch)

{return(cadr(branch));}

const bool isLeaf(const Mobile& mobile)

{return(!mobile->isList());}

const bool isSingleMobile(const Mobile& mobile)

{return(isLeaf(branchStructure(leftBranch(mobile)))

        && isLeaf(branchStructure(rightBranch(mobile))));}

const BranchWeight leafWeight(const Mobile& mobile)

{return(value<BranchWeight>(mobile));}

//---------abstraction barrier---------

// totalWeight

const BranchWeight totalWeight(const Mobile& mobile)

{

    if(isLeaf(mobile)){return(leafWeight(mobile));}

    return(totalWeight(branchStructure(leftBranch(mobile)))

           +totalWeight(branchStructure(rightBranch(mobile))));

}

//balanced?

const Torque torque(const Branch& branch)

{

    return(branchLength(branch)

           *totalWeight(branchStructure(branch)));

}

const bool isBalanced(const Mobile& mobile)

{

    if(isLeaf(mobile)){return(true);}

    if(isSingleMobile(mobile)){

        return(torque(leftBranch(mobile))

               ==torque(rightBranch(mobile)));

    }

    return(isBalanced(branchStructure(leftBranch(mobile)))

           && isBalanced(branchStructure(rightBranch(mobile)))

           && torque(leftBranch(mobile))

           ==torque(rightBranch(mobile)));

}

int main(int argc, char** argv)

{

    const auto branch1(makeBranch(1,2));

    const auto branch2(makeBranch(1,2));

    const auto mobile1(makeMobile(branch1,branch2));

    const auto branch3(makeBranch(1,mobile1));

    const auto mobile2(makeMobile(branch1,branch3));

   

    cout<<"mobile1 = "<<listString(mobile1)<<endl;

    cout<<"(total-weight mobile1) = "<<totalWeight(mobile1)<<endl;

    cout<<"(balanced? mobile1) = "<<isBalanced(mobile1)<<endl;

    cout<<endl;

    cout<<"mobile2 = "<<listString(mobile2)<<endl;

    cout<<"(total-weight mobile2) = "<<totalWeight(mobile2)<<endl;

    cout<<"(balanced? mobile2) = "<<isBalanced(mobile2)<<endl;

    return(0);

}

----

出力

----

mobile1 = ((1 2) (1 2))

(total-weight mobile1) = 4

(balanced? mobile1) = 1

mobile2 = ((1 2) (1 ((1 2) (1 2))))

(total-weight mobile2) = 6

(balanced? mobile2) = 0