10(Базовый уровень, время – 4 мин)
Тема: Кодирование данных, комбинаторика, системы счисления.
Что нужно знать:
принципы работы с числами, записанными в позиционных системах счисления
если слово состоит из Lбукв, причем естьn1вариантов выбора первой буквы,n2вариантов выбора второй буквы и т.д., то число возможных слов вычисляется как произведение
N = n1 · n2 · … · nL
если слово состоит из Lбукв, причем каждая буква может быть выбранаnспособами, то число возможных слов вычисляется какN = n L
Пример задания:
Р-06. Вася составляет 5-буквенные слова, в которых есть только буквы С, Л, О, Н, причём буква С используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
буква С может стоять на одном из пяти мест: С****, *С***, **С**, ***С* и ****С, где * обозначает любой из оставшихся трёх символов
в каждом случае в остальных четырёх позициях может быть любая из трёх букв Л, О, Н, поэтому при заданном расположении буквы С имеем 3 4 = 81 вариант
всего вариантов 5 · 81 = 405.
Ещё пример задания:
Р-05. Сколько существует различных символьных последовательностей длины 5 в четырёхбуквенном алфавите , которые содержат ровно две буквы A?
Решение (вариант 1, перебор):
рассмотрим различные варианты слов из 5 букв, которые содержат две буквы А и начинаются с А:
Здесь звёздочка обозначает любой символ из набора , то есть один из трёх символов.
итак, в каждом шаблоне есть 3 позиции, каждую из которых можно заполнить тремя способами, поэтому общее число комбинаций (для каждого шаблона!) равно 3 3 = 27
всего 4 шаблона, они дают 4 · 27 = 108комбинаций
теперь рассматриваем шаблоны, где первая по счёту буква А стоит на второй позиции, их всего три:
они дают 3 · 27 = 81комбинацию
два шаблона, где первая по счёту буква А стоит на третьей позиции:
они дают 2 · 27 = 54комбинации
и один шаблон, где сочетание АА стоит в конце
они дают 27комбинаций
всего получаем (4 + 3 + 2 + 1) · 27 = 270комбинаций
Решение (вариант 2, использование формул комбинаторики):
в последовательности из 5 символов нужно использовать ровно две буквы А и три символа, не совпадающих с А, которые обозначим звездочкой
сначала найдём количество перестановок из двух букв А и трёх звёздочек
используем формулу для вычисления числа перестановок с повторениями; для двух разных символов она выглядит так:
Здесь 
– количество букв А,
– количество звёздочек и восклицательный знак обозначаетфакториалнатурального числа, то есть произведение всех натуральных чисел от 1 до
:
в нашем случае 
и
, так что получаем
теперь разберёмся со звёздочками: вместо каждой из них может стоять любой из трёх символов (кроме А), то есть на каждую из 10 перестановок мы имеем 3 3 = 27 вариантов распределения остальных символов на месте звёздочек
Презентация «ЕГЭ-2020. Информатика. 10 задание»
Вася составляет 3-буквенные слова , в которых есть только буквы М, У, Х, А. Сколько существует таких слов, которые может написать Вася?
- Буквы могут повторяться
- Каждую букву можно использовать только один раз
1) в каждом случае в трех позициях может быть любая из четырех букв М, У, Х, А , поэтому имеем 4 3 = 64 слова
- всего вариантов 4 · 3 · 2 = 24 слова.
Вася составляет 5-буквенные слова , в которых есть только буквы В, О, Л, К, причём буква В используется в каждом слове ровно 1 раз . Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
- буква В может стоять на одном из пяти мест:
**** В , где * обозначает любой из оставшихся трёх символов ( О, Л, К )
- в каждом случае в остальных четырёх позициях может быть любая из трёх букв О, Л, К , поэтому при заданном расположении буквы В имеем 34= 81 вариант
- всего вариантов 5 · 81 = 405 .
Сколько слов длины 5 , начинающихся с согласной буквы , можно составить из букв М, И, Р ? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
- первая буква слова может быть выбрана двумя способами ( М или Р ), остальные – тремя ( М, И и Р )
- общее число различных слов равно 2*3*3*3*3 = 162
Сколько существует различных символьных последовательностей длины 5 в четырёхбуквенном алфавите < A, З, О, T >, которые содержат ровно две буквы A ?
- рассмотрим различные варианты слов из 5 букв, которые содержат две буквы А и начинаются с А:
в каждом шаблоне есть 3 позиции, каждую из которых можно заполнить тремя способами ( З, О, T) , поэтому общее число комбинаций (для каждого шаблона!) равно 3 3 = 27
всего 4 шаблона, они дают 4 · 27 = 108 комбинаций
- далее рассматриваем шаблоны, где первая по счёту буква А стоит на второй позиции: *АА**, *А*А*, *А**А они дают 3· 27 = 81 комбинацию
3)два шаблона, где первая по счёту буква А стоит на третьей позиции: они дают 2 · 27 = 54 комбинации **АА*, **А*А 4) и один шаблон, где сочетание АА стоит в конце: ***АА они дают 27 комбинаций
5) всего получаем 108+81+54+27=270
Вася составляет 5-буквенные слова из букв П, А, Н, Е, Л, Ь. При этом слово не может начинаться с буквы Ь . Сколько различных слов может составить Вася?
1) Всего составить 5 буквенные слова возможно 6 5 = 7776 способами
2) рассмотрим различные варианты слов из 6 букв, которые содержат первую букву Ь:
6 4 = 1296 комбинаций
Итого 7776-1296=6480 комбинация
Первую букву можно заполнить 5 способами, остальные 6 способами
5 · 6 · 6 · 6 · 6= 5 · 6 4 = 5 · 1296=6480 комбинаций
Вася составляет 6-буквенные коды из букв П, А, Н, Е, Л, Ь. Каждую букву нужно использовать ровно 1 раз , при этом код не может начинаться с буквы Ь и не может содержать сочетания ЕЬ . Сколько различных кодов может составить Вася?
1) Всего составить 6 буквенные слова возможно 6! = 6 5 4 3 2 1 =720 способами
2) рассмотрим различные варианты слов из 6 букв, которые содержат первую букву Ь:
Ь***** 1 5 4 3 2 1 = 120 комбинаций
3) Рассмотрим следующее исключение: ЕЬ
для каждого из остальных случаев количество вариантов распределения остальных букв равно 4 3 2 1 = 24 варианта, то есть запрет сочетания ЕЬ исключает 5 24= 120 кодов
Итого 720-120-120= 480 кодов
Вася составляет 6-буквенные коды из букв П, А, Н, Е, Л, Ь. Каждую букву нужно использовать ровно 1 раз, при этом код не может начинаться с буквы Ь и не может содержать сочетания ЬЕ . Сколько различных кодов может составить Вася?
1) Всего составить 6 буквенные слова возможно 6! = 6 5 4 3 2 1 = 720 способами
2) рассмотрим различные варианты слов из 6 букв, которые содержат первую букву Ь:
Ь***** 1 5 4 3 2 1 = 120 комбинаций
3) Рассмотрим следующее исключение: ЬЕ
первый случай уже исключен (слово не может начинаться с буквы Ь)
для каждого из остальных случаев количество вариантов распределения остальных букв равно 4 3 2 1 = 24 варианта, то есть запрет сочетания ЬЕ исключает 4 24= 96 кодов
Итого 720-120-96= 504
Вася составляет 5-буквенные коды из букв П, А, Н, Е, Л, Ь. Каждую букву нужно использовать ровно 1 раз, при этом код не может начинаться с буквы Ь и не может содержать сочетания ЕЛ . Сколько различных кодов может составить Вася?
1) Всего составить 5 буквенные слова возможно 6 5 4 3 2 = 720 способами
2) рассмотрим различные варианты слов из 5 букв, которые содержат первую букву Ь:
Ь**** 1 5 4 3 2 = 120 комбинаций
3) Рассмотрим следующее исключение: ЕЛ
ЕЛ***, количество вариантов распределения остальных букв равно 4 3 2 = 24 варианта
для каждого из остальных случаев количество вариантов распределения остальных букв равно 3 3 2 = 18 вариантов, так как Ь ранее учтен
24+18*3=24+54= 78
4) Итого 720-120-78= 522
-82%
Задача №10. Измерение количества информации. Основы комбинаторики.
При работе с вычислительной техникой, информационным объемом сообщения называют количество двоичных символов, которое используют для кодирования этого сообщения.
Чтобы найти информационный объем сообщения I, нужно количество символов этого сообщения N умножить на количество бит, выделяемых для кодирования одного символа
K : I = N * K.
Количество символов в некотором алфавите называется мощностью алфавита.
Несложно понять, что количество слов длиной N, составленных из символов (букв) алфавита мощностью M равно M N .
При компьютерном кодировании мощность алфавита равна 2, значит количество слов длиной N равно 2 N .
Подсчет количества буквенных цепочек
Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:
Запишите слово, которое стоит на 210-м месте от начала списка.
Заменим буквы А, О, У на 0, 1, 2 и выпишем начало списка:
Полученная запись есть числа, записанные в троичной системе счисления в порядке возрастания. Тогда на 210 месте будет стоять число 209 (т. к. первое число 0). Переведём число 209 в троичную систему: 20910 = 212023
Заменим обратно цифры на буквы и получим УОУАУ.
Сколько слов длины 6, начинающихся с согласной буквы, можно составить из букв Г, О, Д? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
На первом месте может стоять две буквы: Г или Д, на остальных — три буквы.
Слов, начинающихся на Г, 3 5 . Слов, начинающихся на Д, тоже 3 5 .Таким образом, можно составить 2 · 3 5 = 486 слов.
Вася составляет 5-буквенные слова, в которых есть только буквы С, Л, О, Н, причём буква С используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
Пусть С стоит в слове на первом месте. Тогда на каждое из оставшихся 4 мест можно поставить независимо одну из 3 букв. То есть всего 3*3*3*3 = 81 вариант. Таким образом, С можно по очереди поставить на все 5 мест, в каждом случае получая 81 вариант. Итого получается 81 * 5 = 405 слов.
Количество информации при двоичном (компьютерном) кодировании
Объем сообщения – 7,5 Кбайт. Известно, что данное сообщение содержит 7680 символов. Какова мощность алфавита?
Объем сообщения I, написанного в исходном алфавите мощности M, содержащего N символов, равен: I = log2M * N
Log2M = (7,5 * 2 13 бит) / 7680 =(7,5 * 2 13) /(15 * 2 9 ) = 8
Количество информации при различных (не компьютерных) способах кодирования
Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее четырёх и не более пяти сигналов (точек и тире)?
Мы имеем алфавит из двух букв: точка и тире. Из двух букв можно составить 2 4 четырёхбуквенных слова и 2 5 пятибуквенных слов.
Значит, всего можно закодировать 16 + 32 = 48 различных символов.
Световое табло состоит из лампочек. Каждая лампочка может находиться в одном из трех состояний («включено», «выключено» или «мигает»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 18 различных сигналов?
Мощность алфавита M =3 («включено», «выключено» или «мигает»).
Количество различных сигналов 18 <= M N = 3 N . (Поскольку равенство не выполняется, N берем с избытком, иначе не сможем закодировать все сигналы). N = 3.
Ты нашел то, что искал? Поделись с друзьями!
Спасибо за то, что пользуйтесь нашими материалами. Информация на странице «Задача №10. Измерение количества информации. Основы комбинаторики.» подготовлена нашими авторами специально, чтобы помочь вам в освоении предмета и подготовке к ЕГЭ и ОГЭ. Чтобы успешно сдать нужные и поступить в ВУЗ или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий. Также вы можете воспользоваться другими статьями из разделов нашего сайта.
Вася составляет 5 буквенные слова в которых есть только буквы волк
Вася составляет 5 буквенные слова в которых есть только буквы волк
ЕГЭ 10 задача 51
Ксения: 51) Вася составляет 5-буквенные слова, в которых есть только буквы К, А, Т, Е, Р, причём буква Р используется в каждом слове хотя бы 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася? Всего слов5*5*5*5*5=3125 Буква А встречается хотя бы 1 раз 4*4*4*4*5=1280 3125-1280=1845 В ответе 821. Подскажите, где ошибка?
oval: Ксения пишет: Всего слов5*5*5*5*5=3125 Буква А встречается хотя бы 1 раз 4*4*4*4*5=1280 3125-1280=1845 В ответе 821. Подскажите, где ошибка? Вы определитесь — буква А или Р? А если этой буквы вообще нет в слове?
Поляков: Ксения пишет: Всего слов 5*5*5*5*5=3125 Да. Буква А встречается хотя бы 1 раз 4*4*4*4*5=1280 1) почему? 2) что это дает в этой задаче? 3125-1280=1845 Почему это ответ?
Ксения: Решила другим способом. Две буквы Р: 1*1*4*4*4 =64 Количество сочетаний 2 из 5 =10 итого10*64=640 Три буквы Р: 1*1*1*4*4 =16 Количество сочетаний 3 из 5 =10 итого10*16=160 Четыре буквы Р: 1*1*1*1*4 =4 Количество сочетаний 4 из 5 =5 итого5*4=20 Пять букв Р: 1 способ итого 821
anonymous: Как Вы получили 10, 10, 5? (когда умножаете)
oval: Ксения пишет: Всего слов5*5*5*5*5=3125 Буква А встречается хотя бы 1 раз 4*4*4*4*5=1280 3125-1280=1845 В ответе 821. Подскажите, где ошибка? Буквы А нет в слове 4*4*4*4*4 = 1024 3125-1280-1024 = 821
10) Вася составляет 5 — буквенные слова, в которых есть только буквы Б, А, Л, К, О, Н, причём буква Б используется в каждом слове хотя бы 1 раз?
10) Вася составляет 5 — буквенные слова, в которых есть только буквы Б, А, Л, К, О, Н, причём буква Б используется в каждом слове хотя бы 1 раз.
Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем.
Словом считается любая допустимая последовательность букв, не обязательно осмысленная.
Сколько существует таких слов, которые может написать Вася?
Всего из этих букв можно составить 6 ^ 5 пятибуквенных слов.
Не удовлетворяют условию слова, не содержащие букв Б.
Остаётся пять вариантов букв на каждое место, значит, всего 5 ^ 5 пятибуквенных слов.
Тогда подходит 6 ^ 5 — 5 ^ 5 = 4 651 слово.
Ваня составляет 5 — буквенные слова, в которых встречаются только буквы А, Б, В, Г,причём буква А появляется ровно 2 раза?
Ваня составляет 5 — буквенные слова, в которых встречаются только буквы А, Б, В, Г,
причём буква А появляется ровно 2 раза.
Каждая из других допустимых букв может
встречаться в слове любое количество раз или не встречаться совсем.
Словом считается любая
допустимая последовательность букв, не обязательно осмысленная.
Сколько существует таких
слов, которые может написать Ваня?
Вася составляет 4 — буквенные слова, в которых есть только буквы К, Л, О, У, Н, причём буква У используется в каждом слове хотя бы 1 раз?
Вася составляет 4 — буквенные слова, в которых есть только буквы К, Л, О, У, Н, причём буква У используется в каждом слове хотя бы 1 раз.
Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем.
Словом считается любая допустимая последовательность букв, не обязательно осмысленная.
Сколько существует таких слов, которые может написать Вася?
(Нужно ПОДРОБНОЕ РЕШЕНИЕ !
Пожалуйста, помогите решить олимпиаду?
Пожалуйста, помогите решить олимпиаду!
«ИСПОЛНИТЕЛЬ» На уроке литературы чтобы как — то заинтересовать Вовочку своим предметом учитель предложила составлять из длинных слов разные короткие слова и Вовочке это очень понравилось.
Когда он пришел на урок информатика, где начали изучать основы алгоритмизации вместо того чтобы внимательно слушать Вовочка увидел на доске слово «ИСПОЛНИТЕЛЬ» и решил выписывать разные короткие слова, которые можно составить из букв этого слова, причем так, чтобы каждая буква встречалась только один раз и все слова были разные.
Потом он вспомнил, что компьютер считает, что слово это последовательность любых букв, то есть слова могут быть и бессмысленные – просто набор букв.
Тогда Вовочка решил просто посчитать сколько разных слов можно составить из 4 букв слова «ИСПОЛНИТЕЛЬ», при условии, что каждая буква встречается в четырехбуквенных словах может встречаться не более одного раза?
Но вот с вычислениями у Вовочки не все в порядке, поэтому он обратился за помощью к Вам.
Ответьте на поставленный Вовочкой вопрос.
Комментарий : слово «ТЕЛО» можно считать как правильное, а слово «ЛИЛО» — нельзя, так как буква Л встречается дважды.
На уроке литературы чтобы как — то заинтересовать Вовочку своим предметом учитель предложила составлять из длинных слов разные короткие слова и Вовочке это очень понравилось?
На уроке литературы чтобы как — то заинтересовать Вовочку своим предметом учитель предложила составлять из длинных слов разные короткие слова и Вовочке это очень понравилось.
Когда он пришел на урок информатика, где начали изучать основы алгоритмизации вместо того чтобы внимательно слушать Вовочка увидел на доске слово «ИСПОЛНИТЕЛЬ» и решил выписывать разные короткие слова, которые можно составить из букв этого слова, причем так, чтобы каждая буква встречалась только один раз и все слова были разные.
Потом он вспомнил, что компьютер считает, что слово это последовательность любых букв, то есть слова могут быть и бессмысленные – просто набор букв.
Тогда Вовочка решил просто посчитать сколько разных слов можно составить из 4 букв слова «ИСПОЛНИТЕЛЬ», при условии, что каждая буква встречается в четырехбуквенных словах может встречаться не более одного раза?
Но вот с вычислениями у Вовочки не все в порядке, поэтому он обратился за помощью к Вам.
Ответьте на поставленный Вовочкой вопрос.
Комментарий : слово «ТЕЛО» можно считать как правильное, а слово «ЛИЛО» — нельзя, так как буква Л встречается дважды.
Ольга составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует свое кодовое слово?
Ольга составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует свое кодовое слово.
В качестве кодовых слов Ольга использует 4 — буквенные слова, в которых есть только буквы A, B, C, D, X, Y, Z.
При этом первая буква кодового слова — это буква X, Y или Z, а далее в кодовом слове буквы X, Y, Z не встречаются.
Сколько различных кодовых слов может использовать Ольга?
Вывести на экран все слова из К букв, в которых буква Ы встречается более 1 раза, и подсчитать их количество?
Вывести на экран все слова из К букв, в которых буква Ы встречается более 1 раза, и подсчитать их количество.
Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово?
Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово.
В качестве кодовых слов Игорь использует 5 — буквенные слова, в которых есть буквы А, В, С, Х, причем буква Х появляется ровно 1 раз и только на 1 — й или последней позиции слова.
Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем.
Сколько различных кодовых слов может использовать Игорь?
Палиндром – это символьная строка, которая читается одинаково в обоих направлениях?
Палиндром – это символьная строка, которая читается одинаково в обоих направлениях.
Сколько различных 5 — символьных палиндромов можно составить из строчных русских букв, начинающихся с гласной?
Словом считается любая допустимая последовательность букв, не обязательно осмысленная.
В русском алфавите 33 буквы.
Шифр кодового замка представляет собой последовательность из четырех символов, каждый из которых является одной из букв A, B, C или D?
Шифр кодового замка представляет собой последовательность из четырех символов, каждый из которых является одной из букв A, B, C или D.
Сколько различных вариантов шифра можно задать, если известно, что буква А должна встречаться в коде ровно два раза, а каждая из других допустимых цифр может встречаться в шифре любое количество раз или не встречаться совсем?
Вася составляет 3 — буквенные слова, в которых есть только буквы К, Р, А, Н, причём буква А используется в каждом слове хотя бы 1 раз?
Вася составляет 3 — буквенные слова, в которых есть только буквы К, Р, А, Н, причём буква А используется в каждом слове хотя бы 1 раз.
Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем.
Словом считается любая допустимая последовательность букв, не обязательно осмысленная.
Сколько существует таких слов, которые может написать Вася?
На этой странице находится вопрос 10) Вася составляет 5 — буквенные слова, в которых есть только буквы Б, А, Л, К, О, Н, причём буква Б используется в каждом слове хотя бы 1 раз?, относящийся к категории Информатика. По уровню сложности данный вопрос соответствует знаниям учащихся 5 — 9 классов. Здесь вы найдете правильный ответ, сможете обсудить и сверить свой вариант ответа с мнениями пользователями сайта. С помощью автоматического поиска на этой же странице можно найти похожие вопросы и ответы на них в категории Информатика. Если ответы вызывают сомнение, сформулируйте вопрос иначе. Для этого нажмите кнопку вверху.
Вася составляет 5 буквенные слова в которых есть только буквы волк
Тип 8 № 23908 
Вася составляет 5-буквенные слова, в которых есть только буквы В, О, Л, К, причём буква В используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
Пусть В стоит в слове на первом месте. Тогда на каждое из оставшихся 4 мест можно поставить независимо одну из 3 букв. То есть всего вариант.
Таким образом, В можно по очереди поставить на все 5 мест, в каждом случае получая 81 вариант.