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.

Висновки

 

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


 

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

39967. Гидропривод металлургических машин 8.17 MB
  Рисунок 1 Схемы иллюстрирующие принцип действия объёмного гидропривода. Из рисунка 1а следует что при приложении силы Р к закрытому сосуду через поршень эта сила уравновешивается силой давления жидкости силой трения пренебрегаем и силой тяжести тоже Положение сохраняется если в качестве сосуда возьмём два гидроцилиндра соединённых гидролинией рисунок 1б При перемещении поршня 1 произойдёт вытеснение жидкости под поршнем 2. Реверсирование гидромотора можно осуществить также изменением направления потока жидкости направляемого насосом...
39968. Проектирование привода технологического оборудования 1.54 MB
  Модуль числа зубьев колес и коэффициенты смещения . Модуль числа зубьев колес и коэффициенты смещения. Определим размеры характерных сечений заготовок по формулам тогда мм Кm = 20 коэффициент учитывающий вид передачи; Диаметр заготовки колеса равен Выбираем материал для колеса и шестерни сталь 45 термообработка улучшение твердость поверхности зуба шестерни 269302 HB Dm1 = 80 мм Dm1 Dm твердость поверхности зуба колеса 235262 НВ Sm1 = 80 мм Sm1 Sm. Для их определения используем зависимость Пределы контактной...
39969. Расчет эффективности проекта реконструкции установки АВТ-4 547.41 KB
  Приведены расчеты: анализ использования производственной мощности расчеты производственной программы и производственной мощности материального баланса установки до и после реконструкции расчет ФЗП и себестоимости продукции а также расчет основных техникоэкономических показателей и эффективность инвестиционного проекта кроме того приводится анализ рынка продукции нефтеперерабатывающих заводов. Введение 3 1 Анализ рынка продукции нефтеперерабатывающих заводов 5 2 Анализ использования производственной мощности 9 3 Расчет производственной...
39970. Расчет эффективности проекта реконструкции ОАО «Газпром нефтехим Салават» установка АВТ-4, цех №14 642.35 KB
  При общем объеме экспорта дизельного топлива из России в дальнее зарубежье в количестве 386 млн тонн дизельное топливо класса Евро5 составляет около 22 т. На российских НПЗ около половины всех печных агрегатов имеют КПД 50 60 при среднем показателе на зарубежных заводах 90. Рисунок 4 Индекс Нельсона на НПЗ в РФ Наличие на НПЗ процессов прямой перегонки нефти и установок улучшающих качество прямогонных фракций позволяют получить глубину не более 60 наличие процессов переработки вакуумного газойля увеличивает глубину...
39971. Разработка организации технического обслуживания и ремонта МТП в ЦРМ хозяйства с годовым объемом работ 56000 часов 205.66 KB
  В курсовом проекте рассчитана центральная ремонтная мастерская хозяйства обоснован технологический процесс технического обслуживания и ремонта машинного парка в ЦРМ хозяйства с годовым объемом работ 56000 часов разработан компоновочный план ЦРМ технологическая планировка участка ТО и диагностики разработан генеральный план РОБ хозяйства спроектирован технологический процесс восстановления оси произведена техникоэкономическая оценка ЦРМ. Распределение годового объема работ по объектам ремонта 1. Технологический процесс ТО и ремонта...
39972. Процесс деятельности предприятия, в области управления персоналом, отраженный на диаграммах нотации IDEF0 692.17 KB
  В рамках деятельности по управлению персоналом возникает закономерная потребность оценки состояния человеческого ресурса. Соответственно основной целью является не только проведение процедуры оценки но и процесс использования результатов. В рамках данной темы планируется рассмотреть в теоретической части: привязка процесса оценки к конкретной категории персонала или подразделению организации; установление взаимосвязи деловой оценки с другими направлениями деятельности службы управления персоналом: обучением управлением карьерой...
39973. Классификация причин уязвимости Windows NT 36.89 KB
  Классификация пользователей Unix Суперпользователь Обычные пользователи Специальные пользователи Псевдопользователи Классификация пользователей Windows Администраторы Обычные пользователи Специальные пользователи Псевдопользователи Анонимный пользователь Уязвимости Unix Наличие демонов Механизм SUID SGIDпроцессов Излишнее доверие Человеческий фактор Уязвимости Windows Серверы Системные процессы Анонимный пользователь Человеческий фактор Совместимость с другими ОС Классификация причин уязвимости Windows...