Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- EMPTY BOXES
- 0) Identify knowns and unknowns of final state
- knowns: number of empty boxes
- unknowns: number of boxes in total
- 1) Introduce variables that together represent the state at an arbitrary point in "time"
- at any stage: number of empty boxes e, and number of boxes in total, b
- 2) Model the process of filling boxes as an assignment statement to the state variables, along with dependent composition
- b:=b+8.e:=e+8-1 = b:=b+8.e:=e+7
- 3) Identify an invariant of the assignment (an expression E such that it remains invariant under sequential composition with the above), i.e. b:=b+8.e:=e+7.E = E
- try E = f×b + g×e
- b:=b+8.e:=e+7.E
- = b:=b+8.e:=e+7.(f×b + g×e)
- = b:=b+8.(f×b + g×(e+7))
- = f×b + g×e + f×8 + g×7
- = f×b + g×e
- In order for the above equation to be true, f×8 + g×7 = 0
- ∴ f×8 + g×7 = 0
- = g×7 = -f×8
- = g = -f×(8/7)
- choose, f=1 ∧ g=-(8/7) => b:=b+8.e:=e+7.(f×b + g×e) = (f×b + g×e)
- 4) Combine the previous steps to deduce the final state
- total number of boxes at the start = 11
- number of empty boxes at the start = 11
- number of empty boxes at the end = 102
- what is the total number of boxes at the end?
- we have just deduced that the expression b + (-8/7)×e (where b is the number of boxes in total, and e is the
- number of empty boxes remains invariant (i.e. does not change), at every step of the problem, therefore
- (total number of boxes initially) - (8/7)×(total number of empty boxes initially)
- = (total number of boxes at end) - (8/7)×(total number of empty boxes at end)
- ∴ 11×1 – (8/7)×11 = b' – (8/7)×102 => b'=115
- LESSONS:
- * it is a unnecessary to account for the medium sized and small sized boxes separately! keep your problem-solving process simple; keep it goal-oriented – don't try to grab more than you need!
- * the first question to ask is: "what is the unknown?", then work backwards to determine what is the minimum amount of information needed to determine the unknown
- * accept that change of state caused by an assignment is an inescapable feature of algorithmic problem solving; therefore, learn how to reason about assignments directly rather than avoid them
- * when an assignment involves three or more variables, it can be a useful strategy to seek invariant combinations of subsets of the variables and then combine the invariants into one
- * alludes to a possible general rule?: linear combinations of invariants are invariant too? (question)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement