Материал готовится,

пожалуйста, возвращайтесь позднее

пожалуйста, возвращайтесь позднее

ANNOUNCER: Open content is provided under a creative commons license. Your support will help MIT OpenCourseWare continue to offer high-quality educational resources for free. To make a donation, or view additional materials from hundreds of MIT courses, visit MIT OpenCourseWare at ocw.mit.edu .

PROFESSOR JOHN GUTTAG: All right. That said, let's continue, and if you remember last time, we ended up looking at this thing I called square roots bi. This was using something called a bisection method, which is related to something called binary search, which we'll see lots more of later, to find square roots.

And the basic idea was that we had some sort of a line, and we knew the answer was somewhere between this point and this point. The line is totally ordered. And what that means, is that anything here is smaller than anything to its right. So the integers are totally ordered, the reals are totally ordered, lots of things are, the rationals are totally ordered.

And that idea was, we make a guess in the middle, we test it so this is kind of a guess and check, and if the answer was too big, then we knew that we should be looking over here. If it was too small, we knew we should be looking over here, and then we would repeat. So this is very similar, this is a kind of recursive thinking we talked about earlier, where we take our problem and we make it smaller, we solve a smaller problem, et cetera.

All right. So now, we've got it, I've got the code up for you. I want you to notice the specifications to start. We're assuming that x is greater than or equal to 0, and epsilon is strictly greater than 0, and we're going to return some value y such that y squared is within epsilon of x.

I'd last time talked about the two assert statements. In some sense, strictly speaking they shouldn't be necessary, because the fact that my specification starts with an assumption, says, hey you, who might call square root, make sure that the things you call me with obey the assumption.

On the other hand, as I said, never trust a programmer to do the right thing, so we're going to check it. And just in case the assumptions are not true, we're just going to stop dead in our tracks.

All right. Then we're going to set low to — low and high, and we're going to perform exactly the process I talked about. And along the way, I'm keeping track of how many iterations, at the end I'll print how many iterations I took, before I return the final guess.

All right, let's test it. So one of the things I want you to observe here, is that instead of sitting there and typing away a bunch of test cases, I took the trouble to write a function, called test bi in this case. All right, so what that's doing, is it's taking the things I would normally type, and putting them in a function, which I can then call.

Why is that better than typing them? Why was it worth creating a function to do this? Pardon?

STUDENT:: [INAUDIBLE]

PROFESSOR JOHN GUTTAG: Then I can I can use it again and again and again. Exactly.

By putting it in a function, if I find a bug and I change my program, I can just run the function again. The beauty of this is, it keeps me from getting lazy, and not only testing my program and the thing that found the bug, but in all the things that used to work.

We'll talk more about this later, but it often happens that when you change your program to solve one problem, you break it, and things that used to work don't work.

PROFESSOR JOHN GUTTAG: All right. That said, let's continue, and if you remember last time, we ended up looking at this thing I called square roots bi. This was using something called a bisection method, which is related to something called binary search, which we'll see lots more of later, to find square roots.

And the basic idea was that we had some sort of a line, and we knew the answer was somewhere between this point and this point. The line is totally ordered. And what that means, is that anything here is smaller than anything to its right. So the integers are totally ordered, the reals are totally ordered, lots of things are, the rationals are totally ordered.

And that idea was, we make a guess in the middle, we test it so this is kind of a guess and check, and if the answer was too big, then we knew that we should be looking over here. If it was too small, we knew we should be looking over here, and then we would repeat. So this is very similar, this is a kind of recursive thinking we talked about earlier, where we take our problem and we make it smaller, we solve a smaller problem, et cetera.

All right. So now, we've got it, I've got the code up for you. I want you to notice the specifications to start. We're assuming that x is greater than or equal to 0, and epsilon is strictly greater than 0, and we're going to return some value y such that y squared is within epsilon of x.

I'd last time talked about the two assert statements. In some sense, strictly speaking they shouldn't be necessary, because the fact that my specification starts with an assumption, says, hey you, who might call square root, make sure that the things you call me with obey the assumption.

On the other hand, as I said, never trust a programmer to do the right thing, so we're going to check it. And just in case the assumptions are not true, we're just going to stop dead in our tracks.

All right. Then we're going to set low to — low and high, and we're going to perform exactly the process I talked about. And along the way, I'm keeping track of how many iterations, at the end I'll print how many iterations I took, before I return the final guess.

All right, let's test it. So one of the things I want you to observe here, is that instead of sitting there and typing away a bunch of test cases, I took the trouble to write a function, called test bi in this case. All right, so what that's doing, is it's taking the things I would normally type, and putting them in a function, which I can then call.

Why is that better than typing them? Why was it worth creating a function to do this? Pardon?

STUDENT:: [INAUDIBLE]

PROFESSOR JOHN GUTTAG: Then I can I can use it again and again and again. Exactly.

By putting it in a function, if I find a bug and I change my program, I can just run the function again. The beauty of this is, it keeps me from getting lazy, and not only testing my program and the thing that found the bug, but in all the things that used to work.

We'll talk more about this later, but it often happens that when you change your program to solve one problem, you break it, and things that used to work don't work.

Загрузка...

Выбрать следующее задание

Ты добавил

Выбрать следующее задание

Ты добавил