Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:

. Помогите пожалуйста...буду очень благодарна!

И вот второе задание: КОМБИНАТОРНЫЕ АЛГОРИТМЫ

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

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

Рассмотрим различные типы вариантов заданий.
1. Разгадка числовых ребусов.
В числовых ребусах зашифровывают некоторое арифметическое действие, буквами обозначают цифры. Разным цифрам соответствуют разные буквы. Требуется разгадать, какая цифра скрывается за каждой буквой. Это возможно, если воспользоваться програм-мой генерации размещений без повторений.
Пример. ТОРГ ? Г = ГРОТ. Имеем 4 различных цифры: Т, О, Р, Г. Следовательно, необходимо сгенерировать 4-размещения из 10 (всего 10 цифр), т.е. массив а[1], … , а[4], удовлетворяющий следующим условиям:
1) а[1] ? 0, а[4] ? 0 – т.к. число не может начинаться с 0.
2) а[1]?1000 + а[2]?100 + а[3]?10 + а[4] = а[4]?1000 + а[3]?100 + а[2]?10 + а[1] – это за-пись зашифрованного действия.
В процессе генерации каждое полученное сочетание проверяют на выполнение перечисленных условий и отбирают подходящие. В общем случае решений может быть несколько. В данном примере ТОРГ = 1089 (1089?9 = 9801).
2. Генерация m-последовательностей 0 и 1.
Для решения можно использовать алгоритм генерации размещений с повторения-ми, где xi = 0 и yi = 1.
Однако если в условии задано ограничение на количество 0 или 1, то при таком подходе заведомо будут генерироваться лишние последовательности. В этом случае луч-ше использовать алгоритм генерации сочетаний без повторений для номеров мест, на ко-торые будут расставляться 0 или 1. При получении каждой сгенерированной комбинации номеров мест для 1 (0) в массиве С, нужно обнулить (заполнить 1) массив А требуемых m-последовательностей, а затем расставить в нём на места из массива С единицы (нули).
3. Вычисление кратного интеграла.
Для приближенного вычисления кратного интеграла использовать формулу левых, средних или правых прямоугольников
,
где , k – кратность интеграла, h – шаг разбиения (вводится с клавиатуры), а для формулы левых прямоугольников, для формулы средних прямоугольников и для формулы правых прямоугольников. Для решения используется алгоритм генерации размещений с повторениями для номеров интервалов по каждой переменной.
4. Раскрытие полиномиальной формулы.
Для раскрытия полиномиальной формулы используется алгоритм генерации раз-мещений с повторениями для получения степеней разложения, в котором для каждой сге-нерированной комбинации проверяется условие . На экран монитора выводится формула разложения полинома с использованием знака ^ для операции возведения в сте-пень.
5. Использование принципа включений и исключений.
Для вычисления по формуле включений и исключений генерируются сочетания без повторений для номеров проверяемых свойств. Для каждого числа свойств генерируются различные сочетания, а для каждой сгенерированной комбинации вычисляется (или извлекается) и суммируется количество элементов, удовлетворяющих соответствующему свойству или набору свойств, затем вычисление суммы добавляются в формулу включений и исключений с нужным знаком.
6. Решение задачи коммивояжера.
Используется алгоритм генерации перестановок без повторений, в котором для ка-ждой комбинации вычисляется суммарное расстояние, пройденное коммивояжером, и определяется минимальное из этих расстояний.
7. Генерация числовых комбинаций.
Для генерации используется алгоритм генерации размещений с повторениями или без повторений (в зависимости от условия варианта). Каждая сгенерированная комбина-ция должна проверяться на выполнение условия и выводиться при выполнении условия.
Если требуется исключить заданные p цифр из набора, то нужно определить кон-стантный массив из 10 – p элементов, не включающий эти цифры, и генерировать номера элементов в этом массиве, а выводить сами цифры.
Если требуется включить заданные p цифр в число выводимых, то нужно записать эти цифры в результирующий массив сочетаний на первые p мест, определить констант-ный массив из 10 – p элементов, не включающий эти цифры. Затем сгенерировать номе-ра для k - p элементов в этом массиве, записать цифры с этими номерами в массив сочета-ний на места с p+1-го по k-е.
8. Генерация различных слов из заданного набора букв.
Для генерации используется алгоритм генерации размещений с повторениями или без повторений (в зависимости от условия варианта). Каждая сгенерированная комбина-ция должна проверяться на выполнение условия и выводиться при выполнении условия.