V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
XiongZaizi
V2EX  ›  算法

一道挺好玩的算法题,不知道各位有没有更好的想法

  •  
  •   XiongZaizi · 2017-05-16 10:01:44 +08:00 · 4348 次点击
    这是一个创建于 2749 天前的主题,其中的信息可能已经有所发展或是发生改变。

    小弟这几天在做算法题目,看到一个很 interesting 的题目,贴图如下: 题目

    简单描述下题目内容:这根木棍向右倒,在经过点 a 坐标之后,下一次在重合到一点时,输出离原点最近的那一点的坐标。 举个栗子:如下图

    栗子

    上图重合点是 5,3 这个点,接下来重合的点是 2,1 4,2 6,3 那么离原点最近的点就是 2,1。

    我的想法就是: 1、穷举出木棍 l 能扫过的所有的点,然后计算每个点到原点的距离,以及和横轴的夹角。按照角度进行快速排序;

    2、计算与点 a 重合时,木棍和横轴的夹角,抽取出小于该夹角的所有点

    3、对抽取出来的点按照距离进行一次遍历,找到距离原点最小的点进行输出

    总感觉这个算法有点复杂,不知道有没有更巧妙地算法?还请大家开动脑洞讨论讨论

    35 条回复    2017-05-16 22:55:15 +08:00
    grimpil
        1
    grimpil  
       2017-05-16 10:40:27 +08:00 via Android
    题目看不明白。点 a 是哪个点?重合到一点是什么意思?
    blankme
        2
    blankme  
       2017-05-16 10:48:21 +08:00 via Android
    建议贴原题,不要“简单描述题目内容”,你根本没描述清楚题目。
    yangff
        3
    yangff  
       2017-05-16 10:54:13 +08:00
    没理解错的话,没跨过(1,1)之前最近的是(1,1),跨过(x,1)之后最近的是(x+1,1);因为只需要考虑 gcd(x,y)==1 的点,所以扫过符合要求的 x 的时候,每个 x 显然能符合要求的最小的 y 是 1
    XiongZaizi
        4
    XiongZaizi  
    OP
       2017-05-16 11:01:35 +08:00
    @blankme 原题是日语的,我只能简单的进行翻译了。。。哪里不明白可以说一下
    jmc891205
        5
    jmc891205  
       2017-05-16 11:04:37 +08:00
    那些斜率一样的点只要记一个到原点距离最小的就可以了
    这样你的第一步快排之后就有了一个按斜率(角度)递增的数组
    之后只要拿 A 点的斜率做一次二分查找 找到的那个点的前一个点就是结果
    XiongZaizi
        6
    XiongZaizi  
    OP
       2017-05-16 11:04:49 +08:00
    @grimpil a 是随机输入的一个点,是棍子能够扫到的任何一点;重合到一点就是就是棍子在向下扫的时候,接触到的点。可以看第二个图,图中画的那条线就假设是棍子,在向下倒的时候,接触到了 5,3 这个点,这种情况就叫做重合
    Vinty
        7
    Vinty  
       2017-05-16 11:05:59 +08:00
    大概就是求一个比 a/b 小的最大的两个整数之比 x/y,x/y 有公约数,化简一下即可
    whalegia
        8
    whalegia  
       2017-05-16 11:08:27 +08:00
    重合是什么意思?
    为什么 ( 5,3 )后是( 2,1 ),( 2,1 )后是( 4,2 )?
    感觉我哪里都不明白,对不去语文老师
    XiongZaizi
        9
    XiongZaizi  
    OP
       2017-05-16 11:08:34 +08:00
    @jmc891205 有道理呢,这样能减少很大一部分的操作量了。多谢了
    XiongZaizi
        10
    XiongZaizi  
    OP
       2017-05-16 11:14:10 +08:00
    @whalegia 第二张图中实线是假设的棍子,这根棍子没有题目中的那么长,此时棍子接触到了点 5,3,棍子继续向下倒的时候,最先接触点 2,1,再接触点 4,2。
    Vinty
        11
    Vinty  
       2017-05-16 11:14:57 +08:00
    接 7l,这个值应该等于(ma-1)/(mb-1),m 是令该点在可行域内的最大整数
    XiongZaizi
        12
    XiongZaizi  
    OP
       2017-05-16 11:15:44 +08:00
    @yangff 那这样看来只有 y=1 的点是符合要求的,说的有道理
    XiongZaizi
        13
    XiongZaizi  
    OP
       2017-05-16 11:25:41 +08:00
    @Vinty “大概就是求一个比 a/b 小的最大的两个整数之比 x/y,x/y 有公约数,化简一下即可”,这一步是求出下一个杰出的点的吧?还有后面那个公式是咋计算的?
    liuminghao233
        14
    liuminghao233  
       2017-05-16 14:00:41 +08:00 via iPhone
    根本就不知道你在说什么 什么 a 点
    Vinty
        15
    Vinty  
       2017-05-16 14:37:41 +08:00
    @XiongZaizi 11l 的公式是我猜的,好像不对。。一是只考虑了小于 45°的情况,二是对可行域处理的不好。如果点的数量比较少的话,就列出可行域内的所有点按正切值做个排序就行了。如果是点非常复杂的话,那就找到目前过( a,b )这条线和边界的交点( u,v ),向下取整得到( u',v')。比较( u',v'),( u'+1,v'),( u',v'-1 ),( u'+1,v'-1 )四点即可,也许还有( u'-1,v'-1 )。
    反正就是比较周围几个点看在不在可行域内哪个最大,具体哪几个也许可以简化一下。
    imn1
        16
    imn1  
       2017-05-16 15:16:55 +08:00
    下一次在重合到一点时,输出离原点最近的那一点的坐标
    -------------------------------------------------------------------------
    这句话是要再解释清楚的

    “下一次在重合到一点时”,换言之,重合 A 到这次重合中间没有再重合任何点了,下半句“那一点”指的是什么?
    lingo
        17
    lingo  
       2017-05-16 18:04:39 +08:00
    哈哈哈哈哈题目看不懂
    XiongZaizi
        18
    XiongZaizi  
    OP
       2017-05-16 18:10:40 +08:00
    @Vinty 恩恩,谢谢了,这样也是一种方法
    XiongZaizi
        19
    XiongZaizi  
    OP
       2017-05-16 18:16:41 +08:00
    @imn1 就是棍子在向下倒的这个过程中,会接触到点格中的点,那么假设其中有一时刻棍子和给定的能够接触到的点 a 接触了记为时刻 t1,从这一时刻起开始,棍子继续向下倒,又会接触一个新的点 b,时刻记为 t2。这 t1 和 t2 两个时刻之间,棍子没有和任何的点接触。所要求的就是从 t1 时刻开始,到棍子最终倒在横轴上这一段时间里,棍子所能接触到的所有点中,距离原点最小的一点。
    ZyZyZzz
        20
    ZyZyZzz  
       2017-05-16 18:24:47 +08:00
    你直接把日语题干贴出来吧,这里有的是人懂日语
    不懂的还可以去机翻
    GtDzx
        21
    GtDzx  
       2017-05-16 18:36:57 +08:00
    感觉就是个排序题。按极角和距离排序不就完了...
    hxsf
        22
    hxsf  
       2017-05-16 18:38:15 +08:00 via iPhone
    有意思的题目。
    回家电脑码字
    imn1
        23
    imn1  
       2017-05-16 18:55:57 +08:00
    A(x0, y0)
    棍长 s0
    所经过的点 Pn(xn, yn)

    Pn 满足
    Xn<=S0 && Yn/Xn 反正切的角度<Y0/X0 反正切角度

    Pn 到原点距离 Sn
    Sn^2 = Xn^2 + Yn^2 = (Xn + Yn)^2 - 2*Xn*Yn
    所以,Xn + Yn 最小值为所求
    当有两点或以上满足此条件时,Xn 与 Yn 数值最接近的为所求
    blankme
        24
    blankme  
       2017-05-16 19:36:28 +08:00 via Android
    y = 1
    x = min(n), where arctan(1 / n) < arctan(y0 / x0)
    hxsf
        25
    hxsf  
       2017-05-16 19:43:07 +08:00
    到家,开更。

    最暴力的方法,算一下每个点的角坐标(θn, ln),排除掉 ln > l 棍 和 角度小于 点 a 的,然后根据θn 排序。取第一个。

    ==========================当然不是这么简单啦==============================

    我们真的需要算这么多点么?

    其实我们要算的,只有 线段 OA 附近的点啊。( O 指原点,A 点坐标设为( a,b ))

    OA 附近的点(记为集合 D )如何得出?

    D 中的[ (x1, y1),(x2, y2),……(xn, yn)] 满足

    1. x 属于 0~Xmax 上的所有整数
    由数学方案可知,Xmax = a * 根号( L 棍^2 - a^2 - b^2 ), 及 n = int ( Xmax )
    2. 因为要找 yn/xn 尽可能大的,所以 yn < xn * b/a 的基础上, yn > yn-1 + 1

    于是要计算的点就变成这样:



    完结!
    hxsf
        26
    hxsf  
       2017-05-16 19:45:08 +08:00
    @hxsf #25

    更正

    >>>>>>>>>>
    2. 因为要找 yn/xn 尽可能大的,所以 yn < xn * b/a 的基础上, yn > yn-1 + 1
    ==========
    2. 因为要找 yn/xn 尽可能大的,所以 yn < xn * b/a 的基础上, yn > yn-1
    <<<<<<<<<<

    忘记说了。红色点是要算的点,蓝色点是 满足 yn < xn * b/a 但不满足 yn > yn-1
    XiongZaizi
        27
    XiongZaizi  
    OP
       2017-05-16 21:05:53 +08:00
    @imn1 那这样还是要穷举计算出所有的点,感觉如果 l 很大的话计算量会很多
    XiongZaizi
        28
    XiongZaizi  
    OP
       2017-05-16 21:17:14 +08:00
    @hxsf 学习了。但是我有点没有明白 xmax 的计算公式是怎样得到的?
    hxsf
        29
    hxsf  
       2017-05-16 21:25:04 +08:00   ❤️ 1
    @XiongZaizi #28

    你一说发现算错了。。。尴尬

    下面是正确算法

    棍子与 A(a, b)重合时的 端点 B 设为 (na, nb)

    (na)^2 + (nb)^2 = l^2

    就可以算出来了 n^2 = l^2 / (a^2 + b^2)

    na = a * 根号( l^2 / (a^2 + b^2) )
    XiongZaizi
        30
    XiongZaizi  
    OP
       2017-05-16 21:30:22 +08:00
    @hxsf 哦哦哦,明白了,是按照比例算的。按照你的方法,可以减少很多计算量,多谢!!!
    XiongZaizi
        31
    XiongZaizi  
    OP
       2017-05-16 21:33:29 +08:00
    imn1
        32
    imn1  
       2017-05-16 21:57:49 +08:00
    @XiongZaizi
    怎么需要穷举所有点呢?

    所有的点都是已知坐标的吧?
    从最小值开始计算角度是否符合就够了
    如果是要尽可能大,就从 Xn<=S0 最大值开始,只要(Xn_1<Xn && Yn_1<Yn)符合就可以结束了
    bumz
        33
    bumz  
       2017-05-16 22:00:07 +08:00
    @XiongZaizi #31 这是什么书呀
    XiongZaizi
        34
    XiongZaizi  
    OP
       2017-05-16 22:53:44 +08:00
    @imn1 啊,有理。一时没转过弯来
    XiongZaizi
        35
    XiongZaizi  
    OP
       2017-05-16 22:55:15 +08:00
    @bumz 基友正在看的书,我也不知道叫啥。今天偶然开始讨论起来的题目。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2959 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 14:16 · PVG 22:16 · LAX 06:16 · JFK 09:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.