подстановка шифра со словарем - PullRequest
Новая
       17

подстановка шифра со словарем

0 голосов
/ 30 января 2012

Мое домашнее задание - расшифровать предложение на основе известного и конечного словаря.

Пример: Dict - покажи, дуй, пока

тогда код 12345 8291 поступил в качестве ввода. если мы проверим возможности, единственная опция - "пока покажи".

Может кто-нибудь дать мне направление или известный алгоритм, который решает эту проблему. псевдокод или java будут великолепны.

спасибо

1 Ответ

0 голосов
/ 30 января 2012

Вам необходимо внедрить какой-то вид возврата или другой метод поиска.Я бы предложил следующий подход:

  1. Создайте таблицу переводов с шифра на символ.Первоначально каждый шифр (цифра) отображается в 0 (ничего).
  2. Обработка ввода.Каждый раз, когда вы сталкиваетесь с неназначенной цифрой, у вас есть выбор букв на основе словаря и того, что было определено до сих пор.Если нет назначаемых букв, вернитесь назад (или сообщите об ошибке любым способом, который имеет смысл для вашей техники поиска).Добавьте каждый выбор в свою логику управления поиском.(Например, если вы используете возвратный путь, сохраните список вариантов и запишите произвольный выбор в таблице перевода. Если вы вернетесь к этой точке, назначьте другой выбор.)
  3. Продолжайте, пока не доберетесь доконец или у вас закончились выборы.

РЕДАКТИРОВАТЬ: На шаге 2 сложная часть определяет, какие буквы (если таковые имеются) могут быть назначены следующей цифре шифра.Предположим, что мы отслеживаем декодированное текущее слово и хотим обработать следующую цифру шифра в слове.У нас уже есть глобальная карта присвоений цифр.Логика может выглядеть примерно так (в псевдокоде Java-ish): 

Set assignableLetters(String wordSoFar, int nextCipher) {
    Character assignment = map.get(nextCipher);
    Set set = new Set();
    if (assignment != null) {
        // The next cipher is already assigned. Add the assignment to the
        // return set only if it is compatible with the dictionary contents
        if (dictionary.hasWordsWithPrefix(wordSoFar + assignment)) {
            set.add(assignment);
        }
    } else {
        // The next cipher is not assigned. We will return a set of all
        // compatible characters that can be assigned to it.
        for (Character c : unassignedCharacters()) {
            if (dictionary.hasWordsWithPrefix(wordSoFar + c)) {
                set.add(c);
            }
        }
    }
    return set;
}

Если при этом возвращается пустой набор, текущее назначение (до вызова метода) несовместимо со словарем, и поиск долженотступаться.В противном случае поиск должен выбрать одно назначение за раз из набора и продолжить, при необходимости возвращая обратно.

Вместо того, чтобы пытаться использовать каждый неназначенный символ и спрашивать в словаре, совместим ли он, он может быть более эффективным (но логическиэквивалентно) напрямую запросить в словаре список совместимых следующих символов и пересечь его с набором неназначенных символов.

...