| Вопрос: Help!!! как найти седловую точку в матрице? | Добавлено: 24.04.09 16:54 |
Автор вопроса:  Enrieta
|
|
помогите пожайлуста решить задачу!!! Седловой точкой в матрице называется элемент, являющийся одновременно наибольшим в столбце и наименьшим в строке. Седловых точек может быть и несколько (в этом случае они имеют равные значения). В матрице A(m,n) найти седловую точку и ее координаты p,q либо установить, что такой точки нет. |
| Ответы | Всего ответов: 6 |
|
Номер ответа: 1 Автор ответа:  машинист Вопросов: 6 Ответов: 26 |
Профиль | | #1 | Добавлено: 28.04.09 22:41 |
|
На первый взгляд так и надо делать - по приведенному Вами определению. Сначала пройтись по столбцам и определить/выбрать в каждом максимальный элемент (точнее, номер его строки в своём столбце). Если столбцов m, то и получится m элементов. Потом каждый выбранный на предыдущем шаге эл-т проверить, является ли он наименшим уже в той строке,где он располагается, и достоин ли он звания седловой точки. Вроде, так - точно по определению.
Для проверки можно сделать наоборот: 1) определить минимальные эл-ты по стркам, и 2) проверить их на максимальое значение по столбцам. В обоих случ. результаты поиска должны совпасть. |
||
|
Номер ответа: 2 Автор ответа: mc-black ICQ: 308-534-060 Вопросов: 20 Ответов: 1860 |
Web-сайт: Профиль | | #2 | Добавлено: 29.04.09 09:17 |
|
Создать булевую матрицу той же размерности B(m,n). Проходя по матрице A по столбцам находить максимум(ы) (их может оказаться по нескольку в одном столбце) в каждом из столбцов. При этом в матрице B(m,n) соответствующим элементам максимумов присвоить True (остальным False). Потом начать проходить матрицу A(m,n) построчно и искать минимум(ы) в каждой строке. При этом в матрице B(m,n) соответствующим элементам надо присваивать B(i,j) = B(i,j) And Result, где Result = True для минимумов и False - для максимумов. В конце просто пройтись по матрице B(m,n), выдать все седловые точки с их координатами и подсчитать их количество. При поиске максимумов/минимумов в столбцах/строках я предлагаю делать по 2 прохода на 1 ряд: за первый проход узнаем максимум/минимум ряда, во второй проход проставляем максимум(ы)/минимум(ы) в нужных позициях булевой матрицы.
Я правильно понимаю задачу, что для матрицы со всеми равными элементами все точки будут седловыми? Нужно написать макрос на VBA? |
||
|
Номер ответа: 3 Автор ответа: AngryBadger Вопросов: 33 Ответов: 245 |
Профиль | | #3 | Добавлено: 29.04.09 14:57 |
|
Вот что у меня получилось, наверное, можно и проще.
Заполняешь матрицу на листе Excel, потом выделяешь её и запускаешь макрос. Ячейки, содержащие седловую точку, будут выделены красным. Option Explicit
Option Base 1 Sub mtrx() Dim R As Long, C As Long Dim R1 As Long Dim m As Long, n As Long Dim i As Long Dim k As Long Dim Max As Long, Min As Long Dim MyRange As Range Dim MyArray() As Long Dim MaxArray() As Long Set MyRange = Selection R = MyRange.Rows.Count C = MyRange.Columns.Count ReDim MyArray(1 To R, 1 To C) ReDim MaxArray(1 To R, 1 To R) For n = 1 To C R1 = R1 + 1 i = 0 For m = 1 To R MyArray(m, n) = MyRange.Cells(m, n) If m = 1 Then Max = MyArray(m, n) i = i + 1 MaxArray(R1, i) = m Else If MyArray(m, n) = Max Then Max = MyArray(m, n) i = i + 1 MaxArray(R1, i) = m ElseIf MyArray(m, n) > Max Then Max = MyArray(m, n) i = 1 MaxArray(R1, i) = m For i = 2 To UBound(MaxArray) MaxArray(R1, i) = 0 Next i i = 1 End If End If Next m Next n i = 1 R1 = 0 For m = 1 To R + 1 If m > R Then GoTo EndOfRow If MaxArray(i, m) = 0 Then EndOfRow: i = i + 1 If i > MyRange.Columns.Count Then Exit For m = 1 End If Min = MyArray(MaxArray(i, m), i) For n = 1 To C If Min > MyArray(MaxArray(i, m), n) Then k = k + 1 Next n If k = 0 Then MyRange.Cells(MaxArray(i, m), i).Interior.ColorIndex = 3 k = 0 Next m End Sub |
||
|
Номер ответа: 4 Автор ответа: Enrieta Вопросов: 2 Ответов: 5 |
Профиль | | #4 | Добавлено: 13.05.09 22:18 |
|
Михаил, а как вывести сообщение, когда в матрице нет седловой точки?
И еще мне нужно определит координаты точки |
||
|
Номер ответа: 5 Автор ответа: машинистВопросов: 6 Ответов: 26 |
Профиль | | #5 | Добавлено: 14.05.09 05:55 |
| Как обычно в таких случах. Объявляете переменную логического типа, например Dim OK as Boolean: OK=false; и объявляете Dim i, j, Rs, Cs as integer - переменные циклов и координаты искомой точки. Теперь, при проверке Вашей точки в строках на min (перебором i), если точка соответствует условию (она минимальна), а затем при проверке этой же точки в столбцах на максимум (перебором j) она окажется максимальной, то логической переменной присваиваете OK=true и одновременно фиксируете текущие номера строки и столбца (Rs=i: Cs:=j). По завершении Ваших поисков просто смотрите на OK и Rs, и Cs - и узнаете про седловую точку. | ||
|
Номер ответа: 6 Автор ответа: AngryBadgerВопросов: 33 Ответов: 245 |
Профиль | | #6 | Добавлено: 18.05.09 12:20 |
|
Вверху, после Sub mtrx()
Добавь Dim Sch as Double
Окончание поменяй с If k = 0 Then MyRange.Cells(MaxArray(i, m), i).Interior.ColorIndex = 3
k = 0 Next m End Sub на If k = 0 Then Msgbox "О!!! Седловая точка, координаты: " & MaxArray(i, m) & "," & i
k = 0 Sch = Sch + 1 Next m If Sch = 0 Then Msgbox "Нету тута ни одной седловой точки, давай другую матрицу" End Sub |
||
Страница: 1 |