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.

Висновки

 

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


 

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

34808. Кант: от субстанции у субъекту, от бытия к деятельности. Рассудок и проблема объективности познания. Явление «вещь в себе». Природа и свобода 29.5 KB
  Канта Философия Канта вершина всей истории философии до XX в. Все творчество Канта делится на два периода докритический и критический. В первый период основное внимание Кант уделял вопросам естествознания и философии природы. В нем излагается знаменитая гипотеза возникновения Вселенной из туманности что означает отказ от идеи первотолчка хотя Кант и признавал Бога в качестве создателя мира.
34809. Абсолютный идеализм и диалектический метод Гегеля. Противоречие системы и метода 41 KB
  Диалектическая философия Гегеля Романтики иенской школы Фихте Шеллинг Гегель подвергали пересмотру кантовское понятие трансцендентального субъекта. Согласно романтикам главным недостатком кантовского субъекта является его неисторический характер во многом обязанный тому что Кант противопоставил истинное знание доставляемое точными науками тем формам знания которые нам дают миф искусство язык. В качестве такого субъекта предстала особенно у Гегеля история человечества в целом. Теперь формы трансцендентальной субъективности...
34810. Антропологический материализхм Фейербаха 31 KB
  Фейербаха Фейербах последний великий представитель классической немецкой философии. В отличие от других немецких философов этого периода которые были идеалистами Фейербах материалист. Самая известная книга Сущность христианства Если Гегель отрывал разум мышление от человека от его чувственной деятельности то Фейербах реальным субъектом разума считает только человека.
34811. Принцип делай добро (модель Парацельса) 30.5 KB
  Модель Парацельса это форма врачебной этики в рамках которой нравственное отношение с пациентом понимается как составляющая стратегии терапевтического поведения врача. В границах модели Парацельса в полной мере развивается патернализм как тип взаимосвязи врача и пациента. Смысл слова отец в патернализме фиксирует что образцом связей между врачом и пациентом являются не только кровнородственные отношения для которых характерны положительные психоэмоциональные привязанности и социальноморальная ответственность но и целебность ...
34812. Принцип соблюдения долга (деонтологическая модель) 32 KB
  Петров использовал этот термин чтобы обозначить реально существующую область медицинской практики врачебную этику которая в России была отменена после переворота 1917 года за ее связь с религиозной культурой. Деонтологическая модель врачебной этики это совокупность должных правил соответствующих той или иной конкретной области медицинской практики. Еще одним примером деонтологической модели являются правила относительно интимных связей между врачом и пациентом разработанные Комитетом по этическим и правовым вопросам при Американской...
34813. Принцип уважения прав и достоинства человека (биоэтика) 32.5 KB
  Эти процессы высвечивают почему в 6070х годах XX века формулируется такая форма медицинской этики как биоэтика которая начинает рассматривать медицину в контексте прав человека. Основным моральным принципом биоэтики становится принцип уважения прав и достоинства человека. Под влиянием этого принципа меняется решение основного вопроса медицинской этики вопроса об отношении врача и пациента.
34814. Особенности становления русской философии. Славянофилы и западники 53 KB
  Возникновение русской философии Термин философия или любомудрие начинает встречаться в церковных поучениях и светских рукописных книгах в XI XII вв В XIXV вв. Исторические формы русской философии возникали и существовали внутри крупных эпох развития русской культуры с XI по XIX в. начало формирования русской философии эволюция древнерусской мудрости.
34815. Религиозно-философские концепции . соловьев, Достоевский, толстой 32.5 KB
  соловьев Достоевский толстой. Соловьева Одной из важнейших концепций русской философии XIX в. Соловьева. Он может быть гарантом целостности Соловьев вопреки многим своим современникам настроенным сугубо научно не мог допустить отсутствия принципа абсолютной личности.
34816. Экзистенциальная философия Бердяева 44 KB
  Представители этого направления отвергая господствовавшие в истории классической философии принципы рационализма характерные прежде всего для философии Гегеля обратились в своем творчестве к интуитивным эмоциональноволевым и Iт. Предмет и задачи философии Бердяев однозначно определяет с экзистенциальноантропологических позиций: философия призвана познавать бытие из человека и через человека черпая содержание свое в духовном опыте и духовной жизни. Показав что объект порождается субъектом Кант раскрыл возможность построения...