@Fanessie

Как рассчитать возможное количество вариантов пароля с доп. условиями?

Здравствуйте, уважаемые профессионалы и знатоки! Совсем сломала голову над задачей, которая на первый взгляд мне показалось совсем не сложной, а может уже просто заучилась ))
Дан известный набор символов из 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), а нужно как-то посчитать кол-во возможных вариантов и составить алгоритм получения этих вариантов.

Буду рада любой подсказке, идее или мысли ))
  • Вопрос задан
  • 108 просмотров
Пригласить эксперта
Ответы на вопрос 2
Lynn
@Lynn
nginx, js, css
Стандартная задача на рекурсию.

Представьте что вы уже умеете решать эту задачу для алфавита длиной 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.

База рекурсии: очевидно, что F(1) = 1, F(2) = 2.
Ответ написан
dimonchik2013
@dimonchik2013
...а ну-ка пыль сдуй отсюда...
из пп 2-3 формируете два набора максимальной длины
и затем проходите по ним длинами паролей двигая слева направо с перекрытием по последнему символу
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы