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.

Висновки

 

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


 

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

23522. History of the Mexicans as Told by Their Paintings 266 KB
  This edition is the only available complete English translation published one year after Joaquín García Icazbalceta first published the Spanish text in the Anales del Museo Nacional de México. Of the Mexican Year. Vchilobi 7 the younger brother and god of the Mexicans was born without flesh naciò sin carne but only bones in which condition he lived six hundred years during which period of time the gods did nothing whatever the father as well as the sons and in their representation there is no account taken of these six hundred...
23523. ПРОСТРАНСТВЕННО-ХРОНОЛОГИЧЕСКИЕ АСПЕКТЫ ИНДОЕВРОПЕЙСКОЙ ПРОБЛЕМЫ И КАРТА ПРЕДПОЛАГАЕМЫХ ПРАРОДИН ШЕСТИ НОСТРАТИЧЕСКИХ ЯЗЫКОВ 147.5 KB
  Очевидно что на карте помещены прародины праязыков потомков ностратических языков и что эта картина на несколько тысячелетий отстоит от эпохи ностратического единства датируемого А. Долгопольским VIII тыс. Хелимского: Этот период отделен от нас не одним десятком тысячелетий его ареалом был Южный Прикаспий [3 с. Терентьева считающих что по данным глоттохронологии возраст ностратической макросистемы определяется около 15 тыс.
23524. Водский язык в 19 – 20 веках 294.5 KB
  А теперь как здороваться и прощаться: Terve Tere päivä Тэрве Тэрэпяйвя Здравствуйте Добрый день Tere oomnikkoa Тэрэ оомниккоа Доброе утро Tere õhtagoa Тэрэ ыхтагоа Добрый вечер Jäämm yvässi Яямм ювясси До свидания Познакомимся теперь с так называемыми кумулятивными рунами: Kuza piippu Ađđaa nalla. Возьмем глаголы из прошлого урока и образуем от них будущее время: valaa наливать valavad наливают nõizõn valamaa буду наливать juvva пить joovad пьют nõizõn joomaa буду пить syvvä есть ...
23525. Повседневный арабский язык 1.95 MB
  Что касается ритма занятий то было бы оптимально если бы Вы прослушивали каждый день по новому разговору. Предисловие для преподающих арабский язык Дорогие коллеги Данный материал может быть использован для занятий как в группе так и индивидуально. Это господин Али альХаляби. Меня зовут Али альХаляби.
23526. АРАБСКИЙ ЯЗЫК В ДИАЛОГАХ 590 KB
  Разговор 3 В гостинице اَلْحِوَارُ اَلثَالِثُ فِي اَلْفُنْدُقِ Добрый вечер يُورِي: مَسَاءُ اَلْخَيْرِ Добрый вечер سَعِيدْ: مَسَاءُ اَلْخَيْرِ Меня зовут Юрий Кабанов. شُكْراً جَزِيلاً Не за что прощение اَلْعَفْوُ Разговор 6 Телефонный разговор مُكَالَمَةٌ هَاتِفِيَّةٌ Алло أَلُو Да кто на линии на проводе نَعَمْ، مَنْ عَلَى اَلْخَطِّ؟ Я Юрий из Москвы. Добро пожаловать господин Юрий Где ты сейчас أَهْلاً وَسَهْلاً يَا سَيِّدْ يُورِي أَيْنَ أَنْتَ اَلآنَ؟ Я сейчас в городе Фес в гостинице. Основная часть Разговор 1...
23527. Словарь шумеро-аккадского языка 849 KB
  Составление первого подобного словаря на русском языке при отсутствии картотеки картотека составлявшаяся в течение многих лет погибла во время Отечественной войны и блокады Ленинграда оказалось делом исключительно трудоемким и создание его потребовало большого напряжения и большой затраты сил хотя словарь этот включает только не большое число текстов рассчитанных для чтения на первых двух курсах обучения в университете и естественно не может претендовать на полноту. Струве вполне отвечает научным требованиям составления...
23528. Грамматика датского языка 475 KB
  they немое после l n r и перед t s dreng [дрэŋ] мальчик gade [гэ:ðэ] улица holdt [хольт] остановка e [e] [æ] [a] закрытое как в слове меч в конце открытое э перед g открытое a leve [лeвэ] жить spise [сби:сэ] есть jeg [яй] я meget [майэт] очень f [ф] как русское far [фа:] отец g [г] [у] [ŋ] [и] [ ] в начале слова г в середине или конце слова у носовое ŋ как в англ. слове sing после гласной и иногда немое в середине слова give [gi:væ] or [gi] give brag [брa'у] удар synge [сюŋэ] петь sang [саŋ] песня jeg...
23529. ГРАММАТИКА ИСПАНСКОГО ЯЗЫКА 1.03 MB
  1 Имя существительное Nombre sustantivo В испанском языке существительные бывают: собственные Rosa Роза Carmen Кармен 2 нарицательные la mesa стол el árbol дерево одушевленные el hombre мужчина el gato кот неодушевленные el bosque лес la silla стул конкретные la cara лицо el techo потолок абстрактные el tiempo время el aire воздух собирательные la biblioteca библиотека la muchedumbre толпа 1. Существительные которые оканчиваются в единственном числе на согласные z и x меняют их во множественном числе на c:...
23530. Повседневный немецкий язык 1.92 MB
  ru Einleitung Введение Первая часть Herr Klein Guten Tag Hören Sie bitte zu Ich bin Dieter Klein. Ich bin Lehrer. Ich bin Deutscher. Ich spreche Deutsch.