Hanoi Towers

Loading...

Do curso por University of California San Diego

Mathematical Thinking in Computer Science

380 classificações

University of California San Diego

Mathematical Thinking in Computer Science

380 classificações

Curso 1 de 5 em Specialization Introduction to Discrete Mathematics for Computer Science

Mathematical thinking is crucial in all areas of computer science: algorithms, bioinformatics, computer graphics, data science, machine learning, etc. In this course, we will learn the most important tools used in discrete mathematics: induction, recursion, logic, invariants, examples, optimality. 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 the 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. Prerequisites: 1. 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. 2. Basic programming knowledge is necessary as some quizzes require programming in Python.

Na lição

Recursion and Induction

We'll discover two powerful methods of defining objects, proving concepts, and implementing programs — recursion and induction. These two methods are heavily used, in particular, in algorithms — for analysing correctness and running time of algorithms as well as for implementing efficient solutions. You will see that induction is as simple as falling dominos, but allows to make convincing arguments for arbitrarily large and complex problems by decomposing them and moving step by step. You will learn how famous Gauss unexpectedly solved his teacher's problem intended to keep him busy the whole lesson in just two minutes, and in the end you will be able to prove his formula using induction. You will be able to generalize scary arithmetic exercises and then solve them easily using induction.

Coin Problem4:45

Hanoi Towers7:25

Conheça os instrutores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Vladimir Podolskii
Associate Professor
Computer Science Department

Our final example is the well known Hanoi Towers puzzle.

In this puzzle, we're given three sticks.

Two of them are initially empty.

On the first stick, we have n discs,

sorted by size as shown here on the slide.

Our goal is to move all n discs to some other stick,

to one of the two empty sticks.

This would be easy if not given two constraints.

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.

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.

We can check that it is possible for one, for two, for three, for four, and so on.

But it is not so clear how to ensure that just for

every even very huge number, it is always possible.

And of course, we are going to use recursion again

to show how to do this for every possible value of n.

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.

This will ensure that, if it is possible for one, then it is possible for two.

If it is possible for two, then it is possible for three.

If it is possible for three, then it is possible for four, and so on.

So our goal is basically to show that it is possible in the beginning,

when n is equal to 1.

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 the simplest possible case is indeed when there is just one disc.

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.

Now let's also consider two discs just to get a feeling of how

to solve this problem.

Now in this case, we first move the smallest disc.

So we move it to this stick, then we move the larger disc to another stick.

And finally, we move the smaller one onto larger one, right?

So for two discs, it is also possible.

Now let's consider a general case, where we have n discs.

And let's focus on the larger discs, on the large disc, I'm sorry.

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.

So probably a part of them are on one disc, and

all the remaining of them on the third stick.

I'm sorry.

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.

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 this means that when we are moving the largest disc,

we should move it to an empty stick.

Which in turn means that all the other discs at this point

should be put to the same stick.

And since we know that all the discs are always in increasing order,

we know that at this point, all the other discs should be located as follows, right?

So when we are moving the large disc,

all the remaining discs should be at some other stick.

Which means that up to this point, we've moved all other n minus 1 discs.

So we actually solved the problem for n minus 1 discs, right?

And this gives us an idea for a recursive solution.

Because this is essentially the same problem which was solved for

n minus 1 discs, so a recursive solution in this case is the following.

So we first move n minus 1 discs recursively, to some other stick.

So then we will reach the following state.

After this, we move the largest disc, okay?

And then finally we move, once again, the n minus 1 discs.

Again, using a recursive call, okay?

So we know how to do this because we can call the same

procedure with parameter n minus 1.

And this finally gives us the solution, right?

So again, we reduce the problem with parameter n to the problem

with parameter n minus 1.

This problem in turn will be reduced through a problem with parameter

n minus 2, then with n minus 3, and so on.

Until we reach 1, and for 1, we know that it is possible, right?

So essentially, what we've proved is that it is possible for every value of n.

We can consider this for example like this.

We know that it is possible for 1, then it is possible for 2, right?

Then since it is possible for 2, it is also possible for 3, and so on.

So it will be possible for all the numbers.

Or put it otherwise, to solve the problem for n, we need to solve it for n minus 1.

To solve the problem for n minus 1, we need to solve it for n minus 2.

Meaning that if we know how to do this for n minus 2,

then we definitely know how to do this for n minus 1 and so on.

So going backwards, we will reach 1, and for 1, we know that it is possible.

So which actually proves that it is possible,

and what just happened is that actually we have proved that it is

possible by induction, which is a highly related notion to recursion.

So saying very roughly, induction is a mathematical method for

proving something, where recursion is a method of defining something or

a method of implementing something.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play