V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
bianhua
V2EX  ›  问与答

算法:(数列||矩阵)问题求解

  •  
  •   bianhua · 2017-05-15 12:51:50 +08:00 · 1715 次点击
    这是一个创建于 2733 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有这样一个(数列||矩阵)

    20 21 22 23 24 ..
    19 06 07 08 09
    18 05 00 01 10
    17 04 03 02 11
    16 15 14 13 12
    

    它的特征是,数字从最中间的元素称螺旋状展开,其中的元素可以有无限个。

    楼主的问题是:

    • 1、这种(数列||矩阵)叫什么?
    • 2、给定一个数字 N,如何求与它相邻的元素?

    比如 当 N = 0,它的邻居就是:

    06 07 08
    05 00 01
    04 03 02
    

    当 N = 02,它的邻居就是:

    00 01 10
    03 02 11
    14 13 12
    

    由于数字可以是无限个,那么基本上不可能将元素映射到一个有限集合里算了(比如用一个固定长宽的数组来计算座标之类)。

    楼主是个算法渣,如果这个问题很菜的话,求轻拍

    8 条回复    2017-05-15 14:58:57 +08:00
    sean10
        1
    sean10  
       2017-05-15 13:10:35 +08:00 via iPhone   ❤️ 1
    不明白你说的无限是什么意思,这个不是就叫螺旋矩阵吗
    Mistwave
        2
    Mistwave  
       2017-05-15 13:27:49 +08:00   ❤️ 1
    1. 这个就叫螺旋矩阵

    2. 思考了一下(同算法渣),没有找到给定 N,不建立矩阵直接给出其邻居的方法。还是只能先通过给定 N 建立矩阵,然后去矩阵里面搜索。可以有这些优化方式:快速建立矩阵的方式;保存之前建立的矩阵;在已有矩阵上增量添加。
    bianhua
        3
    bianhua  
    OP
       2017-05-15 13:49:59 +08:00
    @sean10 楼主好傻,之前一直在搜索“螺旋数列”
    @Mistwave 好的,感谢。看来我需要在建立这些数列之前先建立他们的对应关系。还好这并不碍事。
    wuyukai
        4
    wuyukai  
       2017-05-15 14:19:19 +08:00   ❤️ 1
    找找规律吧,简单的绘了个图,通过规律可以得出每一层的边长和四个顶点的值,通过你给定的 N,以起点和终点的值作为范围,求出层数 n 的值。然后边长就可以得出了,以一个点为中心,找其余八个点,主要找左右两侧的点,也就是相邻层的数值,根据的就是边长,按它的绕行方式推算回去,对于一些特殊情况,自己再加以判断,N 落在四条不同的边上还是有不同的区别的,大概就这思路吧。
    ![20170515149482877456134.jpg]( http://ofrdtlim5.bkt.clouddn.com/20170515149482877456134.jpg)
    blankme
        5
    blankme  
       2017-05-15 14:27:01 +08:00 via Android   ❤️ 1
    算算螺旋线的长度就知道 f(x, y)了
    blankme
        6
    blankme  
       2017-05-15 14:32:58 +08:00 via Android   ❤️ 1
    因为图形正好是矩形,所以比较简单的算法就是
    中间区域的面积 + 最外面不完整的那圈的长度
    bianhua
        7
    bianhua  
    OP
       2017-05-15 14:37:19 +08:00
    @wuyukai
    @blankme

    感谢,信息量比较大楼主先消化下。
    wuyukai
        8
    wuyukai  
       2017-05-15 14:58:57 +08:00 via Android   ❤️ 1
    @bianhua 每一层的长度是 8*(n-1),8+16+24+...这样推
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5104 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 36ms · UTC 01:13 · PVG 09:13 · LAX 17:13 · JFK 20:13
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.