Задача о ящиках

Размещено на http://www.allbest.ru/

[Введите текст]

Министерство образования и науки Российской Федерации

Федеральное государственное автономное образовательное учреждение высшего образования «Уральский федеральный университет имени первого Президента России Б.Н. Ельцина» (УрФУ)

Институт Уральский энергетический (УралЭНИН)

Кафедра Прикладная математика

Контрольная работа по теме: Задача о ящиках

Екатеринбург

2018



Введение

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

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

Формулировка задачи.

Имеется N ящиков. Для каждого задан вес m и прочность p. Прочность показывает, какой суммарный вес может выдержать ящик. Написать программу, которая позволяет вывести все комбинации, которыми можно поставить K из N ящиков друг на друга. Число K задается пользователем.

При реализации использовать рекурсивный алгоритм перебора.



1. Описание алгоритма решения задачи

Подробно опишем алгоритм работы программы

Создаем массивов (a[], P[], M[]), задаем каждому из них размерность равную n+1, где n - количество ящиков.

n и k задаются пользователем с клавиатуры, массивы заполняются самостоятельно: a[]-содержит в себе номера ящиков от 1 до n, P[]- содержит в себе прочности и заполнятся числами от 0 до 50,M[]-содержит в себе веса ящиков и заполняется числами в диапазоне от 0 до 30.

Вызываем функцию, осуществляющую полный перебор (void permutations()).

Если номер позиции не меньше n (пусть это будет проверка №1) , то вызывается функция bool PP(), которая находит суммарный вес ящиков со второго по k-й, и затем проверяет прочности всех ящиков, постепенно уменьшая вес, то есть, если сумма весов со 2-го по k-й ящик меньше прочности первого ящика, то происходит следующая итерация, где сравнивается сумма весов с 3-го по k-й с прочностью второго ящика и так далее, затем если каждый раз сумма весов была меньше прочности, функция возвращает true.

Далее если функция PP() вернула true(проверка №2), то мы вызываем функцию Print(), которая выводит номера ящиков вошедших в нашу выборку и прошедших проверку.

Если же первая проверка не была пройдена, тогда начинается смена позиций начального элемента до n-го, также происходит вызов функции permutations(), здесь мы возвращаемся к пункту 3.

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

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

По сути наша задача сводит к решению нескольких более простых:

I Реализовать функцию размещения N объектов по K местам (без повторений).

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

Разберем функцию PP():

bool PP(int k,int *P,int *a,int *M)

{

int s=0;//суммарная масса

for(int i = 2; i < k+1; i++){

s += M[a[i]];

}

for(int i = 1; i < k; i++){

e++;

if(P[a[i]] < s){

return false;

}

s = s - M[a[i+1]];

}

return true;

}

}1) Функция принимает следующие аргументы: необходимое количество ящиков в выборке, указатель на массив с прочностями ящиков, указатель на массив с номерами ящиков, указатель на массив с массами ящиков.

Заводится переменная, хранящая в себе суммарную массу нашей пирамиды.

Далее начинается цикл, в котором идет подсчет суммарной массы, последних k-1 ящика, так как масса первого ящика нас не интересует, так как он ни на что не давит. Посчитав общую сумму цикл заканчивается.

Начинается следующий цикл, в котором идет сравнение прочностей ящиков с 1-го по k-1, если суммарная масса меньше прочности проверяемого ящика, то суммарная масса уменьшается на вес следующего ящика, а если условие не выполняется, то функция возвращает значение false.

Сделаем более подробный разбор алгоритма функции permutations():

void permutations(int *a, int pos, int n, int k, int *P, int *M)

{

if (pos >= n+1)

{

if(PP(k,P,a,M)){

Print(a,k);

}

}

else

{

for (int i = pos; i < n+1; ++i)

{

swap(a[i], a[pos]);

permutations(a, pos + 1, n, k, P, M);

}

}

}

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

Далее проверяется условие pos >= n+1, при выполнении которого проверятся еще одно условие: если данная последовательность из ящиков имеет право на существование, то она выводится.

Если же первое условие не выполнено, то вызывается цикл for (int i = pos; i < n+1; ++i).

В котором происходит обмен мест i-го элемента и элемента с номером pos, с помощью функции swap().

Далее функция permutations() рекурсивно вызывает саму себя с единственным изменением, вместо pos берется pos+1.

Описание используемых структур данных.

Алгоритм был реализован при помощи структуры, содержащей поля и методы, необходимые для реализации алгоритма «полный перебор».

Поля структуры:

Int n -переменная содержащая общее количество ящиков;

Int k - переменная содержащая количество ящиков, выбираемых для составления друг на друга;

Int *a -динамический массив содержащий в себе номера ящиков;

Int *M - динамический массив содержащий в себе массы ящиков;

Int *P - динамический массив содержащий в себе прочности ящиков;

И методы:

Void Print(int *a,intk) - функция принимает указатель на массив с номерами ящиков и необходимое число ящиков в выборке, функция выводит номер размещения (считает с помощью статистической константы) и затем выводит первые k элеменетов массива a.

Bool PP(int k,int *P,int *a,int *M) - функция принимающая указатели на массивы с прочностями, массами и номерами ящиков, а также общее количество ящиков и количество ящиков в выборке. Функция осуществляет проверку прочности выборки и возвращает true в случае, если она возможна, а иначе возвращается false.

Void permutations(int *a, intpos, intn, intk, int *P, int *M) - функция принимающая указатели на массивы с прочностями, массами и номерами ящиков, а таже общее количество ящиков, количество ящиков в выборке и номер первой позиции выборки. Функция перебирает все перестановки для n, т.е. всего n!, и вызывает внутри себя проверку первых k членов каждой выборки, если она успешна, то выводит ее с помощью функции print.

2. Оценка сложности алгоритма

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

void permutations(int *a, int pos, int n, int k, int *P, int *M)

{e++;

if (pos >= n+1)

{e++;

if(PP(k,P,a,M,n)){//o(2*(k-1))

Print(a,k);//o(k)

}

}

else

{

for (int i = pos; i < n+1; ++i)//O(n+1)

{e++;

swap(a[i], a[pos]);//T(3)

permutations(a, pos + 1, n, k, P, M);

}

}

}

Сложность PP= O(k) , swap-имеет константную сложность, print-O(k).

В случае, когда номер позиции нам не подходит, мы будем вызывать фор со сложностью O(n+1), он будет вызваться сначала от 1до n, потом от 2 до n…от n-1 до n и поскольку условие проверяющее позицию в случае успеха имеет сложность k, общую сложность алгоритма можно оценить как :O((n^3)*k).

3. Инструкция для пользователя

Для запуска программы дважды кликните по файлу “ящики.exe”;

Введите количество ящиков, затем нажмите Enter;

Введите необходимое число ящиков в выборке, затем нажмите Enter;

Будет выведена строка с массами ящиков, а следующая за ней с прочностями.

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

Нажмите Enter, чтобы выйти из окна данных.

4. Результаты работы



Заключение

алгоритм программа условие permutation

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



Список литературы

1. В.Б. Костоусов, А.Б. Ложников Алгоритмические средства информатики/ учебно-методическое пособие: УГТУ-УПИ, 2008.

2. Кормен Т. Алгоритмы: Построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. М.: МЦНМО, 1999.

3. Кнут Д. Искусство программирования для ЭВМ / Д. Кнут. М: Мир, 1976.

4. Токманцев Т.Б. Алгоритмические языки и программирование: учебное пособие/ Токманцев Т.Б.-- Электрон. УрФУ 2013.

Размещено на Allbest.ru

...