Презентация по информатике для подготовки учащихся к ОГЭ: задача 7 (декодирование)

Декодирование (ОГЭ, задача 7) Мочалова Марина Владимировна Учитель информатики ГБОУ лицей №144 Калининского района г. Санкт­Петербург

Содержание 1.Теория 2.Разбор решений задач 3.Задачи для  самостоятельного решения 4.Источники

Теория Задачи данного типа нельзя отнести к заданиям повышенной  сложности. Как правило, они относительно легко решаются с помощью  логических рассуждений. Но при этом, как показывает опыт подготовки  учащихся к ОГЭ, процент ошибочных ответов достаточно велик. Это  объясняется тем, что кажущаяся легкость притупляет внимательность.  Совет: при решении задач на однозначное декадировывание следует  сначала проверить на однозначное прочтение начала цепочки или ее  конца. Если такой код имеется, то убрать этот однозначно читаемый  код,  тогда оставшаяся часть станет короче и работать с ней будет легче.  При расшифровывании цепочку символов читаем от начала, пытаясь  последовательно отделять минимальное количество символов,  образующих коды. Далее для этой же цепочки вновь повторяем  алгоритм разделения символов на коды, но при этом коды увеличиваем  по количеству символов. Таким образом, для каждой цепочки получим  несколько различных вариантов декодирования. Ответом будет та цепочка, в которой деление на коды – единственное.  Совет: если первая же цепочка декодируется однозначно, все же  проверить остальные цепочки для исключения ошибки.

Задание 1. Ваня шифрует русские слова, записывая вместо каждой буквы ее  номер в алфавите (без пробелов). Номера букв даны в таблице. Разбор решения задач 2 Й 11 3 4 28 20 Ы 29 Т К 12 У 21 Ъ 30 Л 13 Ф 22 Э 31 23 Ю 32 6 Н 15 Ц 24 Я 33 7 А 1 И 10 С 19 Ь Б В Г Д 5 М 14 Х Е Ё О 16 Ч 25 Ж 8 П 17 Ш 26 18 Щ 27 З 9 Р Некоторые шифровки можно расшифровать несколькими  способами. Например,  311333 может означать «ВАЛЯ», может  «ЭЛЯ», а может «ВААВВВ». Даны четыре шифровки: 3113   9212   6810   2641 Найдите ту, которая расшифровывается единственным способом.

Разбор решения задач Решение задачи: Решение задачи начнем с анализа первой записи ­ 3113.  Поскольку в алфавите 33 буквы, то либо первая цифра 3  означает букву В, либо первым стоит число 31 (буква Э).  Следующие цифры 1 и 3 могут быть либо одним числом (буква  Л), либо двумя отдельными (буквы А и В). Таким образом,  первая запись имеет варианты: ВААВ, ЭАВ, ЭЛ. Во второй записи цифра 9 – это буква З. Далее могут быть  варианты – 2­1­2, 2­12 и 21­2, что не удовлетворяет условию  задачи. Аналогично исключается и последняя шифровка. В последней записи 6810 первая цифра 6 имеет однозначное  решение – буква Е (номера 68 в таблице нет). Далее аналогично  может стоять только номер 8 (буква Ж). Последние две цифры  10 могут означать только букву И, поскольку буквы с номером  0 в таблице нет.  Итого, ответ: ЕЖИ.

Задание 2. Ваня шифрует русские слова, записывая вместо каждой буквы ее  номер в алфавите (без пробелов). Номера букв даны в таблице. Разбор решения задач Ь И 10 С Й 11 Т К 12 У Л 13 Ф 22 Э 19 28 20 Ы 29 21 Ъ 30 31 23 Ю 32 33 А 1 Б 2 3 В 4 Г Д 5 М 14 Е 6 Ё 7 Ж 8 9 З Х Н 15 Ц 24 Я О 16 Ч 25 П 17 Ш 26 18 Щ 27 Р Некоторые шифровки можно расшифровать несколькими  способами. Например,  311333 может означать «ВАЛЯ»,  может «ЭЛЯ», а может «ВААВВВ». Даны четыре шифровки:     112233    135793     203014    412030 Только одна из них расшифровывается единственным  способом. Найдите ее и расшифруйте. То, что получилось,  запишите в качестве ответа.

Разбор решения задач Решение задачи: Решение задачи начнем с анализа первой записи ­ 112233.  Первые цифры 11 могут означать либо АА, либо Й, что сразу  исключает этот вариант как неоднозначный.  Во втором числе 135793 аналогично первые цифры могут быть  или буквами АВ, или Л. Запись неоднозначная, исключаем. В третьей записи 203014 первые цифры могут читаться только  как 20, так как номера, начинающегося с 0, нет. Далее (30) тоже  читается однозначно. А вот последние цифры (14) могут быть  как М и как АГ. Запись исключаем. В записи 412030 первая цифра 4 (номера 41 нет). Далее только  число 1, в противном случае (если будет число 12) следующее  число будет начинаться на 0, а такого номера нет. Таким  образом, запись состоит из чисел 4­1­20­30. Это запись ГАТЪ.  Итого, ответ: ГАТЪ.

Задание 3. Ваня шифрует русские слова, записывая вместо каждой буквы ее  номер в алфавите (без пробелов). Номера букв даны в таблице. Разбор решения задач Ь И 10 С Т Й 11 К 12 У Л 13 Ф 22 Э 19 28 20 Ы 29 21 Ъ 30 31 23 Ю 32 33 А 1 2 Б В 3 4 Г Д 5 М 14 6 Е Ё 7 Ж 8 З 9 Х Н 15 Ц 24 Я О 16 Ч 25 П 17 Ш 26 Р 18 Щ 27 Некоторые шифровки можно расшифровать несколькими  способами. Например,  311333 может означать «ВАЛЯ»,  может «ЭЛЯ», а может «ВААВВВ». Даны четыре шифровки:    1012    1210     1565     5651 Только одна из них расшифровывается единственным  способом. Найдите ее и расшифруйте. То, что получилось,  запишите в качестве ответа.

Разбор решения задач Решение задачи: Решение задачи начнем с анализа первой записи ­ 1012.  Поскольку в алфавите нет номера, начинающегося на 0, то  первые цифры это только 10. Следующие цифры 1 и 2 могут  быть либо одним числом (буква К), либо двумя отдельными  (буквы А и Б). Запись читается неоднозначно, исключаем. Во второй записи 1210 первые цифры 12 могут быть либо 1­2  (АБ) либо 12 (К). Запись исключаем из­за ее неоднозначности. В третьей записи 1565 первые цифры 15 могут быть либо 1­5  (АД) либо 15 (Н). Эту запись также исключаем. В записи 5651 первой может быть только цифра 5 (так как  номера 56 в таблице нет). Далее, аналогично, может быть  только цифра 6. Последние цифры 51 могут означать только  один возможный вариант 5­1. Запись однозначна ­  ДЕДА. Итого, ответ: ДЕДА.

Задание 4. Ваня шифрует русские слова, записывая вместо каждой буквы ее  номер в алфавите (без пробелов). Номера букв даны в таблице. Разбор решения задач Ь И 10 С Т Й 11 К 12 У Л 13 Ф 22 Э 19 28 20 Ы 29 21 Ъ 30 31 23 Ю 32 33 А 1 2 Б В 3 4 Г Д 5 М 14 6 Е Ё 7 Ж 8 З 9 Х Н 15 Ц 24 Я О 16 Ч 25 П 17 Ш 26 Р 18 Щ 27 Некоторые шифровки можно расшифровать несколькими  способами. Например,  311333 может означать «ВАЛЯ», может  «ЭЛЯ», а может «ВААВВВ». Даны четыре шифровки:     8102030    8112131     8112233    8152535 Только одна из них расшифровывается единственным способом.  Найдите ее и расшифруйте. То, что получилось, запишите в  качестве ответа.

Разбор решения задач Решение задачи: Решение задачи начнем с анализа первой записи ­ 8102030.  Поскольку в алфавите 33 буквы, то первая цифра это 8.  Далее может стоять только 10, так как нет номера,  начинающегося с 0. Аналогично далее стоят 20­30. Этот  вариант читается однозначно и можно его принять в качестве  ответа (ЖИТЪ).  Но для точного решения проверим 2­3­4 варианты. Второй  вариант 8112131: первая цифра только 8, но далее идут два  варианта – либо 1­1 либо 11. Запись исключаем. В третьей (8112233) и четвертой (8152535) аналогичное  неоднозначное прочтение второй и третьей цифр 11 или 15.  Поэтому эти записи тоже исключаются. Итого, ответ: ЖИТЪ.

Задание 5. Ваня шифрует русские слова, записывая вместо каждой буквы ее  номер в алфавите (без пробелов). Номера букв даны в таблице. Разбор решения задач Ь И 10 С Т Й 11 К 12 У Л 13 Ф 22 Э 19 28 20 Ы 29 21 Ъ 30 31 23 Ю 32 33 А 1 2 Б В 3 4 Г Д 5 М 14 6 Е Ё 7 Ж 8 З 9 Х Н 15 Ц 24 Я О 16 Ч 25 П 17 Ш 26 Р 18 Щ 27 Некоторые шифровки можно расшифровать несколькими  способами. Например,  311333 может означать «ВАЛЯ», может  «ЭЛЯ», а может «ВААВВВ». Даны четыре шифровки:     3102030    3102033    3112030     3112233 Только одна из них расшифровывается единственным  способом. Найдите ее и расшифруйте. То, что получилось,  запишите в качестве ответа.

Разбор решения задач Решение задачи: Решение задачи начнем с анализа первой записи ­ 3102030.  Поскольку в алфавите нет номера, начинающегося на 0, то  первой идет цифра 3, а не 31. Далее идут 10­20­30. Запись  читается однозначно, является решением (ВИТЪ). Но для точного решения проверим 2,3,4 варианты.  Второй вариант 3102033: первая цифра может быть только 3,  далее идут только 10­20. А последние цифры 33 читаются  двояко (33 или 3­3), поэтому эту запись исключаем. В третьей (3112030) и четвертой (3112233) записях прочтение  первой и второй цифр 31 ­ неоднозначно (31 или 3­1).  Поэтому эти записи тоже исключаем. Итого, ответ: ВИТЪ.

Задание 6.   Валя шифрует русские слова (последовательности букв), записывая  вместо каждой буквы её код: Разбор решения задач А Д К Н О С 01 100 101 10 111 000 Некоторые цепочки можно расифровать не одним способом.  Например, 00010101 может означать не только СКА, но и СНК.  Даны три кодовые цепочки:   100101000 101111100 100111101   Найдите среди них ту, которая имеет только одну  расшифровку, и запишите в ответе расшифрованное слово.

Разбор решения задач Решение задачи: Анализируем цепочки поочередно. В первой цепочке на конце может быть только буква С (000).  Оставшаяся часть 100101 может быть расшифрована двояко:  10­01­01 или 100­101, поэтому этот вариант не подходит. Во второй цепочке на конце может быть только буква Д (100).  Оставшаяся часть 101111 может быть расшифрована только  одним способом: 101­111 (КО), поскольку если в начале будет  стоять буква Н (10), то далее может быть только буква О (111)  и тогда остается одна цифра 1, а такой буквы в условии нет.  Цепочка удовлетворяет условию задачи. Проверим и третью цепочку. В ней может быть два варианта  расшифровки: 100­111­101 или 10­01­111­01. Поэтому эта цепочка не может быть ответом. Итого, ответ: КОД.

Задание 7.   Валя шифрует русские слова (последовательности букв), записывая  вместо каждой буквы её код: Разбор решения задач А Д К Н О С 01 100 101 10 111 000 Некоторые цепочки можно расифровать не одним способом.  Например, 00010101 может означать не только СКА, но и СНК.  Даны три кодовые цепочки:   100101000 100000101 0110001   Найдите среди них ту, которая имеет только одну  расшифровку, и запишите в ответе расшифрованное слово.

Решение задачи: Разбор решения задач Анализируем цепочки поочередно. В первой цепочке на конце может быть только буква С (000).  Оставшаяся часть 100101 может быть расшифрована двояко:  10­01­01 или 100­101, поэтому этот вариант не подходит. Во второй цепочке 100000101 есть два варианта прочтения:  10­000­01­01 или 100­000­101, поэтому этот вариант  исключаем. Рассматриваем третью цепочку 0110001. Первой может быть только буква А (01), поскольку кода 011 в  таблице нет. Далее остается 10001. если предположить, что  первой стоит буква Н (10), то остается 001, а такой буквы нет.  Значит, есть единственное решение этого кусочка: 100­01  (ДА). Третья цепочка удовлетворяет условию задачи. Итого, ответ: АДА

Задание 8.   Валя шифрует русские слова (последовательности букв), записывая  вместо каждой буквы её код: Разбор решения задач К Д А С 01 100 101 10 111 000 Н О Некоторые цепочки можно расифровать не одним способом.  Например, 00010101 может означать не только СКА, но и  СНК.  Даны три кодовые цепочки:   10111101 100111101 0000110   Найдите среди них ту, которая имеет только одну  расшифровку, и запишите в ответе расшифрованное слово.

Решение задачи: Разбор решения задач Анализируем цепочки поочередно. Первая цепочка 10111101 может быть расшифрована двояко:  10­111­101 или 101­111­01, поэтому этот вариант не подходит. Вторая цепочка 100111101 также может быть расшифрована  двумя способами:   100­111­101 или 10­01­111­01. Исключаем ее. Проверим третью цепочку 0000110.  В начале ее может стоять только 000 (С), поскольку в таблице  нет буквы с кодом 00. Далее остается цепочка 0110. Она имеет  только одно решение: 01­10 (АН). Поэтому третья цепочка  является ответом. Итого, ответ: САН.

Задание 9.   Валя шифрует русские слова (последовательности букв), записывая  вместо каждой буквы её код: Разбор решения задач А Д К Н О С 01 100 101 10 111 000 Некоторые цепочки можно расифровать не одним способом.  Например, 00010101 может означать не только СКА, но и СНК.  Даны три кодовые цепочки:   10111101 1010110 10111000   Найдите среди них ту, которая имеет только одну  расшифровку, и запишите в ответе расшифрованное слово.

Разбор решения задач Решение задачи: Анализируем цепочки поочередно. Первая цепочка 10111101 может начинаться как на 10,  так и на 101, поскольку оставшаяся часть может быть  расшифрована (10­111­101 или 101­111­01). Не может  быть ответом. Во второй цепочке 1010110 ситуация аналогичная,  варианты 10­101­10 или 101­01­10, она не удовлетворяет  условию задачи. Проверим третью цепочку 10111000. В конце ее может  быть только 000 (С). В оставшейся части 10111 в начале  может быть только 10, поскольку в противном случае  (если взять 101) остается 11, а такой буквы в таблице нет. Поэтому эта цепочка расшифровывается однозначно и  является ответом. Итого, ответ: НОС.

Задание 10.   Валя шифрует русские слова (последовательности букв), записывая  вместо каждой буквы её код: Разбор решения задач А Д К Н О С 01 100 101 10 111 000 Некоторые цепочки можно расифровать не одним способом.  Например, 00010101 может означать не только СКА, но и СНК.  Даны три кодовые цепочки:   10111101 100111101 0000110   Найдите среди них ту, которая имеет только одну  расшифровку, и запишите в ответе расшифрованное слово.

Разбор решения задач Решение задачи: Анализируем цепочки поочередно. В первой цепочке на конце может быть только буква С  (000). Оставшаяся часть 100101 может быть  расшифрована двояко: 10­01­01 или 100­101, поэтому  этот вариант не подходит. Во второй цепочке на конце может быть только буква Д  (100). Оставшаяся часть 101111 может быть  расшифрована только одним способом: 101­111 (КО),  поскольку если в начале стоит буква Н (10), то далее  может быть только буква О (111) и тогда остается одна  цифра 1, а такой буквы в условии нет. Цепочка  удовлетворяет условию задачи. Проверим и третью цепочку. В ней может быть два  варианта расшифровки: 100­111­101 или 10­01­111­01. Поэтому эта цепочка не может быть ответом. Итого, ответ: КОД.

Задание 11.   Валя шифрует русские слова (последовательности букв), записывая  вместо каждой буквы её код: Разбор решения задач А Д К Н О С 01 100 101 10 111 000 Некоторые цепочки можно расшифровать несколькими  способами. Например, 00010101 может означать не только  СКА, но и СНК.  Даны три кодовые цепочки:   1010110 11110001 100000101   Найдите среди них ту, которая имеет только одну  расшифровку, и запишите в ответе расшифрованное слово

Разбор решения задач Решение задачи: Анализируем цепочки поочередно. В первой цепочке на конце может быть только буква С (000).  Оставшаяся часть 100101 может быть расшифрована двояко:  10­01­01 или 100­101, поэтому этот вариант не подходит. Во второй цепочке на конце может быть только буква Д (100).  Оставшаяся часть 101111 может быть расшифрована только  одним способом: 101­111 (КО), поскольку если в начале стоит  буква Н (10), то далее может быть только буква О (111) и  тогда остается одна цифра 1, а такой буквы в условии нет.  Цепочка удовлетворяет условию задачи. Проверим и третью цепочку. В ней может быть два варианта  расшифровки: 100­111­101 или 10­01­111­01. Поэтому эта цепочка не может быть ответом. Итого, ответ: КОД.

Разбор решения задач Задача 12.   Мальчики играли в шпионов и кодировали сообщения  собственным шифром. Фрагмент кодовой таблицы приведён  ниже: КК Л М @+ ~+ +@ П @~+ О И + ~ Расшифруйте сообщение, если известно, что буквы в нём не  повторяются: + ~ + ~ + @ @ ~ + Запишите в ответе расшифрованное сообщение.

КК Л М @+ П @~+ +@ ~+ + ~ + ~ + @ @ ~ + Разбор решения задач О И + ~ Решение: особенность задач подобного типа состоит в том, что  дана одна лишь цепочка символов, которая должна быть  декодирована.  В начале цепочки стоит однозначно читаемый символ, это " +  " (О). Рассматриваем цепочку далее " ~ + ~+@@~ + ".  Поскольку по условию задачи все буквы в шифровке разные,  то цепочку нельзя разбить на отдельные символы "~" и " + " .  Значит, следующей буквой может быть только Л (~ +). Далее  может идти только буква И (~). Следующая буква также  однозначно читаемая, это М (+ @).  И остаются символы "@ ~ +" , это буква П. Ответ: ОЛИМП

Разбор решения задач Задача 13.   Мальчики играли в шпионов и кодировали сообщения  собственным шифром. Фрагмент кодовой таблицы приведён  ниже: КК ~ Л * П М *@ @~* @* О И ~* Расшифруйте сообщение, если известно, что буквы в нём не  повторяются: * @ @ ~ * * ~ * ~ Запишите в ответе расшифрованное сообщение.

КК ~ Л * П М *@ @~* @* О И ~* Разбор решения задач * @ @ ~ * * ~ * ~ Рассматриваем цепочку от ее начала. Выделить первый  символ * (Л) нельзя, поскольку в таблице нет букв,  соответствующих символам @ и @ @ . Поэтому первой буквой  может быть только М (*@). Следующие символы декодируются однозначно, это буква П  (@~*). Рассматриваем цепочку далее " * ~ * ~ ". Поскольку по  условию задачи все буквы в шифровке разные, то цепочку  нельзя разбить на отдельные символы "*" и "~ " . Значит,  следующей буквой может быть только Л (*). Далее может  идти только буква И (~*). И последней будет буква К (~). Ответ: МПЛИК