Си диез / Говнокод #19447 Ссылка на оригинал

0

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  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 Tryff, (Updated )

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

    • ava Tryff # Ссылка на оригинал 0 ⇈

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

    • ava Tryff # Ссылка на оригинал 0 ⇈

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

      • ava cykablyad # Ссылка на оригинал 0 ⇈

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

    • ava Tryff # Ссылка на оригинал 0 ⇈

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

      • ava j123123 # Ссылка на оригинал 0 ⇈

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

        • ava Tryff # Ссылка на оригинал 0 ⇈

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

            • ava Tryff # Ссылка на оригинал 0 ⇈

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

              • ava bormand # Ссылка на оригинал 0 ⇈

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

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

                • ava kegdan # Ссылка на оригинал 0 ⇈

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

                  https://ideone.com/UXsvAl

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

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

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

                  • ava 1024-- # Ссылка на оригинал 0 ⇈

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

                    • ava kegdan # Ссылка на оригинал 0 ⇈

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

                        • ava kegdan # Ссылка на оригинал 0 ⇈

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

                            • ava kegdan # Ссылка на оригинал 0 ⇈

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

              • ava bormand # Ссылка на оригинал 0 ⇈

                В общем, я бы примерно так написал:
                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 # Ссылка на оригинал 0 ⇈

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

              • ava 3_dar # Ссылка на оригинал 0 ⇈

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

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

    • ava bormand # Ссылка на оригинал 0 ⇈

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

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

Где здесь C++, guest?!

    А не использовать ли нам bbcode?

    ↑
    8
    ↓