|
2 / 2 / 0
Регистрация: 28.05.2020
Сообщений: 58
|
|
Перебор вариантов29.05.2020, 11:26. Показов 6070. Ответов 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,757
|
||
| 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,757
|
||||||||||||||||
| 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,757
|
|
| 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,757
|
|||||||||||||
| 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 вариантов? Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
| Опции темы | |
|
|
Новые блоги и статьи
|
|||
|
Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0.
Maks 31.08.2026
При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка:
Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .
|
Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм
anaschu 30.08.2026
Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо
Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .
|
Оттачиваю умение писать js программы.
russiannick 30.08.2026
Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман.
Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .
|
мат медиц модель 30. презентация проекта
anaschu 27.08.2026
хоп хоп хоп хидахоп, а я кладую))
|
|
Как у меня протекала болезнь
zorxor 27.08.2026
Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .
|
Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему
kumehtar 26.08.2026
ILETXiw9bMQ
Основная суть и тезисы по измерениям:
0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема.
Объект не может перемещаться в 0D.
1D (Первое измерение):. . .
|
[EasyBuilder Pro] Памятка по разработке для панелей Weintek
ФедосеевПавел 26.08.2026
Памятка по разработке для панелей Weintek
ВВЕДЕНИЕ
Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .
|
Модель по догадкам
anaschu 25.08.2026
Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .
|