If it is possible for three, then it is possible for four, and so on. If it is possible for two, then it is possible for three. This will ensure that, if it is possible for one, then it is possible for two. For this, we will first explain that it is possible when n is equal to 1, and then we will show that if it is possible for n minus 1, for example, then it is possible for n. And of course, we are going to use recursion again to show how to do this for every possible value of n. But it is not so clear how to ensure that just for every even very huge number, it is always possible. We can check that it is possible for one, for two, for three, for four, and so on. At the same time, it is not clear at this point how can we be sure that it is possible for every possible value of n. First of all, we are allowed to move only one disc at a time, and naturally we need to take the top most disc from one stick, and to put it to some other stick, right? And also we are not allowed to put a larger disc onto a smaller disc, okay? So the question is whether it is possible for, and if it is possible, then for which values of n this is possible, okay? So it is known to be possible for every value of n. This would be easy if not given two constraints. Our goal is to move all n discs to some other stick, to one of the two empty sticks. On the first stick, we have n discs, sorted by size as shown here on the slide. In this puzzle, we're given three sticks. Our final example is the well known Hanoi Towers puzzle. Basic programming knowledge is necessary as some quizzes require programming in Python. We assume only basic math (e.g., we expect you to know what is a square or how to add fractions), common sense and curiosity.Ģ. In the online course, we use a try-this-before-we-explain-everything approach: you will be solving many interactive (and mobile friendly) puzzles that were carefully designed to allow you to invent many of the important ideas and concepts yourself.ġ. We will use these tools to answer typical programming questions like: How can we be certain a solution exists? Am I sure my program computes the optimal answer? Do each of these objects meet the given requirements? In this course, we will learn the most important tools used in discrete mathematics: induction, recursion, logic, invariants, examples, optimality. I.e MoveDisks ( N - 1, aux_peg, source_peg, dest_peg ).Mathematical thinking is crucial in all areas of computer science: algorithms, bioinformatics, computer graphics, data science, machine learning, etc. Now that we have N - 1 disks on aux_peg, we could move them to dest_peg using source_peg ( as auxiliary peg ) Move the bottom-most disk N left on the source_peg to dest_peg.ĥ. I.e MoveDisks ( N - 1, source_peg, dest_peg, aux_peg ).Ĥ. First move the top ( N - 1 ) disks from source_peg to aux_peg using dest_peg ( which is used as an auxiliary peg ). Thus the rules of the puzzle are obeyed and we get the below recursive algorithm for solving the puzzle of Tower Of Hanoi.Īlgorithm : MoveDisks ( Integer disks, String source_peg, String using_peg, String dest_peg ) The bottom-most disk that is now left on the source peg is then moved to the desitnation peg. Idea : The idea behind recursion is to move the top ( N - 1 ) disks from source peg to auxiliary peg. If N = 3, we could have 2 3 - 1 = 7 moves.If N = 2, we could have 2 2 - 1 = 3 movesġ: Move the smaller disk at the top from peg A to peg B.Ģ: Move the bigger disk at the bottom from A to peg C.ģ: Move the smaller disk from peg B to peg C.If N = 1, we could just moved the disk from peg A to peg C without using the auxiliary peg. It can be mathematically proved that the minumum number of moves required to move N disks is 2 N - 1.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |