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++算法,在矩阵中寻找鞍点。它在该行中最大,而在该列中最小。我们把这样的元素称为“鞍点”。一个矩阵可能没有鞍点,要存在鞍点也只能有一个。输出结果和鞍点位置
算法设计中的一些有趣算法,如:矩阵鞍点的求取,矩阵翻转,多项式求解等
求矩阵中的鞍点~~~~~~
所谓鞍点是指矩阵中的某个元素在其所在的行是最小的,同时在其所在列是最大的。选择合适的矩阵存储方式。以一个4行5列的矩阵为例,从键盘人已输入20个数据给矩阵赋值,然后判断其中是否存在鞍点。如果存在鞍点,输出...
大数据-算法
10、鞍点问题: 若矩阵A中的某一元素A[i,j]是第i行中的最小值,而又是第j列中的最大值,则称A[i,j]是矩阵A中的一个鞍点。写出一个可以确定鞍点位置的程序。 11、稀疏矩阵转置: 输入稀疏矩阵中每个元素的行号、列号...
在SOR-like迭代算法的基础上,通过选取预处理矩阵和待定参数来加速该迭代算法,构造了一种求解鞍点问题的修正对称SOR-like迭代算法,简记为MSSOR-like算法,并研究了新算法的收敛性。数值实验表明新算法是可行且有效的。
包含一些比较常见的数据操作算法:素数判断、矩阵转置、将数组中m个数循环后移n个位置、调用时间函数求运行时间、调用相关time函数进行日期推算、矩阵鞍点、链表的相关操作等
利用边缘极值点集概念,得到了二元函数f(x,y)有鞍点的充分必要条件,将其推广到矩阵,得到了矩阵存在鞍点的一个充分必要条件,并设计了一个求矩阵所有鞍点的算法。利用该算法,可以求出一个矩阵的所有鞍点,且该算法总的...
提出一种全新的寻找无约束最优解的计算机算法。该算法能使得目标函数梯度的模逐渐收缩到零,以达到目标函数...但Hessian矩阵奇异时,牛顿法将无法进行下去,该文算法可以克服这个缺点且能快速确定是否收敛到一个鞍点。
对于乘法结果得到的结果矩阵,设计一个算法,寻找该矩阵的鞍点【最大选题人数:5】 提示:二维数组的鞍点:如果存在一个这样的元素,它是所在行上最大的元素,同时又是所在列上最小的元素,则该元素就是二维数组...
针对分块三乘三结构的鞍点问题,我们提出了一种广义的位移分裂迭代方法。 作为一种新的迭代方法,该方法无条件地收敛到鞍点问题的... 数值实验表明,该新算法可以有效地加快GMRES的速度,从而解决块三乘三鞍点问题。
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中的一个鞍点。写出一个可以确定鞍点位置的程序。 稀疏矩阵转置: 输入稀疏矩阵中每个元素的行号、列号、值,...
为了快速有效地求解大型稀疏鞍点问题,在广义逐次超松弛(GSOR)迭代算法的基础上,结合Chebyshev多项式加速技术,本文构造了一种多项式加速超松弛迭代算法,并研究了该算法的收敛性.通过讨论加速后迭代矩阵的收敛性...
如果矩阵A中存在这样的一个元素A[i][j]满足下列条件:A[i][j]是第i行中值最小的元素,且又是第j列中值最大的元素,则称之为该矩阵的一个马鞍点。编写一个程序计算出矩阵A的所有马鞍点,以及其位置。
实验一 复数运算 实验二 线性表操作 实验三 约瑟夫环 实验四 航空售票管理 实验五 数组鞍点 实验六 稀疏矩阵转置 实验七 稀疏矩阵相乘 实验八 哈夫曼编码 **** TC 安装程序 **** 算法动态演示DSDemo
包含 斐波那契序列,park,prim,鞍点,八皇后,二叉树,深度广度优先,哈希表,排列二叉树,排序,树,员工入职,约瑟夫环,转置矩阵等算法代码以及程序结果截图