1. C# / Говнокод #19447

    −1

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    static int Determinant(int[,] matrix)
	{
			int length = matrix.GetLength(0);
			int result = 0;

			if (matrix.Length > 1)
				for (int i = 0; i < length; ++i)
					result += (2 * (i & 1) - 1) 
						* matrix[i, 0]
						* Determinant(CutMatrix(matrix, i, 0));
			else
				result = matrix[0, 0];

			return result;
	}

		static int[,] CutMatrix(int[,] matrix, int cutRowIndex, int cutColumnIndex)
	{
			int length = matrix.GetLength(0);
			int[,] result = new int[length - 1, length - 1];

			for (int y = 0, ry = 0; y < length; ++y, ++ry)
			{
				if (y != cutRowIndex)
					for (int x = 0, rx = 0; x < length; ++x, ++rx)
					{
						if (x != cutColumnIndex)
							result[ry, rx] = matrix[y, x];
						else
							--rx;
					}
				else
					--ry;
		}

			return result;
	}

    Запостил: Tryff, 12 Февраля 2016

    Комментарии (28) RSS

    • ava d_fomenok 12.02.2016 18:34 # 0

      Наркоман!
      Ответить

      • ava Tryff 12.02.2016 18:37 # 0

        У тебя есть другой способ?
        Вряд ли, т.к. здесь надо думать
        Ответить

    • ava cykablyad 12.02.2016 18:42 # +1

      Кому вообще нужны [,] массивы?
      Ответить

      • ava Tryff 12.02.2016 18:46 # −1

        Они гарантируют одинаковую длину каждой строки.
        Т.е. массив [,] всегда можно представить как таблицу, а [][] - нет
        Ответить

        • ava cykablyad 12.02.2016 18:53 # +2

          Это не отменяет того факта, что [,] ненужный мусор, ибо [][] проверить можно, а Linq и прочие AssParallel для [,] без анальных болей использовать не получится
          Ответить

    • ava nihau 12.02.2016 18:45 # +3

      >рекурсия
      Стек парву!
      Ответить

      • ava Tryff 12.02.2016 19:44 # 0

        Вроде размер стека менять можно. Или нет. new Thread(int maxStackSize)
        Без рекурсии было бы больше страданий и хуже код
        Ответить

        • ava 3_dar 12.02.2016 22:16 # +2

          > int maxStackSize

          боюсь int-а тебе не хватит
          Ответить

        • ava j123123 12.02.2016 22:28 # +1

          Надо на сишарп портировать вот это вот http://www.govnokod.ru/19299 заменив хрень с gcc-шными goto каким-нибудь свичем, и сделать ему стек в куче
          Ответить

          • ava Tryff 12.02.2016 22:46 # +1

            Да я б в qt на c++ написал, просто в c# меньше ошибок делаю (с ним уже 2 года работаю)
            Ответить

            • ava 3_dar 13.02.2016 13:57 # −1

              Так ты этот код реально используешь что-ли?
              Ответить

              • ava Tryff 13.02.2016 16:30 # −2

                Использовал бы, если б появилась такая необходимость.
                Другой реализации не вижу.
                Ответить

                • ava bormand 13.02.2016 17:37 # −1

                  > Другой реализации не вижу.
                  Ну хотя бы наивный способ с суммой по всем перестановкам... Та же факториальная сложность, но там хотя бы матрицу не надо копировать на 100500 раз.

                  P.S. Хотя там, походу, умножений больше выйдет.
                  Ответить

                  • ava kegdan 13.02.2016 19:52 # −1

                    Влобешное решение

                    https://ideone.com/UXsvAl

                    перестановки через алгоритм пилораммы Нарайаны

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

                    А вообще можно и гауссом имбануть так то
                    Ответить

                    • ava 1024-- 13.02.2016 21:25 # 0

                      > Влобешное
                      Прочитал как "волшебное".
                      Всё же, 14 февраля уже, день влюблённых в код, романтика, все дела.
                      Ответить

                      • ava kegdan 13.02.2016 21:26 # −1

                        к сожалению с этим кодом я трахался вчера, на сегодня нужен другой
                        Ответить

                        • ava 1024-- 13.02.2016 21:27 # −1

                          Вертихвост!
                          Ответить

                          • ava kegdan 13.02.2016 21:30 # −1

                            Предлагаю устроить троечек - ты, я и геомэээтрия (начать пилить 3д движок)
                            Ответить

                            • ava bormand 13.02.2016 21:33 # −1

                              > 3д движок
                              В гейдев решил податься?
                              Ответить

                              • ava kegdan 13.02.2016 21:39 # −1

                                Угу, вот плюсы начал читать, движок собрался пилить. Осталось только помаду и тени (динамические) купить - и можно в гейдев
                                Ответить

                • ava bormand 13.02.2016 18:06 # −1

                  В общем, я бы примерно так написал:
                  static int Determinant(int[] indices, int i) {
    if (i == Size - 1)
        return Matrix[i, indices[i]];

    int result = 0;
    for (int j = i; j < Size; ++j) {
        Swap(indices[i], indices[j]);
        int minorDet = Determinant(indices, i + 1);
        int tmp = minorDet * Matrix[i, indices[i]];
        Swap(indices[i], indices[j]);
        if (i & 1)
            result -= tmp;
        else
            result += tmp;
    }
    return result;
}

int Determinant() {
    int[] indices = new int[Size];
    for (int i = 0; i < Size; ++i)
        rest[i] = i;
    return Determinant(indices, 0);
}
                  Код писал прямо в браузере, так что могу жестоко заблуждаться...
                  Ответить

                • ava bormand 13.02.2016 18:21 # −1

                  > Другой реализации не вижу.
                  P.S. Гугл подсказывает, что надо юзать LU или QR разложение, а потом посчитать определитель по-читерски, тупо перемножив циферки на диагоналях. Там будет O(N^3) вместо O(N!).
                  Ответить

                • ava 3_dar 14.02.2016 10:12 # −1

                  Пиздец, я думал ты пошутил.

                  Гугли алгоритм Гаусса за О(N^3)
                  Ответить

      • ava bormand 13.02.2016 18:12 # −1

        > Стек парву!
        Там глубина рекурсии копеечная, всего лишь на размер матрицы. А сложность у алгоритма - O(N!). Так что оно скорее повиснет на годы, чем стек порвёт...
        Ответить

        • ava kegdan 13.02.2016 21:37 # +2

          — Дальше.
          — Вычислял определитель.
          — Чей?
          — Матрицы.
          — Когда?
          — Летом.
          — Как вычислял?
          — Итеративно .
          — КАК?!
          — Итеративно .
          — Точно?
          — Точно.
          — А стек чё у неё порван?
          — Не знаю.
          — Ты порвал?
          — Может не я…
          — А может и ты, да?
          — Нет.
          Ответить

    Добавить комментарий