; TeX output 1996.06.26:0328y?TDtGGcmr17Algorithms3XQ cmr12PreterWilliamszPreter.Williams@dsto.defence.gov.au%ʭ7April1996+č>Nff cmbx12Contents>"V cmbx101MIn9troQduction1>2MTheT3MTheTalgorithmEn9vironment8M3.1dGeneralX................................8M3.2dOptionsFǍ................................9M3.3dCustomization............................10!č>ListffofAlgorithmsM1dCalculateUU b> cmmi10y"=x^ 0ercmmi7n ...........................8>1VLIntros3duction>This packqageprovidestwoenvironments,zalgorithmicandalgorithm,which >areђdesignedtobGeusedtogetherbutmaybeusedseparately*.EThealgorithmic>environment8providesanenvironmentfordescribingalgorithmsandthealgorithm1*y?>environment8providesa\ oat"wrappGerforalgorithms(implementedusing\palgorithmic >or someothermethoGdattheauthor'soption).Thereasonthattwo environ->mentsUUareprovidedistoallowtheauthormaximum exibility*.!č>2VLTheff߆Tff cmtt12algorithmicEnvironment>WithinanalgorithmicanumbGerofcommandsfortypesettingpopularalgo->rithmic|constructsareavqailable.)Ingeneral,ƨthecommandsprovidedcanbGe>arbitrarilyZ}nestedtodescribGequitecomplexalgorithms.>Anoptionalargument>tothe\begin{algorithmic}statementcanbGeusedtoturnonlinenumbGering>by DgivingapGositiveintegerindicatingtherequiredfrequencyoflinenumbGer->ing.F*orbexample,f \begin{algorithmic}[5]wouldcauseevery fthlinetobGe>numbGered.6>N cmbx122.1\TheSimpleStatementuT>TheUUsimplestatementtakestheform>\STATE?>andUUisusedforsimplestatements,e.g.>\begin{algorithmic} >\STATE?$S\leftarrow0$>\end{algorithmic}>wouldUUproGduce HSZ !", cmsy10 0>andUUwithlinenumbGeringUUselectedforeverylineusing>\begin{algorithmic}[1] >\STATE?$S\leftarrow0$>\end{algorithmic}>wouldUUproGduce Cc|{Ycmr81:NSZ 0>F*or,usersofearlierversionsofIalgorithmicthisconstructisacauseofan >incompatibility*.-xIntheearlierversion,insteadofstartingsimplestatements>withthe\STATEcommand,Ԓsimplestatementswereenteredasfreetextand>terminatedwith\\command.BTUnfortunately*,:thissimplermethoGdfailedto>surviveyZthemoGdi cationsnecessaryforstatementnumbGering.However,[the\\>commandUUcanstillbGeusedtoforcealinebreakwithinasimplestatement.6>2.2\TheF C cmbxti10if-then-elseConstructuT>TheUUif-then-elseconstructtakestheforms.2uy?>\IF{}?\ENDIF >\IF{}?\ELSE\ENDIF>\IF{}?\ELSIF{}\ELSE\ENDIF>InLSthethirdoftheseformsthereisnolimitplacedonthenumbGerLSof\ELSIF{}>thatUUmaybGeused.qF*orexample,>\begin{algorithmic}>\IF{some?conditionistrue}>\STATE?dosomeprocessing>\ELSIF{some?otherconditionistrue}>\STATE?dosomedifferentprocessing>\ELSIF{some?evenmorebizarreconditionismet}>\STATE?dosomethingelse>\ELSE>\STATE?dothedefaultactions>\ENDIF>\end{algorithmic}>wouldUUproGduce HiflpsomeUUconditionistruethenRdoUUsomeproGcessingHelseUUiflpsomeotherconditionistruethenRdoUUsomedi erentproGcessingHelseUUiflpsomeevenmorebizarreconditionismetthenRdoUUsomethingelseHelseRdoUUthedefaultactionsHendUUif>withUUappropriateindentations.č>2.3\TheforLo`opuT>TheUUforloGoptakestheforms.>\FOR{}?\ENDFOR>\FORALL{}?\ENDFOR>F*orUUexample,>\begin{algorithmic}>\FOR{$i=0$?to$10$}>\STATE?carryoutsomeprocessing>\ENDFOR>\end{algorithmic}>proGduces HforUUi=0to10do3!y?RcarryUUoutsomeproGcessing HendUUfor >andvJ>\begin{algorithmic}[1]>\FORALL{$i$?suchthat$0\leqi\leq10$}>\STATE?carryoutsomeprocessing>\ENDFOR>\end{algorithmic}>proGduces Cc1:NforTallUUisuchthat0i10UUdoCc2:YcarryUUoutsomeproGcessingCc3:NendUUfor;=>2.4\ThewhileLo`opuT>TheUUwhileloGoptakestheform.>\WHILE{}?\ENDWHILE>F*orUUexample,>\begin{algorithmic}>\WHILE{some?conditionholds}>\STATE?carryoutsomeprocessing>\ENDWHILE>\end{algorithmic}>proGduces HwhileUUsomeconditionholdsdoRcarryUUoutsomeproGcessingHendUUwhile;=>2.5\TherKepeat-untilLo`opuT>TheUUr}'epeat-untilloGoptakestheform.>\REPEAT?\UNTIL{}>F*orUUexample,>\begin{algorithmic}>\REPEAT>\STATE?carryoutsomeprocessing>\UNTIL{some?conditionismet}>\end{algorithmic}>proGduces HrepQeatRcarryUUoutsomeproGcessingHun9tilUUsomeconditionismet4(8y?>2.6\TheIn niteLo`opuT>TheUUin niteloGoptakestheform.>\LOOP?\ENDLOOP>F*orUUexample,>\begin{algorithmic} >\LOOP>\STATE?thisprocessingwillberepeatedforever>\ENDLOOP>\end{algorithmic}>proGduces HloQopRthisUUproGcessingwillberepeatedforeverHendUUloQop6>2.7\ThePrecondition>The~precondition(thatmustbGemetifanalgorithmistocorrectlyexecute)>takesUUtheform.>\REQUIRE?>F*orUUexample,>\begin{algorithmic} >\REQUIRE?$x\neq0$and$n\geq0$>\end{algorithmic}>proGduces >Require:mx6=0UUandn06>2.8\ThePostcondition>ThepGostcondition(thatmustbemetafteranalgorithmhascorrectlyexecuted)>takesUUtheform.>\ENSURE?>F*orUUexample,>\begin{algorithmic} >\ENSURE?$x\neq0$and$n\geq0$>\end{algorithmic}>proGduces >Ensure:ix6=0UUandn05-y?>2.9\CommentsuT>CommentsUUmaybGeinsertedatmostpointsinanalgorithmusingtheform.q.>\COMMENT{}>F*orUUexample,>\begin{algorithmic} >\STATE?dosomething\COMMENT{thisisacomment}>\end{algorithmic}q.>proGduces HdoUUsomethingfthisisacommentg>BecauseLthemechanismsusedtobuildthevqariousalgorithmicstructuresmake >itudiculttousetheabGoveumechanismforplacingcommentsattheendof>the{ rstlineofaconstruct,>thecommands\IF,\ELSIF,\ELSE,\WHILE,\FOR,>\FORALL,N\REPEATNand\LOOPalltakeanoptionalargumentwhichwillbGetreated>asacommenttobGeplacedattheendofthelineonwhichtheyappGear.pF*or>example, HrepQeatUUfthisiscommentnumbGeronegRiflpconditionUUoneismetthenfthisiscommentnumbGertwog\doUUsomethingRelseUUiflpconditiontwoUUismetthenfthisiscommentnumbGerthreeg\doUUsomethingelseRelseUUfthisiscommentnumbGerfourg\doUUnothingRendUUifHun9tilUUhellfreezesoverw>2.10cAnExample>Thefollowingexampledemonstratestheuseofthealgorithmicenvironment>toUUdescribGeacompletealgorithm.qThefollowinginputq.>\begin{algorithmic}>\REQUIRE?$n\geq0$>\ENSURE?$y=x^n$>\STATE?$y\Leftarrow1$>\STATE?$X\Leftarrowx$>\STATE?$N\Leftarrown$>\WHILE{$N?\neq0$}>\IF{$N$?iseven}>\STATE?$X\LeftarrowX\timesX$>\STATE?$N\LeftarrowN/2$>\ELSE[$N$?isodd]>\STATE?$y\Leftarrowy\timesX$>\STATE?$N\LeftarrowN-1$62y?>\ENDIF >\ENDWHILE>\end{algorithmic}>willUUproGduce >Require:mn0>Ensure:iy"=x^nHy"(1HX(xHN3(nHwhileUUN36=0doRiflpNisUUeventhen\X(X¸8X\N3(NA=2RelseUUfNlpisoGddg\y"(y8X\N3(NO81RendUUifHendUUwhile>whichisanalgorithmfor ndingthevqalueofanumbGertakentoanon-negative>pGower.6>2.11cOptionsuT>ThereOisasingleoption,noendthatmaybGeinvokedwhenthealgorithmic>packqagedisloaded.Withthisoptioninvokedtheendstatementsareomittedin>the>output.jOThisallowsspacetobGesavedintheoutputdoGcumentwhenthisis>anUUissue.>2.12cCustomizationuT>In͖ordertofacilitatetheuseofthispackqagewithforeignlanguages,allofthe>wordsintheoutputareproGducedviarede nablemacrocommands.8Thedefault>de nitionsUUofthesemacrosare:>\newcommand{\algorithmicrequire}{\textbf{Require:}}>\newcommand{\algorithmicensure}{\textbf{Ensure:}}>\newcommand{\algorithmicend}{\textbf{end}}>\newcommand{\algorithmicif}{\textbf{if}}>\newcommand{\algorithmicthen}{\textbf{then}}>\newcommand{\algorithmicelse}{\textbf{else}}>\newcommand{\algorithmicelsif}{\algorithmicelse\?\algorithmicif}>\newcommand{\algorithmicendif}{\algorithmicend\?\algorithmicif}>\newcommand{\algorithmicfor}{\textbf{for}}>\newcommand{\algorithmicforall}{\textbf{for?all}}>\newcommand{\algorithmicdo}{\textbf{do}}7:y?>\newcommand{\algorithmicendfor}{\algorithmicend\?\algorithmicfor} >\newcommand{\algorithmicwhile}{\textbf{while}}>\newcommand{\algorithmicendwhile}{\algorithmicend\?\algorithmicwhile}>\newcommand{\algorithmicloop}{\textbf{loop}}>\newcommand{\algorithmicendloop}{\algorithmicend\?\algorithmicloop}>\newcommand{\algorithmicrepeat}{\textbf{repeat}}>\newcommand{\algorithmicuntil}{\textbf{until}}MInήaddition,theformattingofcommentsisimplementedviaasingleargu->mentUUcommandmacrowhichmayalsobGerede ned.qThedefaultde nitionis>\newcommand{\algorithmiccomment}[1]{\{#1\}}!č>3VLTheffalgorithmEnvironment>3.1\General@> ]YǍAlgorithmT1UUCalculatey"=x^nX-ffYRequire:/n08_x6=0 Ensure:+y"=x^n y"(1 iflpn<0UUthenX(1=xN3(n elseX(xN3(n endUUif whileUUN36=0doiflpNisUUeventhenX(X¸8XN3(NA=2elseUUfNlpisoGddgy"(y8XN3(NO81endUUif endUUwhilefdffY>WhenYplacedwithinthetextwithoutbGeingencapsulatedina oatingenviron->mentsalgorithmicenvironmentsmaybGesplitoverapagebGoundarygreatly>detractingfromtheirappGearance.S&Inaddition,itisusefultohavealgorithms>numbGeredN6forreferenceandforlistsofalgorithmstobeappendedtothelistof>contents.jThealgorithmenvironmentismeanttoaddresstheseconcernsby>providingUUa oatingenvironmentforalgorithms.qF*orexample,theinputtext8 By?>\begin{algorithm} >\caption{Calculate?$y=x^n$}>\label{alg1}>\begin{algorithmic}>\REQUIRE?$n\geq0\veex\neq0$>\ENSURE?$y=x^n$>\STATE?$y\Leftarrow1$>\IF{$n?<0$}>\STATE?$X\Leftarrow1/x$>\STATE?$N\Leftarrow-n$>\ELSE>\STATE?$X\Leftarrowx$>\STATE?$N\Leftarrown$>\ENDIF>\WHILE{$N?\neq0$}>\IF{$N$?iseven}>\STATE?$X\LeftarrowX\timesX$>\STATE?$N\LeftarrowN/2$>\ELSE[$N$?isodd]>\STATE?$y\Leftarrowy\timesX$>\STATE?$N\LeftarrowN-1$>\ENDIF>\ENDWHILE>\end{algorithmic}>\end{algorithm}>proGducesZAlgorithm1whichisaslightlymoGdi edversionoftheearlieralgorithm>for6determiningthevqalueofanumbGer6takentoanintegerpGower.kInthiscase,>providedUUthepGowermaybGenegativeprovidedthenumbGerisnotzero.MThevcommand\listofalgorithmsmaybGeusedtoproducealistofalgo->rithmsaspartofthetablecontentsasshownatthebGeginningofthisdocument.>AnUUauxiliary lewithasuxof.loaisproGducedwhenthisfeatureisused.6>3.2\OptionsuT>The{appGearanceofthetypesetalgorithmmaybechangedbyuseoftheoptions:>plain,3boxedxorruledduringtheloadingofthealgorithmpackqage.0The>defaultUUoptionisruled.MThe-numbGeringofalgorithmscanbein uencedbyprovidingthenameof>thedoGcumentcomponentwithinwhichnumbGeringshouldberecommenced.>Thelegalvqaluesforthisoptionare:J|part,chapter,section,subsection,>subsubsection㓲ornothing.Thedefaultvqalueisnothingwhichcausesalgo->rithmsUUtobGenumberedUUsequentiallythroughoutthedoGcument.9 J<y?>3.3\CustomizationuT>Inordertofacilitatetheuseofthispackqagewithforeignlanguages,haveUUbGeenprovidedtofacilitatethenecessarymodi cations.MThetitleusedinthecaptionwithinalgorithmenvironmentcanbGesetby>use8ofthestandard\floatnamecommandwhichisprovidedaspartofthe>floatUUpackqagewhichwasusedtoimplementthispackqage.qF*orexample,>\floatname{algorithm}{Procedure}>would/causeProQceduretobGeusedinsteadofaLAlgorithmwithinthecaption >ofUUalgorithms.MIn:amanneranalogoustothatavqailableforthebuiltin oatingenvironments,>theRheadingusedforthelistofalgorithmsmaybGechangedbyrede ningthe>commandUUlistalgorithmname.qThedefaultde nitionforthiscommandis>\newcommand{\listalgorithmname}{List?ofAlgorithms}10R;y F C cmbxti10N cmbx12߆Tff cmtt12': cmti10 cmmi10 0ercmmi7K`y cmr10V