Задание 8

В задачах этого типа необходимо посчитать, сколько кодов, удовлетворяющих тому или иному условию из заданного набора символов можно составить. Проще всего решать их с помощью программирования.

Пример 1

Задача

Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово.

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

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

Для решения этой задачи необходимо просто создать список букв, и перебрать все тройки из него. Если среди этой тройки ровно одна буква 'K', тогда увеличим счётчик подходящих комбинаций на 1.

Java

public class Example1 {

    // главный метод программы
    public static void main(String[] args) {
        // множество, из которого берутся буквы
        char[] source = new char[]{'Ш', 'К', 'О', 'Л', 'А'};
        // счётчик подходящих кодов на 1
        int r = 0;
        // перебираем буквы на первой позиции
        for (char c1 : source) {
            // перебираем буквы на второй позиции
            for (char c2 : source) {
                // перебираем букв на третьей позиции
                for (char c3 : source) {
                    // кол-во букв К среди них изначально равно нулю
                    int kCnt = 0;
                    // если первая буква - К
                    if (c1 == 'К')
                        // увеличиваем кол-во на 1
                        kCnt++;
                    // если вторая буква - К
                    if (c2 == 'К')
                        // увеличиваем кол-во на 1
                        kCnt++;
                    // если третья буква - К
                    if (c3 == 'К')
                        // увеличиваем кол-во на 1
                        kCnt++;
                    // если букв К ровно 1
                    if (kCnt == 1)
                        // увеличиваем счётчик подходящих кодов на 1
                        r++;
                }
            }
        }
        // выводим кол-во подходящих кодов
        System.out.println(r);
    }
}

C++

#include <iostream>

int main() {
    // множество, из которого берутся буквы
    char source[] = {'S', 'K', 'O', 'L', 'A'};
    // счётчик подходящих кодов на 1
    int r = 0;
    // перебираем буквы на первой позиции
    for (char c1: source) {
        // перебираем буквы на второй позиции
        for (char c2: source) {
            // перебираем букв на третьей позиции
            for (char c3: source) {
                // кол-во букв К среди них изначально равно нулю
                int kCnt = 0;
                // если первая буква - К
                if (c1 == 'K')
                    // увеличиваем кол-во на 1
                    kCnt++;
                // если вторая буква - К
                if (c2 == 'K')
                    // увеличиваем кол-во на 1
                    kCnt++;
                // если третья буква - К
                if (c3 == 'K')
                    // увеличиваем кол-во на 1
                    kCnt++;
                // если букв К ровно 1
                if (kCnt == 1)
                    // увеличиваем счётчик подходящих кодов на 1
                    r++;
            }
        }
    }
    // выводим кол-во подходящих кодов
    std::cout << r;
    return 0;
}

Python

# множество, из которого берутся буквы
source = ['Ш', 'К', 'О', 'Л', 'А']
# счётчик подходящих кодов на 1
r = 0
# перебираем буквы на первой позиции
for c1 in source:
    # перебираем буквы на второй позиции
    for c2 in source:
        # перебираем букв на третьей позиции
        for c3 in source:
            # кол-во букв К среди них изначально равно нулю
            kCnt = 0
            # если первая буква - К
            if c1 == 'К':
                # увеличиваем кол-во на 1
                kCnt = kCnt + 1
            # если вторая буква - К
            if c2 == 'К':
                # увеличиваем кол-во на 1
                kCnt = kCnt + 1
            # если третья буква - К
            if c3 == 'К':
                # увеличиваем кол-во на 1
                kCnt = kCnt + 1
            # если букв К ровно 1
            if kCnt == 1:
                # увеличиваем счётчик подходящих кодов на 1
                r = r + 1

# выводим кол-во подходящих кодов
print(r)

Вывод программы:

48

Ответ: 48

В циклах используется конструкция for...each. Она подставляет в переменную, указанную до двоеточия, каждое из значений перебираемой структуры и запускает для него тело цикла.

В С++ придётся поменять русские буквы на латинскую транскрипцию, т.е. каждую букву заменить её английским аналогом.

Не пишите так

Условия разнесены специально.

Java

    // если первая буква, вторая или третья - К
    if (c1 == 'К' || c2 == 'К' || c3 == 'К')
        // увеличиваем кол-во на 1
        kCnt++;

C++

    // если первая буква, вторая или третья - К
    if (c1 == 'К' || c2 == 'К' || c3 == 'К')
        // увеличиваем кол-во на 1
        kCnt++;

Python

    # если первая буква, вторая или третья - К
    if c1 == 'К' or c2 == 'К' or c3 == 'К':
        // увеличиваем кол-во на 1
        kCnt = kCnt + 1;

Если их объединить, тогда увеличение счётчика букв К будет для каждой комбинации не больше одного раза. Тогда посчитаются и те, комбинации, в которых две или три таких буквы.

Пример 2

Задача

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

Эту задачу проще всего решается с помощью перестановок. Их код рассмотрен в первом задании.

Чтобы сохранить все уникальные комбинации, нам понадобится множество.

Java

import java.util.HashSet;

public class Example2 {

    // множество кодов, сделано специально статическим, чтобы
    // сначала получить все перестановки, добавить их в множество,
    // а потом в main() просто выведем его размер
    static HashSet<String> set = new HashSet<>();

    // обработка перестановки
    static void processPermutation(char[] arr) {
        // кол-во повторяющихся символов
        int c = 0;
        // строка с кодом
        String s = "";
        for (int i = 0; i< arr.length - 1; i++) {
            // если текущий символ равен предыдущему
            if (arr[i] == arr[i + 1])
                // увеличиваем кол-во повторяющихся функций
                c++;
            // прибавляем текущий символ к строке
            s += arr[i];
        }
        // добавляем последний символ к строке
        s += arr[arr.length - 1];
        // если повторяющихся символов в строке нет
        if (c == 0)
            // добавляем её в множество
            set.add(s);
    }

    // поменять местами элементы массива arr с индексами l и r
    public static void swap(char[] arr, int l, int r) {
        char tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }

    // функция-генератор перестановок
    static void permute(char[] p, int pos) {
        // Если мы дошли до последнего элемента
        if (pos == p.length - 1) {
            processPermutation(p);
        } else { // иначе
            // Перебираем все оставшиеся элементы
            for (int i = pos; i < p.length; i++) {
                // меняем местами текущий элемент и перебираемый
                swap(p, pos, i);
                // Вызываем Рекурсию для следующего элемента
                permute(p, pos + 1);
                // меняем местами обратно
                swap(p, pos, i);
            }
        }
    }

    // главный метод программы
    public static void main(String[] args) {
        // запускаем генерацию перестановок
        permute(new char[]{'К', 'А', 'П', 'К', 'А', 'Н'}, 0);
        // выводим размер множества
        System.out.println(set.size());
    }
}

C++

#include <iostream>
#include <bits/stdc++.h>

// множество значений
std::set<std::string> values;

// обработка перестановки
void processPermutation(std::vector<char> arr) {
    // кол-во повторяющихся символов
    int c = 0;
    // строка с кодом
    std::string s;
    for (int i = 0; i < arr.size() - 1; i++) {
        // если текущий символ равен предыдущему
        if (arr[i] == arr[i + 1])
            // увеличиваем кол-во повторяющихся функций
            c++;
        // прибавляем текущий символ к строке
        s += arr[i];
    }
    // добавляем последний символ к строке
    s += arr[arr.size() - 1];
    // если повторяющихся символов в строке нет
    if (c == 0) {
        // добавляем её в множество
        values.insert(s);
    }
}


// главный метод программы
int main() {
    std::vector<char> origin = {'K', 'A', 'P', 'K', 'A', 'N'};
    // ОБЯЗАТЕЛЬНО ОТСОРТИРУЙТЕ ВЕКТОР! иначе перестановки 
    // будут работать неправильно
    std::sort(origin.begin(), origin.end());
    // перебираем перестановки
    do {
        processPermutation(origin);
    } while (std::next_permutation(origin.begin(), origin.end()));
    // выводим размер множества
    std::cout << values.size() << std::endl;

    return 0;
}

Python

import itertools

# множество кодов
values = set()


# обработка перестановки
def process_permutation(arr):
    # кол-во повторяющихся символов
    c = 0
    # строка с кодом
    s = ""
    for i in range(len(arr) - 1):
        # если текущий символ равен предыдущему
        if arr[i] == arr[i + 1]:
            # увеличиваем кол-во повторяющихся функций
            c = c + 1
        # прибавляем текущий символ к строке
        s += arr[i]

        # добавляем последний символ к строке
    s += arr[len(arr) - 1]
    # если повторяющихся символов в строке нет
    if c == 0:
        # добавляем её в множество
        values.add(s)


# получаем перестановки
permutations = list(itertools.permutations(['К', 'А', 'П', 'К', 'А', 'Н']))
# перебираем их
for permutation in permutations:
    process_permutation(permutation)

# выводим размер множества
print(len(values))

Получим

84

Ответ: 84

В Java множество создаётся с помощью конструкции

    HashSet<Integer> values = new HashSet<>();

Обратите внимание: в угловых скобках нужно писать именно тип данных с большой буквы.

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

Integer	Double	Long	Boolean	Character	Byte	Float
int	double	long	boolean	char	byte	float

Чтобы добавить элемент a=10 в множество s, необходимо вызвать метод s.add().

Чтобы перебрать элементы множества, используется модификация цикла for. Она называется for each - для каждого.

Общая идея этой конструкции заключается в том, что в переменную, объявленную до : помещаются по очереди все значения перебираемой структуры и для каждого значения выполняется тело цикла. В нашем случае каждый элемент множества выводится на экран.

В C++ множество создаётся с помощью команды

    std::set<int> values;

В угловых скобках указывается тип элементов множества. Чтобы добавить элемент, используется команда .insert. Перебор выполняется с помощью конструкции for...each.

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

В Python множество создаётся с помощью команды

values = set()

Чтобы добавить элемент, используется команда .add()

Пример 3

Задача

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

Если каждую букву можно использовать только один раз, значит, речь идёт о перестановках. Задача решается примерно так же, как и предыдущая, правда, необходимо поменять критерий добавления в множество.

Java

import java.util.HashSet;

public class Example3 {

    // множество кодов, сделано специально статическим, чтобы
    // сначала получить все перестановки, добавить их в множество,
    // а потом в main() просто выведем его размер
    static HashSet<String> set = new HashSet<>();

    // обработка перестановки
    static void processPermutation(char[] arr) {
        // переменная, которая отвечает на вопрос, подходит ли нам текущая комбинация
        // изначально кладём в неё ответ, правда ли, что первый символ - не 'Ь'
        boolean f = arr[0] != 'Ь';
        // строка с кодом
        String s = "";
        for (int i = 0; i < arr.length - 1; i++) {
            // если текущий символ - 'Ь', а следующий - гласная
            if (arr[i] == 'Ь' && (arr[i + 1] == 'А' || arr[i + 1] == 'У'))
                // тогда комбинация нам не подходит
                f = false;
            // прибавляем текущий символ к строке
            s += arr[i];
        }
        // добавляем последний символ к строке
        s += arr[arr.length - 1];
        // если повторяющихся символов в строке нет
        if (f) {
            // добавляем её в множество
            set.add(s);
        }
    }

    // поменять местами элементы массива arr с индексами l и r
    public static void swap(char[] arr, int l, int r) {
        char tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }


    // функция-генератор перестановок
    static void permute(char[] p, int pos) {
        // Если мы дошли до последнего элемента
        if (pos == p.length - 1) {
            processPermutation(p);
        } else { // иначе
            // Перебираем все оставшиеся элементы
            for (int i = pos; i < p.length; i++) {
                // меняем местами текущий элемент и перебираемый
                swap(p, pos, i);
                // Вызываем Рекурсию для следующего элемента
                permute(p, pos + 1);
                // меняем местами обратно
                swap(p, pos, i);
            }
        }
    }

    // главный метод программы
    public static void main(String[] args) {
        // запускаем генерацию перестановок
        permute(new char[]{'В', 'У', 'А', 'Л', 'Ь'}, 0);
        // выводим размер множества
        System.out.println(set.size());
    }
}

C++

#include <iostream>
#include <bits/stdc++.h>

// множество значений
std::set<std::string> values;

// обработка перестановки
void processPermutation(std::vector<char> arr) {
    // переменная, которая отвечает на вопрос, подходит ли нам текущая комбинация
    // изначально кладём в неё ответ, правда ли, что первый символ - не 'Ь'
    bool f = arr[0] != '.';
    // строка с кодом
    std::string s;
    for (int i = 0; i < arr.size() - 1; i++) {
        // если текущий символ - 'Ь', а следующий - гласная
        if (arr[i] == '.' && (arr[i + 1] == 'A' || arr[i + 1] == 'U'))
            // тогда комбинация нам не подходит
            f = false;
        // прибавляем текущий символ к строке
        s += arr[i];
    }
    // добавляем последний символ к строке
    s += arr[arr.size() - 1];
    // если повторяющихся символов в строке нет
    if (f) {
        // добавляем её в множество
        values.insert(s);
    }
}

// главный метод программы
int main() {
    std::vector<char> origin = {'V', 'U', 'A', 'L', '.'};
    // ОБЯЗАТЕЛЬНО ОТСОРТИРУЙТЕ ВЕКТОР! иначе перестановки
    // будут работать неправильно
    std::sort(origin.begin(), origin.end());
    // перебираем перестановки
    do {
        processPermutation(origin);
    } while (std::next_permutation(origin.begin(), origin.end()));
    // выводим размер множества
    std::cout << values.size() << std::endl;

    return 0;
}

Python

import itertools

# множество кодов
values = set()


# обработка перестановки
def process_permutation(arr):
    # переменная, которая отвечает на вопрос, подходит ли нам текущая комбинация
    # изначально кладём в неё ответ, правда ли, что первый символ - не 'Ь'
    f = arr[0] != 'Ь'
    # строка с кодом
    s = ""
    for i in range(len(arr) - 1):
        # если текущий символ - 'Ь', а следующий - гласная
        if arr[i] == 'Ь' and (arr[i + 1] == 'А' or arr[i + 1] == 'У'):
            # тогда комбинация нам не подходит
            f = False
        # прибавляем текущий символ к строке
        s += arr[i]

        # добавляем последний символ к строке
    s += arr[len(arr) - 1]
    # если повторяющихся символов в строке нет
    if f:
        # добавляем её в множество
        values.add(s)


# получаем перестановки
permutations = list(itertools.permutations(['В', 'У', 'А', 'Л', 'Ь']))
# перебираем их
for permutation in permutations:
    process_permutation(permutation)

# выводим размер множества
print(len(values))

Получим на выходе:

60

Ответ: 60

Пример 4

Задача

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

2. КККК

3. КККЛ

4. КККР

5. КККТ

   ...

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

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

Java

public class Example4 {

    // главный метод программы
    public static void main(String[] args) {
        // множество, из которого берутся буквы
        char[] source = new char[]{'К', 'Л', 'Р', 'Т'};
        // счётчик сформированных кодов
        int r = 0;
        // перебираем буквы на первой позиции
        for (char c1 : source) {
            // перебираем буквы на второй позиции
            for (char c2 : source) {
                // перебираем буквы на третьей позиции
                for (char c3 : source) {
                    // перебираем буквы на четвёртой позиции
                    for (char c4 : source) {
                        // т.к. позиции нумеруются с единицы, а начальное значение
                        // равно 0, то сначала увеличиваем на 1 счётчик,
                        // а потом сравниваем с заданным номером
                        r++;
                        // если счётчик равен заданному номеру строки
                        if (r == 67)
                            // выводим подряд перебираемые символы
                            // (символы необходимо складывать с пустыми строками,
                            // иначе java сложит их как целые числа)
                            System.out.println(c1 + "" + c2 + "" + c3 + "" + c4);
                    }
                }
            }
        }
    }
}

C++

#include <iostream>

int main() {
    // множество, из которого берутся буквы
    char source[] = {'K', 'L', 'R', 'T'};
    //  счётчик сформированных кодов
    int r = 0;
    // перебираем буквы на первой позиции
    for (char c1: source) {
        // перебираем буквы на второй позиции
        for (char c2: source) {
            // перебираем буквы на третьей позиции
            for (char c3: source) {
                // перебираем буквы на четвёртой позиции
                for (char c4 : source) {
                    // т.к. позиции нумеруются с единицы, а начальное значение
                    // равно 0, то сначала увеличиваем на 1 счётчик,
                    // а потом сравниваем с заданным номером
                    r++;
                    // если счётчик равен заданному номеру строки
                    if (r == 67)
                        // выводим подряд перебираемые символы
                        std::cout<<c1 <<c2 << c3 << c4;
                }
            }
        }
    }
    return 0;
}

Python

# множество, из которого берутся буквы
source = ['К', 'Л', 'Р', 'Т']
# счётчик сформированных кодов
r = 0
# перебираем буквы на первой позиции
for c1 in source:
    # перебираем буквы на второй позиции
    for c2 in source:
        # перебираем буквы на третьей позиции
        for c3 in source:
            # перебираем буквы на четвёртой позиции
            for c4 in source:
                # т.к. позиции нумеруются с единицы, а начальное значение
                # равно 0, то сначала увеличиваем на 1 счётчик,
                # а потом сравниваем с заданным номером
                r = r + 1
                # если счётчик равен заданному номеру строки
                if r == 67:
                    # выводим подряд перебираемые символы
                    print(c1, c2, c3, c4)

На выходе получим:

ЛККР

Ответ: ЛККР

Задания для самостоятельного выполнения