Страницу Назад
Поискать другие аналоги этой работы

Породження перестановок ефективним методом

ID: 98491
Дата закачки: 25 Мая 2013
Продавец: SerFACE (Напишите, если есть вопросы)
    Посмотреть другие работы этого продавца

Тип работы: Работа Лабораторная
Форматы файлов: Microsoft Word

Описание:
Мета: навчитися робити породження перестановок ефективним методом
Теоретичні відомості:
Послідовність n! перестановок на множині {1, 2, ..., n},
в якій сусідні перестановки розрізняються так мало, як тільки
можливо, - найкраще, на що можна сподіватися з точки зору міні-
мізації обсягу роботи, необхідного для породження перестали-
вок. Для того щоб така відмінність була мінімально можливим,
будь-яка перестановка в нашій послідовності повинна відрізняти-
ся від попередньої їй транспозицією двох сусідніх елементів.
Таку послідовність перестановок легко побудувати рекур-
вибухобезпечний. Для n = 1 єдина перестановка {1} задовольняє на-
шим вимогам. Припустимо, ми маємо послідовність
перестановок p1; p2> p3> - на множині {1, 2, ..., n}, в якій після-
довательности перестановки розрізняються тільки транспозицією
суміжних елементів. Розширимо кожну з цих (і - 1)! перестали-
вок, вставляючи елемент п на кожне з я можливих місць. Порядок
породжуваних таким чином перестановок буде наступним:
Постанова задачі
1. Реалізувати робочу програму та блок-схему породження перестановок ефективним методом на мові С
2. Ввести у вхідний файл EffectIn.txt довжину перестановки (порядковій номер -5) n=6.
3. Отримати вихідний файл EffectOut.txt виду 1) 1 2 3 4 5 6, де 1) – номер перестановки, а все інше – перестановка.
Виконання роботи
1. Побудував блок-схему до програми
3. Текст програми
#include <iostream>
#include <time.h>
#include <ctime>

const int n_max=20;
typedef int Vector[n_max+1];
FILE *f;
void Effect(Vector z, int n);
void Effect(Vector z, int n){
long int k=0;
Висновок: навчитися робити породження перестановок ефективним методом за допомогою програми на мові С

Размер файла: 118 Кбайт
Фаил: