Advertisement
Guest User

Untitled

a guest
Dec 30th, 2013
144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.46 KB | None | 0 0
  1. EMPTY BOXES
  2. 0) Identify knowns and unknowns of final state
  3. knowns: number of empty boxes
  4. unknowns: number of boxes in total
  5.  
  6. 1) Introduce variables that together represent the state at an arbitrary point in "time"
  7. at any stage: number of empty boxes e, and number of boxes in total, b
  8.  
  9. 2) Model the process of filling boxes as an assignment statement to the state variables, along with dependent composition
  10. b:=b+8.e:=e+8-1 = b:=b+8.e:=e+7
  11.  
  12. 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
  13. try E = f×b + g×e
  14.  
  15. b:=b+8.e:=e+7.E
  16. = b:=b+8.e:=e+7.(f×b + g×e)
  17. = b:=b+8.(f×b + g×(e+7))
  18. = f×b + g×e + f×8 + g×7
  19. = f×b + g×e
  20.  
  21. In order for the above equation to be true, f×8 + g×7 = 0
  22. ∴ f×8 + g×7 = 0
  23. = g×7 = -f×8
  24. = g = -f×(8/7)
  25.  
  26. choose, f=1 ∧ g=-(8/7) => b:=b+8.e:=e+7.(f×b + g×e) = (f×b + g×e)
  27.  
  28. 4) Combine the previous steps to deduce the final state
  29. total number of boxes at the start = 11
  30. number of empty boxes at the start = 11
  31. number of empty boxes at the end = 102
  32. what is the total number of boxes at the end?
  33.  
  34. we have just deduced that the expression b + (-8/7)×e (where b is the number of boxes in total, and e is the
  35. number of empty boxes remains invariant (i.e. does not change), at every step of the problem, therefore
  36.  
  37. (total number of boxes initially) - (8/7)×(total number of empty boxes initially)
  38. = (total number of boxes at end) - (8/7)×(total number of empty boxes at end)
  39. ∴ 11×1 – (8/7)×11 = b' – (8/7)×102 => b'=115
  40.  
  41. LESSONS:
  42. * 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!
  43. * 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
  44. * 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
  45. * 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
  46. * alludes to a possible general rule?: linear combinations of invariants are invariant too? (question)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement