Closest Point

Loading...

来自 Duke University 的课程

Programming Fundamentals

360 个评分

Duke University

Programming Fundamentals

360 个评分

课程 1（共 4 门，Specialization Introduction to Programming in C）

Programming is an increasingly important skill, whether you aspire to a career in software development, or in other fields. This course is the first in the specialization Introduction to Programming in C, but its lessons extend to any language you might want to learn. This is because programming is fundamentally about figuring out how to solve a class of problems and writing the algorithm, a clear set of steps to solve any problem in its class. This course will introduce you to a powerful problem-solving process—the Seven Steps—which you can use to solve any programming problem. In this course, you will learn how to develop an algorithm, then progress to reading code and understanding how programming concepts relate to algorithms.

从本节课中

Introduction

This module introduces a powerful process for solving any programming problem—the Seven Steps. You will learn how to approach a programming problem methodically, so you can formulate an algorithm that is specific and correct. You will work through examples with sequences of numbers and graphical patterns to develop the skill of algorithm development.

A Pattern of Squares4:46

Testing a Pattern of Squares2:21

Drawing a Rectangle4:07

Closest Point5:07

Generalizing Closest Point5:07

与讲师见面

Andrew D. Hilton
Associate Professor of the Practice
Electrical and Computer Engineering
Genevieve M. Lipp
Adjunct Professor
Electrical and Computer Engineering/Mechanical Engineering
Anne Bracy
Senior Lecturer
Computer Science, Cornell University

In this video, we're going to work the problem of finding

the closest point out of a set of points to some other given point.

We'll start by doing an instance of this problem by ourselves.

To do that, I've begun by drawing

a Cartesian coordinate grid and choosing a set S of points,

which you can see here,

another point P, which is one, negative one.

We're going to find the point in S that is closest to

P. The first thing I'm going to do is to draw my points on my Cartesian plane.

Now, I can begin working through this.

First, I need some domain knowledge.

I need the mathematical definition of the distance between two points,

which if you don't remember,

is the difference in the x values squared plus the difference in

the y values squared and then we take the square root of that.

So the way that I would do this is calculate the distance between P and two,

seven, and I would come up with 8.06.

Then, I would compute the distance between P and 10,

5 and come up with 10.82.

The first point was closer,

so I'm going to keep that.

This point is 7.07 away,

so I'm going to keep the new closest point so far.

This point is 7.81 away,

so eight, negative two is still closer.

This point is 5.66 away,

so we have a new closest point.

This point is 9.06 away,

so negative three, negative five is closer.

This point is 9.22 away,

so negative three, negative five is still closer.

And there are no more points to test, so negative three,

negative five is my answer to which point is closest to one, negative one.

If we visually inspect this picture,

that seems pretty reasonable.

It looks like the closest.

Now, I write down exactly what I just did.

I computed one squared plus eight squared,

took the square root and got about 8.06.

I computed the square root of nine squared plus six squared and got 10.82,

and I compared 10.82 to 8.06 and said 8.06 is smaller.

I computed the square root of seven squared plus negative one squared and got 7.07,

and I compared 7.07 to 8.06 and said 7.07 is smaller,

so this is a better choice.

Then I compared the square root of six squared plus negative five squared and got 7.81.

I compared 7.81 with 7.07 and got that 7.07 was smaller and so on and so on and so on.

And then when I got to the end,

I gave my answer as negative three, negative five.

These seem like reasonable steps,

but we actually glossed over

something that we did in the process of writing these steps down.

It is very important that we write our steps down

carefully because if we're missing steps,

we're going to miss them when we go to generalize and end up having a problem.

Here's an important clue.

Look at this step where we give an answer of negative three, negative five.

When we go to generalize,

we're going to ask, "Why did we use negative three, negative five?"

Then we're going to notice we don't see negative three,

negative five anywhere else.

The fact that our answer seemingly comes out of

nowhere indicates that we're missing something.

We did some step without consciously thinking about it and writing it down,

and we need to fix that before we go on.

We may notice this now,

we may notice it when we go to generalize,

in which case we need to come back and fix it.

Why was it that we picked negative three,

negative five as our answer here?

Reviewing our last steps,

the last remaining dotted line of length 5.66 is what we were keeping track of,

our best choice so far.

We started at point two, seven,

then we went around and updated it each time we found a shorter distance.

However, as we wrote our steps,

we never mentioned the point that went with the shortest distance so far.

We should go back and fix our steps to include that.

We start with a best choice of two, seven.

When we got to eight, negative two and decided 7.07 was smaller,

we updated our closest point to eight, negative two.

When we got to negative three,

negative five and found that 5.66 was smaller,

we updated our best choice to negative three, negative five.

Now, this answer at the end makes sense.

It is whatever our best choice was last.

Now we're ready to generalize,

which we'll do in the next video.

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

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

通过 App Store 下载

通过 Google Play 获取