YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← 32-02 Question 1 Solution

32-02 Question 1 Solution

Get Embed Code
2 Languages

Showing Revision 3 created 07/12/2017 by Maya Bergamasco.

  1. The answer to the first question
  2. is given by a simple algorithm.
  3. Suppose you place the largest disk first,
  4. which has three different locations.
  5. And the next disk, on top of it,
  6. which is another three locations.
  7. the third disk and the fourth disk
  8. Then for each disk,
  9. you have three possibilities,
  10. and you have four disks,
  11. so it makes three to the fourth.
  12. That is eighty-one.
  13. The disks on the left side
  14. are an admissible heuristic,
  15. because it takes at least that many steps
  16. to move all the disks
  17. from the left side
  18. to the right side.
  19. And finally,
  20. the number of moves required
  21. is a little bit tricky.
  22. And you have to know the solution here.
  23. You will finally move the big disk once.
  24. But to move it to the right-side,
  25. you previously moved the
  26. second largest disk
  27. to the center. And then move it over
  28. to the right side.
  29. Which is two motions
  30. for the second largest disk.
  31. For the third largest,
  32. you'll move it four times,
  33. by the same logic.
  34. And the smallest is being moved 8 times.
  35. The total is going to be fifteen.
  36. That's the same as two to the n minus one,
  37. if 'n' is the number of disks.