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.

Висновки

 

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


 

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

30838. Раздражимость и возбудимость 44 KB
  По биологической значимости: адекватные присущи для восприятия данному виду рецептора неадекватные не являются естественными с точки зрения природы или силы раздражения. Законы раздражения Действие раздражителя описывается несколькими законами: 1. Закон силы раздражения: Чем больше сила раздражения тем до известных пределов сильнее ответная реакция. Но есть сила раздражения для любого биологического раздражителя которая способна вызывать mx эффект оптимальная сила оптимум частоты и силы раздражения.
30839. Действие постоянного тока 29.5 KB
  Под катодом замыкая цепь мы по существу вносим мощный отрицательный заряд на наружную поверхность мембраны. Это приводит к развитию процесса деполяризации мембраны под катодом. При замыкании цепи происходит внесение мощного положительного заряда на поверхность мембраны что приводит к гиперполяризации мембраны. КУД смещается вслед за потенциалом мембраны но в меньшей степени.
30840. Строение биомембран 52 KB
  Основу мембраны составляет липидный бислой двойной слой амфифильных липидов которые имеют гидрофильную головку и два гидрофобных хвоста . В липидном слое липидные молекулы пространственно ориентированы обращены друг к другу гидрофобными хвостами головки молекул обращены на наружную и внутреннюю поверхности мембраны. Липиды мембраны: фосфолипиды сфинголипиды гликолипиды холестерин. К ним относятся рецепторные белки белки адгезии; трансмембранные пронизывают всю толщу мембраны причем некоторые белки проходят через...
30841. Трансмембранный обмен 28.5 KB
  Осмос когда через мембрану движется растворитель из зоны с меньшей концентрацией в зону с большей концентрацией.Переносчики белки которые тем или иным способом переносят вещества через мембрану – за счет конформации пространственного преобразования молекул переносчика сальтообразно. Активный транспорт транспорт веществ через мембрану который осуществляется против градиента концентрации и требует значительных затрат энергии. Он вмонтирован в мембрану.
30842. Ионные каналы 85.5 KB
  Ионные каналы Ионный канал состоит из нескольких субъединиц их количество в отдельном ионном канале составляет от 3 до 12 субъединиц. Ионные каналы работают по механизму облегченной диффузии. каналам пропускающим только один вид ионов натриевые каналы калиевые каналы кальциевые каналы анионные каналы. Некоторые из ионных каналов неселективные например каналы утечки .
30843. . Воспринимать информацию переводить информацию раздражителя на биологический язык клетки. 21.5 KB
  Воспринимать информацию переводить информацию раздражителя на биологический язык клетки. Обрабатывать информацию т. Кодировать информацию превращать информацию в форму удобную для хранения в мозге.
30844. Рецепторная функция нейронов 30 KB
  Сенсорные рецепторы. Клеточные химические рецепторы. Хеморецепторы нейронов к большому числу специфических и неспецифических химических раздражителей внутренней и внешней среды. Сенсорные рецепторы это нервные окончания чувствительные участки нейрона которые способны воспринимать другие нехимические виды раздражения.
30845. Электрогенез нейронов 25.5 KB
  Вызванная активность возникает под действием раздражителей Исходно все нейроны могут быть разделены на: спонтанноактивные фоноактивные нейроны молчащие нейроны нефоноактивные нейроны. Фоноактивные нейроны это такие нейроны которые продуцируют потенциалы действия спонтанно без внешних раздражителей вследствие особенностей своего обмена веществ. Молчащие нейроны это такие нейроны которые без внешнего стимула не отвечают потенциалом действия. Спонтанноактивные нейроны тоже меняют свою активную деятельность под действием...
30846. Нервные проводники 24 KB
  Все волокна по толщине а значит и по скорости проведения возбуждения могут быть разделены на 3 группы: А В С. Волокна А и В относятся к миелинизированным волокнам а волокна С немиелинизированные. Волокна группы А делятся на 4 подгруппы: 1Аальфа. К ним относятся эфферентные волокна скелетных мышц кроме того афферентные волокна от рецепторов мыщц мышечных веретён; 2Абета.