Как рассчитать возможное количество вариантов пароля с доп. условиями?
Здравствуйте, уважаемые профессионалы и знатоки! Совсем сломала голову над задачей, которая на первый взгляд мне показалось совсем не сложной, а может уже просто заучилась ))
Дан известный набор символов из n элементов в определенном порядке, например возьмем английский алфавит - 26 символов: a b c ... x y z.
Имеется пароль который состоит из этих символов. Пароль соответствует след. условиям:
1) Пароль не имеет фиксированной длинны, может быть как 1 символ, так и несколько десятков, но символы не могут повторяться.
2) Символы в пароле идут в том же порядке, в котором они расположены в наборе, только в обратном )))))
3) Символы не могут быть соседними в наборе.
Используя все вышеуказанное, пароль может быть: z, g, z x v, x k c a и т.п., вариантов типа a s y, z y, b b a и т.п. быть не может. Это все что до меня "дошло" ))) ну и то, что максимальная длинна пароля для данного набора символов: 13 (z x v t r p n l j h f d b), а нужно как-то посчитать кол-во возможных вариантов и составить алгоритм получения этих вариантов.
Представьте что вы уже умеете решать эту задачу для алфавита длиной n-1, n-2 и т.д. Пусть F(k) — количество паролей для алфавита длины k.
Тогда для алфавита длины n у вас есть варианты:
1. Не использовать в пароле последний символ — таких паролей очевидно F(n-1)
2. Использовать в пароле последний символ — тогда в пароле не может быть предпоследнего символа и дальше можно его продолжать всеми вариантами паролей из n-2 символов. Т.е. таких паролей F(n-2)
3. Пароль из одного последнего символа — один.
Итого всего паролей из n символов F(n) = F(n-1) + F(n-2) + 1.
Да вот я уже поняла что без рекурсии тут никуда )) Но если в плане реализации "генератора" я её еще более менее справлюсь одним циклом и рекурсивной функцией с циклом, то математически обосновать мне что-то не дается...
Давайте перейдем на числа 0-9, чтобы короче )
n = 10, максимальная длина 5 (9 7 5 3 1 и 8 6 4 2 0, только 2 варианта, других быть не может).
Уменьшаю длину до 4 цифр, возможные варианты: 9 7 5 0, 9 7 5 1, 9 7 5 2, 9 7 5 3, 8 6 4 0, 8 6 4 1 и 8 6 4 2 (7 вариантов). Так? Далее уменьшаю до 3, 2, 1...
Но как у меня тогда получатся варианты: 9 3 1, 9 2 0, 3 0 и т.п.?
Может проще начать с минимальной длины? 9, 8, 7, ...., 1, 0, потом добавлять по символу (9 7, 9 6, 9 5, 9 4, 9 3, 9 2, 9 1, 9 0, 8 6, ..., 8 0, ..., 3 1, 3 0, 2 0, 9 7 5, 9 7 4 и т.д.). Но здесь, похоже, нужна рекурсия? Циклами никак?
А вот по формуле что-то совсем туго, первый уровень 10 вариантов, второй 36 (8+7+6+5+4+3+2+1), третий - ?. Всего - ?
Простой
