Задание 8 номер 10476 информатика

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

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

— базовый,

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

— нет,

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

— 1,

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

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

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

N = 2^L

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

Ответ: 4

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

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

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

26

*

26

*

26

= 17576

Ответ: 17576

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

два раза буква А, на остальных местах - одна из трех оставшихся букв:
А А 3 3     = 3 * 3 = 32 = 9
А 3 А 3     = 9
А 3 3 А     = 9 
3 А А 3     = 9
3 А 3 А     = 9
3 3 А А     = 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 * 9 = 54

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

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

8_1: ЕГЭ по информатике 2017 задание 8 (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 = 54 = 625

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

1 5 5 5 5 - 1 * Q=54 = 625
5 1 5 5 5 - 1 * Q=54 = 625
5 5 1 5 5 - 1 * Q=54 = 625
5 5 5 1 5 - 1 * Q=54 = 625
5 5 5 5 1 - 1 * Q=54 = 625

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

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

625 * 5 = 3125

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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.

1
2
3
4

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

1
2
3
4
5
6
7
8
9
10

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_2: ЕГЭ по информатике 2017 задание 8 (10) ФИПИ вариант 10 (Крылов С.С., Чуркина Т.Е.):

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

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

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

Q = N^L

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

Q = 2 * 34 = 162

AB  123 123 123 123 = 162

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

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

5 * 162 = 810

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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.

1
2
3
4

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

1
2
3
4
5
6
7
8
9
10
11

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)

8_3: Разбор 8 (10) задания ЕГЭ по информатике (К. Поляков, задание 69):

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

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

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

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

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

Г ? ? ? = 1 * 5 * 5 * 5 = 53 = 125 
? ? ? Г = 5 * 5 * 5 * 1 = 53 = 125

125 + 125 = 250

Результат: 250

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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.

1
2
3
4

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

1
2
3
4
5
6
7
8
9
10

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)

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

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

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

Q = N^L

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

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

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

X X ? ? ? -> 12 * Q = 23 = 8

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

X X ? ? ? - 12 * Q = 23 = 8
X ? X ? ? - 12 * Q = 23 = 8
X ? ? X ? - 12 * Q = 23 = 8
X ? ? ? X - 12 * Q = 23 = 8
? X X ? ? - 12 * Q = 23 = 8
? X ? X ? - 12 * Q = 23 = 8
? X ? ? X - 12 * Q = 23 = 8
? ? X X ? - 12 * Q = 23 = 8
? ? X ? X - 12 * Q = 23 = 8
? ? ? X X - 12 * Q = 23 = 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

8 * 10 = 80

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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.

1
2
3
4

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

1
2
3
4
5
6
7
8
9
10

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_5: Разбор 8 (10) задания Тренировочный вариант №1 2018 (от 03.09.2018):

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

2   5   5   5   2
СН   все  все  все   ОЕ

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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.

1

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

1
2
3
4
5
6
7
8
9
10
11

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

8_6: Разбор 8 (10) задания ЕГЭ по информатике (К. Поляков, задание 42):

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

✎ Решение теоретическое:
✎ 1 способ:
• Количество вариантов различных слов вычислим по формуле:

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

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

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

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

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

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

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

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

? ? ? Е = 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

256 - 81 = 175

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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.

1
2

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

1
2
3
4
5
6
7
8
9

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_7: Разбор 8 задания ЕГЭ по информатике (К. Поляков, задание 50):

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

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

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

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

5 * 5 * 5 * 5 = 54 = 625

4 * 4 * 4 * 4 = 44 = 256

р ? ? ? = 1 * 4 * 4 * 4 = 43
? р ? ? = 4 * 1 * 4 * 4 = 43
? ? р ? = 4 * 4 * 1 * 4 = 43
? ? ? р = 4 * 4 * 4 * 1 = 43

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

625 - 256 - 256 = 113

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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.

1
2
3
4
5
6
7
8
9

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_8: Разбор 8 задания ЕГЭ по информатике (К. Поляков, задание 70):

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

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

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

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

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

1 раз: ? ? ? ? Г = 3 * 3 * 3 * 3 * 1 = 34 = 81 
0 раз: ? ? ? ? ? = 3 * 3 * 3 * 3 * 3 = 35 = 243

81 + 243 = 324

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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.

1
2
3
4

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

Результат: 324

8_9: Разбор 8 задания ЕГЭ по информатике (К. Поляков, задание 52):

Вася составляет 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 = 16 вариантов

А А _ _  -> 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

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

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

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

_ _ _ _ -> 44 = 256

16 + 96 + 256 + 256 = 624

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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.

1
2
3

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

1
2
3
4
5
6
7
8
9
10

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

8_10: Разбор 8 задания ЕГЭ по информатике (К. Поляков, задание 32):

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

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

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

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

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

Начинаем с A: A D 4ABCD = 1 * 1 * 4 = 4 
Начинаем с B: B A D, B B 2BD, B D 4ABCD = 7
Начинаем с C: C A D, C C 2CD, C D 4ABCD = 7
Начинаем с D: D A 3BCD, D B 2BD, D C 2CD, D D 4ABCD = 11

4 + 7 + 7 + 11 = 29

Результат: 29

8_11: Разбор 8 задания Тренировочный вариант №3 2018 (от 01.10.2018):

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

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

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

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

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

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

1
2
3
4
5
6

### 
'среда'.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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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.

1
2
3
4
5
6
7
8
9
10
11
12

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

8_12: Решение 8 задания (К. Поляков, задание 76):

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

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

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

3 * 4 * 2 * 3 * 1 = 72

Результат: 72

8_21: Решение 8 задания (К. Поляков, задание 210):

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

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

PascalABC.net (приближенный к традиционному, долгое решение): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 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, быстрое решение): 1 2 3 4 5 ### 'МИМИКРИЯ'.Permutations // перестановки букв .Select(w->w.JoinToString('')) // собираем в строку .Distinct // выбираем уникальные .Count.Print * LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

С++:

Ответ: 3360

8_19: Решение 8 задания (К. Поляков, задание 116):

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

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

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

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

10 * 24 = 240

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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.

Ответ: 240

8_20: Разбор 8 задания (К. Поляков, задание 112):

Маша составляет 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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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.

Ответ: 4080

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

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

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

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

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

1
2
3
4
5

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

Ответ: 1008

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

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

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

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

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

1. 00000
2. 00001
3. 00002
4. 00010
...

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

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

1
2
3
4

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

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

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

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

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

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

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

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

1. 0000
2. 0001
3. 0002
4. 0003
5. 0004
6. 0010
...

K -> 2 -> 2000

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

20005 = 2 * 53 + 0 * 22 + 0 + 0 = 2 * 125 = 25010 

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

1
2
3
4
5
6

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

Результат: 251

8_15: Решение 8 задания ЕГЭ по информатике 2018 (контрольный вариант № 2 экзаменационной работы 2018 года, С.С. Крылов, Д.М. Ушаков, Тренажер ЕГЭ):

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

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

8_16: Разбор 8 задания (К. Поляков, задание 80):

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

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

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

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

1. 0000
2. 0001
3. 0002
4. 0003
5. 0004
6. 0010

11115 = 1 * 53 + 1 * 52 + 1 * 51 + 1 * 50 = 156
156 + 1 = 157

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

1
2
3
4
5
6
7

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

Результат: 157

8_17: Решение 8 задания ЕГЭ по информатике (сайт «Решу ЕГЭ», задание № 4795):

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

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

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

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

x = log₂(1/p)

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

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

p(A) = m/n

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

2 = log2(1/p);
    => 
1/p = 4; 
    =>
p = 1/4

p = ?/20

1/4 = ?/20

? = 1/4 * 20 = 5

Результат: 5