На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Закрыто Math 11-04-2005: Вопрос исчерпан
  
> Детерминант
    Я вот тут давно думал написать прогу, считающую детерминант. Одна только мысль - написать через рекурсию. Слышал про метод гаусса. Токо не разу не встретил. Не мог бы кто-нить подкинуть идею про Гаусса или вообще про алгоритм.
      Цитата experimenter, 12.12.02, 07:25:05
      Я вот тут давно думал написать прогу, считающую детерминант. Одна только мысль - написать через рекурсию. Слышал про метод гаусса. Токо не разу не встретил. Не мог бы кто-нить подкинуть идею про Гаусса или вообще про алгоритм.

      никогда не считай определитель матрицы больше чем 3x3 по определению. Эта штука работает с трудоемкостью n! а это при n>10 жуткие тормоза.

      А идея метода Гаусса основана на двух фактах:
      1. при добавлении к i-ой строке матрицы j-ой строки, умноженной на константу (i не равно j), определитель не меняется.
      2. определитель диагональной (или верхне/нижне треугольной) матрицы равен произведению диагональных элементов

      Путем линейных комбинаций приводим матрицу к этому виду (трудоемкость n3) и считаем произведение диагональных элементов.

      см http://alglib.dore.ru/linalg/index.html#det
        эврика! какой я оказывается недогадливый.  ;D спасибо.
          дело в следующем.

          наша матрица напр такова:

          а11 а12 а13 ... a1n
          a21 а22 ....
          ....  .... ... ...
              ... ..
          an1 ...             ann

          сначала "обнуляем" первый столбец следующим способом.
          из всех строк ниже первого вычитается первая строка с такими коэффициентами, чтобы в 1 столбце получился 0, те напр из 2й строки надо вычесть 1ю , умноженную на а21/а11. для каждой строки будет свой коэффициент. таким способом 1й столбец будет содержать нули, кроме 1го элемента, потому обнуляем написано в кавычках.

          повторяем вышеописанную операцию со вторым столбцом. вычитаем с вышеописанными коэффициентами вторую строку из всех последующих строк, те напр из 5й строки вычитаем 2ю , умноженную на а52/а22. заметим, что из вышележащих строк не надо ничего вычитать, ибо мы стремимся к нулям только ниже главной диагонали.

          сию операцию следует произвести со всеми столбцами. в итоге мы получим матрицу следующего содержания:

          а11 а12 а13 ... a1n
          0    b22 ....
          ..0..  .... ... ...
           ...  0 ....bkk .. bkn
          ..0.. .. 0 ...  .. ...
          0 ...      ...    0  bnn

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

              но если там стоят буквы икс игрек и т.п то задача превращается в експоненциальную


              иногда вместо детерминанта считают перманент матрецы - как и детерминант только все миноры складывают так вот определение перманенты тоже экспоненциально
                дакстати. ежели один из диагональных елементов окажется нулём, то конечно же будет деление на 0, поэтому в случае появления нуля строку следет обменять со строкой, лежащей ниже и имеющей ненулевой елемент в соответствующем столбце. ежели таковые строки отсутствуют, определитель равен нулю.
                  Цитата wormball @ 27.12.02, 19:40
                  дакстати. ежели один из диагональных елементов окажется нулём, то конечно же будет деление на 0, поэтому в случае появления нуля строку следет обменять со строкой, лежащей ниже и имеющей ненулевой елемент в соответствующем столбце. ежели таковые строки отсутствуют, определитель равен нулю.

                  Более того, в реальных случаях техники перемещения столбцов/строк (их несколько основных) необходимы, иначе
                  происходит серьезная потеря точности.
                    Нахождение обратной матрицы
                    Сообщение отредактировано: Adil -
                      тема кстати двухлетней давности :lol:

                      Добавлено в :
                      или ето мне напоминание, чтобы я фак дописывал?
                      искренне каюсь, при первой же возможности (при первом же желании :lol: ) начну дописывать.

                      Добавлено в :
                      кстати илье кантору пламенный привет :yes:
                        Ребята, кто нибудь может помочь написать программу на с++???
                        Срочно требуется , не могу додуматься.
                          Может, но не хочет. :yes:
                            Возьми у меня на сайте.
                            0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                            0 пользователей:
                            Закрыто Math 11-04-2005: Вопрос исчерпан


                            Рейтинг@Mail.ru
                            [ Script execution time: 0,0510 ]   [ 15 queries used ]   [ Generated: 27.02.24, 02:53 GMT ]