Презентация Простейшие переборные задачи. Генерация подмножеств и перестановок онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Простейшие переборные задачи. Генерация подмножеств и перестановок абсолютно бесплатно. Урок-презентация на эту тему содержит всего 15 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:15 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:1.54 MB
- Просмотров:70
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Простейшие переборные задачи:
генерация подмножеств и перестановок
Лабораторная работа №1
Раздел: комбинаторика
№2 слайд
Содержание слайда: Цель занятия:
Изучение простейших переборных задач: генерация подмножеств и перестановок.
№3 слайд
Содержание слайда: Генерация множества перестановок
№4 слайд
Содержание слайда: Генерация множества перестановок
№5 слайд
Содержание слайда: Генерация множества перестановок
№6 слайд
Содержание слайда: Генерация множества перестановок
№7 слайд
Содержание слайда: Генерация множества перестановок
Реализуем этот способ
Необходима функция, принимающая на вход вектор и множество
Множество реализуем бинарным вектором
Также будем передавать число элементов, которые еще необходимо добавить к вектору: если оно равно нулю, значит, перестановка построена
№8 слайд
Содержание слайда: Генерация множества перестановок
void GenPermut(size_t elems, vector<size_t>& cur, vector<bool>& used) {
if (elems == cur.size()) {
for (size_t i = 0; i < cur.size() - 1; ++i) {
cout << cur[i] + 1 << " ";
}
cout << cur[cur.size() - 1] + 1 << "\n";
}
for (size_t next = 0; next < elems; ++next) {
if (!used[next]) {
cur.push_back(next);
used[next] = true;
GenPermut(elems, cur, used);
cur.pop_back();
used[next] = false;
}
}
}
№9 слайд
Содержание слайда: Построение перестановки по ее номеру
№10 слайд
Содержание слайда: Построение перестановки по ее номеру
№11 слайд
Содержание слайда: Построение перестановки по ее номеру
№12 слайд
Содержание слайда: Построение перестановки по ее номеру
№13 слайд
Содержание слайда: Построение перестановки по ее номеру
vector<size_t> Permutation(size_t elemCount, size_t permNumber) {
vector<size_t> numbers;
for (size_t i = 0; i < elemCount; ++i) {
numbers.push_back(i);
}
int64 currentElementsCount = elemCount;
vector<size_t> ans;
while (currentElementsCount > 0) {
int64 k = 0;
int64 L = fact(currentElementsCount - 1);
while ((k + 1) * L < permNumber) {
++k;
}
size_t curNumber = -1;
for (size_t j = 0; j < elemCount; ++j) {
if (numbers[j] != -1) {
++curNumber;
}
if (curNumber == k) {
ans.push_back(numbers[j] + 1);
numbers[j] = -1;
break;
}
}
permNumber -= L*k;
--currentElementsCount;
}
return ans;
}
№14 слайд
Содержание слайда: Задания
№15 слайд
Содержание слайда: Задания
Скачать все slide презентации Простейшие переборные задачи. Генерация подмножеств и перестановок одним архивом:
