Как найти длину сообщения в информатике - Исправление недочетов и поиск решений вместе с Examum.ru

На уроке рассматривается разбор 8 задания ЕГЭ по информатике про измерение количества информации

8-е задание: «Измерение количества информации»

Уровень сложности

— базовый,

Требуется использование специализированного программного обеспечения

— нет,

Максимальный балл

— 1,

Примерное время выполнения

— 4 минуты.

Проверяемые элементы содержания: Знание о методах измерения количества информации

До ЕГЭ 2021 года — это было задание № 10 ЕГЭ

Типичные ошибки и рекомендации по их предотвращению:

«При использовании способа решения со системой счисления с основанием N следует помнить, что слова в списке нумеруются с единицы, поэтому числу 0 будет соответствовать первое слово»

ФГБНУ «Федеральный институт педагогических измерений»

Содержание:

Объяснение темы
- Измерение количества информации
- Двоичное кодирование сообщений (равновероятностные события)
- Количество различных сообщений в алфавите разной мощности
- Количество сообщений при различном вхождении (встречаемости) букв
- Дополнительные формулы
Тренировочные задания 8 ЕГЭ по информатике и их решение
- Сколько вариантов шифра или кодовых слов
- Перестановка букв в слове (каждая буква 1 раз)
- Сколько существует n-значных чисел, записанных в m-ной системе счисления
- Список в алфавитном порядке
- Вероятность событий

Объяснение темы

Рассмотрим кратко необходимые для решения 8 задания ЕГЭ понятия и формулы.

Измерение количества информации

Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом.
1 бит – это количество информации, которое можно передать с помощью одного знака в двоичном коде (0 или 1).

1 байт (bytе) = 8 бит
1 Кб (килобайт) = 1024 байта
1 Мб (мегабайт) = 1024 Кб
1 Гб (гигабайт) = 1024 Мб
1 Тб (терабайт) = 1024 Гб
1 Пб (петабайт) = 1024 Тб

8 = 2³
1024 = 2¹⁰

Рассмотрим еще несколько определений:

Алфавит — это набор знаков, используемый в том или ином языке.
Мощность алфавита — это количество используемых в алфавите знаков.

Мощность алфавита

Сообщение — это любая последовательность символов какого-либо алфавита.

Для вычисления количества информации применяются несколько различных формул в зависимости от ситуации:

Двоичное кодирование сообщений (равновероятностные события)

При вычислении количества информации в сообщении для равновероятностных событий, общее количество которых равно N, используется формула:

N = 2^L

N — количество сообщений

L — длиной битов

* следует иметь в виду, что также приняты следующие обозначения: Q = 2^k

Пример 2: Зашифруем буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и посчитаем количество возможных сообщений:

Решение:

Таким образом, мы получили равномерный код, т.к. длина каждого кодового слова одинакова для всех кодовых слов (L = 2).

Количество сообщений длиной L битов:

N = 2^L

Т.е. количество сообщений длиной 2 бита, как в примере с нашими буквами, будет равно N = 2² = 4

Ответ: 4

Количество различных сообщений в алфавите разной мощности

Рассмотрим вариант с 5 буквами (мощность алфавита = 5), которые надо разместить в сообщении длиной 2 символа:

Найдем формулу для нахождения количества различных сообщений в алфавите различной мощности:

Если мощность некоторого алфавита составляет N, то количество различных сообщений длиной L знаков:

N – мощность алфавита
L – длина сообщения
Q – количество различных сообщений

Пример: Сколько существует всевозможных трехбуквенных слов в английском языке?

Решение:

В английском алфавите 26 букв. Значит, мощность алфавита = 26. Длина сообщения = 3. Найдем по формуле количество трехбуквенных слов:
Q = 26³
или

= 17576

Ответ: 17576

Таким, образом, если слово состоит из L букв, причем есть n1 вариантов выбора первой буквы, n2 вариантов выбора второй буквы и т.д., то число возможных слов вычисляется как произведение:

N = n1 * n2 * … * nL

Количество сообщений при различном вхождении (встречаемости) букв

В таком случае можно использовать формулу для вычисления числа перестановок с повторениями; для двух разных символов она выглядит так:

[ P = frac{na+n*!}{na!n*!} ]

na – количество букв a

n* — количество звёздочек или кол-во вариантов

Иногда в заданиях 8 можно использовать формулу комбинаторики для проверки полученных результатов перебора. Число сочетаний из n элементов по k элементов:

[ C{binom{k}{n}}= frac{n!}{k!(n-k)!} ]

I – количество информации в битах

N – количество вариантов

n! = 1 * 2 * 3 * … * n

Пример: Сколько существует всевозможных четырехбуквенных слов в алфавите из 4 букв: А, Б, В, Г, если известно, что буква А встречается ровно два раза?

Решение:

Длина сообщения = 4. Мощность алфавита = 4. Но мешает условие: буква А встречается ровно два раза.
В таких заданиях можно использовать способ перебора всевозможных вариантов:

два раза буква А, на остальных местах - одна из трех оставшихся букв:
А А 3 3     = 3 * 3 = 3² = 9
А 3 А 3     = 9
А 3 3 А     = 9 
3 А А 3     = 9
3 А 3 А     = 9
3 3 А А     = 9

Получили 6 вариантов, каждый из которых равен 9.
Проверим формулой числа сочетаний:

Число сочетаний из n элементов по k элементов:

[ C{binom{k}{n}}= frac{n!}{k!(n-k)!} ]

В задаче:

[ C{binom{2}{4}}= frac{4!}{2!(4-2)!} = frac{24}{2*2} = 6 ]

* Факториал числа n! = 1 * 2 * 3 *..* n

Т.е. проверка прошла успешно, мы получили 6 вариантов.
Осталось посчитать количество всех сообщений:

6 * 9 = 54

Дополнительные формулы

Количество информации и равновероятные события

При определении количества информации для равновероятностных событий могут понадобиться две формулы:

Формула Шеннона:

x = log₂(1/p)

x — количество информации в сообщении о событии

p — вероятность события

Формула вероятности случайного события:

p(A) = m / n

m — количество благоприятных исходов (число случаев, способствующих событию А)

n — количество общих исходов (общее число равновозможных случаев)

Количество информации и неравновероятные события

При использовании неравновероятного события, вероятность которого равна p, для вычисления количества информации используется формула:

i = -[log₂p]

*квадратные скобки означают ближайшее целое, меньшее или равное значению выражения в скобках

Формула Хартли:

Формула Хартли

I – количество информации в битах

N – количество вариантов

Алфавитный подход:

Информационный объем сообщения длиной L:

Алфавитный подход

N — мощность алфавита

L — длина сообщения

Плейлист видеоразборов задания на YouTube:
Задание демонстрационного варианта 2022 года ФИПИ

Сколько вариантов шифра или кодовых слов

Такие задания можно решить программированием.

На языке PascalAbc.net можно использовать язык интегрированных запросов LINQ (Language Integrated Query).

Cartesian(n) — метод расширения последовательности, возвращающий декартову степень множества символов Когда применяется:
Если требуется полный перебор вариантов букв для каждой позиции (каждая буква может встречаться в кодовом слове любое количество раз)

Пример:
Сравним полный перебор букв слова «школа», размещенных на две позиции:

Pascal PascalABC.NET

##
var str:='школа';
foreach var s1 in str do
  foreach var s2 in str do
         print(|s1,s2|)

## // 1 вариант
var str:='школа';
str.cartesian(2).print
 
## // 2 вариант
'школа'.cartesian(2).print
 
### // 3 вариант (спортивное прогр-е)
'школа'.cart(2).print

Результат:

[ш,ш] [ш,к] [ш,о] [ш,л] [ш,а] [к,ш] [к,к] [к,о]
[к,л] [к,а] [о,ш] [о,к] [о,о] [о,л] [о,а] [л,ш]
[л,к] [л,о] [л,л] [л,а] [а,ш] [а,к] [а,о] [а,л] [а,а]

Итого 25 штук (5*5)

[ш,ш] [ш,к] [ш,о] [ш,л] [ш,а] [к,ш] [к,к] [к,о]
[к,л] [к,а] [о,ш] [о,к] [о,о] [о,л] [о,а] [л,ш]
[л,к] [л,о] [л,л] [л,а] [а,ш] [а,к] [а,о] [а,л] [а,а]

Permutations — метод возвращает все перестановки множества элементов, заданного массивом или последовательностью Когда применяется:
Если требуется перестановка букв в слове. То есть количество каждой буквы в словах сохраняется, и каждая буква встречается только 1 раз

Пример:
Сравним перестановку букв слова «мимикрия»:

Pascal PascalABC.NET

## // 1 вариант
 'мимикрия'.Permutations
  // собираем в строку:
  // к строкам можно distinct применять, а к массивам - нет
 .Select(w->w.JoinToString('')) 
 .Distinct  // выбираем уникальные, т.к. от перестановки двух букв "м" 
            // и букв "и" слово не меняется
 .Count.Print

1	## // 2 вариант

### // 3 вариант (спортивное прогр-е)
'мимикрия'.Prm
 .Sel(w->w.ToS('')) 
 .Dst  
 .Cnt.Pr

Результат:

[М,И,М,И,К,Р,И,Я] [М,И,М,И,К,Р,Я,И] [М,И,М,И,К,И,Р,Я] [М,И,М,И,К,И,Я,Р] [М,И,М,И,К,Я,Р,И] [М,И,М,И,К,Я,И,Р] [М,И,М,И,Р,К,И,Я] [М,И,М,И,Р,К,Я,И]
…

Используются также следующие запросы и методы LINQ:

Фильтрация последовательностей (Where)
Метод Count([Type -> boolean]) Вычисление скаляра
Метод CountOf(s: Type) — Возвращает количество элементов, равных указанному значению
Метод First() — Возвращает первый элемент последовательности.
Метод Last() — Возвращает последний элемент последовательности.
Метод Pairwise(Self: sequence of T; func: (T,T)->Res) — Превращает последовательность в последовательность пар соседних элементов, применяет func к каждой паре полученных элементов и получает новую последовательность

8_1:

Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является цифрой от 1 до 6.

Сколько различных вариантов шифра можно задать, если известно, что цифра 1 должна встречаться в коде ровно 1 раз, а каждая из других допустимых цифр может встречаться в шифре любое количество раз или не встречаться совсем?

Типовые задания для тренировки

✍ Решение:

✎ Решение теоретическое:

Формула нахождения количества различных сообщений:

Q = N^L

Итак, что у нас дано из этой формулы:
Длина сообщения (L) = 5 символов
Мощность алфавита (N) = 6 (цифры от 1 до 6).
Но так как цифра 1 встречается по условию ровно один раз, а остальные 5 цифр — любое количество раз, то будем считать, что N = 5 (цифры от 2 до 6, исключая 1). Т.е. возьмем вариант, когда 1 стоит на первом месте, а остальные 5 цифр размещаем на 4 позиции:

1 5 5 5 5 - 1 * Q = 5⁴ = 625

✎ 1 способ. Найдем количество вариантов методом перебора:

Методом перебора найдем количество вариантов размещения:

1 5 5 5 5 - 1 * Q=5⁴ = 625
5 1 5 5 5 - 1 * Q=5⁴ = 625
5 5 1 5 5 - 1 * Q=5⁴ = 625
5 5 5 1 5 - 1 * Q=5⁴ = 625
5 5 5 5 1 - 1 * Q=5⁴ = 625

получили 5 вариантов;

✎ 2 способ. Найдем количество вариантов при помощи формулы комбинаторики:

[ C{binom{4}{5}}= frac{5!}{4!(5-4)!} = 5 ]

получили 5 вариантов;
В итоге получим:

625 * 5 = 3125

Результат: 3125

✎ Решение с использованием программирования:

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var n := 0;
  var str := '123456';
  foreach var s1 in str do
    foreach var s2 in str do
      foreach var s3 in str do
        foreach var s4 in str do
          foreach var s5 in str do
          begin
            if (s1 + s2 + s3 + s4 + s5).CountOf('1') = 1 then
              n += 1;
          end;
  print(n)
end.

PascalABC.net (использование LINQ, быстрое решение):

##
var d:='123456'.Cartesian(5) 
.where(w->w.countOf('1')=1)// кол-во '1' в слове
.count.print

Cartesian(5) — метод расширения последовательности, возвращающий декартову степень множества символов, т.е. в нашем случае перебор 5-знаковых слов из заданных символов

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

n=0
str='123456'
for s1 in str:
  for s2 in str:
    for s3 in str:
      for s4 in str:
        for s5 in str:
          if (s1+s2+s3+s4+s5).count('1')==1:
            n+=1
print(n)

С++:

Детальный теоретический разбор задания 8 ЕГЭ по информатике предлагаем посмотреть в видеоуроке:

📹 YouTube здесьздесь (теоретическое решение)

8_2:

Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является либо буквой (A или B) или цифрой (1, 2 или 3).

Сколько различных вариантов шифра можно задать, если известно, что в коде присутствует ровно одна буква, а все другие символы являются цифрами?

✍ Решение:

✎ Решение теоретическое:

Формула нахождения количества различных сообщений:

Q = N^L

Посчитаем количество возможных шифров для одного из вариантов (например, когда буквы находятся на первой позиции). Так как цифры (1, 2, 3) могут занимать 4 позиции из пяти, а две буквы (А и В) одну из позиций, значит:

Q = 2 * 3⁴ = 162

Имеем 162 вариантов шифра для слова, в котором буквы могут стоять на первой позиции:

AB  123 123 123 123 = 162

Получим все варианты размещения:

"2" означает одна из двух букв: А или B, "3" - одна из трех цифр:

2 3 3 3 3 -> Q = 2 * 3⁴ = 162
3 2 3 3 3 -> Q = 2 * 3⁴ = 162
3 3 2 3 3 -> Q = 2 * 3⁴ = 162
3 3 3 2 3 -> Q = 2 * 3⁴ = 162
3 3 3 3 2 -> Q = 2 * 3⁴ = 162

Получили 5 вариантов с размещением букв А и B.
Осталось умножить:

5 * 162 = 810

Результат: 810

✎ Решение с использованием программирования:

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var n := 0;
  var str := 'AB123';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          for var s5 := 1 to length(str) do
          begin
            var res := str[s1] + str[s2] + str[s3] + str[s4] + str[s5];
            if (res.CountOf('A') = 1) and (res.CountOf('B') = 0) 
            or (res.CountOf('B') = 1) and (res.CountOf('A') = 0) then
              n += 1;
          end;
  print(n)
end.

PascalABC.net (использование LINQ, быстрое решение):

##
var d:='АВ123'.Cartesian(5) 
.where(w->w.count(letter -> letter in 'АВ')=1)// кол-во букв в слове
.count.print

Cartesian(5) — метод расширения последовательности, возвращающий декартову степень множества символов, т.е. в нашем случае перебор 5-знаковых слов из заданных символов

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

n=0
str='AB123'
for s1 in str:
  for s2 in str:
    for s3 in str:
      for s4 in str:
        for s5 in str:
          if ((s1+s2+s3+s4+s5).count('A')==1 and (s1+s2+s3+s4+s5).count('B')==0) 
          or ((s1+s2+s3+s4+s5).count('B')==1 and (s1+s2+s3+s4+s5).count('A')==0):
            n+=1
print(n)

С++:

Подробное теоретическое решение данного задания предлагаем посмотреть на видео:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

8_3:

Олег составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Олег использует 4-буквенные слова, в которых есть только буквы A, Б, В, Г, Д и Е, причём буква Г появляется ровно 1 раз и только на первом или последнем месте. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем.

Сколько различных кодовых слов может использовать Олег?

✍ Решение:

✎ Решение теоретическое:

Вспомним формулу получения количества возможных вариантов слов:

N = n1 * n2 * n3 * … * nL = n^L

где n1 — количество вариантов выбора первой буквы, n2 — количество вариантов выбора второй буквы и т.п.
Рассмотрим варианты, когда буква Г встречается на первом или последнем месте:

Г ? ? ? = 1 * 5 * 5 * 5 = 5³ = 125 
? ? ? Г = 5 * 5 * 5 * 1 = 5³ = 125

Вместо знаков ? может стоять одна из пяти букв (А, Б, В, Д, Е), т.к. буква Г там стоять не может
Теперь суммируем количество найденных вариантов:

125 + 125 = 250

Результат: 250

✎ Решение с использованием программирования:

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var n := 0;
  var str := 'АБВГДЕ';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          begin
            var res := str[s1] + str[s2] + str[s3] + str[s4];
            if (res[1]='Г') and (res[2]<>'Г') and (res[3]<>'Г') and (res[4]<>'Г')
            or (res[1]<>'Г') and (res[2]<>'Г') and (res[3]<>'Г') and (res[4]='Г') then
              n += 1;
          end;
  print(n)
end.

PascalABC.net (использование LINQ, быстрое решение):

##
var d:='АБВГДЕ'.Cartesian(4)
.where(w->(w.countOf('Г')=1)and((w.First='Г')or(w.Last='Г'))) // или: 
// .where(w->(w.countOf('Г')=1)and(w[1]<>'Г')and(w[2]<>'Г'))
.count.print

Cartesian(4) — метод расширения последовательности, возвращающий декартову степень множества символов, т.е. в нашем случае перебор 4-знаковых слов из заданных символов

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

n=0
str='АБВГДЕ'
for s1 in str:
  for s2 in str:
    for s3 in str:
      for s4 in str:
        if (s1 =='Г') and (s2!='Г') and (s3!='Г') and (s4!='Г') 
        or (s1 !='Г') and (s2!='Г') and (s3!='Г') and (s4=='Г'):
            n+=1
print(n)

С++:

Видеоразбор данного задания (теоретический способ):

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

8_4:

Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является одной из букв X, Y или Z.

Сколько различных вариантов шифра можно задать, если известно, что буква X должна встречаться в коде ровно 2 раза, а каждая из других допустимых букв может встречаться в шифре любое количество раз или не встречаться совсем?

Типовые задания для тренировки

✍ Решение:

✎ Решение теоретическое:

Формула нахождения количества различных сообщений:

Q = N^L

Итак, что у нас дано из этой формулы:
Начальная мощность алфавита (N) = 3 (буквы X, Y, Z). Но так как буква X встречается ровно два раза, то мы ее рассмотрим отдельно, а остальные 2 буквы — встречаются любое количество раз, значит, будем считать, что:

N = 3 - 1 = 2 (Y и Z)

Исходя из предыдущего пункта, длина сообщения тоже сократится:

(L) = 5 - 2 = 3 символа (остальные два символа отведем на размещение X)

Количество различных сообщений (вариантов шифра) = Q = ?
Т.е. для одного варианта размещения (для одного варианта шифра) имеем:

X X ? ? ? -> 1² * Q = 2³ = 8

Согласно условию получим следующие варианты размещения:

✎1 способ. Перебор всех вариантов:

X X ? ? ? - 1² * Q = 2³ = 8
X ? X ? ? - 1² * Q = 2³ = 8
X ? ? X ? - 1² * Q = 2³ = 8
X ? ? ? X - 1² * Q = 2³ = 8
? X X ? ? - 1² * Q = 2³ = 8
? X ? X ? - 1² * Q = 2³ = 8
? X ? ? X - 1² * Q = 2³ = 8
? ? X X ? - 1² * Q = 2³ = 8
? ? X ? X - 1² * Q = 2³ = 8
? ? ? X X - 1² * Q = 2³ = 8

✎ 2 способ. При помощи формулы поиска числа сочетаний:

[ C{binom{k}{n}}= frac{n!}{k!(n-k)!} ]

Число сочетаний из n элементов по k элементов:

[ C{binom{2}{5}}= frac{5!}{2!(5-2)!} = frac{120}{12} = 10 ]

* Факториал числа: n! = 1 * 2 * 3 * .. * n

Количество вариантов найдено верно, т.к. результат обоих способов = 10. В итоге получаем:

8 * 10 = 80

* задание достаточно решить одним из способов!

Результат: 80

✎ Решение с использованием программирования:

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var n := 0;
  var str := 'xyz';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          for var s5 := 1 to length(str) do
          begin
            var res := str[s1] + str[s2] + str[s3] + str[s4] + str[s5];
            if res.countOf('x') = 2 then // или if res.Count(y -> y = 'x') = 2 then
              n += 1;
          end;
  print(n)
end.

PascalABC.net (использование LINQ, быстрое решение):

##
var d:='XYZ'.Cartesian(5)
.where(w->w.countOf('X')=2)
.count.print

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

n=0
str='xyz'
for s1 in str:
  for s2 in str:
    for s3 in str:
      for s4 in str:
        for s5 in str:
          if (s1+s2+s3+s4+s5).count('x') == 2:
            n+=1
print(n)

С++:

Детальный теоретический разбор задания 8 ЕГЭ по информатике теоретическим способом предлагаем посмотреть в видеоуроке:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

8_5:

Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв ОСЕНЬ? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

Типовые задания для тренировки

✍ Решение:

✎ Решение теоретическое:

Из букв слова ОСЕНЬ имеем 2 гласных буквы (О, Е) и 2 согласных буквы (С, Н). Буква мягкий знак «нейтральна».
Подсчитаем количество букв на каждой из 5 позиций:

2   5   5   5   2
^{СН   все  все  все   ОЕ}

Вспомним формулу получения количества возможных вариантов слов:

N = n1 * n2 * n3 * … * nL = n^L

где n1 — количество вариантов выбора первой буквы, n2 — количество вариантов выбора второй буквы и т.п.
Т.е. количество вариантов равно произведению полученных чисел:

N = 2 * 5 * 5 * 5 * 2 = 500

✎ Решение с использованием программирования:

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var n := 0;
  var str := 'ОСЕНЬ';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          for var s5 := 1 to length(str) do
          begin
            var res := str[s1] + str[s2] + str[s3] + str[s4] + str[s5];
            if ((res[1] = 'С') or (res[1] = 'Н')) and ((res[5] = 'О') or (res[5] = 'Е')) then
              n += 1;
          end;
  print(n)
end.

PascalABC.net (использование LINQ, быстрое решение):

1	'ОСЕНЬ'.Cartesian(5).Where(w->w[0] in 'СН').Where(w->w[4] in 'ОЕ').Count.Print

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

str = 'ОСЕНЬ'
n = 0
for s1 in str:
    for s2 in str: 
        for s3 in str:
            for s4 in str:
                for s5 in str:
                    res = s1 + s2 + s3 + s4
                    if (s1 == 'С' or s1 == 'Н') and (s5 == 'О' or s5 == 'Е'):
                        n += 1
print(n)

С++:

Результат: 500

Разбор можно также посмотреть на видео (теоретическое решение):

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

8_6:

Вася составляет 4-буквенные слова, в которых есть только буквы Л, Е, Т, О, причём буква Е используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем.

✍ Решение:

✎ Решение теоретическое:

✎ 1 способ:

Количество вариантов различных слов вычислим по формуле:

N = n1 * n2 * n3 * …
где

n1 — количество вариантов выбора первой буквы и т.п.
Рассмотрим все варианты расположения буквы Е:

1. Е ? ? ? или 
2. ? Е ? ? или 
3. ? ? Е ? или
4. ? ? ? Е 

Где вопросительный знак означает любую букву из Л, Е, Т, О.

Подсчитаем по формуле количество слов для варианта 1:

Е ? ? ? = 1 * 4 * 4 * 4 = 64

т.е. на первой позиции - только 1 буква - Е, на каждой последующей - одна из четырех букв Л, Е, Т, О.

Подсчитаем по формуле количество слов для варианта 2; учтем, что на первой позиции букву Е мы уже посчитали для первого варианта!:

? Е ? ? = 3 * 1 * 4 * 4 = 48

Подсчитаем по формуле количество слов для варианта 3; учтем, что на первой и второй позициях букву Е мы уже посчитали в предыдущих вариантах!:

? ? Е ? = 3 * 3 * 1 * 4 = 36

Подсчитаем по формуле количество слов для варианта 4; учтем, что на первой, второй и третьей позициях букву Е мы уже посчитали в предыдущих вариантах:

? ? ? Е = 3 * 3 * 3 * 1 = 27

Поскольку у нас каждый вариант связан операцией логическое ИЛИ, то теперь суммируем все варианты:

64 + 48 + 36 + 27 = 175

Результат: 175
✎ 2 способ:

Так как по условию буква Е встретится хотя бы 1 раз, значит, можно утверждать, что не может быть такого, чтобы буква Е не встретилась бы ни одного раза.
Таким образом, рассчитаем случай, когда буква Е встречается все 4 раза (т.е. все случаи) и отнимем от результата невозможный случай: когда буква Е не встретится ни одного раза:

1. Буква Е используется 4 раза (т.е. на всех позициях):
4 * 4 * 4 * 4 = 256

2. Буква Е не используется совсем (т.е. только 3 буквы):
3 * 3 * 3 * 3 = 81

Вычтем из первого варианта невозможный вариант № 2:

256 - 81 = 175

Результат: 175

✎ Решение с использованием программирования:

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var n := 0;
  var str := 'ЛЕТО';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          begin
            var res := str[s1] + str[s2] + str[s3] + str[s4];
            if res.countOf('Е') >= 1 then // или if res.Count(y -> y = 'Е') >= 1 then
              n += 1;
          end;
  print(n)
end.

PascalABC.net (использование LINQ, быстрое решение):

1 2	## var d:='лето'.Cartesian(4).where(w->w.countOf('е')>=1).count.print

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

n=0
str='ЛЕТО'
for s1 in str:
  for s2 in str:
    for s3 in str:
      for s4 in str:
          if (s1+s2+s3+s4).count('Е') >= 1:
            n+=1
print(n)

С++:

Теоретическое решение задания 8 смотрите в видеоуроке:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

8_7:

Вася составляет 4-буквенные слова, в которых есть только буквы К, А, Т, Е, Р, причём буква Р используется в каждом слове хотя бы 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем.

✍ Решение:

✎ Решение теоретическое:

Количество возможных вариантов слов вычислим по формуле:

N = n1 * n2 * n3 * … * nL = n^L

где n1 — количество вариантов выбора первой буквы, n2 — количество вариантов выбора второй буквы и т.п.
Сначала по формуле получим все варианты для всех пяти букв, включая букву Р:

5 * 5 * 5 * 5 = 5⁴ = 625

Из общего количества вариантов нам необходимо исключить те варианты, где Р не встречается вообще и Р встречается только 1 раз. Найдем их последовательно:
1. Буква Р не встречается совсем:

4 * 4 * 4 * 4 = 4⁴ = 256

2. Буква Р встречается только один раз:

р ? ? ? = 1 * 4 * 4 * 4 = 4³
? р ? ? = 4 * 1 * 4 * 4 = 4³
? ? р ? = 4 * 4 * 1 * 4 = 4³
? ? ? р = 4 * 4 * 4 * 1 = 4³

Получим  4³ * 4 = 256

Теперь вычтем из общего количества найденные варианты (№ 1 и № 2):

625 - 256 - 256 = 113

✎ Решение с использованием программирования:

PascalABC.net (традиционный):

begin
  var n := 0;
  var str := 'КАТЕР';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          begin
            var res := str[s1] + str[s2] + str[s3] + str[s4];
            if res.CountOf('Р') >= 2 then
              n += 1;
          end;
  print(n)
end.

PascalABC.net (LINQ):

1 2	## var d:='катер'.Cartesian(4).where(w->w.countOf('р')>=2).count.print

Python:

n=0
str='КАТЕР'
for s1 in str:
  for s2 in str:
    for s3 in str:
      for s4 in str:
          if (s1+s2+s3+s4).count('Р') >= 2:
            n+=1
print(n)

С++:

Результат: 113

Теоретическое решение 8 задания предлагаем посмотреть в видеоуроке:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

8_8:

Олег составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Олег использует 5-буквенные слова, в которых есть только буквы A, Б, В, и Г, причём буква Г появляется не более одного раза и только на последнем месте. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем.

Сколько различных кодовых слов может использовать Олег?

✍ Решение:

✎ Решение теоретическое:

Вспомним формулу получения количества возможных вариантов слов:

N = n1 * n2 * n3 * … * nL = n^L

где n1 — количество вариантов выбора первой буквы,
n2 — количество вариантов выбора второй буквы и т.п.
Так как буква Г появляется не более одного раза и только на последнем месте, значит, она может либо появиться 1 раз на последнем месте, либо не появиться совсем.
Рассмотрим варианты, когда буква Г встречается 1 раз на последнем месте и встречается 0 раз:

1 раз: ? ? ? ? Г = 3 * 3 * 3 * 3 * 1 = 3⁴ = 81 
0 раз: ? ? ? ? ? = 3 * 3 * 3 * 3 * 3 = 3⁵ = 243

Вместо знаков ? может стоять одна из трех букв (А, Б, В), т.к. буква Г там стоять не может
Теперь суммируем количество найденных вариантов:

81 + 243 = 324

✎ Решение с использованием программирования:

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var n := 0;
  var str := 'АБВГ';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          for var s5 := 1 to length(str) do
          begin
            var res := str[s1] + str[s2] + str[s3] + str[s4] + str[s4];
            if (res[1]<>'Г') and (res[2]<>'Г')and (res[3]<>'Г') and (res[4]<>'Г') then
              n += 1;
          end;
  print(n)
end.

PascalABC.net (использование LINQ, быстрое решение):

##
var d:='абвг'.Cartesian(5)
.where(w->(w.countOf('г')<=1)and(w[0]<>'г')and(w[1]<>'г')and(w[2]<>'г')
     and(w[3]<>'г')).count.print

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

С++:

Результат: 324

8_9:

Вася составляет 4-буквенные слова, в которых есть только буквы К, О, М, А, Р, причём буква А используется в них не более 3-х раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная.

✍ Решение:

✎ Решение теоретическое:

Вспомним формулу получения количества возможных вариантов слов:

N = n1 * n2 * n3 * … * nL = n^L

где n1 — количество вариантов выбора первой буквы,
n2 — количество вариантов выбора второй буквы и т.п.
Так как буква А по условию используется не более 3-х раз, это значит, что она используется либо 3 раза, либо 2 раза, либо 1 раз, либо не используется совсем. Рассмотрим все эти варианты отдельно.
1. Буква А используется 3 раза:

А А А _  -> 1 * 1 * 1 * 4 = 4
А А _ А  -> 1 * 1 * 4 * А = 4
А _ А А  -> 1 * 4 * 1 * 1 = 4
_ А А А  -> 4 * 1 * 1 * 1 = 4

Итого получаем 4 варианта, в которых вместо символа _ может быть любая из 4 букв: К О М Р. Значит, имеем:

 4 * 4 = 16 вариантов

2. Буква А используется 2 раза:

А А _ _  -> 1 * 1 * 4 * 4 = 16
А _ А _  -> 1 * 4 * 1 * 4 = 16
А _ _ А  -> 1 * 4 * 4 * 1 = 16
_ А А _  -> 4 * 1 * 1 * 4 = 16
_ А _ А  -> 4 * 1 * 4 * 1 = 16
_ _ А А  -> 4 * 4 * 1 * 1 = 16

Итого получаем 6 вариантов, в которых вместо символа _ может быть любая из 4 букв: К О М Р. Значит имеем:

 16 * 6 = 96 вариантов

3. Буква А используется 1 раз:

А _ _ _  -> 1 * 4 * 4 * 4 = 64
_ А _ _  -> = 64
_ _ А _  -> = 64
_ _ _ А  -> = 64

Итого имеем:

64 * 4 = 256 вариантов

Буква А используется 0 раз:

_ _ _ _ -> 4⁴ = 256

Суммируем результаты всех трех случаев:

16 + 96 + 256 + 256 = 624

✎ Решение с использованием программирования:

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var n := 0;
  var str := 'КОМАР';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          begin
            var res := str[s1] + str[s2] + str[s3] + str[s4];
            if res.CountOf('А') <=3 then
              n += 1;
          end;
  print(n)
end.

PascalABC.net (использование LINQ, быстрое решение):

1
2
3

##
var d:='комар'.Cartesian(4)
.where(w->w.countOf('а')<=3).count.print

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

str = 'КОМАР'
n = 0
for s1 in str:
    for s2 in str: 
        for s3 in str:
            for s4 in str:
                res = s1 + s2 + s3 + s4
                if res.count('А')<=3:
                    n += 1
print(n)

С++:

Результат: 624

Теоретическое решение смотрите также на видео:

📹 YouTube здесьздесь (теоретическое решение)

8_10:

Сколько существует различных символьных последовательностей длины 3 в четырёхбуквенном алфавите {A,B,C,D}, если известно, что одним из соседей A обязательно является D, а буквы B и C никогда не соседствуют друг с другом?

✍ Решение:

✎ Решение теоретическое:

Вспомним формулу получения количества возможных вариантов слов:

N = n1 * n2 * n3 * … * nL = n^L

где n1 — количество вариантов выбора первой буквы,
n2 — количество вариантов выбора второй буквы и т.п.
Будем рассматривать варианты, расставляя каждую букву последовательно по алфавиту, начиная с первой буквы. При этом будем учитывать указанные ограничения для букв А, B и С:

Начинаем с A: A D 4_ABCD = 1 * 1 * 4 = 4 
Начинаем с B: B A D, B B 2_BD, B D 4_ABCD = 7
Начинаем с C: C A D, C C 2_CD, C D 4_ABCD = 7
Начинаем с D: D A 3_BCD, D B 2_BD, D C 2_CD, D D 4_ABCD = 11

Теперь суммируем количество найденных вариантов:

4 + 7 + 7 + 11 = 29

Результат: 29

Видеоурок демонстрирует подробное теоретическое решение задания:

📹 YouTube здесьздесь (теоретическое решение)

8_22:

Лена составляет 5-буквенные слова из букв Я, С, Н, О, В, И, Д, Е, Ц, причём слово должно начинаться с согласной и заканчиваться гласной. Первая и последняя буквы слова встречаются в нем только один раз; остальные буквы могут повторяться.

Сколько слов может составить Лена?

✍ Решение:

✎ Решение с использованием программирования:

PascalABC.net (использование LINQ, быстрое решение):

##
var d:='ясновидец'.Cartesian(5) 
.where(l->(l[0] in 'снвдц') and (l[4] in 'яоие'))// учитываем гласные и согласные
.where(l->(l.countOf(l[0])=1)and(l.countOf(l[4])=1))//учитываем, что они не повторяются
.count.print

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var str := 'ЯСНОВИДЕЦ';
  var n := 0;
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          for var s5 := 1 to length(str) do
          begin
            var slovo := str[s1] + str[s2] + str[s3] + str[s4] + str[s5];
            if (slovo[1] in 'СНВДЦ') and (slovo[5] in 'ЯОИЕ') then
              if (slovo[1] <> slovo[2]) and (slovo[1] <> slovo[3]) and (slovo[1] <> slovo[4])            
              and (slovo[1] <> slovo[5]) and (slovo[5] <> slovo[1]) and (slovo[5] <> slovo[2]) 
              and (slovo[5] <> slovo[3]) and (slovo[5] <> slovo[4]) then
              begin
                n += 1
              end;
          end;
  print(n)
end.

Python:

С++:

Результат: 6860

Использование метода Pairwise()

8_11:

Из букв С, Р, Е, Д, А составляются трехбуквенные комбинации по следующему правилу – в комбинации не может быть подряд идущих гласных и одинаковых букв.

Например, комбинации ААР или ЕСС не являются допустимыми.

Сколько всего комбинаций можно составить, используя это правило?

✍ Решение:

✎ Решение теоретическое:

Рассмотрим два варианта: когда слово начинается с гласной буквы, и когда оно начинается с согласной.

1. С гласной:

1.1
2 3 2 = 2 * 3 * 2 = 12
^{гл с  с}

1.2
2 3 2 = 2 * 3 * 2 = 12
^{гл с гл}

2. С согласной:

2.1
3  2  2 = 3 * 2 * 2 = 12
с  с  с

2.2
3  2  3 = 3 * 2 * 3 = 18
с гл  с

2.3
3  2  2 = 3 * 2 * 2 = 12
с  с  гл

Подсчитаем общее количество вариантов:

12 + 12 + 12 + 18 + 12 = 66

✎ Решение с использованием программирования:

PascalABC.net (использование LINQ, быстрое решение):

### 
'среда'.cart(3)// 
 .Select(w -> w.JoinToString('')) // собираем в строку;
 .where(w->w.Pairwise.All((a,b) -> a+b not in 'еае'))
 .where(w->w.Pairwise.All((a,b) -> a<>b))
 .count.print

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var n := 0;
  var str := 'СРЕДА';
  var glas := 'ЕА';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
      begin
        var res := str[s1] + str[s2] + str[s3];
        // условие для подряд идущих гласных
        if not ((res[1] in glas) and (res[2] in glas) or
           (res[2] in glas) and (res[3] in glas)) then
        // условие для подряд идущих одинаковых букв
          if not ((res[1] = res[2]) or (res[2] = res[3])) then
            n += 1;
      end;
  print(n)
end.

Python:

str = 'СРЕДА'
glas = 'ЕА'
n = 0
for s1 in str:
    for s2 in str: 
        for s3 in str:
            res = s1 + s2 + s3 
            if not (s1 in glas and s2 in glas or
           s2 in glas and s3 in glas) :
                if not (s1 == s2 or s2 == s3) :
                    n += 1
print(n)

С++:

Результат: 66

Перестановка букв в слове (каждая буква 1 раз)

8_12:

Дано слово КОРАБЛИКИ. Таня решила составлять новые 5-буквенные слова из букв этого слова по следующим правилам:
1) слово начинается с гласной буквы;
2) гласные и согласные буквы в слове должны чередоваться;
3) буквы в слове не должны повторяться.

✍ Решение:

✎ Решение теоретическое:

Учтем, что в слове КОРАБЛИКИ две буквы К и две И.
Всего в слове 4 гласных, но поскольку две буквы И, то необходимо считать только 3 гласных.
Всего в слове 5 согласных, однако две из них — буквы К, поэтому считать следует 4 согласных.
Посчитаем количество согласных и гласных для каждой из 5 позиций слова, учитывая, что с каждой последующей буквой количество используемых гласных/согласных уменьшается. Под позициями приведем пример букв:

гл   с   гл   с   гл  
3    4    2   3    1
^{оаи   крбл   оа   крб    и}

Количество слов вычисляется как произведение полученных чисел:

3 * 4 * 2 * 3 * 1 = 72

Результат: 72

✎ Решение с использованием программирования:

PascalABC.net (использование LINQ, быстрое решение):

###
'кораблики'
.Cart(5)
.select(w->w.JoinToString(''))
.Distinct //Обязательно!
.where(w-> w.First in 'оаи')
.where(w->w.Pairwise.All((a,b)->not ((a in 'оаи') and (b in 'оаи')) 
       and not( ( a in'крбл') and (b in 'крбл' ))))
.where(w->'корабли'.All(c->w.countOf(c)<=1))
.count.print

Python:

С++:

Результат: 72

8_21:

Ксюша составляет слова, меняя местами буквы в слове МИМИКРИЯ.
Сколько различных слов, включая исходное, может составить Ксюша?

✍ Решение:

✎ Решение с использованием программирования:

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var str := 'МИМИКРИЯ';
  var set1: set of string;
  set1 := [];
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do 
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do 
          for var s5 := 1 to length(str) do  
            for var s6 := 1 to length(str) do
              for var s7 := 1 to length(str) do  
                for var s8 := 1 to length(str) do 
                begin
                  var slovo := str[s1] + str[s2] + str[s3] + str[s4] + str[s5] + str[s6] + str[s7] + str[s8];
                  if (slovo.CountOf('М') = 2) and (slovo.CountOf('И') = 3)
                  and (slovo.CountOf('К') = 1)
                  and (slovo.CountOf('Р') = 1)
                  and (slovo.CountOf('Я') = 1) then
                    include(set1, slovo);
                end;
  print(set1.count);
end.

Смысл решения в использовании типа множества (set). При добавлении новых элементов к множеству исключаются повторения.

PascalABC.net (использование LINQ, быстрое решение):

### 
 'МИМИКРИЯ'.Permutations // перестановки букв
 .Select(w->w.JoinToString('')) // собираем в строку
 .Distinct  // выбираем уникальные
 .Count.Print

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

С++:

Ответ: 3360

Подробное решение программным способом смотрите на видео:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (программное решение)

8_19:

Петя составляет шестибуквенные слова

перестановкой букв

слова АДЖИКА. При этом он избегает слов с двумя подряд одинаковыми буквами. Сколько всего различных слов может составить Петя?

Типовые задания для тренировки

✍ Решение:

✎ Решение теоретическое:

Посчитаем количество слов без двух подряд одинаковых букв. Будем считать относительно буквы А, которых две в заданном слове АДЖИКА. Буквы не могут повторяться, поэтому их кол-во в каждом варианте будет уменьшается:

А*А*** = 4*3*2*1 = 24 слова с данным расположением буквы А. 
А**А** = 4*3*2*1 = 24
А***А* = 4*3*2*1
А****А = ...
*А*А**
*А**А*
*А***А
**А*А*
**А**А
***А*А

Получили 10 вариантов, и в каждом из них можно составить по 24 слова.
Таким образом, получим общее количество слов:

10 * 24 = 240

✎ Решение с использованием программирования:

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var s: set of string;
  s := [];
  var str := 'АДЖИКА';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          for var s5 := 1 to length(str) do
            for var s6 := 1 to length(str) do
            begin
              var res := str[s1] + str[s2] + str[s3] + str[s4] + str[s5] + str[s6];
              if (res.CountOf('А') = 2) and (res.CountOf('Д') = 1) 
                  and (res.CountOf('Ж') = 1) and (res.CountOf('И') = 1) 
                  and (res.CountOf('К') = 1) then
                     if (res[1] <> res[2]) and (res[2] <> res[3]) and (res[3] <> res[4]) 
                        and (res[4] <> res[5]) and (res[5] <> res[6]) then
                           include(s, res);
            end;
  print(s.count)
end.

Смысл решения в использовании типа — множества (set). При добавлении новых элементов к множеству исключаются повторения.

PascalABC.net (использование LINQ, быстрое решение):

### 
'аджика'.Permutations
 .Select(w -> w.JoinToString('')) // собираем в строку;
 .distinct // исключаем дубли
 .where(s -> not ('аа' in s)) // исключаем две подряд буквы 'а'
  // или так: .where(w->w.Pairwise.All((a,b) -> a<>b))
 .count.pr

Python:

С++:

Ответ: 240

8_20:

Маша составляет 7-буквенные коды из букв В, Е, Н, Т, И, Л, Ь. Каждую букву нужно использовать

ровно 1 раз

, при этом код буква Ь не может стоять на последнем месте и между гласными. Сколько различных кодов может составить Маша?

Типовые задания для тренировки

✍ Решение:

✎ Решение теоретическое:

Выполним задание следующим образом: 1. посчитаем общее количество слов, не учитывая никакие ограничения. 2. Затем посчитаем случаи, которые необходимо исключить. 3. Вычтем из результата пункта 1 результат пункта 2.
Общее количество независимо от ограничений (учтем, что буквы не должны повторяться):

7 6 5 4 3 2 1 - количество возможных вариантов букв на семи позициях

ИТОГО:
7! = 5040 слов

Посчитаем варианты, которые необходимо исключить. Их будет несколько:
а) буква ь — на последнем месте:

6 5 4 3 2 1 Ь = 6! = 720

б) буква ь — между гласными:

И Ь Е 4 3 2 1  = 24 варианта
Так как буквы смещаются по всем позициям, то получим (4 И Ь Е 3 2 1, ...):
24 * 5 = 120
Е Ь И 4 3 2 1  = 24 варианта
24 * 5 = 120

Посчитаем количество слов, согласно условию задачи:

5040 - 720 - 120 - 120 = 4080

✎ Решение с использованием программирования:
Стоит заметить, что теоретическое решение занимает меньше времени, чем программный способ!

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var n := 0;
  var str := 'ВЕНТИЛЬ';
  var glas := 'ЕИ';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          for var s5 := 1 to length(str) do
            for var s6 := 1 to length(str) do
              for var s7 := 1 to length(str) do
              begin
                var res := str[s1] + str[s2] + str[s3] + str[s4] + str[s5] + str[s6] + str[s7];
                if (res.CountOf('В') = 1) and (res.CountOf('Е') = 1) 
                    and (res.CountOf('Н') = 1) and (res.CountOf('Т') = 1) 
                    and (res.CountOf('И') = 1) and (res.CountOf('Л') = 1)
                    and (res.CountOf('Ь') = 1) then
                  if not (res[7] = 'Ь') then
                    if not ((res[1] in glas) and (res[3] in glas) and (res[2] = 'Ь') or
                        (res[2] in glas) and (res[4] in glas) and (res[3] = 'Ь') or
                        (res[3] in glas) and (res[5] in glas) and (res[4] = 'Ь') or
                        (res[4] in glas) and (res[6] in glas) and (res[5] = 'Ь') or
                        (res[5] in glas) and (res[7] in glas) and (res[6] = 'Ь')) then
                      n += 1
              end;
  print(n)
end.

PascalABC.net (использование LINQ, быстрое решение):

### 
'вентиль'.Permutations// здесь можно без distinct, т.к. буквы не повторяются
 .Select(w -> w.JoinToString('')) // собираем в строку
 .where(s -> not ('еьи' in s) and not ('иье' in s) and (s.last <> 'ь'))
.Count.Print

Python:

С++:

Ответ: 4080

8_23:

Артур составляет 6-буквенные коды перестановкой букв слова ВОРОТА. При этом нельзя ставить рядом две гласные.
Сколько различных кодов может составить Артур?

✍ Решение:

✎ Решение с использованием программирования:

PascalABC.net (использование LINQ, спортивное прогр-е):

###
'ВОРОТА'.prm
.Sel(w->w.ToS('')).dst
.Wh(w-> not w.Pairwise.Any((a,b)->a+b in 'АООАА'))
.Cnt.pr

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

С++:

Ответ: 72

Сколько существует n-значных чисел, записанных в m-ной системе счисления

8_18: Объяснение 8 задания экзамена ЕГЭ 2020 г. (со слов учащегося):

Сколько существует восьмизначных чисел, записанных в восьмеричной системе счисления, в которых все цифры различны и рядом не могут стоять 2 чётные или 2 нечётные цифры?

Типовые задания для тренировки

✍ Решение:

✎ Решение теоретическое:

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

четные: 0, 2, 4, 6 - итого 4 цифры
нечетные: 1, 3, 5, 7 - итого 4 цифры

Рассмотрим два случая построения числа по заданию: 1) начиная с четной цифры и 2) начиная с нечетной цифры. Изобразим схематично числа, указывая сверху возможное количество цифр на разряд:

1) с четной цифры:
3  4  3  3  2  2  1  1 = 3*4*3*3*2*2*1*1 = 432
ч  н  ч  н  ч  н  ч  н

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

2) с нечетной цифры:
4  4  3  3  2  2  1  1 = 4*4*3*3*2*2*1*1 = 576
н  ч  н  ч  н  ч  н  ч

Каждый последующий разряд включает на одну цифру меньше, так как по заданию цифры не могут повторяться.

Сложим количество вариантов в обеих случаях:

432 + 576 = 1008

✎ Решение с использованием программирования:

PascalABC.net (использование LINQ, быстрое решение):

###
'01234567'.Permutations // т.к. цифр итак 8 штук
.where(w->w.First<>'0') // первая цифра не может быть 0
.where(w->w.Pairwise.All((a,b)-> (a.ToDigit + b.ToDigit).IsOdd)) // проверка пар четных и нечетных
.count.print

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

С++:

Ответ: 1008

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

8_13:

Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Ниже приведено начало списка:

1. ААААА
2. ААААО
3. ААААУ
4. АААОА
…

Запишите слово, которое стоит под номером 242 от начала списка.

✍ Решение:

✎ Решение теоретическое:

Данное задание лучше решать следующим образом. Подставим вместо букв цифры (А -> 0, О -> 1, У -> 2):

Видим, что каждая последующее число получается путем прибавления в столбик единицы к предыдущему числу. В троичной системе счисления! Т.к. цифр всего три.
Порядковый номер, написанный рядом с пунктом, всегда на единицу больше располагающейся рядом цифры в троичной системе счисления.
Значит, пункту под номером 242 будет соответствовать число 241 в троичной системе счисления.
Переведем 241 в 3-ю систему делением на 3:

        ^{остатки}
241 | 3 | 1
 80 | 3 | 2
 26 | 3 | 2
  8 | 3 | 2
  2 |   |

Перепишем остатки снизу вверх: 22221, им соответствуют буквы УУУУО

✎ Решение с использованием программирования:

PascalABC.net (использование LINQ, быстрое решение):

##
var d:='АОУ'.Order // сортируем по алфавиту
.Cartesian(5)
.Numerate.print

Смотрим слова и находим по номеру нужное слово:

… (241,[У,У,У,У,А]) (242,[У,У,У,У,О]) (243,[У,У,У,У,У])

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

С++:

Результат: УУУУО

Подробное решение теоретическим способом смотрите на видео:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

8_14: 8 задание. Демоверсия ЕГЭ 2018 информатика:

Все 4-буквенные слова, составленные из букв Д, Е, К, О, Р, записаны в алфавитном порядке и пронумерованы, начиная с 1.
Ниже приведено начало списка.

1. ДДДД
2. ДДДЕ
3. ДДДК
4. ДДДО
5. ДДДР
6. ДДЕД
…

Под каким номером в списке идёт первое слово, которое начинается с буквы K?

✍ Решение:

✎ Решение теоретическое:

Подставим вместо букв цифры (Д -> 0, Е -> 1, К -> 2, О -> 3, Р -> 4):

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

K -> 2 -> 2000

Полученное число — 2000 — необходимо перевести из пятеричной системы счисления в десятичную, чтобы узнать порядковый номер:

По формуле разложения числа по степеням основания:

2000₅ = 2 * 5³ + 0 * 2² + 0 + 0 = 2 * 125 = 250₁₀

Поскольку порядковый номер числа всегда на единицу больше самого числа, то имеем 251.

✎ Решение с использованием программирования:

PascalABC.net (использование LINQ, быстрое решение):

###
var d:='декор'.Order // сортируем по алфавиту
.Cartesian(4) // d - массива из массивов символов 
.Numerate // нумерация
.where((i,w)->w[0] = 'к') // рассматриваем и номер и слово
.first[0].print // выводим именно номер

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

С++:

Результат: 251

Подробное решение 8 (10) задания демоверсии ЕГЭ 2018 года смотрите на видео:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

8_15:

Все 4-буквенные слова, составленные из букв П, Р, С, Т, записаны в алфавитном порядке.
Вот начало списка:

1. ПППП
2. ПППР
3. ПППС
4. ПППТ
5. ППРП
... ...

✍ Решение:

Результат: 65

Видеоразбор задания смотрите ниже:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

8_16:

Все четырёхбуквенные слова, составленные из букв В, Е, Г, А, Н записаны в алфавитном порядке и пронумерованы, начиная с 1. Начало списка выглядит так:

1. АААА
2. АААВ
3. АААГ
4. АААЕ
5. АААН
6. ААВА
…

Под каким номером в списке идёт первое слово, в котором нет буквы А?

✍ Решение:

✎ Решение теоретическое:

Пронумерованный список начинается со всех букв А. Представим, что А — 0, В — 1, Г — 2, Е — 3, Н — 4. Получим следующий список:

Такой список представляет из себя увеличивающиеся числа 5-й системы счисления.
Так как букве А соответствует 0, то первое (самое младшее) четырехзначное число без нуля — это 1111.
Чтобы вычислить под каким номером стоит данное число, переведем его в 10-ю систему и прибавим к результату единицу (так как порядковые номера в списке на единицу больше самих чисел):

1111₅ = 1 * 5³ + 1 * 5² + 1 * 5¹ + 1 * 5⁰ = 156
156 + 1 = 157

✎ Решение с использованием программирования:

PascalABC.net (использование LINQ, быстрое решение):

###
var d:='веган'.Order // сортируем по алфавиту
.Cartesian(4) // d - массива из массивов символов
.Select(x->x.JoinToString(''))// d - массив из строк 
.Numerate // нумерация
.where((i,w)->'а' not in w) // рассматриваем и номер и слово
.first[0].print // выводим именно номер

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

С++:

Результат: 157

Видеорешение задания (теоретическое):

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

Вероятность событий

8_17:

За четверть Василий Пупкин получил 20 оценок. Сообщение о том, что он вчера получил четверку, несет 2 бита информации.

Сколько четверок получил Василий за четверть?

✍ Решение:

Для решения данного задания необходимо вспомнить две формулы:

1. Формула Шеннона:

x = log₂(1/p)

x - количество информации в сообщении о событии
p - вероятность события

2. Формула вероятности случайного события:

p(A) = m/n

m - число случаев, способствующих событию А
n - общее число равновозможных случаев

Подставим в первую формулу известное значение — вероятность того, что Василий получил четверку:

2 = log₂(1/p);
    => 
1/p = 4; 
    =>
p = 1/4

Затем подставим известное по условию значение в формулу вероятности случайного события:

p = ?/20

Поскольку p мы уже нашли, подставим найденное значение и найдем искомое число — количество четверок за четверть:

1/4 = ?/20

? = 1/4 * 20 = 5

Результат: 5

Видеоразбор задания:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

Источник

Объяснение
заданий 10 ЕГЭ по информатике

10 тема —
«Измерение количества информации» — характеризуется, как задания базового
уровня сложности,
время выполнения – примерно 4 минуты,
максимальный балл — 1

Типичные
ошибки и рекомендации по их предотвращению:

«При
использовании способа решения со системой счисления с основанием N
следует помнить, что слова в списке нумеруются с единицы, поэтому числу 0
будет соответствовать первое слово»

Рассмотрим кратко
необходимые для решения 10 задания ЕГЭ понятия и формулы.

Измерение
количества информации

Кодирование — это
представление информации в форме, удобной для её хранения, передачи и
обработки. Правило преобразования информации к такому представлению
называется кодом.
1 бит – это
количество информации, которое можно передать с помощью одного знака в
двоичном коде (0 или 1).

Единицы
измерения:

1 байт (bytе)
= 8 бит
1 Кб (килобайт) = 1024 байта
1 Мб (мегабайт) = 1024 Кб
1 Гб (гигабайт) = 1024 Мб
1 Тб (терабайт) = 1024 Гб
1 Пб (петабайт) = 1024 Тб

8 = 2³
1024 = 2¹⁰

Рассмотрим
еще несколько определений:

Алфавит — это набор
знаков, используемый в том или ином языке.
Мощность алфавита —
это количество используемых в алфавите знаков.

Мощность алфавита

Сообщение — это любая
последовательность символов какого-либо алфавита.

Для вычисления количества
информации применяются несколько различных формул в зависимости от ситуации:

Двоичное кодирование сообщений
(равновероятностные события)

При вычислении
количества информации в сообщении для равновероятностных событий,
общее количество которых равно N, используется формула:

N = 2^L

·
N —
количество сообщений

·
L — длиной
битов

*
следует иметь в виду, что также приняты следующие обозначения: Q = 2^k

Пример 2: Зашифруем
буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и
посчитаем количество возможных сообщений:

Решение:

Таким
образом, мы получили равномерный код, т.к. длина
каждого кодового слова одинакова для всех кодовых слов (L = 2).

Количество
сообщений длиной L битов:

N = 2^L

Т.е. количество
сообщений длиной 2 бита, как в примере с нашими буквами, будет равно N
= 2² = 4

Ответ: 4

Количество
различных сообщений в алфавите разной мощности

Рассмотрим вариант
с 5 буквами (мощность алфавита = 5), которые надо
разместить в сообщении длиной 2 символа:

Найдем формулу
для нахождения количества различных сообщений в алфавите различной мощности:

Если
мощность некоторого алфавита составляет N, то количество
различных сообщений длиной L знаков:

o N – мощность алфавита

o L – длина сообщения

o Q – количество различных сообщений

Пример: Сколько существует всевозможных
трехбуквенных слов в английском языке?

Решение:

В
английском алфавите 26 букв. Значит, мощность алфавита = 26. Длина
сообщения = 3. Найдем по формуле количество трехбуквенных слов:
Q = 26³
или
26 * 26 * 26 = 17576

Ответ: 17576

· Таким, образом,
если слово состоит из L букв, причем есть n1 вариантов выбора
первой буквы, n2 вариантов выбора второй буквы и т.д., то число
возможных слов вычисляется как произведение:

N = n1 *
n2 * … * nL

Количество
сообщений при различном вхождении (встречаемости) букв

Иногда в заданиях 10 приходится использовать формулу
комбинаторики для проверки полученных результатов перебора. Число
сочетаний из n элементов по k элементов:

· I –
количество информации в битах

· N –
количество вариантов

Факториал
числа n:

n! = 1 * 2
* 3 * … * n

Пример: Сколько существует всевозможных четырехбуквенных
слов в алфавите из 4 букв: А, Б, В, Г, если известно, что буква
А встречается ровно два раза?

Решение:

·
Длина
сообщения = 4. Мощность алфавита = 4. Но мешает условие: буква
А встречается ровно два раза.

·
В
таких заданиях можно использовать способ перебора всевозможных вариантов:

два раза буква А, на остальных местах — одна из трех
оставшихся букв:

А А 3
3 = 3 * 3 = 3² = 9

А 3 А
3 = 9

А 3 3
А = 9

3 А А
3 = 9

3 А 3
А = 9

3 3 А
А = 9

·
Получили 6 вариантов, каждый из которых равен 9.

·
Проверим формулой числа сочетаний:

Число сочетаний из n элементов по k элементов:

C(kn)=n!k!(n−k)!

·
В задаче:

C(24)=4!2!(4−2)!=242∗2=6

* Факториал числа n! = 1 * 2 * 3 *..* n

·
Т.е. проверка прошла успешно, мы получили 6 вариантов.

·
Осталось
посчитать количество всех сообщений:

6 * 9 = 54

Дополнительные
формулы

Количество
информации и равновероятные события

При определении
количества информации для равновероятностных событий могут понадобиться две
формулы:

Формула Шеннона:

x = log₂(1/p)

·
x —
количество информации в сообщении о событии

·
p — вероятность
события

Формула
вероятности случайного события:

p(A) = m / n

·
m —
количество благоприятных исходов (число случаев, способствующих событию А)

·
n —
количество общих исходов (общее число равновозможных случаев)

Количество
информации и неравновероятные события

При использовании
неравновероятного события, вероятность которого равна p, для
вычисления количества информации используется формула:

i = -[log₂p]

*квадратные скобки
означают ближайшее целое, меньшее или равное значению выражения в скобках

Формула
Хартли:

Формула Хартли

·
I –
количество информации в битах

·
N –
количество вариантов

Алфавитный
подход:

Информационный
объем сообщения длиной L:

Алфавитный подход

·
N —
мощность алфавита

·
L — длина
сообщения

ЕГЭ по
информатике 2017 задание 10 ФИПИ вариант 1 (Крылов С.С., Чуркина Т.Е.):

Шифр
кодового замка представляет собой последовательность из пяти символов,
каждый из которых является цифрой от 1 до 6.

Сколько различных
вариантов шифра можно задать, если известно, что цифра 1 должна встречаться в коде ровно 1 раз, а каждая из других допустимых цифр может встречаться
в шифре любое количество раз или не встречаться совсем?

Решение:

·
Формула
нахождения количества различных сообщений:

Q = N^L

·
Итак,
что у нас дано из этой формулы:

·
Длина
сообщения (L) = 5 символов

·
Мощность
алфавита (N) = 6 (цифры от 1 до 6).

·
Но
так как цифра 1 встречается по условию ровно один раз, а остальные 5
цифр — любое количество раз, то будем считать, что N = 5 (цифры от 2 до
6, исключая 1). Т.е. возьмем вариант, когда 1 стоит на первом месте, а
остальные 5 цифр размещаем на 4 позиции:

1 5 5 5 5 — 1 *
Q = 5⁴ = 625

1 способ.
Найдем количество вариантов методом перебора:

·
Методом
перебора найдем количество вариантов размещения:

1 5 5 5 5 - 1 * Q=5⁴ = 625

5 1 5 5 5 - 1 * Q=5⁴ = 625

5 5 1 5 5 - 1 * Q=5⁴ = 625

5 5 5 1 5 - 1 * Q=5⁴ = 625

5 5 5 5 1 - 1 * Q=5⁴ = 625

получили 5
вариантов;

2
способ. Найдем количество вариантов при помощи формулы комбинаторики:

C(45)=5!4!(5−4)!=5

получили 5
вариантов;
В итоге
получим:

625
* 5 = 3125

Результат: 3125

Источник

Все мы привыкли к тому, что все вокруг можно измерить. Мы можем определить массу посылки, длину стола, скорость движения автомобиля. Но как определить количество информации, содержащееся в сообщении? Ответ на вопрос в статье.

Итак, давайте для начала выберем сообщение. Пусть это будет «Принтер — устройство вывода информации.«. Наша задача — определить, сколько информации содержится в данном сообщении. Иными словами — сколько памяти потребуется для его хранения.

Определение количества информации в сообщении

Для решения задачи нам нужно определить, сколько информации несет один символ сообщения, а потом умножить это значение на количество символов. И если количество символов мы можем посчитать, то вес символа нужно вычислить. Для этого посчитаем количество различных символов в сообщении. Напомню, что знаки препинания, пробел — это тоже символы. Кроме того, если в сообщении встречается одна и та же строчная и прописная буква — мы считаем их как два различных символа. Приступим.

В слове Принтер 6 различных символов (р встречается дважды и считается один раз), далее 7-й символ пробел и девятый — тире. Так как пробел уже был, то после тире мы его не считаем. В слове устройство 10 символов, но различных — 7, так как буквы с, т и о повторяются. Кроме того буквы т и р уже была в слове Принтер. Так что получается, что в слове устройство 5 различных символов. Считая таким образом дальше мы получим, что в сообщении 20 различных символов.

Далее вспомним формулу, которую называют главной формулой информатики:

2ⁱ=N

Подставив в нее вместо N количество различных символов, мы узнаем, сколько информации несет один символ в битах. В нашем случае формула будет выглядеть так:

2ⁱ=20

Вспомним степени двойки и поймем, что i находится в диапазоне от 4 до 5 (так как 2⁴=16, а 2⁵=32). А так как бит — минимальная единица измерения информации и дробным быть не может, то мы округляем i в большую сторону до 5. Иначе, если принять, что i=4, мы смогли бы закодировать только 2⁴=16 символов, а у нас их 20. Поэтому получаем, что i=5, то есть каждый символ в нашем сообщении несет 5 бит информации.

Осталось посчитать сколько символов в нашем сообщении. Но теперь мы будем считать все символы, не важно повторяются они или нет. Получим, что сообщение состоит из 39 символов. А так как каждый символ — это 5 бит информации, то, умножив 5 на 39 мы получим:

5 бит x 39 символов = 195 бит

Это и есть ответ на вопрос задачи — в сообщении 195 бит информации. И, подводя итог, можно написать алгоритм нахождения объема информации в сообщении:

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

Автор:

Источник

Сегодня на повестке дня 8 задание из ЕГЭ по информатике 2021. Данный тип заданий включает в себя нахождение количества вариантов, элементы комбинаторики и другие математические понятия.

Перейдём к практике решения задач задания 8 ЕГЭ по информатике 2021.

Задача (Классика)

Все 4-буквенные слова, составленные из букв А, Е, И, О записаны в алфавитном порядке и пронумерованы. Вот начало списка:

1. АААА
2. АААЕ
3. АААИ
4. АААО
5. ААЕА
…

Запишите слово, стоящее на 248-м месте от начала списка.

Решение:

Обозначим условно А — 0, Е — 1, И — 2, О — 3.

Важно: Нужно буквам присваивать цифры именно в том порядке, в котором они идут в самом правом столбце, потому что буквы могут дать в «перепутанном порядке» (например Е, А, И, О), и тогда ничего не получится.

Теперь запишем список с помощью цифр.

1. 0000
2. 0001
3. 0002
4. 0003
5. 0010
…

Получился обычный счёт в четверичной системе!! (всего используются 4 цифры: 0, 1, 2, 3). А слева нумерация показывает соответствие нашей десятичной системе. Но все числа десятичной системы в этой таблице соответствия сдвинуты на 1, ведь мы должны были начать с нуля.

Нас просят записать слово стоящее на 248, т.е. если была обычная таблица соответствия чисел десятичной системы и четверичной системы, слово стоящее на 248 месте, находилось бы на 247 (248 — 1) месте. Значит, наше искомое четверичное число соответствует 247 в десятичной системе.

Переведём число 247 в четверичную систему!

Получилось число 3313₄ в четверичной системе. Сделаем обратное декодирование в буквы. Таким образом, ответ будет ООЕО.

Ответы: ООЕО

Ещё одна похожая задача 8 задания из примерных вариантов ЕГЭ по информатике, но другой вариации.

Задача (Классика, Другая вариация)

Все 5-буквенные слова, составленные из букв А, Р, У, К записаны в алфавитном порядке. Вот начало списка:

1. ААААА
2. ААААК
3. ААААР
4. ААААУ
5. АААКА
……
Укажите номер слова УКАРА

Решение:

Закодируем буквы цифрами: А — 0, К — 1, Р — 2, У — 3. Здесь как раз буквы даны не в том порядке, как они идут в самом правом столбце. Но мы должны кодировать именно в том порядке, как буквы идут в самом правом столбце.

У нас получилось четыре цифры! Значит снова можно слова превратить в таблицу соответствия между десятичной системой и четверичной системой. Но десятичная система смещена на 1 позицию.

1. 00000
2. 00001
3. 00002
4. 00003
5. 00010
……

Выписываем данное нам слово и посмотрим, какое число в четверичной системе было бы, если бы у нас были в место слов числа в четверичной системе!

Получили число в четверичной системе 31020₄. Узнаем, какое число в десятичной системе соответствовало этому числу, если бы была обычная таблица соответствия. Для этого переведём число 31020₄ из четверичной системы в десятичную. Перевод делаем по аналогии перевода из двоичной системы в десятичную.

Но помним, что у нас нумерация идёт на 1 быстрее, нежели мы бы поставили десятичные числа, как в таблице соответствия, потому что нумерация начинается не с нуля, а с 1. Поэтому к числу 840 нужно прибавить 1, и в ответе будет 841

Ответ: 841

Задача (Демонстрационный вариант ЕГЭ по информатике, 2020)

Все 4-буквенные слова, в составе которых могут быть буквы Н, О, Т, К, И,
записаны в алфавитном порядке и пронумерованы, начиная с 1.
Ниже приведено начало списка.

1. ИИИИ
2. ИИИК
3. ИИИН
4. ИИИО
5. ИИИТ
6. ИИКИ
…

Под каким номером в списке идёт первое слово, которое начинается
с буквы О?

Решение:

Закодируем буквы цифрами.

Получилось 5 цифр ( 0, 1, 2, 3, 4 ), значит, будем работать в пятеричной системе.

Нужно найти номер первого слова, которое начинается с буквы О. Если говорить на языке пятеричных чисел, то нужно найти номер числа 3000₅. Мы «забиваем нулями», чтобы число было четырёхразрядное, т.к. слова 4-х буквенные. Именно нулями, потому что нужно именно первое слово найти.

Теперь, как в предыдущей задаче, переведём число 3000₅ из пятеричной системы в десятичную.

0 * 5 ⁰ + 0 * 5 ¹ + 0 * 5 ² +
3 * 5 ³ = 375 (в десят. системе)

Но опять же должны прибавить 1 к числу 375, т.к. нумерация отличается от десятичных чисел на 1 в большую сторону.

Ответ: 376

Задача (Досрочная волна 2020 ЕГЭ по информатике, вариант 1)

Вася составляет 5-буквенные слова, в которых есть только буквы В, О, Л, К,
причём буква В используется в каждом слове ровно 1 раз. Каждая из других
допустимых букв может встречаться в слове любое количество раз или
не встречаться совсем. Словом считается любая допустимая
последовательность букв, не обязательно осмысленная. Сколько существует
таких слов, которые может написать Вася?

Решение:

Для начала решим вводную подзадачу.

Пусть у нас есть те же буквы В, О, Л, К, каждая из букв может встречаться в слове любое количество раз или
не встречаться совсем. Сколько можно составить 5-буквенных слов ?

Т.е буквы могут повторяться!

Например

Такая конструкция сильно напоминает перебор чисел, где вместо цифр используются буквы.

Рассмотрим перебор трёхразрядных чисел. Вместо 5 букв теперь можно использовать 10 цифр ( 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ). Цифры так же могут повторяться. Сколько получится вариантов ?

Выведем общую формулу для количества вариантов, когда символы могут повторяться!

Для трёхразрядных чисел от 000 до 999:

N = 10³ = 1000 вариантов.

Вернёмся к пятибуквенным словам и нашей подзадаче. Здесь количество букв (разрядов) в слове равно 5, количество допустимых символов равно 4 ( В, О, Л, К ).

N = 4⁵ = 1024 вариантов.

Вернёмся к изначальной задаче. Сначала найдём количество вариантов, когда буква В находится в самой левой ячейке!

Применим формулу! Здесь слово сократилось до четырёхразрядного. А количество букв для использования 3 (О, Л, К).

N = 3⁴ = 81 комбинация.

Но буква В так же может стоять во второй ячейке слева. Этот случай тоже даст 81 других комбинаций. Буква В может стоять в каждой из 5-ти ячеек, и везде будет получатся 81 комбинация.

Таким образом, окончательный ответ будет:

N = 81 * 5 = 405 различных вариантов.

Ответ: 405

Разобравшись с этой задачей, больше половины тренировочных задач десятого задания из различных книг и сайтов по подготовке к ЕГЭ по информатике будут решаться, как по маслу!

Задача(Закрепление формулы)

Рассматриваются символьные последовательности длины 5 в шестибуквенном алфавите {У, Ч, Е, Н, И, К}. Сколько существует таких последовательностей, которые начинаются с буквы У и заканчиваются буквой К?

Решение:

Применим главную формулу 8 задания из ЕГЭ по информатике

N = mⁱ = 6³ = 216

Здесь буквы могут изменяться на 3 ячейках! Значит, в формуле i=3. Количество допустимых символов, которые можно поставить в каждую ячейку равно 6. Значит, в формуле m=6.

В ответе будет 216.

Примечание: Здесь можно использовать все буквы в каждой ячейке, включая У и К. В некоторых задачах их уже использовать нельзя, т.е. сказано, что буквы У и К используются один раз в слове. Тогда в формуле m, будет на 2 единицы меньше. Нужно внимательно читать задачу!

Ответ: 216

Задача (Демонстрационный вариант ЕГЭ по информатике, 2019)

Вася составляет 5-буквенные слова, в которых есть только буквы З, И, М, А,
причём в каждом слове есть ровно одна гласная буква и она встречается
ровно 1 раз. Каждая из допустимых согласных букв может встречаться
в слове любое количество раз или не встречаться совсем. Словом считается
любая допустимая последовательность букв, не обязательно осмысленная.
Сколько существует таких слов, которые может написать Вася?

Решение:

Рассмотрим количество вариантов, когда гласная И стоит в первом месте!

Подсчитаем количество слов с помощью супер-формулы

N = mⁱ = 2⁴ = 16

Длина изменяющихся ячеек равна 4, а количество допустимых букв равно 2.

Но буква И может стоять не только на первом месте. Она так же может стоять и на 2, и на 3, и на 4, и на 5 месте. Каждый такое случай добавляет столько же новых слов.

Значит, при использовании только буквы И будет количество слов 16 * 5 = 80. Ещё столько же слов добавится, если в словах вместо буквы И будет использоваться буква А. Поэтому окончательный ответ будет 80 * 2 = 160

Ответ: 160

Отработаем главную формулу 8 задания из ЕГЭ по информатике.

Задача (Развиваем понимание формулы!)

Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв З, И, М, А? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

Решение:

Рассмотрим, какие варианты могут быть, если у нас на первом месте стоит согласная, а на последнем месте гласная

Получилось 4 разных случая. Подсчитаем, сколько слов можно составить при одном случае.

N = mⁱ = 4³ = 64

Длина изменяющихся ячеек равна 3, а количество возможных букв 4.

Но т.к. таких случая у нас четыре, то ответ будет 4 * 64 = 256

Ответ: 256

Рассмотрим важнейший «метод умножения» при решении 8 задания из ЕГЭ по информатике.

Задача (Другой метод решения!!)

Матвей составляет 6-буквенные коды из букв М, А, Т, В, Е, Й. Каждую букву нужно использовать ровно 1 раз , при этом код не может начинаться с буквы Й и не может содержать сочетания АЕ. Сколько различных кодов может составить Матвей?

Решение:

Эта задача отличается от уже разобранных тем, что каждую букву можно использовать один раз. В этой задаче удобнее воспользоваться немного другим методом решения! «Методом умножения»!

Решим вводную подзадачу (без дополнительных ограничений).

Сколькими способами можно составить 6-x буквенное слово из букв М, А, Т, В, Е, Й. Каждую букву нужно использовать ровно 1 раз .

Чтобы найти возможные варианты, перемножаем для каждой ячейки количество букв из которых у нас есть выбор!

N = 6 * 5 * 4 * 3 * 2 * 1 = 720

Вернёмся к изначальной задаче!

В начале подсчитаем «методом умножения» количество слов, не обращая внимание, на условие, в котором сказано, что слово не может содержать сочетание АЕ.

N = 5 * 5 * 4 * 3 * 2 * 1 = 600

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

Но в 600 комбинаций входят и те случаи, когда в слове присутствует сочетание АЕ. Теперь найдём сколько таких слов, где присутствует сочетание АЕ

Узнаем количество вариантов в каждом таком случае.

N1 = 4 * 3 * 2 * 1 = 24

На первом месте мы не можем использовать букву Й, поэтому мы на первом месте выбираем из 3 букв.

N2 = 3 * 3 * 2 * 1 = 18

Аналогично предыдущему случаю.

N3 = 3 * 3 * 2 * 1 = 18

N4 = 3 * 3 * 2 * 1 = 18

N5 = 3 * 3 * 2 * 1 = 18

Всего слов с сочетанием АЕ будет

24 + 18 + 18 + 18 + 18 = 96

Значит, всего слов, которые удовлетворяют условию задаче будет

N = 600 — 96 = 504

Примечание: Метод умножения можно было использовать и в задачах, которые мы рассмотрели ранее. Например, в задаче «Закрепление формулы» в первой свободной ячейке выбираем из 6 букв, во второй свободной ячейке тоже из 6 букв, и в третий свободной ячейке тоже можно использовать 6 букв. Значит, по методу умножения получается N = 6 * 6 * 6 = 6³ = 216

Ответ: 504

Задача (Закрепления «метода умножения»)

Полина составляет 6-буквенные коды из букв П, О, Л, И, Н, А. Каждую букву нужно использовать ровно 1 раз, при этом нельзя ставить подряд две гласные или две согласные. Сколько различных кодов может составить Полина?

Решение:

Опять сказано, что каждая буква используется 1 раз, следовательно, нужно применять «метод умножения».

На первое место можно выбрать из 6 букв, предположим, мы выберем согласную. Тогда на второе место нужно выбирать из 3 гласных. Потом опять должна идти согласная, но их у нас осталось только 2. Далее, на следующее место выбираем из 2 гласных букв. И на предпоследнее место выбирается 1 согласная, а на последнее место остаётся 1 гласная.

Т.к. количество гласных букв и согласных одинаковое, и равно трём, то если мы бы начали делать «метод умножения» с гласной буквы, количество вариантов бы не поменялось.

N = 6 * 3 * 2 * 2 * 1 * 1 = 72

Ответ: 72

Задача (Азбука Морзе)

Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т.д.) можно закодировать, используя код Морзе длиной не менее трёх и не более четырёх сигналов (точек и тире) ?

Решение:

Зная формулу, без проблем решим данную примерную задачу из ЕГЭ по информатике.

У нас есть 2 символа, которые можно использовать: точка и тире. Фраза, что сообщение может иметь «не менее трёх и не более четырёх сигналов», означает, что сообщения могут быть длиною 3 символа и длиною 4 символа.

Подсчитаем общее количество вариантов.

N = 2³ + 2⁴ = 8 + 16 = 24 комбинаций.

Значит, для 24 различных символов (цифр, букв, знаков пунктуации и т.д.) мы найдём различные комбинации, чтобы их закодировать

Ответ: 24

Задача (Обратная предыдущей)

Световое табло состоит из цветных индикаторов. Каждый индикатор может окрашиваться в четыре цвета: белый, черный, желтый и красный. Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 300 различных сигналов?

Решение:

Нам нужно закодировать 300 различных вариантов! Имеются 4 различных лампочки! (Они имеют смысл, как количество допустимых символов!) На этот раз нужно узнать количество лампочек (количество разрядов, «длину слова»). Применяем формулу.

N = 4^x = 300

Не найдётся такое целое x, чтобы равенство стало верным. Поэтому берём целое минимальное x такое, чтобы 4^x больше 300.

4⁵ = 1024

Пять лампочек на табло хватит, чтобы закодировать 300 сигналов, но, к сожалению, много комбинаций просто не пригодится!

Ответ: 5

Задача (Важная!)

Нужно выбрать в подарок 3 книги из 5. Сколькими способами можно выбрать ?

Решение:

На рисунке показано две комбинации, как можно выбрать в подарок 3 книги из 5.

Данную задачку нужно решать используя формулу сочетаний из раздела комбинаторика.

n — количество книг, из которых мы выбираем подарок, m — количество книг, которое мы хотим выбрать, C — количество вариантов (способов).

Восклицательный знак — это факториал!

Факториалом числа «n» (условное обозначение n!- читается как «эн» — факториал) называется произведение чисел от 1 до «n»

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

Ответ: 10

Следующая задача часто встречается в книгах по подготовке к ЕГЭ по информатике.

Задача (Главная формула + сочетания)

Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является цифрой от 1 до 5. Сколько различных вариантов шифра можно задать, если известно, что цифра 1 встречается ровно три раза, а каждая из других допустимых цифр может встречаться в шифре любое количество раз или не встречаться совсем?

Решение:

В начале нужно посчитать, сколькими способами на 5-ти ячейках можно расположить 3 единицы!

Обратите внимание, как будто мы выбираем 3 книги в подарок из 5 возможных! Значит, опять применяем формулу сочетаний из комбинаторики. Мы вычисляли уже её точно с такими же числами в прошлой задаче, количество вариантов равно 10.

Подсчитаем, сколько вариантов кодового замка можно составить при одном определённом расположении трёх единиц.

Применим формулу, есть две ячейки, в которых изменяются цифры, а в каждой ячейке может быть одна из 4 цифр.

N = mⁱ = 4² = 16

Т.к. различных вариантов, как расположить единицы на 5 ячейках равно 10, то ответ будет 16 * 10 = 160

Ответ: 160

Ещё одна задача из примерных вариантов по подготовке к ЕГЭ по информатике.

Задача (Таблица соревнований)

Для записи результатов соревнований используется таблица, в которой для каждой из 20-ти команд по каждому из 10-ти видов состязаний записано 1, 2 или 3 (если команда заняла соответствующее место в этом состязании) или прочерк (если не заняла призовое место или не участвовала). Какое количество информации (бит) содержит таблица ?

Решение:

Есть таблица с 20 командами и для каждой команды есть результат по 10-ти видам состязаний.

	1 команда	2 команда	3 команда	…	20 команда
1 дисциплина	1	—	1	…	3
2 дисциплина	—	2	1	…	2
…	…	…	…	…	…
10 дисциплина	1	1	2	…	—

В каждой ячейке может быть 4 различных значения ( 1, 2, 3, — ). Нужно узнать, сколько бит занимает одна ячейка таблицы. Один бит может быть либо единицей, либо нулём.

Сделав рисунок, задача обрела привычные очертания.

Как будто мы решаем задачу с перебором слов. Но здесь длина слова неизвестна, а количество вариантов, которое должно получится уже дано и равно 4 (четырём). Применим главную формулу из 10 задания из ЕГЭ по информатике.

N = mⁱ = 2ⁱ = 4

i=2 бита (длина равна «2 буквам», если воспринимать задачу, как со словами.)

Одна ячейка таблицы весит 2 бита. Найдём количество ячеек во всей таблице соревнований.

Всего ячеек = 20 * 10 = 200

Тогда вся таблица будет весит:

V = 2 бита * 200 = 400 бит.

Ответ: 400

Формула Шеннона

Задача (Формула Шеннона)

В корзине лежат 8 черных шаров и 24 белых. Сколько бит информации несет сообщение о том, что достали черный шар?

Решение:

Данную задачу нужно решать по формуле Шеннона

Найдём вероятность p того, что вытащили чёрный шарик.

p = (количество чёрных шаров) / (количество всех шаров) = 8 / (24 + = 8 / 32 = 1 /4

p = 1 / 4

Применим формулу Шеннона.

x = log₂(4)
2^x = 4

x = 2 бита

Ответ: 2

Доброго времени суток ! Помогите пожалуйста решить задачу .) Матвей составляет 6-буквенные коды из букв М, А, Т, В, Е, Й. Каждую букву нужно использовать ровно 1 раз, при этом код не может начинаться с буквы Й и не может содержать сочетания АЕ. Сколько различных кодов может составить Матвей?

В закрытом ящике находится 32 карандаша, некоторые из них синего цвета. Наугад вынимается один карандаш. Сообщение «этот карандаш – НЕ синий» несёт 4 бита информации. Сколько синих карандашей в ящике?
Был бы очень рад , если вы разберете и эту задачку

Добрый день. Полностью разобрал этот номер, но наткнулся на один интересный пример. Объясните доступным языком, пожалуйста. На решу егэ вообще не понял их решение:

Тимофей составляет 5-буквенные коды из букв Т, И, М, О, Ф, Е, Й. Буква Т должна входить в код не менее одного раза, а буква Й — не более одного раза. Сколько различных кодов может составить Тимофей? (ответ: 8006)

Добрый день! Подскажите пожалуйста, как решить следующую задачу: Сколько существует чисел, шестнадцатеричная запись которых содержит 3 цифры, причём все цифры различны и никакие две чётные и две нечётные цифры не стоят рядом.

Петя составляет семибуквенные слова перестановкой букв слова АССАСИН. Сколько всего различных слов может составить Петя? Мое решение: 21 вариант с буквой А, 35- с буквой С, и 4 на буквы И и Н. Всего 60 и умножаем на 7. Получается 420. Не уверена, что применила верный алгоритм. Прокомментируйте, пожалуйста, решение

Можете заказать решение задачи через раздел «связь».

В Задаче (Другой метод решения!!) допущена ошибка в решении, ведь 24 + 18 + 18 + 18 + 18 = 114,значит N = 600 — 114 = 486!

Добрый день! Помогите пожалуйста решить задачку
Сколько чисел длиной 6 можно составить, если известно, что цифры идут в порядке убывания, при этом четные и нечетные цифры чередуются?

У меня только один вопрос. Почему в школах на уроках информатики вместо действительно полезного изучения какого нибудь языка программирования, заставляют заниматься вот этой вот ересью и решать какое по счету слово напишет Вася? Я могу только составить в ответ на это только слова которые нельзя здесь писать. От таких знаний и занятий ни один ребенок не захочет стать программистом, потому что это непонятно, и неизвестно зачем уметь решать такие задачи. Я сам программист с 10 летним стажем не смог объяснить ребенку как решать некоторые задачи и самое главное, я не знаю зачем дети должны уметь это решать.

Дмитрий, согласен с Вами. Особенно 11 задание и формула Шеннона. Надо либо излагать задание корректно, либо исключить вообще: «В корзине лежат черные и белые шары. Среди них 18 черных шаров. Сообщение о том, что достали белый шар, несет 2 бита информации. Сколько всего шаров в корзине?» — для двух состояний достаточно одного бита.

marvell special for u

c = 0
from itertools import*
for i in permutations(‘МАТВЕЙ’, r=6):
i = ».join(i)
if i[0] != ‘Й’ and i.count(‘АЕ’) == 0:
print(i)
c += 1
print(c)

Источник

На прошлых уроках мы
узнали:

· Алфавитом
языка называется набор всех различных символов, которые
используются для представления информации на этом языке.

· Любой
алфавит характеризуется своей мощностью, так называется количество
символов, которые в него входят.

· Мощность
двоичного алфавита – всего два символа.

· Двоичным
кодированием называется запись информации с помощью
символов двоичного алфавита, а двоичным кодом – код информации,
получившийся в результате двоичного кодирования.

· Двоичное
кодирование универсально, это означает, что с помощью
двоичного кода можно представить любую информацию.

· На
компьютере любая информация хранится в виде двоичных кодов.

Вопросы:

· Алфавитный
подход к измерению информации.

· Информационный
вес символа.

· Информационный
объём сообщения.

· Единицы
измеряется информации.

Как мы помним, информация
для человека – это набор сигналов, которые человек получает из различных
источников. Человек, каким-то образом их воспринимает и интерпретирует, придёт
им какое-то значение. Однако разные люди могут интерпретировать сигналы по-разному.
Так одно и то же сообщение, то есть один и тот же набор сигналов, может нести
разным людям совершенно разную информацию. Как же тогда можно измерить
информацию?

Всего существует два
подхода к измерению информации. Первый подход – содержательный. Как ясно
из названия, он оценивает содержание информации. А как же можно оценить
содержание информации? Универсально оценить содержание любой информацию
позволяют её свойства: объективность, достоверность полнота, актуальность,
полезность и понятность. Однако, часть свойств информации субъективна, то есть
для разных людей информация может быть по-разному полезна, понятна или
актуальна. Потому измерение информации с помощью этого подхода часто тоже
субъективно. Для того, чтобы объективно измерить информацию нельзя опираться на
её содержание.

Измерить информацию независимо
от её содержания позволяет алфавитный подход. Рассмотрим его подробнее.
Прежде чем что-нибудь выразить количественно, необходимо установить, для этого
единицу измерения. Так расстояние измеряется в метрах, а время в секундах. А в
чём же измеряется информация? В алфавитном подходе считается, что каждый символ
алфавита, который использован для записи информации, имеет некоторый
информационный вес. Это означает, что он несёт некоторое количество информации.
Все символы одного и того же алфавита имеют одинаковый информационный вес.
Информационный вес каждого из символов алфавита зависит от мощности этого
алфавита. Минимальная единица измерения информации – это информационный вес
одного символа двоичного алфавита. Эта величина получила название один бит.
Слово бит на английском языке (Bit)
произошло как результат сокращения словосочетания «Binary
digit», что в переводе
на русский язык, означает «двоичный символ».

Почему же именно один бит
был принят в качестве минимальной единицы измерения информации? Как мы помним
из прошлого урока, любую информацию можно записать в виде её двоичного кода, то
есть представить её как совокупность двоичных символов. В то же время меньшей
информационной единицы, чем один бит просто не существует. Наверняка у вас
возник вопрос, почему? Вспомним, чем является любой алфавит. Любой алфавит –
это знаковая система. А какая знаковая система минимальна? Сколько символов она
содержит? 2. Так как 1 символ, вне знаковой системы не может нести информацию.
То есть двоичный алфавит – это минимальная знаковая система.

Раньше мы узнали, что
алфавит любого языка, естественного или формального можно заменить двоичным
алфавитом. Для этого всем символам алфавита можно присвоить уникальные двоичные
коды одинаковой разрядности. Причём минимальная разрядность двоичного кода, необходимая,
для кодирования одного символа алфавита,
зависит от мощности кодируемого алфавита. Запишем выражение для этой
зависимости. Мощность алфавита обозначим латинской буквой «М», а минимальную
необходимую разрядность двоичного кода – буквой «i».
Тогда M = 2ⁱ,
или перемноженной последовательности из i
двоек. При этом, если мощность алфавита нельзя получить простым перемножением
двоек, то она увеличивается до числа, которое можно получить таким образом. Это
делается потому, что иначе двоичный код с меньшей разрядностью не сможет
уникальным образом закодировать все символы алфавита.

Информационным весом
символа называется, количество информации, которое он несёт в
рамках своего алфавита. Она равна минимальной разрядности двоичного кода,
необходимой для равномерного кодирования алфавита этого символа. Информационный
вес символа, как и любая информация измеряется в битах.

Задача: алфавит
русского языка содержит:

·
тридцать
три буквы,

·
десять
арабских цифр,

·
одиннадцать
знаков препинания,

·
и
пробел.

Вычислить информационный
вес одного символа из алфавита русского языка.

В начале нужно найти
мощность русскоязычного алфавита M.
Для этого посчитаем общее число всех символов: букв – 33, количество цифр – 10,
количество знаков препинания – 11 и добавим ещё 1, то есть пробел. M
= 33 + 10 + 11+ 1 = 55. Общая мощность русского алфавита равна 55 символам.
Теперь найдём, какая разрядность двоичного кода потребуется, чтобы закодировать
1 символ алфавита мощностью 55 символов. Информационный вес символа будет равен
этой разрядности. То есть M
= 55 = 2ⁱ. Число 55 мы не можем
получить простым перемножением двоек. Поэтому увеличим число до 64-х. Для того,
чтобы получить 64, нужно перемножить 6 двоек или 2⁶. i
= 6. Мы можем дать ответ: информационный вес одного символа русского алфавита –
6 бит.

Таким образом мы
научились измерять информацию, которую несёт 1 символ алфавита. Однако в
действительности информация передаётся целыми сообщениями, которые складываются
из множества символов. Как же измерить такую информацию? Размер информации,
которую несёт сообщение, называется его информационным объёмом. Он
складывается из информационных весов всех символов, из которых состоит
сообщение. Его можно рассчитать следующим образом… Обозначим информационный
объём сообщения латинской буквой «V»,
а латинской буквой «L» — длину сообщения, в
символах. Так V = i
× L. То есть информационный
объём равен произведению информационного веса одного символа и количества
символов в сообщении.

Задача: сообщение
содержит 296 бит информации. Его длина – 37 символов. Какова максимальная
мощность алфавита, с помощью символов которого записано это сообщение?

Так как мы знаем
информационный объём сообщения и его длину – мы можем найти информационный вес
одного его символа. Информационный вес символа равен информационному объёму
сообщения делённому на длину сообщения, i
= V / L.
296 / 37 = 8 бит. Информационный вес одного символа нашего алфавита – восемь
бит. Так как мы знаем информационный вес каждого символа алфавита, то есть
разрядность двоичного кода символа такого алфавита, мы можем найти его
максимальную мощность. Максимальная мощность равна двум в степени
информационного веса символа. M
= 2ⁱ = 2⁸ = 256.
Мы можем дать ответ: максимальная мощность алфавита – 256 символов.

Итак, минимальная единица
измерения информации один бит, и мы можем выразить с помощью этой величины
любой объём информации, но всегда ли это удобно? Ведь текст на компьютере может
содержать десятки и даже сотни тысяч символов, а звуки и изображения
представляются миллиардами символов двоичного кода. Для удобства измерения
такой информации были введены и более крупные единицы.

Первая из них – байт,
рассмотрим, как же он появился и чему равен. В самом начале большая
часть информации на компьютерах была текстовой. Для набора информации
использовалось несколько алфавитов, или кодировок. Большинство из них содержало
по 256 символов. Это означает что информационный вес одного символа в таком
алфавите был 8 бит. Так же именно 8 бит информации могли одновременно
обрабатывать процессоры того времени. Эта величина и была названа байтом.

Так же существуют и ещё
более крупные единицы информации, например килобайты (Кб). Некоторые из вас
могут подумать, что в 1 килобайте 1000 байт, так же как в 1 килограмме – 1000
грамм. Однако это не верно. Для более удобного измерения информации на
компьютере 1 килобайт содержит не 1000, а 1024 байта. Почему именно 1024?
Потому, что 1024 = 2¹⁰. Есть и ещё более крупные величины. Так один
мегабайт (Мб) содержит 1024 Кб. Ещё десять лет назад информация, содержащаяся на
компьютере, измерялась в гигабайтах. Один гигабайт (Гб) содержит 1024 Мб. Сейчас
на одном домашнем компьютере могут храниться терабайты (Тб) информации, и в 1 Тб
– сколько, как вы думаете? – Правильно: 1024 Гб.

Задача:
на заводе работает автоматическая система учёта рабочего времени. По приходу на
работу, и при уходе с работы сотрудник вставляет свою карту-пропуск в
специальное устройство и оно заносит в память сообщение, которое состоит из 2
частей: уникального двоичного кода сотрудника и текущего времени. Найти
минимальный информационный объём, который устройство внесло
в память за день, если известно, что:

· всего
на заводе работает 714 сотрудников;

· на
работу вышло 698 сотрудников;

· часть
сообщения, которая содержит текущее время, имеет информационный объём 3 байта;

· все
уникальные двоичные коды сотрудников имеют одинаковую разрядность.

Итак, минимальный
информационный объём – V_общ.,
который устройство занесло в память в течение дня можно найти, умножив
информационный объём одного сообщения V_сообщ.
на количество сообщений N_сообщ.
Количество сообщений N_сообщ.
равно количеству сотрудников N_сотр.,
которые вышли на работу в течение дня, умноженному на 2, так как на каждого
сотрудника приходится 2 сообщения: одно – когда он приходит на работу, а второе
– когда уходит. N_сообщ.
= N_сотр.
× 2 = 1396 сообщений за день.

Информационный объём
одного сообщения состоит из информационного объёма уникального двоичного кода
сотрудника V_кода и
информационного объёма времени, который равен 3 байтам. Теперь нам нужно найти
информационный объём уникального двоичного кода сотрудника. Мы можем
представить всех сотрудников, которые работают на заводе, в качестве алфавита
мощностью 714 символов. Нам остаётся найти информационный вес одного символа.

Как мы помним это можно
сделать по формуле M=2ⁱ.
Мы не можем получить 714 путём перемножения двоек, зато мы можем так получить
число 1024. 1024 = 2¹⁰. Значит информационный объём V_кода
= 10 бит. Теперь найдём информационный объём V_сообщ.
он состоит из 10 бит уникального двоичного кода и 3 байт времени. Переведём 3
байта в биты, для этого умножим число 3 на 8. 3 × 8 = 24 бита и 10 бит
кода. Информационный объём одного сообщения V_сообщ. =
24 + 10 = 34 бита. Теперь остаётся лишь найти информационный объём V_общ.
Для этого информационный объём одного сообщения V_сообщ.
умножим на количество сообщений N_сообщ.
34 × 1396 = 47 464 бита. Для удобства переведём в более крупные величины.
47 464 / 8 = 5933 байта, 5933 / 1024 = 5,8 Кб. Ответ: За день в память
устройства поступило 5,8 Кб информации.

Важно запомнить:

· Алфавитный
подход позволяет измерить объём информации не зависимо от её
содержания. При этом каждый символ несёт, некоторое количество информации, имеет
информационный вес (i).

· Минимальная
единица измерения информации – 1 бит.

· Мощность
алфавита равна двум в степени, равной информационному весу
символа (M = 2ⁱ).

· Информационный
объём сообщения равен произведению информационного веса
одного символа и длины сообщения (V
= i × L).

· 1
байт
= 8 бит.

· Байты,
килобайты (Кб), мегабайты (Мб), гигабайты (Гб), терабайты (Тб)
– единицы измерения информация. Каждая следующая больше предыдущей в 1024 раза.

Источник