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.

Висновки

 

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


 

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

65707. Внутрішньоісламські протиріччя в мусульманській уммі Криму: природа, стан, еволюція 160.5 KB
  Генезис та ескалація внутрішньорелігійних протиріч в ісламі який на теренах України переживає процес відродження та реінтеграції у нове для нього суспільне буття стали ще одним підтвердженням складності й багаторівневості релігійних процесів в умовах конфліктогенного...
65708. Наукові основи технологій одержання заряджених полімерних мембран з антибактеріальними властивостями 1.56 MB
  Мембранні технології в сучасному світі відіграють значну роль як у вирішенні локальних галузевих питань так і глобальних проблем що постали перед людством серед яких: забезпечення населення якісними продуктами харчування питною водою та сучасними джерелами енергії охорона...
65709. УДОСКОНАЛЕНІ ЗАХОДИ ДОГЛЯДУ ЗА НАСІННИКАМИ ЦУКРОВИХ БУРЯКІВ В УМОВАХ НЕСТІЙКОГО ЗВОЛОЖЕННЯ ЛІСОСТЕПУ УКРАЇНИ 303 KB
  Одним із надійних шляхів підвищення урожайності та якості насіння гібридів цукрових буряків є впровадження у виробництво удосконалених технологій вирощування які забезпечували б високу продуктивність насінників тобто максимальну реалізацію їх біологічного потенціалу...
65710. Комп’ютерний комплекс моделювання динаміки фізіологічного стану людини при роботі у приміщенні 360 KB
  Забезпечення належних умов праці на робочому місці безпека технологічних процесів санітарнопобутові умови праці та створення комфортних умов перебування людини у приміщенні набувають особливого значення оскільки більшу частину свого часу людина проводить саме в приміщенні.
65711. ПУБЛІЧНИЙ КОНТРОЛЬ ЗА ДІЯЛЬНІСТЮ ОРГАНІВ ДЕРЖАВНОЇ ВЛАДИ: ТЕОРЕТИКО-МЕТОДОЛОГІЧНИЙ АНАЛІЗ 199 KB
  Одним із ефективних засобів розвитку та функціонування сучасного постмодерного суспільства є налагодження діалогу між державою та громадянином між відповідними гілками влади політичними партнерами культурами та цивілізаціями.
65712. Податкова політика російського царату в українському селі у другій половині ХІХ – на початку ХХ ст.: історичний аспект 143.5 KB
  Трансформаційні процеси в аграрному секторі економіки України кінця ХХ – початку ХХІ ст. стимулюють зростання значного інтересу як дослідників-фахівців, так і широкої громадськості до специфічних особливостей перебігу аграрних перетворень, що мали місце в українському селі у минулому.
65713. Теплоізоляційні матеріали на основі модифікованих лужних алюмосилікатних композицій, здатних до спучування 927 KB
  Отже враховуючи все вищезазначене особливої актуальності набуває питання щодо розробки принципово нових видів теплоізоляційних матеріалів на основі модифікованих лужних алюмосилікатних композицій здатних до спучування які можуть бути виготовлені з використанням недорогої...
65714. РОЗВИТОК ТВОРЧИХ ЗДІБНОСТЕЙ УЧНІВ ОСНОВНОЇ ШКОЛИ ЗАСОБАМИ ГРАФІЧНИХ ЗАДАЧ З КРЕСЛЕННЯ 184 KB
  Звідси виникає перше протиріччя суть якого проявляється у важливості і значущості розвитку творчих здібностей школярів і відсутності методичної основи забезпечення цього процесу на засадах розвязування творчих графічних задач на уроках креслення.
65715. Особистісна реалізованість людини в онтогенезі 382 KB
  Мета дослідження теоретико-методологічне обґрунтування та емпіричне вивчення феномену особистісної реалізованості людини в онтогенезі. Відповідно до зазначеної мети поставлено такі завдання: здійснити теоретичний аналіз...