Which in turn means that all the other discs at this point should be put to the same stick. So this means that when we are moving the largest disc, we should move it to an empty stick. If there is at least one stick, at least one disc, I'm sorry, on this stick then by moving the largest disc to this stick, we will put a larger disc onto a smaller one. So if we are moving this large disc, so for which stick we can move it? So I'm claiming that the only stick for which we can move it is the empty stick, right? Because if there are any discs on this stick then we will be allayed the rules. So probably a part of them are on one disc, and all the remaining of them on the third stick. So what is the condition under which we can move it? So first of all, if we are moving the large disc, this actually means that all the remaining n minus 1 discs are already on some other stick. And let's focus on the larger discs, on the large disc, I'm sorry. Now let's consider a general case, where we have n discs. And finally, we move the smaller one onto larger one, right? So for two discs, it is also possible. So we move it to this stick, then we move the larger disc to another stick. Now in this case, we first move the smallest disc. Now let's also consider two discs just to get a feeling of how to solve this problem. So in this case, n is equal to 1, and our goal is to move this disc to some other place, to some other stick, and of course it is very easy to do this so we just move it to another stick. So the simplest possible case is indeed when there is just one disc. And then we need to show some generic procedure of building a solution for n discs using a recursive solution for n minus 1 discs, okay? So let's start. So our goal is basically to show that it is possible in the beginning, when n is equal to 1. 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. Mathematical thinking is crucial in all areas of computer science: algorithms, bioinformatics, computer graphics, data science, machine learning, etc.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |