Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- -- Searching for the maximum (http://www.cs.ox.ac.uk/admissions/ugrad/Sample_interview_problems)
- findMax' _ a b xa xb 0
- | a < b = (xb, b)
- | otherwise = (xa, a)
- findMax' f a b xa xb i
- | a < b = let xc = xb + d
- in findMax' f b (f xc) xb xc (i - 1)
- | otherwise = let xc = xa - d
- in findMax' f (f xc) a xc xa (i - 1)
- where d = (xb - xa) * ((sqrt 5) - 1) / 2
- findMax f = let xa = (3 - sqrt 5) / 2
- xb = 1 - xa
- in findMax' f (f xa) (f xb) xa xb
- {- Explanation
- Two values are read at each step.
- If the left value is smaller, everything to its left is discarded.
- Otherwise, everything to the right of the right value is discarded.
- The larger value is passed on to the next step, meaning only 1 new value is taken.
- | | |
- b| | +
- a| + |
- | | |
- |____|__|____|
- 0 xa xb 1
- b > a, so move right:
- |#### | |
- a|#### + |
- b|#### | +
- |#### | |
- |_##_|__|_|__|
- 0 xa xb 1
- Note that old xb and new xa are the same, so no remeasuring takes place.
- The value xa = (3 - sqrt 5) / 2 comes about through solving:
- -----|---|-----
- ( x + y + x ) / x
- ==
- ---|-|---
- ( x + y) / y
- where x + y + x = 1. The value of d comes about in a similar way, but is based on a given y,
- rather than a given 2*x + y.
- Both numbers are heavily related to the golden ratio:
- (3 - sqrt 5) / 2 == 2 - phi
- ((sqrt 5) - 1) / 2 == phi - 1
- == 1 / phi
- -}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement