7.5.STUDY INDESIGN:MAXOFTHREE 113
Thesecondquestiontoaskis theconverseofthefirst.Arewecertainthatthisconditionis trueinall
caseswherex1is themax?Unfortunately, ourconditiondoesnotmeetthistest.Supposethevaluesare5,
2,and4.Clearly,x1is thelargest,butourconditionreturnsfalsesincetherelationship 5 2 4 doesnot
hold.We needtofixthis.
We wanttoensurethatx1isthelargest,butwedon’t careabouttherelative orderingofx2andx3.
Whatwereallyneedis two separateteststodeterminethatx1 >= x2andthatx2 >= x3. Pythonallows
ustotestmultipleconditionslike thisbycombiningthemwiththekeywordand. We’ll discusstheexact
semanticsofandinChapter8.Intuitively, thefollowingconditionseemstobewhatwearelookingfor:
if x1 >= x2 and x1 >= x3: # x1 is greater than each of the others
max = x1
To completetheprogram,wejustneedtoimplementanalogoustestsfortheotherpossibilities.if x1 >= x2 and x1 >= x3:
max = x1
elif x2 >= x1 and x2 >= x3:
max = x2
else:
max = x3
Summingupthisapproach,ouralgorithmis basicallycheckingeachpossiblevalueagainstalltheothersto
determineif it is thelargest.
Withjustthreevaluestheresultis quitesimple.Buthow wouldthissolutionlookif weweretryingto find
themaxoffive values?ThenwewouldneedfourBooleanexpressions,eachconsistingoffourconditions
andedtogether. Thecomplex expressionsresultfromthefactthateachdecisionis designedtostandonits
own;informationfromonetestis ignoredinthefollowing.To seewhatI mean,lookbackat oursimplemax
ofthreecode. Supposethefirstdecisiondiscoversthatx1is greaterthanx2, butnotgreaterthanx3. At
thispoint,weknow thatx3mustbethemax.Unfortunately, ourcodeignoresthis;Pythonwillgoaheadand
evaluatethenextexpression,discoverit tobefalseandfinallyexecutetheelse.
7.5.2 Strategy2:DecisionTree
Onewaytoavoidtheredundanttestsofthepreviousalgorithmis touseadecisiontreeapproach.Suppose
westartwitha simpletestx1 x2. Thisknockseitherx1orx2outofcontentiontobethemax.If
theconditionis true,wejustneedtoseewhichislarger,x1orx3. Shouldtheinitialconditionbefalse,
theresultboilsdowntoa choicebetweenx2andx3. Asyoucansee,thefirstdecision“branches”intotwo
possibilities,eachofwhichis anotherdecision.Hencethename,decisiontree.Figure7.5showsthesituation
ina flowchart.Thisflowcharttranslateseasilyintonestedif-elsestatements.
if x1 >= x2:
if x1 >= x3:
max = x1
else:
max = x3
else:
if x2 >= x3:
max = x2
else:
max = x3
Thestrengthofthisapproachisitsefficiency. Nomatterwhattheorderingofthethreevalues,this
algorithmwillmake exactlytwo comparisonsandassignthecorrectvaluetomax. However, thestructureof
thisapproachis morecomplicatedthanthefirst,andit suffersa similarcomplexityexplosion,shouldwetry
thisdesignwithmorethanthreevalues.Asa challenge,youmightseeif youcandesigna decisiontreeto
findthemaxoffourvalues.(Youwillneedif-elses nestedthreelevelsdeepleadingtoeightassignment
statements.)