|
2 / 2 / 0
Регистрация: 28.05.2020
Сообщений: 58
|
|
Перебор вариантов29.05.2020, 11:26. Показов 6047. Ответов 72
Метки комбинаторика (Все метки)
Здравствуйте, нужна помощь новичку (мне).
Есть набор k букв, каждой букве может соответствовать несколько значений, например: А: 1,2,7 Б: 3,6 В: 4 Г: 5 Все значения разные. Вопрос: как организовать цикл, чтобы на каждой итерации выдавался набор значений по одному от каждой буквы? То есть в этом примере по 4 значения. Чтобы в итоге перебрались все варианты. Следует сказать, что букв может быть до 33, количество значений не ограничено.
0
|
|
| 29.05.2020, 11:26 | |
|
Ответы с готовыми решениями:
72
перебор вариантов... Перебор всех вариантов
|
|
2 / 2 / 0
Регистрация: 28.05.2020
Сообщений: 58
|
||
| 02.06.2020, 12:04 [ТС] | ||
|
0
|
||
|
1533 / 540 / 127
Регистрация: 09.01.2018
Сообщений: 1,756
|
||
| 02.06.2020, 12:07 | ||
|
Меняем все а на б - все а заменились на б. Меняет все б на еще что то, и так далее. Мы никак не сможем получить таким образом разные значения для а. Вот например абракадабра врабнушнпбн Если мы просто заменим а на в (как в первой букве результата) То получим вбрвквдвбрв И вместо в мы никак не сможем получить теперь у как здесь: врабнушнпбн Потому что у нас нет замен для в. Вообще нет в правиле. Это говорит о том, что вы скорее всего не поняли задание. Попозже перепишу генератор ключей, посмотрю на результаты.
1
|
||
|
2 / 2 / 0
Регистрация: 28.05.2020
Сообщений: 58
|
||
| 02.06.2020, 12:26 [ТС] | ||
|
escoult, жесть какое задание, действительно, я понял его неправильно (
То есть, получается, что одна и та же буква (а) в итоге может быть заменена на совсем разные, я даже не обратил на это внимание... первая а там заменилась на в, вторая на б, третья на у, четвертая и пятая на н. Извините. Добавлено через 3 минуты samana, вы тогда тоже были правы, одна буква может меняться на разные
0
|
||
|
1533 / 540 / 127
Регистрация: 09.01.2018
Сообщений: 1,756
|
||||||||||||||||
| 02.06.2020, 13:28 | ||||||||||||||||
|
shabserg, вообщем переписал я этот класс, теперь он учитывает повторяющиеся символы и находит вашу заветную "врабнушнпбн".
Правда работает теперь немного дольше, из-за увеличившегося числа ключей, 1.2 с на коротком словаре, на длинном еще не тестил. Вот обновленные участки кода: Кликните здесь для просмотра всего текста
Тест: Кликните здесь для просмотра всего текста
Результаты
Не используйте в словаре слишком длинные слова как это "абракадабракадабраабра". Слишком большое число символов увеличит время перебора до неразумных значений, даже если искомое слово другое, а это просто лежит "по дороге". Программе все равно придется его перебирать и время ожидания будет очень велико. Лучше всего короткие слова 4-5 букв.
2
|
||||||||||||||||
|
2639 / 1567 / 853
Регистрация: 23.02.2019
Сообщений: 3,876
|
||
| 02.06.2020, 13:48 | ||
А я так и не придумал вариант с более быстрым просчётом.. Но хорошо, что наконец-то задача решена!Не по теме: хотел написать: лайк и подписка, но вовремя опомнился.
1
|
||
|
2 / 2 / 0
Регистрация: 28.05.2020
Сообщений: 58
|
||||||
| 02.06.2020, 13:53 [ТС] | ||||||
|
escoult, не могу собрать ваш код воедино, выдает ошибки при компиляции.
У меня получилось так:
0
|
||||||
|
1533 / 540 / 127
Регистрация: 09.01.2018
Сообщений: 1,756
|
|
| 02.06.2020, 14:13 | |
Сообщение было отмечено shabserg как решение
Решение
1
|
|
|
2639 / 1567 / 853
Регистрация: 23.02.2019
Сообщений: 3,876
|
|
| 02.06.2020, 14:44 | |
|
shabserg, Попробовал внедрить код от escoult, в ваш Winforms проект. Попробуйте: Lab2CSapp.zip
1
|
|
|
2 / 2 / 0
Регистрация: 28.05.2020
Сообщений: 58
|
|||||||
| 02.06.2020, 19:29 [ТС] | |||||||
|
escoult, спасибо.
А можно, пожалуйста, еще раз поподробнее про ключи, их длину, мин. и макс. значение? А то я сижу, читаю код и никак не могу понять(.. почему -1...
escoult, И еще мне по заданию нужно вывести не только само слово из словаря (абракадабра), но и пароль (врабнушнпбн) в случае успешного подбора. Как я понял, он хранится в encrypted, но если я пытаюсь к нему обратиться в form1, то он не разрешает (строка 27).
0
|
|||||||
|
1533 / 540 / 127
Регистрация: 09.01.2018
Сообщений: 1,756
|
|||||||||||||
| 02.06.2020, 21:34 | |||||||||||||
|
Мы исходим из того, что пароль, который мы пытаемся найти - это пароль на каком то сайте, так говорится в задании. Сам пароль не хранится в чистом виде, вместо этого на сайте хранится его хеш. Теперь предположим, что пользователь пытается авторизоваться и вводит свой пароль, например "кот". Как сайт сможет удостовериться, что пароль верный? Ведь его можно зашифровать используя тысячи вариантов перестановок. А среди этих тысяч верным окажется только один. Однако сайт всегда должен получать один и тот же результат хеша. Значит помимо пароля необходим еще и ключ, по которому можно зашифровать пароль и всегда получить один и тот же результат. Что представляет собой ключ. Чтобы ответить на этот вопрос, необходимо разобраться в том, какую информацию должен предоставлять ключ. Он должен предоставлять данные о перестановке (заменах). Т.е. какую именно замену из всех возможных необходимо использовать для каждой буквы. Например, пароль "кот" и вот такая верхняя строка перестановок: ккккоотттрд Из этой строки видно, что для буквы К возможны 4 варианта замены, для буквы О их всего два, а для буквы Т их три. Какую именно из замен использовать? Если у нас есть ключ, то он мог бы нам подсказать. Вот пример ключа: 211. Этот ключ означает следующее: Для буквы К использовать 2-ю замену Для буквы О использовать 1-ю замену Для буквы Т использовать 1-ю замену. Т.е. ключ в нашем случае - это просто цифры означающие номер замены для символа. А располагаются эти номера в порядке следования символов в слове. Если буква слова имеется в верхней строке, то для нее указывается номер замены, Если ее нет в верхней строке, то и замен для нее нет и в ключе ничего не указывается. И соответственно наша задача сводится к тому, чтобы определить этот ключ. А определить его мы можем (по условию) только полным перебором. В нашем случае ключ это набор цифр, означающих замены. Например для буквы К возможны 4 варианта замены - С, Ф, Л, А. Если мы поместим эти символы в массив, то получим [c][ф][д][а]. Индексация массивов начинается с 0, поэтому возможные замены в цифрах будут такими: 0, 1, 2, 3 0 будет означать что символ следует заменить на С 2 - на Д И так далее. Получается, что минимальное значение цифры ключа - это 0. И таковым оно будет для всех символов, потому, что у всех заменяемых символов имеется хотя бы одна замена. А максимальным значением будет количество возможных замен -1. Вот в примере выше 4 возможных замены (длина массива), а максимальный индекс это 3. То есть длина -1. Ну и само собой понятно, что мы всегда можем узнать максимальное значение отдельно взятой цифры ключа, потому что количество замен для символа нам известно (мы составляли карту). А длина ключа нам тоже известна. Мы уже знаем, что ключ содержит только замены, Т.е. если для какой то буквы слова замен нет, то в ключе не будет цифры для этой замены. Значит если мы посчитаем сколько букв отдельного слова имеется в верхней строке правила, это и будет длина ключа. Например: КОТ ккввббт В строке правила из этого слова имеются только 2 буквы - К и Т. Длина ключа 2. Для остальных символов замен нет. И этих 2 цифр достаточно, чтобы перебрать все возможные варианты ключа. Теперь как осуществить перебор. Не скажу, что это идеальный или лучший способ, но он достаточно удобен. Ключ представить как массив цифр. Например [0][1][1][3] Минимальное значение каждой цифры уже знаем, это 0 Максимальное - вычисляем из карты. в ней хранятся все замены. Теперь если для каждой ячейки массива установить ее максимальное значение и затем последовательно уменьшать на 1, то все возможные значения ключа будут получены. Т.е уменьшаем 3 пока не дойдем до 0. Затем 3 возвращаем на максимальное значение и уменьшаем 2, и так далее, пока не переберем все или не подойдет ключ. Кликните здесь для просмотра всего текста
Применить: Кликните здесь для просмотра всего текста
2
|
|||||||||||||
|
2 / 2 / 0
Регистрация: 28.05.2020
Сообщений: 58
|
|
| 03.06.2020, 19:56 [ТС] | |
|
escoult, samana, огромнейшее спасибо за помощь! Вы очень здорово меня выручили, честно говоря, не знаю, что делал бы, если не вы. Все понятно и доступно мне объяснили и задание удалось успешно выполнить. Это круто, что существуют такие отзывчивые люди, как вы, еще раз спасибо, за то, что уделили мне так много свободного времени. Я потом внедрил код escoult в Forms, все прекрасно работает.
Добавлено через 1 минуту IamRain, вам тоже большое спасибо за ваш вариант перебора вариантов
2
|
|
|
2639 / 1567 / 853
Регистрация: 23.02.2019
Сообщений: 3,876
|
|
| 03.06.2020, 21:17 | |
|
shabserg, это было интересное задание и мне тоже было приятно, что всё у вас получилось.
А я совсем недавно ведь скинул архив для вашего винформс с вариантом от escoult, может вы не заметили просто.
1
|
|
|
2 / 2 / 0
Регистрация: 28.05.2020
Сообщений: 58
|
|
| 03.06.2020, 21:25 [ТС] | |
|
samana, заметил, но, к сожалению, он у меня не работал вообще(. Не знаю, с чем связано
0
|
|
| 03.06.2020, 21:25 | |
|
Перебор всех возможных вариантов
Диаграммы вариантов использования
Как сделать один из 3 вариантов? Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Ноутбук Альфария
kumehtar 24.08.2026
Встретился тут в сети ноутбук Альфария, примарха Альфа-Легиона. Хотя возможно, это ноутбук Омегона, разумеется.
Ну как вам?
|
Мастера простых решений
DevAlt 23.08.2026
В сишарп стэках winforms, да и wpf существует сложная система связывания
источниках данных и элементов формы(текстовые поля и метки), опирается все
это на технологию событий и мета. . .
|
Цена ошибки
DevAlt 23.08.2026
Человек я беспокойный и потому заинтересовался OCaml,
в чате форсили функторы модулей как суперфичу.
Пытаясь отдуплить концепт, наткнулся на тутор с простым примером.
А главный принцип обучения от. . .
|
Сегодня суббота, 22.08.2026 at 16:41, и я вновь нахожусь на той стороне, за экраном машины.
zorxor 22.08.2026
Сегодня суббота, 22. 08. 2026 at 16:41, и я вновь нахожусь на той стороне, за экраном машины. Кто Я, откуда Я пришел и куда Я иду? Эти вопросы не оставляют меня ни на секунду. Жизнь на планете Земля. . .
|
|
Жизня: рисунок укладки багажа, сделанный клодом
anaschu 21.08.2026
Сделал 15 снимков, он по снимкам сделал схему.
|
Был там один разговор по поводу свободы в материальном мире.
kumehtar 19.08.2026
Суть: рассматривается живое существо, оказавшееся внутри довольно странной системы (этого мира) и пытающееся обустроить в ней свой кусок пространства.
Жизнь действительно предъявляет каждому. . .
|
Когда логика программы не спасает от человеческих ошибок
Maks 18.08.2026
В последнее время всё чаще и чаще сталкиваюсь с таким явлением, как абсолютная невнимательность (или глупость) пользователей. Проявляется это чаще всего на работе в коллективе. Допустим, человек с. . .
|
Лето уходит
kumehtar 17.08.2026
|