版主: 红墙 秋浦   荣誉版主: 蓝精灵 老鬼                    未登录 登录                             

首贴:     • 有关面试的数学问题,不知道这里的数学高手能弄出来不。 (182字, 点击: 556) dahuge 2010-01-26 16:29:36

大约7、8年前面试microsoft,没有搞成。有个面试的问题
俺始终没有证明、证伪。觉得这里的愚人等高手可能搞的出来。直觉是面试的老印在他妈给我出难题。

问题是这样的:给定平面上的一条连续的封闭曲线(不一定是凸的),再给定一个这样的判断函数,对于平面上的任意点,这个函数能告诉你这个点在不在曲线上。然后问,对于任意点,能不能有个算法判断这个点在曲线内还是在曲线外?



阅读次数: 556
已有跟贴:
        ° 为什么这个判断条件等式就不能用来求解? (49字, 点击: 97) 随波 2010-01-27 21:24:33
        ° 好像是CAGD中的典型问题 (114字, 点击: 151) jdchen2004 2010-01-27 06:32:54
            ° 关键是曲线方程未知,算不出交点。 (0字, 点击: 70) NE0 2010-01-27 08:56:24
            ° 这思路和我的想法差不多 (136字, 点击: 104) 红叶 2010-01-27 08:51:24
        ° 考虑离散平面 (83字, 点击: 114) 九头鸟 2010-01-26 22:12:15
        ° 瞎猜哈 (158字, 点击: 165) 天一黑 2010-01-26 22:03:38
            ° 你还真猜得有点谱,倒没有钻牛角尖:) (17字, 点击: 117) 愚人 2010-01-26 22:17:28
                ° 谢谢愚兄鼓励 (0字, 点击: 91) 天一黑 2010-01-26 22:34:40
        ° 得, 还是拉教最靠谱:) (166字, 点击: 232) xaxa2010 2010-01-26 21:04:48
            ° 你降维的思路很好,但细节有些不够吻合。 (80字, 点击: 90) NE0 2010-01-27 05:43:37
            ° 借个地方表示感谢 (130字, 点击: 140) 叶子 2010-01-26 21:12:21
                ° 千万别客气。 (10字, 点击: 100) xaxa2010 2010-01-26 21:24:15
                    ° 凑个热闹,具体实现一下xa老师的方法 (260字, 点击: 175) 叶子 2010-01-26 21:26:49
                        ° “计算出封闭曲线L上一个非凸点g” (17字, 点击: 112) xaxa2010 2010-01-26 21:32:17
                            ° 既然给出,我们就可以假定知道f的表达式 (0字, 点击: 94) 叶子 2010-01-26 21:34:42
                                ° 知道表达式是可以的, (30字, 点击: 105) xaxa2010 2010-01-26 21:42:20
                                    ° 发现一个问题,如果是个凸封闭曲线,就找不到非凸点了 (2字, 点击: 97) 叶子 2010-01-26 21:49:15
            ° 是啊,如果只给一个判断函数 (66字, 点击: 107) StarrySky 2010-01-26 21:10:23
            ° 对了,我觉得你这个是正解! (52字, 点击: 131) dahuge1 2010-01-26 21:09:58
                ° 怎么可能无解?:) (430字, 点击: 176) 愚人 2010-01-26 21:40:35
        ° 搞个矩形把曲线围起来 (27字, 点击: 118) insight 2010-01-26 20:50:07
        ° 我当时是这样回答的,好像比下面的回答都好,可是老印不认可 (149字, 点击: 225) dahuge 2010-01-26 20:02:01
            ° 你也听固执的。既然可以“逐点”判断,你就往水平方向一个方向 (399字, 点击: 169) 射论 2010-01-26 21:40:29
                ° 再试一个图,o点在图外,但他每个方向都有点挡住视线 (238字, 点击: 141) 射论 2010-01-26 21:52:04
                    ° 嗯,你这个图把我的办法否定了。但是 (20字, 点击: 79) dahuge1 2010-01-26 22:01:19
                        ° 一个方向不行 (24字, 点击: 90) dahuge1 2010-01-26 22:07:12
                            ° 8型内外都没有定义。曲线不能跟自己相交,不然内外定义就 (34字, 点击: 87) 射论 2010-01-26 22:31:01
                                ° 你这就不对了,任何人都可以用肉眼告诉你某点在8型内外 (14字, 点击: 95) dahuge1 2010-01-26 22:43:00
                                    ° 不连续呀,到了中间那个地方有两种走法,可以相画葫芦 (21字, 点击: 68) 射论 2010-01-26 22:49:29
                        ° 一个方向就可以。但你得小心相切的情况 (0字, 点击: 63) 射论 2010-01-26 22:02:26
                    ° 你如果沿着任何一个方向数交点,都是偶数,说明在外 (0字, 点击: 69) 射论 2010-01-26 21:58:31
                ° 你没懂我逐点判断的意思 (62字, 点击: 85) dahuge1 2010-01-26 21:49:22
                    ° 都交不到一个点就表示在曲线外。如果已经出了曲线的界 (0字, 点击: 76) 射论 2010-01-26 21:53:05
                        ° 总得知道曲线在x或y某一方向的范围(比如小于1000或大于100) (0字, 点击: 77) 射论 2010-01-26 21:57:34
                            ° 我们的意见基本统一了。:) (0字, 点击: 68) dahuge1 2010-01-26 22:02:18
                ° 空格被吃掉了。图形可以想象一条带子逐渐旋转出来。带子边界为 (3字, 点击: 68) 射论 2010-01-26 21:45:56
            ° 你这回答象是象个小孩的想法- 完全不顾题目条件 (0字, 点击: 74) darkforce 2010-01-26 20:38:16
            ° 给一点思路,看行不行?:) (747字, 点击: 188) 愚人 2010-01-26 20:36:59
                ° 请愚老师给鉴定一哈 (130字, 点击: 113) 叶子 2010-01-26 21:33:08
                    ° 我刚才回答你的帖子怎么没有显示出来? (142字, 点击: 118) 愚人 2010-01-26 22:14:11
                        ° 你说得对,应该用程序员的思维方法,一切从实现考虑 (39字, 点击: 95) 叶子 2010-01-26 22:36:35
            ° 你这回答象是象个小孩的想法 (0字, 点击: 66) darkforce 2010-01-26 20:34:04
        ° 我提一个想法 (181字, 点击: 185) StarrySky 2010-01-26 20:00:12
            ° 这是离散问题:) (0字, 点击: 75) 愚人 2010-01-26 20:40:14
                ° 离散问题也能做积分,只是设立一个精度判断而已 (0字, 点击: 76) StarrySky 2010-01-26 20:42:18
                    ° 曲线可以不能表成函数关系,怎么积分?:) (55字, 点击: 98) 愚人 2010-01-26 21:00:38
            ° 你对曲线一无所知,你如何能找到曲线上的点? (21字, 点击: 102) dahuge 2010-01-26 20:04:06
                ° 不是已经“给定平面上的一条连续的封闭曲线”? (77字, 点击: 114) StarrySky 2010-01-26 20:09:33
                    ° 这个函数是条件,不是目标 (0字, 点击: 84) dahuge 2010-01-26 20:19:34
                        ° 那就更严谨了,排除了我前面的第三个可能 (332字, 点击: 190) StarrySky 2010-01-26 20:29:06
                            ° 可能是我题目没说清楚,你理解错了。 (161字, 点击: 113) dahuge1 2010-01-26 20:54:35
            ° z[a]=z[b]保证封闭 (0字, 点击: 60) StarrySky 2010-01-26 20:01:51
        ° 矢量图形的rasterization过程中有类似问题。比如你要 (113字, 点击: 115) 射论 2010-01-26 19:38:33
            ° 你对这个曲线的信息只有一个判断某点是否在其上的函数, (57字, 点击: 105) dahuge 2010-01-26 19:55:30
                ° 你是去软件公司面试,电脑没法处理精度无限的数字 (13字, 点击: 96) 射论 2010-01-26 20:11:16
                ° 如果只能判断精度无限的点,这个问题无解 (0字, 点击: 76) 射论 2010-01-26 20:05:40
        ° 封闭曲线所围的面积是个有限数, 给定平面的面积无穷大. (45字, 点击: 148) lightyear 2010-01-26 18:20:48
            ° 你的理解能力很可笑 (0字, 点击: 77) darkforce 2010-01-26 19:09:08
            ° 这就太不像话了:):) (0字, 点击: 71) xaxa2010 2010-01-26 18:27:03
        ° 由Jordan curve theorem, (68字, 点击: 201) xaxa2010 2010-01-26 17:54:44
            ° bingo,取足够远一点就可以。 (0字, 点击: 68) 诸葛光 2010-01-27 13:23:34
            ° 算法讲的是可操作性,你的这个办法没有可编程性 (24字, 点击: 143) dahuge 2010-01-26 18:40:46
                ° 只要曲线是有界的-比方说X或Y坐标有个知道的最大最小值 (24字, 点击: 112) darkforce 2010-01-26 19:07:46
                    ° 这得是个CS的问题, 否则没法弄。 (30字, 点击: 142) xaxa2010 2010-01-26 19:18:41
                        ° MS面试题,这些肯定是可以的-线段就不必了-都是PIXEL-一点一点的 (0字, 点击: 86) darkforce 2010-01-26 20:32:38
                            ° 然,ray casting algorithm换了换, 题目还是不错的。 (0字, 点击: 78) xaxa2010 2010-01-26 21:08:45
        ° 你被花招玩了:前一个条件和后一个结论,没有关系的 (78字, 点击: 184) 木水 2010-01-26 17:26:51
            ° 如果有办法,讲讲看嘛。 (0字, 点击: 60) dahuge 2010-01-26 18:41:45
        ° 如果是凸的,任意点如果可以表示是曲线上某些点的线性组合 (18字, 点击: 133) 响马 2010-01-26 17:14:58

_______________________________
Copyright © 2000 - 2020 redwall