Здравствуйте ещё раз прошу помощи, на этот раз в составлении алгоритма решения одной задачи и её дальнейшей реализации на C. ) Составить программу которая считала бы определитель матрицы, а результат записывала бы в файл. Размерность задаёт пользователь. Матрица имеет следущий вид: |1 2 3 ... n |n 1 2 ... n-1 |n-1 n 1 ... n-2 |..................... |2 3 4 ... n 1 как написать программу представление имею, но вот алгоритм по которому бы вычислялся бы данный массив придумать не могу, точнее формулу для вычисления данного определителя.
(10 ссылка в гугле) http://www.ict.edu.ru/ft/005158/it200506.pdf - жмем ctrl+F, вводим циркулянт, жмем enter, любуемся формулой вычисления определителя циркулянта.
Есть и другой способ - с помощью вычитаний сделать большинство элементов матрицы нулями. Первый шаг - вычесть из всех строк первую.
al_4 Вычисление определителя по правилу Саррюса: к матрице n-ого порядка дописывают первые n-1 столбцов, элементы на диагоналях перемножают, диагональ вправо с плюсом, диагональ влево с минусом | a11 a12 a13 |a11 a12 | \ X X / | a21 a22 a23 |a21 a22 = a11*a22*a33 + a12*a23*a31 + a13*a21*a32 - | / X X \ -a13*a22*a31 - a11*a23*a32 - a12*a21*a33 | a31 a32 a33 | a31 a32 в вашем случае | 1 2 3 | 1 2 | 3 1 2 | 3 1 = 1*1*1+2*2*2+3*3*3 - 1*2*3 - 1*2*3 - 1*2*3 = 1^3+2^3+3^3 - 3 * 3! | 2 3 1 | 2 3 в случае с N пересчитаете сами, а уж программу я думаю напишете
опа, понял) спасибо) 2halyavin точно) "циркулянт" я эту матрицу уже всяко заобзывался.. спиральная, циклическая.. ) спасибо) 2Mikl__ интересно, попробую) спасибо) вопрос снят.
halyavin Единственным делением Гаусса. O(N^3) Mikl__ Этот способ очень тормознутый. К тому же для произвольной матрицы он несколько более сложный, и отсюда ещё более тормознутый. O(N!). Так делать ещё можно для матрицы 3x3, но для больших не советую.
>Этот способ очень тормознутый. Так делать ещё можно для матрицы 3x3 Ага, есть такое дело. Но всё же. но всё же лучше по-обычному. ) имхо) >Единственным делением Гаусса. O(N^3) поясните пжл? O(N^3)?
al_4 Ну это типо сложность алгоса. N - в данном случае разрядность матрицы. А (N^3) кол-во вычислений для данного алгоса, то есть разрядность в кубе. Для Саррюса она N!, что ужасно много, а для Гаусса N^3, что гораздо лучше. Так что советую Гаусса. Я недавно писал на С++ класс матрицы произвольной размерности, в шаблонах, использовал именно метод обратного деления Гаусса. Им ещё очень удобно обратную матрицу находить и сами корни. Думаю при реализации Саррюса для произвольной, ты сталкнёшся с проблемами. Гаусс IMHO и проще и гораздо оптимальней.
al_4 Чудак, человек, тебе только порядок матрицы нужен 2-го порядка 1+4-2*2=1 3-го порядка 1+8+27-3*6=18 4-го порядка 1+2^4+3^4+4^4-4*24=354-96=258 5-го порядка 1+2^5+3^5+4^5+5^5-5*120 и так далее неужели формулу для N-го порядка не выведешь? N-го порядка 1^n+2^n+3^n+...+n^n-n*n! Матрица-то у вас не произвольная, а вот такая, например 99-го порядка | 1 2 3 4 5 ... 99| | 99 1 2 3 4 ... 98| ......... | 2 3 4 5 6 ... 1 | Да посчитай на бумажке до 10-го порядка
Code (Text): 2-го порядка 1+4-2*2=1 3-го порядка 1+8+27-3*6=18 4-го порядка 1+2^4+3^4+4^4-4*24=354-96=258 5-го порядка 1+2^5+3^5+4^5+5^5-5*120 правильный ответ был только для одного порядка, для третьего, 18. а все остальные.. не получается, решал через миноры) проверил быстренько в екселе, тот же результат, что и через миноры) а второй порядок |12 |21 тут всяко -3 получается.. 1*1 - 2*2 = -3
Это называется правилом Саррюса? Не знал, что у этого вообще существует название. Но в любом случае, оно работает только для размера 3*3 (ну и 1*1). В общем случае лучший метод вычисления определителя - это действительно метод Гаусса, работающий за O(N^3). Но сейчас имеется конкретная матрица, над которой можно провести конкретные операции, не меняющие определителя, но упрощающие вид матрицы, просто ручкой на бумаге (перед всякими вычислительными действиями). P.S. Правильный ответ: (-n)^(n-1)*(n+1)/2
>Это называется правилом Саррюса? Не знал, что у этого вообще существует название. Но в любом случае, оно работает только для размера 3*3 (ну и 1*1). ну или правило треугольника, единственное что.. так это "к матрице n-ого порядка дописывают первые n-1 столбцов" действие вроде как лишнее. >P.S. Правильный ответ: (-n)^(n-1)*(n+1)/2 хм.. а как Вы вывели эту формулу? хех, самая простая и _рабочая_.. Щас пробовал преобразовывать матрицу методом Гаусса (но не O(N^3), так как слегка не понял это ), но пока ничего толкового не вижу..
Используем следующие свойства определителя: 1) если к i-й строке прибавить j-ю строку (при i, не равном j), умноженную на что угодно (в том числе на 1 или на -1), значение определителя не изменится; 2) то же самое верно для столбцов; 3) разложение по строке или столбцу (выражение определителя порядка k в виде суммы/разности определителей порядка k-1). Добавляем к последней строке предпоследнюю. Затем к предпоследней предпредпоследнюю. И так далее n-1 раз, в конце ко второй добавим первую. Получим определитель 1 2 3 ... n n-1 -1 -1 ... -1 -1 n-1 -1 ... -1 ... -1 -1 -1 ... n-1 -1 Теперь к последнему столбцу добавляем все предыдущие n-1 столбцов. Элемент первой строки станет равным сумме всех чисел от 1 до n, то есть n(n+1)/2. В остальных строках получится 0. Раскладываем определитель по последнему столбцу. Там только один ненулевой элемент в первой строке, который идёт со знаком (-1)^(n-1). Получаем, что исходный определитель равен (-1)^(n-1)*n(n+1)/2*следующий размера n-1: n-1 -1 -1 ... -1 -1 n-1 -1 ... -1 ... -1 -1 -1 ... n-1 Снова прибавляем к последнему столбцу все предыдущие. Последний столбец заменяется на столбец из всех единиц. Теперь прибавляем, наоборот, его ко всем предыдущим. Получаем n 0 0 ... 0 1 0 n 0 ... 0 1 0 0 n ... 0 1 ... 0 0 0 ... n 1 0 0 0 ... 0 1 что уже легко считается и даёт n^(n-2). Окончательно как раз и получаем (-1)^(n-1)*n(n+1)/2*n^(n-2) = (-n)^(n-1)*(n+1)/2
