`
luoping0425
  • 浏览: 106059 次
  • 性别: Icon_minigender_2
  • 来自: 赣州
文章分类
社区版块
存档分类
最新评论

算法:矩阵鞍点

阅读更多

10.12 求一个矩阵的鞍点,即在行上最小而在列上最大的点。

  思路是:

1. 找出第i行上最小的数

2.检验该数是否是该列上最大的数

 

def saddle_point(arr)
  # arr为m行n列,arr为矩政
  m = arr.length
  n = arr[0].length
  b = []  # 存放每行最小点的行列数组

  for i in 0...m  # 每一行最小的点    
    # 行中找出最小的点
    t = arr[i][0]
    minij = 0
    for j in 1...n
      if arr[i][j] < t
        t = arr[i][j]
        minij = j
      end      
    end
    
    b << [i, minij]
    puts "The row #{i}'s minimum is arr[#{i}][#{minij}]:#{arr[i][minij]}."
  end
  
  # 对数组b处理,b[m][2],b[m][0]:行数,b[m][1]:列数
  c = []
  
  
  b.each do |k|
    row = b[i][0]
		line = b[i][1]
		t = arr[row][line]
		
		# 判断该数是否是该列上最大的数
		flag = 1
		for i in 0...m
		  if t < arr[i][line]
		    flag = 0
		    break
		  end
		end
  
    c << [row, line, t] if flag == 1
  end
  
  c = c.uniq
  
  if c.empty?
    puts "Thers is no saddle point!"
    return
  else
		c.each do |i|
		  row = i[0]
		  line = i[1]
		  t = arr[row][line]
		  puts "arr[#{row}][#{line}]:#{t} is saddle point."
		end
		return c
  end

end

a1 =[[1,2,3,4],[1,5,8,6],[6,4,3,7],[6,3,4,1]]
c = saddle_point(a1)
puts "--------------------------------------"

a2 = [[1,2,3,4],[4,5,6,7],[8,9,10,11],[12,13,14,15]]
c = saddle_point(a2)
puts "--------------------------------------"

关于多个鞍点的,我实在是没有找出例子,不知有没有谁可以给我一个,验证一下。

 

有点难度,花了一个多小时吧。

明天去做新公司的体检,下周一入职。

分享到:
评论

相关推荐

    矩阵中寻找鞍点_C++_算法_矩阵鞍点算法_鞍点_

    C++算法,在矩阵中寻找鞍点。它在该行中最大,而在该列中最小。我们把这样的元素称为“鞍点”。一个矩阵可能没有鞍点,要存在鞍点也只能有一个。输出结果和鞍点位置

    算法设计中的有趣算法

    算法设计中的一些有趣算法,如:矩阵鞍点的求取,矩阵翻转,多项式求解等

    求矩阵中的鞍点

    求矩阵中的鞍点~~~~~~

    数据结构课程设计 鞍点等。。。

    所谓鞍点是指矩阵中的某个元素在其所在的行是最小的,同时在其所在列是最大的。选择合适的矩阵存储方式。以一个4行5列的矩阵为例,从键盘人已输入20个数据给矩阵赋值,然后判断其中是否存在鞍点。如果存在鞍点,输出...

    大数据-算法-特殊矩阵数值分析和鞍点问题迭代求解预处理技术.pdf

    大数据-算法

    北京交通大学数据结构上机题10-19

    10、鞍点问题: 若矩阵A中的某一元素A[i,j]是第i行中的最小值,而又是第j列中的最大值,则称A[i,j]是矩阵A中的一个鞍点。写出一个可以确定鞍点位置的程序。 11、稀疏矩阵转置: 输入稀疏矩阵中每个元素的行号、列号...

    求解鞍点问题的一种修正对称SOR-like算法 (2010年)

    在SOR-like迭代算法的基础上,通过选取预处理矩阵和待定参数来加速该迭代算法,构造了一种求解鞍点问题的修正对称SOR-like迭代算法,简记为MSSOR-like算法,并研究了新算法的收敛性。数值实验表明新算法是可行且有效的。

    data_manipulation.rar_数值算法/人工智能_Visual_C++_

    包含一些比较常见的数据操作算法:素数判断、矩阵转置、将数组中m个数循环后移n个位置、调用时间函数求运行时间、调用相关time函数进行日期推算、矩阵鞍点、链表的相关操作等

    一个鞍点定理及其应用 (2008年)

    利用边缘极值点集概念,得到了二元函数f(x,y)有鞍点的充分必要条件,将其推广到矩阵,得到了矩阵存在鞍点的一个充分必要条件,并设计了一个求矩阵所有鞍点的算法。利用该算法,可以求出一个矩阵的所有鞍点,且该算法总的...

    论文研究-一种新型高效的计算机寻优算法.pdf

    提出一种全新的寻找无约束最优解的计算机算法。该算法能使得目标函数梯度的模逐渐收缩到零,以达到目标函数...但Hessian矩阵奇异时,牛顿法将无法进行下去,该文算法可以克服这个缺点且能快速确定是否收敛到一个鞍点。

    java三元组

    对于乘法结果得到的结果矩阵,设计一个算法,寻找该矩阵的鞍点【最大选题人数:5】 提示:二维数组的鞍点:如果存在一个这样的元素,它是所在行上最大的元素,同时又是所在列上最小的元素,则该元素就是二维数组...

    论文研究 - 块三乘三结构鞍点问题的广义移位分离预处理器

    针对分块三乘三结构的鞍点问题,我们提出了一种广义的位移分裂迭代方法。 作为一种新的迭代方法,该方法无条件地收敛到鞍点问题的... 数值实验表明,该新算法可以有效地加快GMRES的速度,从而解决块三乘三鞍点问题。

    《妙趣横生的算法(C语言实现)》(杨峰 编著)

    4.17 寻找矩阵中的“鞍点” 4.18 n阶勒让德多项式求解 4.19 递归反向输出字符串 4.20 一年中的第几天 第5章 数学趣题(一) 5.1 舍罕王的失算 5.2 求两个数的最大公约数和最小公倍数 5.3 歌德巴赫猜想的近似证明 ...

    数组的存储

    若矩阵A中的某一元素A[i,j]是第i行中的最小值,而又是第j列中的最大值,则称A[i,j]为矩阵A中的一个鞍点。请写出一个可确定此鞍点位置的算法

    《算法与数据结构》实验内容资源包

    实验一 复数运算 实验二 线性表操作 实验三 约瑟夫环 实验四 航空售票管理 实验五 数组鞍点 实验六 稀疏矩阵转置 实验七 稀疏矩阵相乘 实验八 哈夫曼编码 实验报告范例.doc 算法动态演示DSDemo TC 安装程序

    数据结构课程设计

    鞍点问题: 若矩阵A中的某一元素A[i,j]是第i行中的最小值,而又是第j列中的最大值,则称A[i,j]是矩阵A中的一个鞍点。写出一个可以确定鞍点位置的程序。 稀疏矩阵转置: 输入稀疏矩阵中每个元素的行号、列号、值,...

    求解鞍点问题的多项式加速超松弛方法丰 (2011年)

    为了快速有效地求解大型稀疏鞍点问题,在广义逐次超松弛(GSOR)迭代算法的基础上,结合Chebyshev多项式加速技术,本文构造了一种多项式加速超松弛迭代算法,并研究了该算法的收敛性.通过讨论加速后迭代矩阵的收敛性...

    马鞍点的代码(含注释)

    如果矩阵A中存在这样的一个元素A[i][j]满足下列条件:A[i][j]是第i行中值最小的元素,且又是第j列中值最大的元素,则称之为该矩阵的一个马鞍点。编写一个程序计算出矩阵A的所有马鞍点,以及其位置。

    数据结构实验项目资料

    实验一 复数运算 实验二 线性表操作 实验三 约瑟夫环 实验四 航空售票管理 实验五 数组鞍点 实验六 稀疏矩阵转置 实验七 稀疏矩阵相乘 实验八 哈夫曼编码 **** TC 安装程序 **** 算法动态演示DSDemo

    数据结构程序集合

    包含 斐波那契序列,park,prim,鞍点,八皇后,二叉树,深度广度优先,哈希表,排列二叉树,排序,树,员工入职,约瑟夫环,转置矩阵等算法代码以及程序结果截图

Global site tag (gtag.js) - Google Analytics