Even and Odd Numbers

Loading...

來自 University of California San Diego 的課程

Mathematical Thinking in Computer Science

230 個評分

University of California San Diego

Mathematical Thinking in Computer Science

230 個評分

課程 1（共 5 門，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.

從本節課中

Invariants

"There are things that never change". Apart from being just a philosophical statement, this phrase turns out to be an important idea that can actually help. In this module we will see how it can help in problem solving. Things that do not change are called invariants in mathematics. They form an important tool of proving with numerous applications, including estimating running time of programs and algorithms. We will get some intuition of what they are, see how they can look like, and get some practice in using them.

Even and Odd Numbers4:36

Summing up Digits4:36

Switching Signs3:19

Advanced Signs Switching8:30

與講師見面

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

Hi, I'm Vladimir Poldoskii,

and today we're going to discuss the properties of numbers to be even or odd.

Even numbers are integer numbers that are divisible by two.

And odd numbers are all other integer numbers.

For example, numbers 2, 4, 6,

8, and so on are even. They're divisible by two.

And numbers 1, 3, 5,

7, are odd, they're not divisible by two.

What about number zero?

Zero is also an even number, it is divisible by two.

We can divide zero by two and obtain zero.

It is also an integer,

so zero is even.

It is also useful to look at numbers on the number line.

Let's position all numbers in the increasing order, all integer numbers.

And let's color even numbers in green color and odd numbers in the red color.

Now we can see that odd and even numbers are interchangeable on this line.

Zero is even and one is odd and two is even and three is odd and so on,

and the same in reverse direction.

So even and odd numbers are interchangeable and this is good to keep in mind.

The properties of numbers to be even or odd

are important invariants that I use very often.

Let's see it on the example.

Consider a full on problem.

We have a chessboard and a piece which can move in one move,

in one move it can move to one cell that is adjacent by edge to the current one.

It can one cell the right,

to the left, up, or down.

Can it return to the original position after 17 moves or after 18 moves?

So there are two questions in this problem.

So let's proceed to a solution and let's start with a more simple case of 18 moves.

This case is more simple because it's possible to

return to the initial position in this case

and it is usually more simple to show

possibility to do something than impossibility to do something.

Okay, let's see how to do this.

It turns out that you can return to the initial position just after just two steps.

And you can do for example in this way,

you can move to the right first and then on the second step we can move

back and so they are back in the initial position after just two steps.

And now we can just repeat it nine times and

we'll be back in the initial position after 18 moves.

And note that here in the solution we used,

that 18 is an even number.

It is divisible by two,

so we can return to the initial position just two steps and then it

repeats a certain number of times and get to the initial position two after 18 moves.

So now let's proceed to the second part.

The previous solution doesn't work because 17 is odd,

and we can not just apply the same argument we used that 18 is even.

So now we have to do something else and it turns out that even more of it,

in this case this is impossible.

And let's see why.

It turns out that we can make a full on observation.

After even number of steps this piece is always on the white field.

And after odd number of steps it is always on the black field.

Indeed it, initially zero steps,

it is on the white field.

Then it moves after the first steps,

the number of steps becomes odd and the piece should move to the black cell,

and then after a second step it moves to the white cell.

But now the number of steps is two and it is even, and so on and so forth.

So we can observe it this also,

this property always is satisfied,

and this is our invariant.

And this means that there is no way to get back after odd number of steps.

Let's observe 17 as odd again.

Because after 17 number of steps you will be on

the black square and our initial square is white.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2018 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取