4.6 The [standard approach].

We know what a Lion is from [ISO] 4711/X.123. Since [CCITT] have specified a Lion to be a [particular option] of a [cat] we will have to wait for a [harmonized standard] to appear. $20,000,000 have been [fund]ed for [initial investigations] into this [standard development].\r\n\r\n

[linear search|4.7 Linear search.]

Stand in the top left hand [corner] of the Sahara Desert. Take one [step] east. Repeat until you have found the lion, or you reach the right hand edge. If you reach the right hand [edge], take one step southwards, and proceed towards the left hand edge. When you finally reach the lion, put it the cage. If the lion should happen to eat you before you manage to get it in the cage, press the [reset button], and try again.\r\n

Optionally, [experienced programmer]s will place a [pink elephant] in [Johannesburg] as a [sentinel value]. (thanks [ariels])\r\n \r\n

[Dijkstra's algorithm |4.8 The Dijkstra approach:]

The way the problem reached me was: catch a wild lion in the Sahara\r\nDesert. [Another way of stating the problem] is:\r\n\r\n

\r\n       [Axiom] 1: Sahara [elem] deserts\r\n       Axiom 2: Lion elem Sahara\r\n       Axiom 3: NOT(Lion elem cage)\r\n

We observe the following invariant:\r\n\r\n

       P1:     C(L) v not(C(L))\r\n

where C(L) means: the value of \"L\" is in the cage.\r\n\r\n

Establishing C initially is trivially accomplished with the statement\r\n\r\n

       ;cage := {}\r\nNote 0:\r\n[This is easily implemented] by opening the door to the \r\ncage and shaking out any lions that happen to be there \r\ninitially.\r\n(End of note 0.)\r\n

The obvious [program structure] is then:\r\n

\r\n       ;cage:={}\r\n       ;do NOT (C(L)) ->\r\n               ;\"approach lion under [invariance] of P1\"\r\n               ;if P(L) ->\r\n                       ;\"insert lion in cage\"\r\n                [] not P(L) ->\r\n                       ;skip\r\n               ;fi\r\n       ;od\r\n\r\nwhere P(L) means: the value of L is within arm's reach.\r\n\r\nNote 1:\r\nAxiom 2 ensures that the [loop termination|loop terminates].\r\n(End of note 1.)\r\n\r\nExercise 0:\r\nRefine the step \"Approach lion under invariance of P1\".\r\n(End of exercise 0.)\r\n\r\nNote 2:\r\nThe program is [robust] in the sense that it will lead to\r\n[abortion] if the value of L is \"lioness\".\r\n(End of note 2.)\r\n\r\nRemark 0: This may be a new sense of the word \"robust\" for you.\r\n(End of remark 0.)\r\n\r\nNote 3:\r\n\r\nFrom observation we can see that the above program leads to the\r\n[desired goal]. It goes without saying that we therefore do not \r\nhave to [run] it.\r\n(End of note 3.)\r\n(End of approach.) \r\n(End of document)\r\n

You can find an infinity of variations on the above [theme] floating around in the [cyberspace] (and probably in [dead tree] format too), but some of them tend to wear the concept a bit [thin]...