Матрица вопрос

[mycoding]

Подскажите пожалуйста, вот дали задание.

Дана матрица A. Найти в ней ненулевой минор максимального размера. В случае, если таких миноров несколько, напечатать любой из них.

Как понял, предположим матрица 6, 7.
Т.е. максимальный размер минора 6 на 6?
А если он равен 0, т надо перебрать остальные более маленькие. Но вот как сделать алгоритм, чтобы перебирались все миноры начиная с самого большого до тех пор пока не найдётся не нулевой.
Можете подсказать.

[ewert]

Задача довольно нетривиальна.

Перебирать все миноры, конечно, -- занятие неблагодарное. Лучше привести матрицу к ступенчатому виду методом Гаусса (можно обойтись без перестановок). Тогда для искомого минора набор первых индексов образуют номера строк, оставшихся ненулевыми. А набор вторых индексов -- это номера первых ненулевых элементов тех строк.

Но тут появляется техническая проблема, и обойти её никак не удастся (вообще ни при каком способе решения не удастся). Если использовать арифметику с плавающей точкой, то возникает вопрос: что считать нулём? Если же арифметика целочисленная, то числа будут довольно быстро возрастать, и очень велика вероятность переполнения.

[mycoding]

Просто думал, что уже есть готовый код , чтобы пробегало по всем минорам, любой матрицы, но похоже такого кода нет?

[ewert]

Готовый код -- это неспортивно.

А организовать перебор всех миноров несложно. Напишите рекурсивную процедуру вычисления минора, входными параметрами которой являются порядок минора и два массива -- массив индексов используемых строк и массив индексов используемых столбцов. Процедура должна вычислять минор разложением по строке, обращаясь для этого к самой себе.

Теперь дополните её двумя вещами. Во-первых, заставьте её продублировать вычисление многократно -- не только по какой-то одной строке, а по всем задействованным. Во-вторых: если вычисление даст ненулевой результат, то пусть она выведет свои входные аргументы во вспомогательные переменные (например, глобальные) -- при условии, что уже хранящиеся в этих вспомогательных переменных данные отвечают минору меньшего размера.

Теперь запустите эту процедуру в цикле по всем минорам верхнего уровня (если матрица квадратная,то -- просто один раз ко всей матрице). На выходе в тех вспомогательных массивах окажутся индексы одного из ненулевых миноров наибольшего порядка.

(Хранить массив индексов можно по-разному: можно как именно индексы, а можно как булевский массив с флажками "задействован/не задействован". Второе, кажется, эффективнее, хотя не уверен; давно такими вещами не баловался.)

[Roman Voznyuk]

mycoding в сообщении #293207 писал(а):

Но вот как сделать алгоритм, чтобы перебирались все миноры начиная с самого большого до тех пор пока не найдётся не нулевой.
Можете подсказать.

Метод Гаусса с запоминанем перестановок строк. Как только упретесь в линейную зависимость строк (деление на нуль) так сразу переставив строки найдете положение этого ненулевого минора.
Короче говоря классическая задача на вычисление ранга матрицы.

[ewert]

Roman Voznyuk в сообщении #293345 писал(а):

Короче говоря классическая задача на вычисление ранга матрицы.

, которая вычислительно некорректна -- ввиду погрешностей округления.

[DadaSasa]

ewert
в общем, в учебной задаче обычно этим можно пренебречь

[mycoding]

А можно попросить написать код который любую квадратичную матрицу считает?
Если не трудно, хоть псевдо-код.

[ewert]

mycoding в сообщении #293721 писал(а):

А можно попросить написать код который любую квадратичную матрицу считает?

Нельзя категорически. Матрицу невозможно "сосчитать" в принципе. Так же как и "решить" и т.п.. Постарайтесь выражаться яснее.

[mycoding]

А может кто-нибудь помочь с кодом, который будет любую квадратную матрицу считать?
Просто одной из подзадач будет вычисление всех минора,
а минор это квадратная матрица, следовательно, надо будет проверить , что он не нулевой, т.е. вычислить определитель.

[worm2]

ewert писал(а):

Матрицу невозможно "сосчитать" в принципе. Так же как и "решить" и т.п.. Постарайтесь выражаться яснее.

mycoding писал(а):

А может кто-нибудь помочь с кодом, который будет любую квадратную матрицу считать?

Характер стойкий, нордический

[mycoding]

Просто мне то прогу сдавать, а как её делать ???
Если нельзя подсчитать любую квадратную матрицу, то прога не делается?

[mycoding]

Подскажите пожалуйста, а вот как сделать так, если матрица не определена, то ...

Это делать директивами #ifndef ?
Попробовал, что-то не получается.

[ewert]

mycoding в сообщении #294845 писал(а):

Подскажите пожалуйста, а вот как сделать так, если матрица не определена, то ...Это делать директивами #ifndef ?

А-а, я, кажется понял, это просто была такая шутка юмора.

(невозможно поверить, что человек непонимает (именно так, слитно) разницы между вырожденными матрицами и не определёнными явно системными переменными. Ну т.е. типа между козлами в огороде и бузиной в Киеве)