Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4   вперед  Ctrl      все
 Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
vi0
Member

Откуда:
Сообщений: 232
Есть комбинаторная задача: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр, если в пароле должна быть обязательно одна цифра?
Правильный ответ: 36^8 - 26^8

Рассматривается еще неправильный вариант: 36^7 * 10
Не могу понять почему он неправильный, хотя проверяя не простых примерах убеждаюсь в этом.
Подскажите, как дойти логически что этот ответ неверный, интуитивно он мне кажется верным, и не только мне.

задание Б на 3:52
https://www.coursera.org/learn/kombinatorika-dlya-nachinayushchikh/lecture/PuY6x/parol-k-komp-iutieru
5 июл 20, 16:57    [22162369]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
miksoft
Member

Откуда:
Сообщений: 38470
vi0
Рассматривается еще неправильный вариант: 36^7 * 10
Не могу понять почему он неправильный
Он был бы правильный, если бы позиция цифры была фиксирована, а она произвольная.

Сообщение было отредактировано: 5 июл 20, 17:06
5 июл 20, 17:09    [22162373]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Задача требует уточнения.

пароле должна быть обязательно одна цифра


означает что ТОЛЬКО одна или КАК МИНИМУМ ОДНА ?
5 июл 20, 17:17    [22162376]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
vi0
Member

Откуда:
Сообщений: 232
mayton, верно, некорректно указал
как минимум одна
5 июл 20, 17:21    [22162379]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Хм... что-то это мне до боли напоминает задачки на теорвер. Вобщем давайте от частного случая.

Нас интересуют все символы от '0' до '9' и от 'a' до 'z'

Тоесть диапазон паролей
'00000000' до 'zzzzzzzz'

Таковых будет 36^8

Но с условием что 1 позция имеет меньше комбинаций (это 1 цифра)
'0000000' до 'zzzzzzz' в сочетании с '0'-'9'

36^7 * 10 ^ 1

А также с двумя
'000000' до 'zzzzzz' в сочетании с '00'-'99'

36^6 * 10 ^ 2

..... и дак далее до вырожденного случая когда все 8 символов - цифры.

Тоесть надо всё это просуммировать. Там еще можно раскрыть скобки и будет правильный ответ.

И вобщем убежден что есть несколько формул или несколько подходов как это посчитать.
Разумеется все они должны дать один ответ.
5 июл 20, 17:31    [22162385]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
mini.weblab
Member

Откуда:
Сообщений: 1027
miksoft
vi0
Рассматривается еще неправильный вариант: 36^7 * 10
Не могу понять почему он неправильный
Он был бы правильный, если бы позиция цифры была фиксирована, а она произвольная.


так и есть нужно учитывать перестановку и количество цифр в пароле
попробуйте расписать все возможные варианты с цифрой в пароле
5 июл 20, 17:42    [22162389]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
mini.weblab
Member

Откуда:
Сообщений: 1027
mayton,
еще перестановки нужно учесть и получится бином Ньютона
5 июл 20, 17:44    [22162390]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
mini.weblab
mayton,
еще перестановки нужно учесть и получится бином Ньютона

Да. В мои формулы еще вносится поправка. Если

C(m,n) - это число сочетаний m по n. Тогда:

summ = 36^7 * 10 ^ 1 * C(1,8) + 
     36^6 * 10 ^ 2 * C(2,8) +
     ......
5 июл 20, 17:49    [22162393]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
fkthat
Member

Откуда:
Сообщений: 3030
mayton,

Все намного проще. Всего комбинаций 36^8 из них неправильных (где одни буквы) 26^8. Отсюда и получаем ответ 36^8 - 26^8.
5 июл 20, 19:48    [22162420]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Согласен. Яж писал про это. Есть несколько способов как посчитать.
5 июл 20, 20:10    [22162424]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
softwarer
Member

Откуда: 127.0.0.1
Сообщений: 62839
Блог
vi0
Рассматривается еще неправильный вариант: 36^7 * 10
....Подскажите, как дойти логически что этот ответ неверный

Думаю, неверность этого ответа нагляднее всего продемонстрировать так. Каким образом вообще строятся ответы типа 36^8? В первой позиции могут быть 36 вариантов, в каждом из них во второй позиции могут быть тоже 36 вариантов ..... в каждом из них в восьмой позиции могут быть 36 вариантов. Отсюда 36^8. Теперь правильно распишем ту же логику: в первой позиции могут быть 36 вариантов.... если в первой позиции буква, во второй буква итп., то в восьмой могут быть 10 вариантов, если хоть одна цифра - в восьмой 36. Отсюда становится ясно, что верный ответ как минимум сложнее, чем 36^7 * 10.
5 июл 20, 21:14    [22162435]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Будет неплохо завершить мои вычисления и сравнить две полученные формулы.
5 июл 20, 21:15    [22162438]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
vi0

Подскажите, как дойти логически что этот ответ неверный, интуитивно он мне кажется верным, и не только мне.


Доказать, что он неверный проще простого: он неверный, т.к. отличается от верного.

Теперь вы попробуйте доказать обратное, т.е. что он верный (уверен, что не получится).
5 июл 20, 21:44    [22162444]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
vi0
Member

Откуда:
Сообщений: 232
softwarer
vi0
Рассматривается еще неправильный вариант: 36^7 * 10
....Подскажите, как дойти логически что этот ответ неверный

Думаю, неверность этого ответа нагляднее всего продемонстрировать так. Каким образом вообще строятся ответы типа 36^8? В первой позиции могут быть 36 вариантов, в каждом из них во второй позиции могут быть тоже 36 вариантов ..... в каждом из них в восьмой позиции могут быть 36 вариантов. Отсюда 36^8. Теперь правильно распишем ту же логику: в первой позиции могут быть 36 вариантов.... если в первой позиции буква, во второй буква итп., то в восьмой могут быть 10 вариантов, если хоть одна цифра - в восьмой 36. Отсюда становится ясно, что верный ответ как минимум сложнее, чем 36^7 * 10.
да, похоже что эта формула подходит для одного случая, или даже не подходит..
все таки у нам размещения, а не сочетания
спасибо
6 июл 20, 16:45    [22162866]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
exp98
Member

Откуда:
Сообщений: 2446
vi0, прочь сомнения. Ответ правильный. Проще всего такие задачи решаются именно вычитанием:
fkthat
Все намного проще. Всего комбинаций 36^8 из них неправильных (где одни буквы) 26^8. Отсюда и получаем ответ 36^8 - 26^8.
подучите про "независимые события".
6 июл 20, 18:02    [22162922]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
vi0
Member

Откуда:
Сообщений: 232
exp98, рекомендую внимательно прочитать мой вопрос
6 июл 20, 18:18    [22162931]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
mini.weblab
Member

Откуда:
Сообщений: 1027
vi0,
чтобы разобраться с решением нужно рассмотреть следующие случаи

0) количество комбинаций пароля из 8 символов, который можно составить из 10 букв и 26 цифр
Решение: K = 36^8

1) в пароле нет ни одной цифры: посчитать количество комбинаций по условию
Пример:
U0 = 26^8
2) в пароле ровно одна цифра
U1 = C(8,1) * 10 * 36^7
3) в пароле ровно две цифры
U2 = C(8,2) * 10^2 * 36^6

Дальше попробуйте сами:
4) в пароле ровно три цифры
5) в пароле ровно четыре цифры
6) в пароле ровно пять цифр
7) в пароле ровно шесть цифр
8) в пароле ровно семь цифр
9) в пароле ровно восемь цифр

когда вы все подробно распишете, то придете к формуле, которую привел mayton
K = U0 + U1 + U2 + U3 + U4 + U5 + U6 + U7 + U8

решение задачи можно получить двумя способами
1) Способ, который вы нам привели.
K = 36^8: количество всех возможных комбинаций
U_C = 26^8: количество комбинаций противоречащих условию
U = K - U_C = 36^8 - 26^8: количество комбинаций, соответсвующих условию

2) Можно просуммировать количество комбинаций, соответсвующих условию
U = U1 + U2 + U3 + U4 + U5 + U6+ U7 + U8

если все правильно посчитаете, то ответы для первого и второго способа должны совпасть
6 июл 20, 18:48    [22162957]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
mini.weblab,

в форуме еще такой функционал есть. Latex. Можно красиво формулы вставлять.

Пример.

[latex]U1 = C(8,1) * 10 * 36^{7}[/latex]

6 июл 20, 18:52    [22162959]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
softwarer
Member

Откуда: 127.0.0.1
Сообщений: 62839
Блог
mayton
Можно красиво формулы вставлять.

Тогда уж



Сообщение было отредактировано: 6 июл 20, 18:58
6 июл 20, 18:57    [22162961]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Да. Ну и в обобщённом варианте там будет знак суммы. Большая сигма.
6 июл 20, 18:59    [22162963]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 12791
softwarer
mayton
Можно красиво формулы вставлять.

Тогда уж

6 июл 20, 19:43    [22162980]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
vikkiv
Member

Откуда: London
Сообщений: 2704
vi0
..Подскажите, как дойти логически что этот ответ неверный..
ну тут в ветке зациклились, проще надо, ещё-бы начали с 32-х символьных паролей то вообще-бы завал получился
логическая (связь) вылезет из элементарной индуктивной проверки
в пространстве более измеряемых и легче осознаваемых величин
напр. начни с 3х букв и 2х цифр (для абстрагирования - фактически две
любых непересекающихся группы символов, пароль с повторами или без),
увеличь на две-одну позиции, комбинациями в сущности "пароль" от двух-трёх,
ставить длину пароля больше четырёх - смысла нету
там походу приближения натренированному глазу и будут видны причины

Сообщение было отредактировано: 6 июл 20, 21:46
6 июл 20, 21:42    [22163037]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
Dima T
Member

Откуда:
Сообщений: 14886
vi0
Есть комбинаторная задача: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр, если в пароле должна быть обязательно одна цифра?
Правильный ответ: 36^8 - 26^8

В чем проблема? всего буквоцифр 36^8, но только из букав нельзя, а их 26^8 поэтому 36^8 - 26^8
6 июл 20, 21:46    [22163041]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
vikkiv
Member

Откуда: London
Сообщений: 2704
Dima T
В чем проблема? всего буквоцифр 36^8, но только из букав нельзя, а их 26^8 поэтому 36^8 - 26^8
имо - идеальное объяснение на второй вопрос (косвенно даже - почему дрогой ответ не верный, связь приводится, но косвенно т.к. результаты получатся разные, след. 2e неверно),
но оно предполагает что сделано какое-то заключение, проведено исследование, т.е. на основе имеющихся знаний,
между тем - тс в первом вопросе спрашивает "как логически дойти" а у тебя уже готовое решение с раскладом "почему"
... может конечно сложности на ночь придумываю по лишней доказательной базе.

Сообщение было отредактировано: 6 июл 20, 21:58
6 июл 20, 21:56    [22163046]     Ответить | Цитировать Сообщить модератору
 Re: Сколько 8ми символьных паролей можно составить из 26 букв и 10 цифр  [new]
Dima T
Member

Откуда:
Сообщений: 14886
vikkiv
Dima T
В чем проблема? всего буквоцифр 36^8, но только из букав нельзя, а их 26^8 поэтому 36^8 - 26^8
имо - идеальное объяснение на второй вопрос (косвенно даже - почему дрогой ответ не верный, но косвенно т.к. результаты получатся разные, след. неверно),
но оно предполагает что сделано какое-то заключение, проведено исследование, т.е. на основе имеющихся знаний,
между тем - тс в первом вопросе спрашивает "как логически дойти" а у тебя уже готовое решение с раскладом "почему"
... может конечно сложности на ночь придумываю по лишней доказательной базе.

Ничего не понял
6 июл 20, 22:01    [22163049]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4   вперед  Ctrl      все
Все форумы / Программирование Ответить