Контрольные задания
Вопрос:Фото задания: 1. Валя шифрует русские слова (последовательности букв), записывая вместо каждой буквы её код: АДКНОС 01 100 101 10 111 000…Фото задания

Ответ:

Привет! Давай попробуем разобраться с этим шифром.

У нас есть буквы и их коды:

  • А - 01
  • Д - 100
  • К - 101
  • Н - 10
  • О - 111
  • С - 000

Смотри, некоторые коды состоят из одной или двух цифр (10, 01, 000), а некоторые из трех (100, 101, 111).

Когда мы видим код, мы должны решить, как его разбить на отдельные коды букв. Например, если у нас есть код 10111000, мы можем получить:

  • 101 (К) + 111 (О) + 000 (С) = КОС

Или, если бы у нас был код 01100101:

  • 01 (А) + 100 (Д) + 101 (К) = АДК

А еще может быть так, что одна и та же комбинация цифр может быть началом разных слов. Например, 00010101:

  • 000 (С) + 101 (К) + 01 (А) = СКА
  • 000 (С) + 10 (Н) + 101 (К) = СНК

Наша задача — найти такую кодовую цепочку из трех данных, которая имеет только ОДНУ возможную расшифровку.

Давай проверим каждую цепочку:

  1. 100101000
    • Вариант 1: 100 (Д) + 101 (К) + 000 (С) = ДКС
    • Вариант 2: 100 (Д) + 10 (Н) + 1000 (нет такого кода)
    • Вариант 3: 1001 (нет такого кода)
    • Вариант 4: 1 (нет такого кода)

    Похоже, что ДКС — единственная расшифровка для этой цепочки.

  2. 101111100
    • Вариант 1: 101 (К) + 111 (О) + 100 (Д) = КОД
    • Вариант 2: 101 (К) + 111 (О) + 10 (Н) + 0 (нет такого кода)
    • Вариант 3: 101 (К) + 11 (нет такого кода)
    • Вариант 4: 10 (Н) + 111 (О) + 1100 (нет такого кода)

    Смотри, тут тоже похоже, что КОД — единственная расшифровка.

  3. 100111101
    • Вариант 1: 100 (Д) + 111 (О) + 101 (К) = ДОК
    • Вариант 2: 100 (Д) + 111 (О) + 10 (Н) + 1 (нет такого кода)
    • Вариант 3: 100 (Д) + 11 (нет такого кода)
    • Вариант 4: 10 (Н) + 0111 (нет такого кода)
    • Вариант 5: 100 (Д) + 111 (О) + 1 (нет такого кода)

    Здесь тоже похоже, что ДОК — единственная расшифровка.

Хм, кажется, я ошиблась в проверке. Давай посмотрим внимательнее на пример:

00010101 может быть СКА (000 + 101 + 01) ИЛИ СНК (000 + 10 + 101).

Это значит, что коды могут пересекаться.

Давай попробуем еще раз:

А-01, Д-100, К-101, Н-10, О-111, С-000

  1. 100101000
    • 100 (Д) + 101 (К) + 000 (С) = ДКС
    • 100 (Д) + 10 (Н) + 1000 (нет кода)
    • 10 (Н) + 0101000 (нет кода)

    Похоже, что ДКС — единственная расшифровка.

  2. 101111100
    • 101 (К) + 111 (О) + 100 (Д) = КОД
    • 101 (К) + 111 (О) + 10 (Н) + 0 (нет кода)
    • 101 (К) + 11 (нет кода)
    • 10 (Н) + 111 (О) + 1100 (нет кода)

    Похоже, что КОД — единственная расшифровка.

  3. 100111101
    • 100 (Д) + 111 (О) + 101 (К) = ДОК
    • 100 (Д) + 111 (О) + 10 (Н) + 1 (нет кода)
    • 100 (Д) + 10 (Н) + 111101 (нет кода)
    • 10 (Н) + 0111101 (нет кода)

    И здесь похоже, что ДОК — единственная расшифровка.

Давай посмотрим ещё раз на пример: 00010101 -> СКА (000-101-01), СНК (000-10-101).

Значит, коды могут перекрываться.

В первой цепочке 100101000:

100(Д) + 101(К) + 000(С) = ДКС

100(Д) + 10(Н) + 1000 (нет кода)

10(Н) + 0101000 (нет кода)

100101000 - кажется, что только ДКС.

Во второй цепочке 101111100:

101(К) + 111(О) + 100(Д) = КОД

101(К) + 111(О) + 10(Н) + 0 (нет кода)

101(К) + 10(Н) + 11100 (нет кода)

10(Н) + 111(О) + 1100 (нет кода)

101111100 - кажется, что только КОД.

В третьей цепочке 100111101:

100(Д) + 111(О) + 101(К) = ДОК

100(Д) + 111(О) + 10(Н) + 1 (нет кода)

100(Д) + 10(Н) + 111101 (нет кода)

10(Н) + 0111101 (нет кода)

100111101 - кажется, что только ДОК.

Возможно, я неправильно поняла условие про перекрытие. Давай попробуем иначе. В задаче говорится, что некоторые цепочки можно расшифровать не одним способом. Это значит, что одна и та же последовательность цифр может быть разбита по-разному.

Ключ:

  • А - 01
  • Д - 100
  • К - 101
  • Н - 10
  • О - 111
  • С - 000

Проверяем цепочки:

  1. 100101000
    • 100 (Д) + 101 (К) + 000 (С) = ДКС
    • Есть ли другие варианты? Например, если мы начнем с 10 (Н)? Тогда останется 0101000. Из этого мы можем получить 01 (А) + 01000 (нет кода). Или 010 (нет кода).

    Скорее всего, ДКС — единственная расшифровка.

  2. 101111100
    • 101 (К) + 111 (О) + 100 (Д) = КОД
    • Если начнем с 10 (Н)? Тогда останется 1111100. Из этого можно получить 111 (О) + 1100 (нет кода). Или 111 (О) + 100 (Д). Получится НОД.

    Значит, 101111100 имеет как минимум две расшифровки: КОД и НОД. Эта цепочка нам не подходит.

  3. 100111101
    • 100 (Д) + 111 (О) + 101 (К) = ДОК
    • Если начнем с 10 (Н)? Тогда останется 0111101. Из этого можно получить 01 (А) + 11101 (нет кода). Или 011 (нет кода).
    • А если посмотрим на конец: 101 (К). Тогда впереди 10011110. Можно получить 100 (Д) + 111 (О) + 10 (Н) = ДОН.

    Значит, 100111101 имеет как минимум две расшифровки: ДОК и ДОН. Эта цепочка нам не подходит.

Остается первая цепочка: 100101000. Мы выяснили, что она может быть расшифрована как ДКС (100 + 101 + 000).

Давай еще раз проверим, можно ли ее разбить по-другому. Если начнем с 10 (Н), то останется 0101000. Из этого можно получить 01 (А) + 01000 (нет). Или 010 (нет). Или 0101 (нет). Или 01010 (нет). Или 010100 (нет).

Так что, похоже, ДКС — единственная расшифровка.

Ответ: ДКС