【算法题】螺旋矩阵I (求解n阶螺旋矩阵问题)

这篇具有很好参考价值的文章主要介绍了【算法题】螺旋矩阵I (求解n阶螺旋矩阵问题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、问题的提出

螺旋矩阵是一种常见的矩阵形式,它的特点是按照螺旋的方式排列元素。n阶螺旋矩阵是指矩阵的大小为n×n,其中n为正整数。

【算法题】螺旋矩阵I (求解n阶螺旋矩阵问题),算法,矩阵,python,经验分享

 二、解决的思路

当N=1时,矩阵为;

当N=2时,矩阵为;

当N>2(N为偶数如N=4)时,矩阵为;


当N>2(N为奇数如N=5)时,矩阵为。

【算法题】螺旋矩阵I (求解n阶螺旋矩阵问题),算法,矩阵,python,经验分享

图1 螺旋矩阵分析图

三、递推法解题

从上思路分析和图1可知,当N>2时可分为k(k=N//2)个四边形的螺旋框,每边长为框长度(n)-1(即n-1),只是左上角的起始值和边框长度不同而已。如N为奇数,则正中心还有一个终值N²。

因此可用用递推来计算。

程序代码如下:

N = 5
def prt(b):                           # 打印二维列表
    for i in range(N):
        for j in range(N):
            print("%3d" % b[i][j], end='')
        print()

def Helix_Matrix(N):
    matrix = []                       # 初始化二维矩阵matrix(二维列表)
    for i in range(N):
        matrix.append([])
        for j in range(N):
            matrix[i].append(0)
    matrix[N//2][N//2] = N*N          # 若N为奇数时,正中间为N²
    cnt = 0
    n = N
    for k in range(N//2):
        for j in range(n-1):          # 矩形上边,从左向右
            cnt += 1
            matrix[k][k+j] = cnt
        for i in range(n-1):          # 矩形右边,从上往下
            cnt += 1
            matrix[k+i][k+n-1] = cnt
        for j in range(n-1):          # 矩形下边,从右向左
            cnt += 1
            matrix[k+n-1][k+n-1-j] = cnt
        for i in range(n-1):          # 矩形左边,从下往上
            cnt += 1
            matrix[k+n-1-i][k] = cnt
        n -= 2                        # 缩小规模时,矩形边长减2
    return matrix

hm = Helix_Matrix(N)
prt(hm)

执行结果:

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

回到开头的题目,则

def Helix_Matrix(N):
    matrix = []                    # 初始化二维矩阵matrix(二维列表)
    for i in range(N):
        matrix.append([])
        for j in range(N):
            matrix[i].append(0)
    matrix[N//2][N//2] = N*N       # 若N为奇数时,正中间为N²
    cnt = 0
    n = N
    for k in range(N//2):
        for j in range(n-1):       # 矩形上边,从左向右
            cnt += 1
            matrix[k][k+j] = cnt
        for i in range(n-1):       # 矩形右边,从上往下
            cnt += 1
            matrix[k+i][k+n-1] = cnt
        for j in range(n-1):       # 矩形下边,从右向左
            cnt += 1
            matrix[k+n-1][k+n-1-j] = cnt
        for i in range(n-1):       # 矩形左边,从下往上
            cnt += 1
            matrix[k+n-1-i][k] = cnt
        n -= 2                     # 缩小规模时,矩形边长减2
    return matrix

n, i, j = map(int,input().split())
hm = Helix_Matrix(n)
print(hm[i-1][j-1])

输入4 2 3,输出为14。

四、递归法解题

当规模为1时直接填写(1个元素),见“二、解决的思路,结束递归;

当规模为2时直接填写(4个元素),见“二、解决的思路,结束递归;

当规模大于2时直接先写本圈(k)四边,见“二、解决的思路,再缩小规模递归调用。

这就是递归计算算法。

程序代码如下:

N = 6
def prt(b):                           # 打印二维列表
    for i in range(N):
        for j in range(N):
            print("%3d" % b[i][j], end='')
        print()

def Helix_Matrix(n,k,cnt):
    if n == 1:                        # 规模为1
        matrix[k][k] = cnt
    elif n == 2:                      # 规模为2
        matrix[k][k] = cnt
        cnt += 1
        matrix[k][k+1] = cnt
        cnt += 1
        matrix[k+1][k+1] = cnt
        cnt += 1
        matrix[k+1][k] = cnt
    else:                             # 规模大于2
        for j in range(n-1):          # 矩形上边,由左向右
            matrix[k][k+j] = cnt
            cnt += 1
        for i in range(n-1):          # 矩形右边,由上往下
            matrix[k+i][k+n-1] = cnt
            cnt += 1
        for j in range(n-1):          # 矩形下边,由右向左
            matrix[k+n-1][k+n-1-j] = cnt
            cnt += 1
        for i in range(n-1):          # 矩形左边,由下往上
            matrix[k+n-1-i][k] = cnt
            cnt += 1
        Helix_Matrix(n-2, k + 1, cnt) # 递归,缩小螺旋矩阵规模

matrix = []                           # 初始化二维矩阵matrix(二维列表)
for i in range(N):
    matrix.append([])
    for j in range(N):
        matrix[i].append(0)
Helix_Matrix(N,0,1)                   # 初始n=N, k=0, cnt=1
prt(matrix)

执行结果:

1 2 3 4 5 6
20 21 22 23 24 7
19 32 33 34 25 8
18 31 36 35 26 9
17 30 29 28 27 10
16 15 14 13 12 11

 回到开头的题目,则

def Helix_Matrix(n,k,cnt):
    if n == 1:                       # 规模为1
        matrix[k][k] = cnt
    elif n == 2:                     # 规模为2
        matrix[k][k] = cnt
        cnt += 1
        matrix[k][k+1] = cnt
        cnt += 1
        matrix[k+1][k+1] = cnt
        cnt += 1
        matrix[k+1][k] = cnt
    else:                             # 规模大于2
        for j in range(n-1):          # 矩形上边,由左向右
            matrix[k][k+j] = cnt
            cnt += 1
        for i in range(n-1):          # 矩形右边,由上往下
            matrix[k+i][k+n-1] = cnt
            cnt += 1
        for j in range(n-1):          # 矩形下边,由右向左
            matrix[k+n-1][k+n-1-j] = cnt
            cnt += 1
        for i in range(n-1):          # 矩形左边,由下往上
            matrix[k+n-1-i][k] = cnt
            cnt += 1
        Helix_Matrix(n-2, k + 1, cnt) # 递归,缩小螺旋矩阵规模

N, x, y = map(int,input().split())
matrix = []                           # 初始化二维矩阵matrix(二维列表)
for i in range(N):
    matrix.append([])
    for j in range(N):
        matrix[i].append(0)
Helix_Matrix(N,0,1)                   # 初始n=N, k=0, cnt=1
print(matrix[x-1][y-1])

输入4 2 3,输出为14。文章来源地址https://www.toymoban.com/news/detail-643043.html

到了这里,关于【算法题】螺旋矩阵I (求解n阶螺旋矩阵问题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 整数规划——分支界定算法(旅行商问题,规约矩阵求解)

    一、普通优化问题分枝定界求解 题目的原问题为   在计算过程中,利用MATLAB中的linprog()函数进行求解最优解,具体的计算步骤如下: A为约束系数矩阵,B为等式右边向量,C为目标函数的系数向量。   进行第一次最优求解以A=[2 9;11 -8],B=[40;82],C=[-3,-13]利用linprog函数求解。解

    2024年02月16日
    浏览(37)
  • 算法刷题-数组-螺旋矩阵

    力扣题目链接 给定一个正整数 n,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。 示例: 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] 这道题目可以说在面试中出现频率较高的题目, 本题并不涉及到什么算法,就是模拟过程,但却十分考察对代

    2024年02月08日
    浏览(53)
  • 【常用算法】螺旋矩阵

    目录 1. 螺旋矩阵 2. 螺旋矩阵 II 3. 螺旋矩阵 III 4. 螺旋矩阵 IV 题目描述: 给你一个m行n列的矩阵matrix,请按照顺时针螺旋顺序 ,返回矩阵中的所有元素。 提示: m == matrix.length n == matrix[i].length 1 = m, n = 10 -100 = matrix[i][j] = 100 题解: 4×5的矩阵按顺时针螺旋顺序打印如图所示。

    2024年02月12日
    浏览(33)
  • 【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵

    废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是螺旋矩阵,使用【二维数组】这个基本的数据结构来实现 二维数组的结构特性入手 根据题目示例 matrix = [[1,2,3],[4,5,6],[7,8,9]] 的对应输出 [1,2,3,6,9,8,7,4,5] 可以发现,顺时针打印矩阵的顺序

    2024年02月06日
    浏览(51)
  • 面试项目算法 - 数桥问题python求解

    本项目基于一个流行的日本谜题--\\\"Hashiwokakero\\\"、\\\"Hashi \\\"或 \\\"Bridges\\\"。你需要编写一个程序来解决这个谜题,并简要说明你所使用的算法和数据结构。 程序的输入将是一个由数字和点组成的矩形数组,例如: 每个数字代表一个 \\\"岛屿\\\",而点代表岛屿之间的空隙(水域)。大于 9

    2024年03月20日
    浏览(38)
  • 算法leetcode|54. 螺旋矩阵(rust重拳出击)

    给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。 m == matrix.length n == matrix[i].length 1 = m, n = 10 -100 = matrix[i][j] = 100 面对这道算法题目,二当家的再次陷入了沉思。 可以每次循环移动一步,判断移到边界就变换方向,巧用数组可以减少逻辑判断

    2024年02月08日
    浏览(47)
  • 遗传算法求解旅行商问题(含python源代码)

    目录 前言 编码初始化种群 计算适应度 选择 交叉 变异 完整代码 总结 这次的算法有一点不能确定是否正确,希望有大佬能够批评指正。 遗传算法的一般步骤 种群(population) 指同一时间生活在一定自然区域内,同种生物的所有个体。 所以种群是由个体组成的,所以先需要

    2024年01月23日
    浏览(66)
  • 算法leetcode|59. 螺旋矩阵 II(rust重拳出击)

    给你一个正整数 n ,生成一个包含 1 到 n 2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 1 = n = 20 面对这道算法题目,二当家的再次陷入了沉思。 可以每次循环移动一步,判断移到边界就变换方向,巧用数组可以减少逻辑判断的复杂性。 也可以每次循环

    2024年02月11日
    浏览(41)
  • 【算法题】螺旋矩阵 I II III IV

    目录 1. 螺旋矩阵 2. 螺旋矩阵 II 3. 螺旋矩阵 III 4. 螺旋矩阵 IV 题目描述: 给你一个m行n列的矩阵matrix,请按照顺时针螺旋顺序 ,返回矩阵中的所有元素。 提示: m == matrix.length n == matrix[i].length 1 = m, n = 10 -100 = matrix[i][j] = 100 题解: 4×5的矩阵按顺时针螺旋顺序打印如图所示。

    2024年02月15日
    浏览(42)
  • 遗传算法求解车辆路径优化问题VRP(Python代码实现)

    学会了前面两篇遗传算法,但是那都是针对抽象的数学问题求解的,那么应用到现实中的实际问题中,我们又该怎样把遗传算法套进去呢,然后我第一个接触到的问题就是车辆路径优化问题VRP,当然也是找到了一篇比较好的文章,物流管理论文实现:基于遗传算法的带时间窗

    2024年01月18日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包