75674

Задачі комбінаторики (перебору)

Практическая работа

Информатика, кибернетика и программирование

На початку виконання програми користувачу пропонується ввести кількість елементів, а потім, відповідно, вагу кожного елемента (ціле число). Усі елементи записуються я у головний масив. Для двох груп елементів створюються два нових пустих масиви.

Украинкский

2015-01-24

547.83 KB

0 чел.

Міністерство  освіти  і  науки України

Вінницький національний технічний університет

Інститут інформаційних технологій та комп’ютерної інженерії

Кафедра ПЗ

Практична робота №2 варіант №9

з дисципліни Алгоритми та структури даних

Виконала: ст. гр. 1 ПІ-13б                            Лілик Л. С.

Перевірив:                                                       Власюк В. Х.

Вінниця, 2013

Тема: Задачі комбінаторики (перебору).

 

Мета: Показати застосування різних методів до розв’язування переборних задач. Закріпити уміння рекурсивного опису алгоритмів.

Завдання:

Варіант № 9. Маємо n предметів, вага яких рівна a1, a2, ... , an. Розділити ці предмети на дві групи так, щоб загальна вага двох груп була максимально близькою.

Алгоритм, що використаний у програмі:

На початку виконання програми користувачу пропонується ввести кількість елементів, а потім, відповідно, вагу кожного елемента (ціле число). Усі елементи записуються я у головний масив. Для двох груп елементів створюються два нових пустих масиви.

Після цього визивається рекурсивна функція для перебору усіх варіантів розміщення елементів у двох групах. Перший виклик функції: в якості аргументів всі  масиви. Функція ділить елементи основного масиву, записуючи їх два нових доти, доки мінімальна різниця між сумами елементів обох нових масивів не стане рівною нулю (поки масиви не зрівняються), або доки лічильник не перевищить 10 000 ітерацій. Рекурсивно функція викликається двічі для кожного елемента за одну ітерацію. Перший виклик, аргументи: основний масив без і-того елемента, перший масив з і-тим елементом, другий масив; другий виклик, аргументи: основний масив без і-того елемента, перший масив, другий масив з і-тим елементом  і т.д.

Коли всі елементи розподілені на дві групі відбувається підрахунок різниці сум масивів. Відповідно ця різниця дорівнює нулю, або мінімально можлива різниця за даних значень.


Блок-схема алгоритму

 


Лістинг програми

// Pr-2-9-vs.cpp: определяет точку входа для консольного приложения.

//

 

#include "stdafx.h"

class MainArray

{

   public:

       MainArray();

       MainArray(int _main_n);

       ~MainArray(void);

       MainArray(const MainArray& other);

       void Print();

       void Fill();

       int sumWeight();

//  protected:

 //  private:

       int main_n; // number of el

       int *main_arr;

};

MainArray::MainArray(int _main_n):main_n(_main_n)

{

   //ctor

   main_arr = new int [main_n];

}

MainArray::MainArray()

{

   //ctor

   main_n=0;

   main_arr=0;

}

MainArray::~MainArray()

{

   //dtor

}

MainArray::MainArray(const MainArray& other)

{

   //copy ctor

   main_n=other.main_n;

   main_arr = new int[main_n];

   for(int i=0;i<main_n;++i)

       main_arr[i]=other.main_arr[i];

}

void MainArray::Print()  // output matrix

{

  cout<<"\n";

   for (int i=0; i<main_n; ++i)

{

 //if (main_arr[i] != 0)

           cout<<main_arr[i]<<"  ";

}

}

void MainArray::Fill()

{

    for (int i=0; i<main_n; ++i)

   {

       int a;

       cin>>a;

       main_arr[i]=a;

   }

}

int MainArray::sumWeight()

{

   int sumW = 0;

   for (int i=0; i<main_n; ++i)

       sumW+=main_arr[i];

   return sumW;

}

int minDif = 65576;

MainArray *first=0;

MainArray *second=0;

MainArray addElem(MainArray arr, int elem)

{

   MainArray temp(arr.main_n+1);

   for (int i=0; i<arr.main_n; ++i)

   {

       temp.main_arr[i]=arr.main_arr[i];

   }

   temp.main_arr[arr.main_n]=elem;

   return temp;

}

MainArray withoutEl(MainArray arr, int elemNum)

{

       MainArray temp(arr.main_n-1);

       for (int i=0; i<elemNum; ++i)

           temp.main_arr[i]=arr.main_arr[i];

       for (int i=elemNum+1; i<arr.main_n; ++i)

           temp.main_arr[i-1]=arr.main_arr[i];

       return temp;

}

void Sort(MainArray &arr) // sorting of the array (improved bubble sort)

{

   bool flag=false;

MainArray temp(arr.main_n);

while(flag==false)

{

 flag=true;

 for(int i=1;i<arr.main_n;++i)

 {

  if(arr.main_arr[i]<arr.main_arr[i-1])

  {

   temp.main_arr[i]=arr.main_arr[i];

   arr.main_arr[i]=arr.main_arr[i-1];

   arr.main_arr[i-1]=temp.main_arr[i];

   flag=false;

  }

 }

}

}

void Division(MainArray arr, MainArray a, MainArray b )

{

    static int counter=0;

   if (arr.main_n==0)

   {

       if(abs(a.sumWeight()-b.sumWeight())<minDif)

       {

           minDif=abs(a.sumWeight()-b.sumWeight());

  if (first!=0) delete first;

  if (second!=0) delete second;

           first = new MainArray(a);

           second = new MainArray(b);

        }

 

 counter++;

   }

  if (minDif==0||counter>10000)  return;

   for (int i=0;  i<arr.main_n; ++i)

   {

       Division(withoutEl(arr,i),addElem(a,arr.main_arr[i]),b);

       Division(withoutEl(arr,i),a,addElem(b,arr.main_arr[i]));  

   }

}

int main()

{

   cout<<"Input number of elements: ";

   int n=0;

   cin>>n;

if (n==0) return 0;

   MainArray *a;

   cout<<"Input "<<n<<" elements of array: ";

   a = new MainArray(n);

   a->Fill();

   cout<<"\nMain array: ";

   a->Print();

 

   first = new MainArray();

   second = new MainArray();

   Division(*a, *first, *second);

cout<<"\n\n~~~Array is devided~~~";

cout<<"\n\nFirst group: ";

   first->Print();

cout<<"\n\nSecond group: ";

   second->Print();

if (minDif==0)

 cout<<"\n\nGroups are equal.\n";

else

 cout<<"\n\nDifference between two groups is  "<<minDif<<endl;

cout<<endl;

   delete a;

   delete first;

   delete second;

   return 0;

}


Результат виконання

Складність алгоритму

Складність sumWeight дорівнює О( 2n ) від деякого часу виконання T.

Складність addElem дорівнює О( N2 + 2n + 3 ) від деякого часу виконання T.

Складність withoutEl дорівнює О( 2N2 + 4n + 2 ) від деякого часу виконання T.

Складність алгоритму дорівнює О( 2N + 8n + 21 ) від деякого часу виконання T.

Висновки

 

Навчилися застосувати різні методи до розв’язування переборних задач. Закріпили уміння рекурсивного опису алгоритмів. В результаті виконання лабораторної роботи отримали програму, що розділює предмети певної ваги на дві групи так, щоб загальна вага двох груп була максимально близькою. В програмі обчислюється різниця двох груп розділених  предметів.


 

А также другие работы, которые могут Вас заинтересовать

30518. Ключи криптосистемы. Жизненный цикл ключей. Требования к обеспечению безопасности жизненного цикла ключей. Управление ключами в криптографических системах 34.39 KB
  Методы разграничения доступа: Разграничение доступа по спискам; Использование матрицы установления полномочий; Разграничение доступа по уровням секретности и категориям; Парольное разграничение доступа.; управление сроком действия паролей их периодическая смена; ограничение доступа к файлу паролей; ограничение числа неудачных попыток входа в систему это затруднит применение метода грубой силы ; обучение пользователей; использование программных генераторов паролей такая программа основываясь на несложных правилах может...
30519. Технологии обеспечения безопасности корпоративной сети с использованием оборудования 2-го уровня модели OSI 228.33 KB
  VLN Virtul Loclre Network – это одна из функций Fst Ethernet. VLN позволяет изменять конфигурацию сети объединять пользователей в отдельные рабочие группы определять доступные сегменты для отдельно взятого порта. VLN дает возможность значительно оптимизировать работу локальной сети за счет разгрузки отдельных ее сегментов от лишнего трафика. С помощью VLN можно еще контролировать и эффективно подавлять широковещательные штормы которые в больших сетях иногда останавливают работу целых сегментов.
30520. Технологии обеспечения безопасности корпоративной сети с использованием оборудования 3-го уровня модели OSI 53.73 KB
  Метод анализа на лету заключается в мониторинге сетевого трафика в реальном или близком к реальному времени и использовании соответствующих алгоритмов обнаружения. Системы обнаружения атакIntrusion Detection Systems IDSs анализирует трафик поступающий на нее на соответствие сигнатурам в случае соответствия трафика сигнатуре оповещает администраторов по безопасности о наличии совпадения. Обычно на IDS поступает копия трафика который необходимо анализировать то есть IDS не ставят в разрез соединению это достигается...
30521. Средства обеспечения защиты данных от несанкционированного доступа, средства идентификации и аутентификации объектов БД, языковые средства разграничения доступа, организация аудита в системах БД. Задачи и средства администратора безопасности БД 32.18 KB
  В современных условиях любая деятельность сопряжена с оперированием большими объемами информации, которое производится широким кругом лиц. Защита данных от несанкционированного доступа является одной из приоритетных задач при проектировании любой информационной системы. Следствием возросшего в последнее время значения информации стали высокие требования к конфиденциальности данных. Системы управления базами данных, в особенности реляционные СУБД
30522. Основные понятия защиты информации (субъекты, объекты, доступ, граф доступов, информационные потоки). Постановка задачи построения защищенной автоматизированной системы (АС). Ценность информации 50.99 KB
  Ценность информации. Доска Пример матрицы доступа дискреционная модель защиты Выступление Основные понятия защиты информации. В связи с развивающимся процессом информатизации общества все большие объемы информации накапливаются хранятся и обрабатываются в автоматизированных системах построенных на основе современных средств вычислительной техники и связи.
30523. Модель системы безопасности HRU. Основные положения модели. Теорема об алгоритмической неразрешимости проблемы безопасности в произвольной системе 111.25 KB
  Теорема об алгоритмической неразрешимости проблемы безопасности в произвольной системе На доске множество исходных объектов O o1 o2 oM ; множество исходных субъектов S s1 s2 sN при этом S ⊆ O множество прав доступа субъектов к объектам R матрицей доступа каждая ячейка которой специфицирует права доступа к объектам из конечного набора прав доступа R r1 r2 rK т . Классическая Дискреционная модель реализует произвольное управление...
30524. Основні культурологічні теорії 143 KB
  Історичні науки вивчають процеси становлення і розвитку конкретних народів в їх безпосередній реальності, в хронологічній послідовності подій, вказуючи на конкретні форми міжрегіональної взаємодії.
30526. Модель Белла - Ла-Падулы 97 KB
  Устная часть Основным положением политики безопасности является назначение всем участникам процесса обработки защищаемой информации и документам в которых она содержится специальной метки секретно совершенно секретно и т. Такая метка называется уровнем безопасности. Все уровни безопасности упорядочиваются с помощью установленного отношения доминирования. Контроль доступа осуществляется в зависимости от уровней безопасности взаимодействующих сторон на основании двух правил: 1.