请教一个面试问题（software eng） - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Programming - 葵花宝典

请教一个面试问题（software eng）

请教一个面试问题（software eng）# Programming - 葵花宝典

y*y2007-09-05 07:09

1 楼

第一问：一个平面，给n条线两两互不平行，问能形成几个三角形？
答案是c^3_n
再问这个答案有什么条件？
条件是没有三条线交于一点
最后问：那么如果没有这个条件（没有三条线交于一点），需要什么条件才能唯一确定
形成了几个三角形呢？
我的回答是：需要知道总共有几个交点
interviewer认为：需要知道3线相交的点有几个，4线相交的点有几个，5线相交的点有
几个，依次类推
我知道interviewer的条件肯定正确，但是比我的条件要强
请问：我的答案对不对呢？刚才又想了想，好像没找出反例:(
诚心求教！

t*t2007-09-05 07:09

2 楼

明明是数学问题,不要打着software eng的幌子!

【在 y***y 的大作中提到】

: 第一问：一个平面，给n条线两两互不平行，问能形成几个三角形？
: 答案是c^3_n
: 再问这个答案有什么条件？
: 条件是没有三条线交于一点
: 最后问：那么如果没有这个条件（没有三条线交于一点），需要什么条件才能唯一确定
: 形成了几个三角形呢？
: 我的回答是：需要知道总共有几个交点
: interviewer认为：需要知道3线相交的点有几个，4线相交的点有几个，5线相交的点有
: 几个，依次类推
: 我知道interviewer的条件肯定正确，但是比我的条件要强

A*e2007-09-05 07:09

3 楼

这都被你看出来了

【在 t****t 的大作中提到】

: 明明是数学问题,不要打着software eng的幌子!

r*m2007-09-05 07:09

4 楼

这是因为你第一体没答对。他其实是想诱到你得到第一个问题的正确答案，你要是第一
个问题答 c^3_n-n_3 c^3_3-n_4 c^3_4......,（n_i 是i线交点的个数）根本就不会
有后面的问题。

【在 y***y 的大作中提到】

y*y2007-09-05 07:09

5 楼

但是你觉得一定要知道有多少个i线交点么？
我觉得知道总共多少个交点就可以了，因为如果两两不相交有C^2_n个点
每减少两个点就减少一个三角形

【在 r*******m 的大作中提到】

: 这是因为你第一体没答对。他其实是想诱到你得到第一个问题的正确答案，你要是第一
: 个问题答 c^3_n-n_3 c^3_3-n_4 c^3_4......,（n_i 是i线交点的个数）根本就不会
: 有后面的问题。

t*t2007-09-05 07:09

6 楼

你随便举个例子也知道不对啊...

【在 y***y 的大作中提到】

: 但是你觉得一定要知道有多少个i线交点么？
: 我觉得知道总共多少个交点就可以了，因为如果两两不相交有C^2_n个点
: 每减少两个点就减少一个三角形

p*s2007-09-05 07:09

7 楼

那你给个公式啊

【在 y***y 的大作中提到】

: 但是你觉得一定要知道有多少个i线交点么？
: 我觉得知道总共多少个交点就可以了，因为如果两两不相交有C^2_n个点
: 每减少两个点就减少一个三角形

r*m2007-09-05 07:09

8 楼

再想一想，你这个只对没有4条以上直线交于一点的情况成立。这时候三角形的个数等于
C^3_n-n_3
n_3是三线交点的个数，也就是你说的（顶点减少数/2）
但是如果有多条线交于一点就不对了。
举个例子，如果有四条线，四条线都交于一点，那么共有0个三角形。按照我给的公式
C^3_4- 0*C^3_3 -1*C^3_4=0
用你的办法试一试：
本来有C^2_4=6个顶点，现在1个损失了5个，所以三角形少了2.5个。C^3_4-2.5=1.5

【在 y***y 的大作中提到】

: 但是你觉得一定要知道有多少个i线交点么？
: 我觉得知道总共多少个交点就可以了，因为如果两两不相交有C^2_n个点
: 每减少两个点就减少一个三角形

p*b2007-09-05 07:09

9 楼

每个三角形都是由3条线组成，
每增加一条线，
每个随之增加的三角形都是由这条线与任意两条其他的线相交得来的，
而这条线和所有其他人一条线有且只有一个交点，
所以增加的三角形数目 = C(n,2) n是平面已有线的数目 n >=2
when there are n lines on the surface the total # of triangle
M = C(2,2)+C(3,2)+C(4,2)+...+C(n-1,2)