求推荐，入门级50mm定焦 for D80 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PhotoGear - 摄影器材

求推荐，入门级50mm定焦 for D80

求推荐，入门级50mm定焦 for D80# PhotoGear - 摄影器材

l*b2010-05-27 07:05

1 楼

最近似乎G的面筋的不多，俺报一下，今天下午面的。面完大概一小时候后接到他们的
电话要约2面。我正好下周要去那出差2个月，问可不可以直接onsite，还在等答复。
一开始就是问做的项目，聊了大概15分钟。对我写的一个database特干兴趣。然后做题：
一个matrix上，有n个人，这n个人要找一个地方开会，问哪个地方让大家移动的距离
最近。

s*p2010-05-27 07:05

2 楼

150刀以内吧

w*x2010-05-27 07:05

3 楼

题：
G的题真是被问烂了, 区二维的median吧

【在 l*********b 的大作中提到】

: 最近似乎G的面筋的不多，俺报一下，今天下午面的。面完大概一小时候后接到他们的
: 电话要约2面。我正好下周要去那出差2个月，问可不可以直接onsite，还在等答复。
: 一开始就是问做的项目，聊了大概15分钟。对我写的一个database特干兴趣。然后做题：
: 一个matrix上，有n个人，这n个人要找一个地方开会，问哪个地方让大家移动的距离
: 最近。

q*z2010-05-27 07:05

4 楼

除了50 1.8没别的选择了吧

【在 s******p 的大作中提到】

: 150刀以内吧

g*e2010-05-27 07:05

5 楼

geometric median? 只能近似吧

们的
距离

【在 w****x 的大作中提到】

:
: 题：
: G的题真是被问烂了, 区二维的median吧

H*m2010-05-27 07:05

6 楼

我在卖你往前面找找

【在 s******p 的大作中提到】

: 150刀以内吧

f*e2010-05-27 07:05

7 楼

min sum_i (|x_i-x|+|y_i-y|)
over(x,y)
先找 min_y sum_i(|y_i-y|)
再找 min_x sum_i(|x_i-x|)
目标函数好像都是凸的，找斜率接近0的，在median上，一半xi小于x，一半xi大于x
加起来斜率正好为0。

题：

【在 l*********b 的大作中提到】

i*h2010-05-27 07:05

8 楼

怎么证明这个总距离最近?
比如所有坐标求平均好象也行?

【在 w****x 的大作中提到】

:
: 题：
: G的题真是被问烂了, 区二维的median吧

i*h2010-05-27 07:05

9 楼

如果N=2的话,
连线上任意一点的移动距离都是一样的, 就是线段长度, 对不对?

题：

【在 l*********b 的大作中提到】

c*s2010-05-27 07:05

10 楼

Can we directly take the derivative of sum_i(|y_i-y|) and sum_i(|x_i-x|),
set them to zero and find the corresponding y and x?

c*s2010-05-27 07:05

11 楼

The matrix is a discretized space. Results from continuos optimization may
not be directly applied.

x*o2010-05-27 07:05

12 楼

这个是对的，可是这个问题相当于一个多边形求中间哪点到所有顶点和最近，which我
不知道怎么做。

【在 i***h 的大作中提到】

: 如果N=2的话,
: 连线上任意一点的移动距离都是一样的, 就是线段长度, 对不对?
:
: 题：

g*e2010-05-27 07:05

13 楼

http://en.wikipedia.org/wiki/Geometric_median

【在 f*****e 的大作中提到】

: min sum_i (|x_i-x|+|y_i-y|)
: over(x,y)
: 先找 min_y sum_i(|y_i-y|)
: 再找 min_x sum_i(|x_i-x|)
: 目标函数好像都是凸的，找斜率接近0的，在median上，一半xi小于x，一半xi大于x
: 加起来斜率正好为0。
:
: 题：

w*x2010-05-27 07:05

14 楼

G给的距离公式因该是|x2 - x1| + |y2 - y1|吧

【在 i***h 的大作中提到】

: 怎么证明这个总距离最近?
: 比如所有坐标求平均好象也行?

f*e2010-05-27 07:05

15 楼

知道,boyd那本书上有这题。最简单的方法就是分段看斜率，一开始斜率为负，后来斜
率为正。就是一个拔河的过程。其实看到|xi-x|是凸的，n个凸函数的和任然是凸函数
，心里就有谱了。

【在 g**e 的大作中提到】

: http://en.wikipedia.org/wiki/Geometric_median

g*e2010-05-27 07:05

16 楼

大牛，你数学太nb了

【在 f*****e 的大作中提到】

: 知道,boyd那本书上有这题。最简单的方法就是分段看斜率，一开始斜率为负，后来斜
: 率为正。就是一个拔河的过程。其实看到|xi-x|是凸的，n个凸函数的和任然是凸函数
: ，心里就有谱了。

g*e2010-05-27 07:05

17 楼

原来是曼哈顿距离，我真土

【在 w****x 的大作中提到】

:
: G给的距离公式因该是|x2 - x1| + |y2 - y1|吧

i*h2010-05-27 07:05

18 楼

OK, 然后怎么做?

【在 w****x 的大作中提到】

:
: G给的距离公式因该是|x2 - x1| + |y2 - y1|吧

w*x2010-05-27 07:05

19 楼

median

【在 i***h 的大作中提到】

: OK, 然后怎么做?

T*o2010-05-27 07:05

20 楼

可以证明，N个点中，存在一个点，这个点做为开会点，结果=最优解。分x，y轴分
别sort所有的点(NlogN)。找出各自维上的最优点(O(N)可做)，然后x, y 座标组合起
来，就是最后结果。

N*n2010-05-27 07:05

21 楼

大牛你在哪儿找的800道题啊，能分享一下么

【在 w****x 的大作中提到】

:
: median

r*e2010-05-27 07:05

22 楼

这是Sterner Tree吧
http://en.wikipedia.org/wiki/Rectilinear_Steiner_tree

r*e2010-05-27 07:05

23 楼

sorry，是ST的特殊情况，median的做法是对的。可以理解为linear programming问题
，因为函数convex，最优解确实在boundary（即x-median和y-median的交点）。

g*n2010-05-27 07:05

24 楼

请问是分别找x和y的median么？是有什么证明么？为什么不是平均数？（虽然感觉应该
是median）
谢谢！

【在 w****x 的大作中提到】

:
: median

r*e2010-05-27 07:05

25 楼

Median number minimizes \sum |x_i-x|
since the solution space is convex, the optimal solution is at the boundary,
i.e. the intersection of x-median and y-median.