`
mars914
  • 浏览: 432567 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

螺旋队列算法设计

阅读更多

21    22    23    24     25
20    7      8       9     10
19    6      1       2     11
18    5      4       3     12
17    16    15    14     13

        看清以上数字排列的规律,设1点的坐标是(0,0),x方向向右为正,y方向向下为正.例如:7的坐标为(-1,-1) ,2的坐标为(0,1),3的坐标为(1,1).编程实现输入任意一点坐标(x,y),输出所对应的数字。


        解析:规律能看出来,问题就在于如何利用它。很明显这个队列是顺时针螺旋向外扩展的,我们可以把它看成一层一层往外延 伸。第 0 层规定为中间的那个 1,第 1 层为 2 到 9,第 2 层为 10 到 25,注意到 1、9、25、……不就是平方数吗?而且是连续奇数(1、3、5、……)的平方数。这些数还跟层数相关,推算一下就可以知道第 t 层之内一共有 (2t-1)^2 个数,因而第 t 层会从 [(2t-1)^2] + 1 开始继续往外螺旋。给定坐标 (x,y),如何知道该点处于第几层?层数 t = max(|x|,|y|)。知道了层数,接下来就好办多了,这时我们就知道所求的那点一定在第 t 层这个圈上,顺着往下数就是了。要注意的就是螺旋队列数值增长方向和坐标轴正方向并不一定相同。我们可以分成四种情况——上、下、左、右——或者——东、南、西、北,分别处于四条边上来分析。


  东|右:x == t,队列增长方向和 y 轴一致,正东方向(y = 0)数值为 (2t-1)^2 + t,
    所以 v = (2t-1)^2 + t + y
  南|下:y == t,队列增长方向和 x 轴相反,正南方向(x = 0)数值为 (2t-1)^2 + 3t,
    所以 v = (2t-1)^2 + 3t - x
  西|左:x == -t,队列增长方向和 y 轴相反,正西方向(y = 0)数值为 (2t-1)^2 + 5t,
    所以 v = (2t-1)^2 + 5t - y
  北|上:y == -t,队列增长方向和 x 轴一致,正北方向(x = 0)数值为 (2t-1)^2 + 7t,
    所以 v = (2t-1)^2 + 7t + x


  其实还有一点很重要,不然会有问题。其它三条边都还好,但是在东边(右边)那条线上,队列增加不完全符合公式!注意 到东北角(右上角)是本层的最后一个数,再往下却是本层的第一个数,那当然不满足东线公式啊。所以我们把东线的判断放在最后(其实只需要放在北线之后就可 以),这样一来,东北角那点始终会被认为是北线上的点。

 

答案:代码如下:

#include <stdio.h>
#define max(a,b) ((a)<(b)?(b):(a))
#define abs(a) ((a)>0?(a):-(a))
int foo(int x, int y)
{
    int t = max(abs(x), abs(y));
    int u = t + t;
    int v = u - 1;
    v = v * v + u;
    if (x == - t)
        v += u + t - y;
    else if (y == - t)
        v += 3 * u + x - t;
    else if (y == t)
        v += t - x;
    else
        v += y - t;
    return v;
}

int main()
{
    int x, y;
    for (y = - 4; y <= 4; y++)
    {
        for (x = - 4; x <= 4; x++)
            printf("%5d", foo(x, y));
            printf("\n");
    }
    while (scanf("%d%d", &x, &y) == 2)
        printf("%d\n", foo(x, y));
    return 0;
}

 

分享到:
评论

相关推荐

    【Linux】关于螺旋队列算法的精讲

    螺旋队列算法是一种特定的数据结构处理方式,在算法设计和实现领域具有一定的研究价值。特别是在软件开发过程中,它能够帮助开发者更好地理解和操作复杂的数据结构,提升程序效率。 #### 理解螺旋队列算法 螺旋...

    螺旋阵列_C++_算法

    螺旋阵列,输入坐标,显示阵列对应数 螺旋矩阵

    基于螺旋线的Round-Robin Crossbar调度算法

    1. **路径规划**:首先需要设计出一条螺旋路径,该路径应覆盖所有的输入输出端口组合。 2. **请求管理**:对于每个输入端口而言,需要维护一个队列来记录待处理的请求,并根据Round-Robin机制更新队列中的请求顺序。...

    栈和队列源代码

    7. **最小生成树的Prim算法**:Prim算法在构造最小生成树时,使用优先队列(如Java的PriorityQueue)存储待考虑的边。 通过学习和理解这些源代码,你可以深入理解栈和队列的工作原理,提高解决实际问题的能力,并为...

    软件工程的数据结构与算法.pptx

    算法设计的基本方法包括算法定义、算法设计、算法分析等。快速排序、归并排序、堆排序、冒泡排序等都是常见的排序算法。深度优先搜索、广度优先搜索等都是常见的图遍历算法。 数据结构与数据库 数据结构与数据库是...

    高速数字振动信号无线接收螺旋缓冲算法

    【高速数字振动信号无线接收螺旋缓冲算法】是针对nRF24L01+无线设备在传输32字节数据包时可能出现的数据包粘连和不连续问题而提出的一种解决方案。这种问题会导致接收数据的不完整性和实时性降低,尤其在大数据量的...

    经典算法大全

    数据结构的设计和操作对算法效率有很大影响。 12. **其他经典问题** 其他经典问题包括约瑟夫问题(Josephus Problem)、排列组合、格雷码(Gray Code)、魔方阵构造等。 这些算法和问题不仅在学术上具有重要价值...

    JavaScript版 数据结构与算法

    2-3 反转单词代码演示 2-4 计算子串原理讲解 试看 2-5 计算子串代码演示第3章 基础算法之“数组类”数组是JS世界里必不可少的类型,“小小”的数组,“大大”的世界,一维、二维空间、组合、分组、堆栈、队列等等都...

    0.《程序设计课程设计》指导书(2018版)1

    这将涉及到数据结构(如优先队列)和算法设计。 5. **最小生成树**:这个设计题目涉及到图论,要求学生构建一个算法来连接n个城市,使得边的总权重最小。Prim或Kruskal算法可能会被用到。 6. **学生信息管理系统**...

    算法数据结构面试40讲.txt

    - **矩阵操作**: 处理二维数组的问题,例如螺旋矩阵、路径搜索等。 - **链表操作**: 如链表反转、合并两个有序链表等经典问题。 - **递归与迭代**: 掌握递归的基本原理及其在实际问题中的应用,同时学会如何将递归...

    C语言算法(nolock)

    书中还专门讨论了数组的各种操作,包括数组转换、螺旋数组生成、杨辉三角形的编程实现等。 在编程竞赛和实际应用方面,书中提供了大量的编程题目和经典的C语言程序,如绘制图形、算法优化、数据处理等。这些内容...

    数据结构与算法 腾讯精选练习50 V1.0.pdf

    上述内容涉及了数据结构中的链表、栈、队列、树和图等概念,算法方面则包括了二分查找、动态规划、递归、回溯、哈希、排序、搜索等基础算法技巧。通过对这些具体问题的练习,学习者可以深化对数据结构与算法知识的...

    软件设计师考试题型与技巧

    上午主要是选择题(75 题 75 分),涵盖了计算机组成原理、编译原理、计算机操作系统、计算机网络、数据库设计、数据结构、算法设计、软件工程、面向对象与设计模式等知识点。下午为 6 道大题(6 题 75 分,其中五/...

    史上最全经典数据结构算法c语言实现代码合集

    N皇后问题回溯算法.txt ping.txt re.txt source.txt winsock2.txt ww.txt 万年历.txt 万年历的算法 .txt 乘方函数桃子猴.txt 乘法矩阵.txt 二分查找1.txt 二分查找2.txt 二叉排序树.txt 二叉树.txt ...

    经典数据结构算法c语言实现代码(大全)

    N皇后问题回溯算法.txt ping.txt re.txt source.txt winsock2.txt ww.txt 万年历.txt 万年历的算法 .txt 乘方函数桃子猴.txt 乘法矩阵.txt 二分查找1.txt 二分查找2.txt 二叉排序树.txt 二叉树.txt ...

    第2届Mathorcup数学建模竞赛优秀论文-A题-A题最佳飞行队列.doc

    飞行队列的研究对于理解自然界的生物行为(如大雁迁徙)以及人工系统的优化设计(如战斗机编队)都具有重要意义。通过数学建模可以更深入地了解不同队列形式对能源消耗的影响,进而指导实际应用。 **模型构建**: ...

    数据结构及算法C语言实现代码集[推荐下载]

    效验算法 数学问题 数据结构 数组 文件程序 求进制 汉诺塔 硬币情况 逆阵 链串.c 链栈.c 链队列.c 问题算法 顺序栈.c 顺序表.c 顺序队列.c ./其它&#58; c语言窗体实例.zip 傻瓜递归.c 冒泡法改进.c 小字库DIY-.c 小...

    luoxuan.rar_螺旋

    螺旋矩阵是一种特殊的矩阵...总的来说,“luoxuan.rar_螺旋”是一个用于学习和理解螺旋矩阵生成算法的实例,对于初学者来说,可以通过阅读和分析“luoxuan.cpp”代码,掌握如何用C++编程语言实现这种特定的矩阵排列。

Global site tag (gtag.js) - Google Analytics