g30zAZLYUG

1.34. На данный момент в блоке else процедуры K производится печать сочетания с повторениями. Но мы должны распечатать не само сочетание с повторениями, а соответствующую ему композицию. В процедуре K блок else замените следующим фрагментом:

};

// Просмотр m-элементного массива myArray и модификация массива z for (j=1; j<=m; j++)

{

z[myArray[j]]++;

};

// Печать композиции for (j=1; j<=n; j++)

{

cout << z[j] << "\t";

};

cout << "\n";

}

Запустите программу на выполнение.

При n = 2, m = 3 (что соответствует разложению числа 3 в сумму двух целых неотрицательных чисел с фиксированным порядком слагаемых) у Вас должен получиться следующий результат:

Протестируйте программу с другими значениями n и m.

1.35. Обсудим проблему генерации тех композиций (z1, z2, …, zn) числа m, которые отвечают условию:

101

Введем новые переменные ri по правилу:

ri = zi 1, i = 1, 2, …, n.

Отсюда

zi = ri + 1, i = 1, 2, …, n.

Подставим эти значения в уравнение: z1 + z2 + …+ zn = m, получим

(r1 +1) + (r2 +1) + … + (rn +1) = m,

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

r1 + r2 + … + rn = m−n.

Значит, в новых переменных соответствующая композиция (r1, r2, …, rn) будет для числа m n.

Поскольку zi − число натуральное, то ri = zi 1 − число целое неотрицательное. Тем самым мы свели задачу к предыдущей, т.к. генерация целых неотрицательных слагаемых композиции (r1, r2, …, rn) разобрана выше.

Добавляя к каждому из найденных значений ri по единице (zi = ri + 1), получим слагаемые искомой композиции (z1, z2, …, zn).

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

1.36. Наконец, мы добрались до последнего раздела, в котором речь пойдёт о разбиениях натурального числа m.

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

z1 z2 … zn.

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

Сначала положим

sum = 0.

На k-м шаге:

sum = z1 + z2 +... + zk 1 .

Вектор-решение формируем до тех пор, пока sum < m.

Закройте файл lab_06 (если он был открыт). Откройте файл lab_06_SP. В нём содержится программа генерации сочетаний с повторениями. Сохраните этот файл под именем lab_06.

1.37. Закомментируйте (или удалите) ввод переменной n. Так как мы будем формировать все разбиения числа m, то она не понадобится.

102

1.38. Переименуйте процедуру SP в RBN и добавьте в описание процедуры ещё один параметр sum

в объявлении процедуры:

void RBN(int k, int previous, int sum)

в рекурсивном вызове:

RBN(k+1, myArray[k], sum+myArray[k]);

в первоначальном вызове:

RBN(1,1,0);

1.39. В процедуре RBN поменяйте условие цикла for:

for (i=previous; i<=m-sum; i++) // Цикл по всем допустимым значениям

Верхняя граница цикла − m-sum – не позволит нам «перешагнуть» через число m.

1.40. В процедуре RBN поменяйте условие продолжения рекурсивных вызовов:

1.43. В процедуре RBN в блоке else печати решения верхнюю границу n замените на k:

for (j=1; j<=k; j++)

Запустите программу на выполнение.

При m = 4 (что соответствует разложению числа 4 в сумму натуральных чисел с произвольным порядком слагаемых) у Вас должен получиться следующий результат:

Протестируйте программу с другими значениями m.

103

ЗАДАНИЕ № 1. Генерация комбинаторных объектов

Разработайте консольное приложение, в котором решается задача, представленная в Вашем варианте (см. ниже).

Работающую версию программы, а также программный код, предъявите преподавателю.

Вариант № 1. Разработать и отладить программу, по заданным значениям n и m генерирующую все перестановки с повторениями. Каждая комбинация должна состоять из элементов множества {1, 2, ..., n} и содержать m элементов (m n).

Для каждой комбинации подсчитать сумму S её повторяющихся элементов. Вывести все комбинации и соответствующие им суммы S в выходной текстовый файл.

Вариант № 2. Разработать и отладить программу, по заданным значениям n и m генерирующую все размещения. Каждая комбинация должна состоять из элементов множества {1, 2, ..., n} и содержать m элементов

(m n).

Для каждой комбинации подсчитать сумму S её четных элементов. Вывести все комбинации и соответствующие им суммы S в выходной текстовый файл.

Вариант № 3. Разработать и отладить программу, по заданным значениям n и m генерирующую все сочетания с повторениями. Каждая комбинация должна состоять из элементов множества {1, 2, ..., n} и содержать m элементов.

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

Вариант № 4. Разработать и отладить программу, генерирующую все разбиения натурального числа n.

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

Вариант № 5. Разработать и отладить программу, по заданным значениям n и m генерирующую все размещения с повторениями. Каждая комбинация должна состоять из элементов множества {1, 2, ..., n} и содержать m элементов.

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

104

Вариант № 6. Разработать и отладить программу, по заданным значениям n и m генерирующую все композиции (z1, z 2, …, z n) натурального числа m. Слагаемые композиции должны отвечать условию:

zi − число целое неотрицательное, т.е. zi N {0}; i = 1, 2, …, n.

Для каждой композиции подсчитать сумму S вида: n ( 1)i zi . Вывес-

i 1

ти все комбинации и соответствующие им суммы S в выходной текстовый файл.

Вариант № 7. Разработать и отладить программу, по заданным значениям n и m генерирующую все сочетания. Каждая комбинация должна состоять из элементов множества {1, 2, ..., n} и содержать m элементов (m

n).

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

Вариант № 8. Сгенерировать все двухэлементные подмножества множества {1, 2, ..., n}, n>2.

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

Вариант № 9. Разработать и отладить программу, по заданным значениям n и m генерирующую все перестановки с повторениями. Каждая комбинация должна состоять из элементов множества {1, 2, ..., n} и содержать m элементов (m n).

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

Вариант № 10. Разработать и отладить программу, по заданным значениям n и m генерирующую все размещения. Каждая комбинация должна состоять из элементов множества {1, 2, ..., n} и содержать m элементов (m

n).

Кроме того, для каждой комбинации, у которой произведение нечёт-

ных элементов превышает сумму чётных элементов, помимо самой ком-

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

Вариант № 11. Разработать и отладить программу, по заданным значениям n и m генерирующую все сочетания с повторениями. Каждая комбинация должна состоять из элементов множества {1, 2, ..., n} и содержать m элементов.

105

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

Вариант № 12. Сгенерировать все трёхэлементные подмножества множества {1, 2, ..., n}, n>3.

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

Вариант № 13. Разработать и отладить программу, по заданным значениям n и m генерирующую все сочетания. Каждая комбинация должна состоять из элементов множества {1, 2, ..., n} и содержать m элементов

(m n).

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

Вариант № 14. Разработать и отладить программу, по заданным значениям n и m генерирующую все размещения с повторениями. Каждая комбинация должна состоять из элементов множества {1, 2, ..., n} и содержать m элементов.

Кроме того, для каждой комбинации, у которой произведение эле-

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

Вариант № 15. Сгенерировать все четырёхэлементные подмножества множества {1, 2, ..., n}, n>4.

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

Контрольные вопросы

1.Какие задачи называются трудно решаемыми?

2.Приведите примеры трудно решаемых задач.

3.Какие комбинации называются размещениями из n элементов по m элементов?

4.Какая формула позволяет подсчитать количество размещений из n по m?

5.Опишите рекурсивную процедуру для генерации размещений.

6.Какие комбинации называются размещениями с повторениями из n элементов по m элементов?

106

7.Как подсчитать количество размещений с повторениями из n по m?

8.Опишите процедуру для генерации размещений с повторениями.

9.Какие комбинации называются перестановками из n элементов?

10.Чему равно количество перестановок из n элементов?

11.Опишите процедуру для генерации перестановок.

12.Какие комбинации называются перестановками с повторениями из n элементов по m элементов?

13.Какая формула позволяет подсчитать количество перестановок с повторениями данного состава ( 1, 2,..., n)?

14.Опишите процедуру для генерации перестановок с повторениями.

15.Какие комбинации называются сочетаниями из n элементов по m элементов?

16.Как подсчитать количество сочетаний из n по m?

17.Опишите процедуру для генерации сочетаний.

18.Какие комбинации называются сочетаниями с повторениями из n элементов по m элементов?

19.Чему равно количество сочетаний с повторениями из n по m?

20.Опишите процедуру для генерации сочетаний с повторениями.

21.Какие комбинации называются n-элементной композицией числа m?

22.Опишите процедуру для генерации n-элементной композиции числа m.

23.Какие комбинации называются n-элементным разбиением числа m?

24.Опишите процедуру для генерации всех разбиений числа m.

107

ЛИТЕРАТУРА

1.Ахо Альфред В., Хопкрофт Джон Э., Ульман Джеффри Д. Структуры данных и алгоритмы. М.: Вильямс, 2010. 400 с.

2.Вирт Н. Алгоритмы и структуры данных. СПб.: Невский Диалект,

2008. – 352 с.

3.Иванов Б. Н. Дискретная математика. Алгоритмы и программы. Расширенный курс: [учебное пособие для студентов вузов, обучающихся по специальности «Прикладная математика и информатика»]. – М.: Из-

вестия, 2011. – 511 с.

4.Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск. М.: Издательский дом «Вильямс», 2011. – 824 с.

5.Котов В.М., Соболевская Е.П., Толстиков А.А. Алгоритмы и структуры данных: [учебное пособие для студентов учреждений высшего образо-

вания, обучающихся по специальностям «Прикладная математика»

и др.]. – Минск: БГУ, 2011. – 267 с.

6.Круглински Д., Уингоу С., Шеферд Дж. Программирование на Microsoft Visual C++ 6.0 для профессионалов / пер. с англ. – СПб.: Питер; М.: Издательско-торговый дом «Русская редакция», 2004. – 861 с.

7.Ланина Н.Р. Теория графов: учебно-методическое пособие для студентов заочной формы обучения по направлению подготовки 080500.62 «Бизнес-информатика». ‒ Мурманск: МГГУ, 2014. – 104 с.

108

ПРИЛОЖЕНИЕ

1. Программная реализация сортировки простыми вставками

#include "stdafx.h" #include <iostream> #include <locale.h> #include <ctime> using namespace std;

#define MAX_SIZE 101 // Максимальное количество элементов в массиве struct MY_NODE

{

int key;

char info[15]; };

MY_NODE a[MAX_SIZE]; int n;

void InsertSort()

{int i,j,k; MY_NODE buf; for (i=1; i<n; i++)

{ buf=a[i]; k=a[i].key;

for (j=i-1; j>=0 && a[j].key>k; j--) {a[j+1]=a[j];}

a[j+1]=buf;

};

}

int main ()

{

int i; char *stars="***"; setlocale(LC_ALL, "RUS"); cout << "Insert Sr\n";

cout << "Введите размерность массива n (n<=100) и нажмите <<Enter>>: ";

109

cout << "Нажмите клавишу ENTER, чтобы закрыть программу \n"; getchar();

return 0;

}

2. Программная реализация сортировки Шелла

#include "stdafx.h" #include <iostream> #include <locale.h> #include <ctime> using namespace std;

#define MAX_SIZE 101 // Максимальное количество элементов в массиве struct MY_NODE

{

int key;

char info[15]; };

MY_NODE a[MAX_SIZE]; int n;

void ShellSort()

{ int h,i,j,k,y,kh; MY_NODE buf; for (h=1; h<(n/9); h=3*h+1); while (h>0)

{ for (k=0; k<h; k++)

{for (i=k+h; i<n; i+=h)

{buf=a[i]; y=buf.key;

for (j=i-h; j>=0 && y<a[j].key; j-=h) {a[j+h]=a[j];}; a[j+h]=buf;

}

}

h/=3;

}

}

int main ()

{

int i; char *stars="***"; setlocale(LC_ALL, "RUS"); cout << "Shell Sr\n";

cout << "Введите размерность массива n (n<=100) и нажмите <<Enter>>: "; cin >> n; cin.ignore();

srand ( time(NULL) ); // Инициализация генератора случайных чисел for (i=0; i<n; i++)

{

110