Статьи Задачи Купить CD

Алгоритмы

Комбинаторика

Перестановки, факториал и т.д. (источник: журнал MSDN Magazine)

Перестановка строк – это изменение их порядка в наборе. Например, для исходного набора, состоящего из трех строк: «apple», «banana» и «cherry», существует всего шесть возможных перестановок:

  1. { "apple", "banana", "cherry" }
  2. { "apple", "cherry", "banana" }
  3. { "banana", "apple", "cherry" }
  4. { "banana", "cherry", "apple" }
  5. { "cherry", "apple", "banana" }
  6. { "cherry", "banana", "apple" }

Программист должен уметь: вычислять точное количество перестановок для данного набора строк и создавать все перестановки.

Общее число элементов перестановки порядка n равно n! (читается «эн факториал»). Например, для четырех элементов общее число перестановок составляет

4! = 4 * 3 * 2 * 1 = 24

Перестановки тесно связаны с сочетаниями, и эти понятия иногда путают. Сочетания строк – это подмножества исходного набора строк, где порядок не имеет значения. Например, вернемся к нашему исходному множеству строк: «apple», «banana» и «cherry». Существует три элемента сочетания для размера подмножества k = 1.

  1. { "apple" }
  2. { "banana" }
  3. {"cherry" }

Три элемента сочетания существуют и для размера подмножества k = 2.

  1. { "apple", "banana" }
  2. { "apple", "cherry" }
  3. { "banana", "cherry" }

И только один элемент сочетания - для размера подмножества k = 3.

  1. { "apple", "banana", "cherry" }
Число элементов перестановки порядка n

Вычисление общего числа элементов перестановки строк для данного набора строк – это парадоксальная задача, простая и в то же время сложная. Предположим, имеется четыре строки: «ant», «bat», «cow» и «dog», так что порядок равен n = 4. Общее число возможных элементов перестановки равно 24. В каждом из элементов может присутствовать только одна из четырех строк на первой (самой левой) позиции, любой из оставшихся трех атомов на следующей позиции, один из оставшихся двух строк на следующей позиции, и, наконец, единственный оставшаяся строка на последней позиции. Другими словами, для порядка n = 4 существует 4 * 3 * 2 * 1 = 24 элемента перестановки. Вы, вероятно, узнали формулу n факториал (часто она записывается как n!). Следовательно, общее число элементов перестановки строк порядка n равно n факториал. Давайте рассмотрим три различных реализации метода вычисления факториала.

Первый подход заключается в расчете факториала с помощью рекурсии. Например:

public static ulong FactorialRecursive(int n)
{
  if (n < 0) throw new ArgumentOutOfRangeException("n");
  if (n == 0 || n == 1) return 1;
  else return (ulong)n * FactorialRecursive(n - 1);
}

В большинстве случаев это не самый удачный подход. Если не соблюдать осторожность, легко получить неверный ответ. Значение n! очень быстро становится очень большим. Например, значение 64! примерно равно

126,886,932,100,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000

На самом деле, самое большое значение, которое можно хранить в переменной типа ulong, составляет всего 20!, то есть:

20 * 19 * 18 *. .. * 2 * 1 = 2,432,902,008,176,640,000

Как вы думаете, что произойдет при вызове

ulong result = FactorialRecursive(21)

в программе? По умолчанию, когда компьютер достигнет значения ulong.MaxValue (равного 18 446 744 073 709 551 615), то компеьютер вернется обратно к 0 и продолжит вычисления, не показывая никаких предупреждающих сообщений. Обратите внимание, что общеязыковая среда исполнения (CLR) может выполнять проверку переполнения и потери точности для числовых операций. Эту функцию можно включить при компиляции. Впрочем, не существует никаких особенных причин для того, чтобы использовать рекурсивный метод для решения данной задачи.

Второй подход к созданию метода расчета факториала заключается в итеративном вычислении ответа, примерно так:

public static ulong FactorialCompute(int n)
{
  if (n < 0 || n > 20)
      throw new Exception("Значение аргумента должно находиться между 0 и 20");
  ulong answer = 1;
  for (int i = 1; i <= n; ++i) answer = checked(answer * (ulong)i);
  return answer;
}

В большинстве случаев это безусловно лучше. Метод проверяет входной параметр и использует ключевое слово C# checked, которое генерирует исключение выполнения в случае возникновения арифметического переполнения.

Третий способ - поскольку набор возможных значений входного аргумента очень мал – от 0 до 20 – с тем же успехом можно было бы просто хранить 21 возможный результат в таблице поиска. Это решение выглядит примерно так:

public static ulong FactorialLookup(int n)
{
  if (n < 0 || n > 20)
    throw new Exception("Значение аргумента должно находиться между 0 и 20");
  ulong[] answers = new ulong[] { 1, 1, 2, 6, 24, 120, 720, 5040, 40320,
    362880, 3628800, 39916800, 479001600, 6227020800, 87178291200,
    1307674368000, 20922789888000, 355687428096000, 6402373705728000,
    121645100408832000, 2432902008176640000 };
  return answers[n];
}

Для большинства сценариев тестирования программного обеспечения последний способ с поиском является самым эффективным.

Реклама