Программирование (комбинаторика)

1.

Задание №8
Программирование
(комбинаторика)

2.

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

3.

Решение задачи (вручную)
Ж * 2 * 2 *2 *2 = 16
2 * Ж * 2 * 2 *2 = 16
2 * 2 * Ж * 2 * 2 = 16
2 * 2 * 2 * Ж * 2 = 16
2 * 2 * 2 *2 * Ж = 16
Ответ: 80

4.

Решение с помощью программы
from itertools import product
k=0
for i in product("ЖИР", repeat=5):
s=''.join(i)
if s.count('Ж')==1:
k=k+1
print(k)

5.

Задача 2
Вася составляет 6-буквенные слова, в которых
могут быть использованы только буквы В, И,
Ш, Н, Я. Причём буква В используется не более
одного раза. Каждая из других допустимых букв
может встречаться в слове любое количество раз
или не встречаться совсем. Слово не должно
начинаться с буквы Ш и не должно
оканчиваться гласными буквами. Словом
считается любая допустимая последовательность
букв, не обязательно осмысленная. Сколько
существует таких слов, которые может написать
Вася?

6.

Решение задачи (вручную)
Буква В встречается только 0 раз
3 *4 *4 * 4 *4 *2= 6 * 44
Буква В встречается только 1 раз
В * 4 * 4 * 4 *4 *2 = 2 * 44
3 * В * 4 * 4 * 4 * 2=6 * 43
3 * 4 * В * 4 * 4 * 2= 6 * 43
3 * 4 * 4 * В * 4 * 2=6 * 43
3 * 4 * 4 * 4 * В * 2=6 * 43
3 *4 * 4 *4 * 4 *В =3 * 44
44 * (6+2+6+3)= 256 * 17 = 4352
Ответ: 4352
6 * 43 * 4=6*44

7.

Решение с помощью программы
1 вариант
from itertools import product
k=0
for i in product('ВИШНЯ',repeat=6):
s=''.join(i)
if s.count('В')<=1 and s[0] !='Ш' and s[5] !='И'and s[5] !='Я':
k=k+1
print(k)

8.

Решение с помощью программы
2 вариант
alf=['В', 'И','Ш','Н','Я']
k=0
for a1 in alf:
for a2 in alf:
for a3 in alf:
for a4 in alf:
for a5 in alf:
for a6 in alf:
word=a1+a2+a3+a4+a5+a6
if word.count('В')<=1 and word[0] !='Ш' and
word[5] !='И' and word[5] !='Я':
k=k+1
print(k)

9.

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

10.

Решение задачи (вручную)
1. Найдём все возможные комбинации
4*4 *4 *4 * 4=1024
2. Найдем исключения:
K*K*K*K*K =1 (буква К встречается 5 раз)
3 * 3 * 3 * 3 * 3 = 243 (буква К совсем не встречается)
Рассмотрим варианты, где К встречается 4 раза:
К* К*К*К*3=3
К* К*К*3*К=3
К* К*З*К*К=3
К* 3*К*К*К=3
3* К*К*К*К=3
Всего 15 слов
3. Итак: 1024-1-243-15 = 765
Ответ: 765

11.

Решение с помощью программы
from itertools import product
k=0
for i in product("ДОКА", repeat=5):
s=''.join(i)
if s.count('К')<=3 and s.count('К')>0:
k=k+1
print(k)

12.

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

13.

Решение с помощью программы
from itertools import product
k=0
for i in product("ЧЕТО", repeat=6):
s=''.join(i)
if s.count('Е')>=1:
k=k+1
print(k)
Ответ: 3367

14.

Задача 5
Маша составляет 6-буквенные коды из букв
РУЛЬКА. Каждую букву нужно использовать
ровно 1 раз, при этом буква Л не может
стоять на первом месте. Сколько различных
кодов может составить Маша?

15.

Решение с помощью программы
from itertools import permutations
k=0
for i in permutations("РУЛЬКА",6):
s=''.join(i)
if s[0] !='Л':
k=k+1
print(k)
Ответ: 600

16.

Задача 6

17.

Решение с помощью программы
from itertools import permutations
k=0
for i in permutations("ЗЛОЙ"):
s=''.join(i)
if s[0] !='Й' and "ОЙ" not in s:
k=k+1
print(k)
Ответ:12

18.

Задача 7
Миша составляет 6-буквенные коды из букв
С, А, Л, Ь, С, А. Каждая допустимая гласная
буква может входить в код не более одного
раза. Сколько кодов может составить Миша?

19.

Решение с помощью программы
alf=['С', 'А','Л','Ь']
k=0
for a1 in alf:
for a2 in alf:
for a3 in alf:
for a4 in alf:
for a5 in alf:
for a6 in alf:
word=a1+a2+a3+a4+a5+a6
if word.count('А')<=1:
k=k+1
print(k)
Ответ: 2187

20.

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

21.

Решение с помощью программы
ch=['0', '2','4','6','8']
nch=['1', '3','5','7','9']
k=0
for a1 in ch:
for a2 in nch:
for a3 in ch:
for a4 in nch:
for a5 in ch:
for a6 in nch:
word=a1+a2+a3+a4+a5+a6
if
word[0]>word[1]>word[2]>word[3]>word[4]>word[5]:
k=k+1

22.

Продолжение задачи 8
for a1 in nch:
for a2 in ch:
for a3 in nch:
for a4 in ch:
for a5 in nch:
for a6 in ch:
word=a1+a2+a3+a4+a5+a6
if word[0]>word[1]>word[2]>word[3]>word[4]>word[5]:
k=k+1
print(k)
Ответ: 35

23.

Задача 9

24.

Решение с помощью программы
alf = ['М', 'Е', 'Ч', 'Т', 'А']
k=0
for a1 in alf:
for a2 in alf:
for a3 in alf:
for a4 in alf:
for a5 in alf:
for a6 in alf:
word = a1 + a2 + a3 + a4 + a5 + a6
if word.count('А') >= 3:
k=k+1
print(k)
Ответ: 1545