комбинаторные проблемы.

я тут внезапно осознал, что совершенно не помню элементарных вещей.

вот, например, понятно, что если у нас есть две переменные [a, b] и значения [true, false], которые они могут принимать, то всего комбинаций будет 4, и их несложно составить. Но по какому алгоритму они составляются? И в более общем виде, если у нас [a..z] переменных и [1..n] значений?

или, например, есть у нас те же [a,b], но «a» может принимать значения [0,1], а «b» — [m, n, p]. Как получаются все комбинации?

читал википедию, ответа не нашел.

GD Star Rating
loading...

7 Responses to Комбинаторные проблемы

  1. Taova:

    [a..z] переменных и [1..n] значений
    Если переменные называть 1..n, а значения a..z (наоборот), то получается задача о составлении слов длинны n над алфавитом a..z. Количество их будет p^n, где p — мощность множества алфавита. Алгоритм простой: «aaa», «aab», …, «zzy», «zzz» — называется лексиграфическим порядком слов.

    Ответ ко второму вопросу: 2*3 = 6. правило умножения.

    Вики хороша, когда знаешь: максимум ее можно использовать как плохой справочник. Советую почитать лекции или найти книгу.

  2. Taova:

    Лексикографический порядок, конечно же.

  3. NoBig:

    с каких пор принято переменные обозначать символами констант?

  4. Sbalr:

    честно скажу, не буду спорить про обозначенияя констант, примерно тему понял, буду дальше рыть.

  5. Tokder:

    Соответствующий раздел математики называется комбинаторика.
    И там очень любят факториал (это та штука, которая «!» обозначается). Вот и все что я сходу могу вспомнить про комбинаторику.

  6. ReMonkey:

    Там очень любят хитрожопые задачи на пересечение множеств и количество вариантов.

  7. EgDr:

    Там еще любят треугольник Паскаля.
    Я его когда решал задачу с TopCoder сначала сам изобрел (три дня на сволочь потратил), а на следующий день случайно наткнулся в Википедии.

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