75659

Плгоритми пошуку та сортування для одновимірних масивів

Лабораторная работа

Информатика, кибернетика и программирование

Розробити процедури та функції для пошуку в одновимірних масивах посортованих та непосортованих та для їх сортування. В контрольному прикладі забезпечити пошук потрібних елементів в непосортованих масивах. Здійснити їх сортування. Здійснити пошук в посортованих масивах. Оцінити час виконання операцій.

Украинкский

2015-01-24

338.16 KB

2 чел.

Міністерство  освіти  і  науки України

Вінницький національний технічний університет

Інститут інформаційних технологій та комп’ютерної інженерії

Кафедра ПЗ

Лабораторна робота №9 варіант №9

з дисципліни Алгоритми та структури даних

Виконала: ст. гр. 1 ПІ-13б                            Лілик Л. С.

Перевірив:                                                       Власюк В. Х.

Вінниця, 2013

Тема: алгоритми пошуку та сортування для одновимірних масив.

Мета: набуття практичних навичок застосування алгоритмів пошуку та сортування.

Завдання:

Розробити процедури та функції для пошуку в одновимірних масивах посортованих та непосортованих та для їх сортування. В контрольному прикладі забезпечити пошук потрібних елементів в непосортованих масивах. Здійснити їх сортування.  Здійснити пошук в посортованих масивах. Оцінити час виконання операцій.

 

Варіант № 9.

9

Елементи присутні в обох масивах А і В в одному екземплярі

Складність алгоритму

Складність алгоритму пошуку (для одного масиву) дорівнює O( 2N ) від t ;

Складність алгоритму сортування дорівнює O( 4N2 +4N+1 ) від t, де:

t - час виконання;
Nкількість елементів масиву.

Опис алгоритму

У програмі реалізовано обхід усього масиву і пошук усіх елементів, що задовольняють умові варіанту. Крім того, реалізовано функцію для визначення, чи задовольняє введений користувачем елемент умові. Пошук реалізовано лінійним алгоритмом. Сортування масивів – бульбашковим методом.


Блок-схема алгоритму



Лістинг програми 

#include <iostream>

#include <vector>

using namespace std;

void Input(int arr[], int num)  // input array

{

   for (int i=0; i<num; ++i)

       cin>>arr[i];

}

void Print(int arr[], int num)  // output array

{

   cout<<endl;

   for (int i=0; i<num; ++i)

       cout<<arr[i]<<" ";

}

void Sort(int arr[], int num)  // bubble sort

{

   int temp=0;

   for (int j=0; j<num-1; ++j)

       for (int i=0; i<num-j-1; ++i)

           if (arr[i]>arr[i+1])

           {

               temp=arr[i];

               arr[i]=arr[i+1];

               arr[i+1]=temp;

           }

}

bool Search(int arr1[], int n, int arr2[], int m, int val)  // search

{

   int arrVal_1 = 0;

   int arrVal_2 = 0;

   for (int i=0; i<n; ++i)

       if(arr1[i]==val)

           ++arrVal_1;

   for (int i=0; i<m; ++i)

       if(arr2[i]==val)

           ++arrVal_2;

   if (arrVal_1==1&&arrVal_2==1)

       return true;

   else return false;

}

void SearchWithoutVal(int arr1[], int n, int arr2[], int m, vector<int> &mutual)

{

       vector<int> singleArr1;

       for  (int i=0; i<n; ++i)

       {

           int arr1_val=0;

           int temp=arr1[i];

           for (int j=0; j<n; ++j)

           {

               if (temp==arr1[j])

                   ++arr1_val;

           }

            if (arr1_val==1)

                   singleArr1.push_back(temp);

       }

       vector<int> singleArr2;

       for  (int i=0; i<m; ++i)

       {

           int arr2_val=0;

           int temp=arr2[i];

           for (int j=0; j<m; ++j)

           {

               if (temp==arr2[j])

                   ++arr2_val;

           }

               if (arr2_val==1)

                   singleArr2.push_back(temp);

       }

      for (size_t i=0; i<singleArr1.size(); ++i)

           for (size_t j=0; j<singleArr2.size(); ++j)

               if(singleArr1[i]==singleArr2[j])

                   mutual.push_back(singleArr1[i]);

}

int main()

{

   int n=0;

   int m=0;

   int value=0;

   int command = 0;

   cout<<"n(A)= "; cin>>n;

   cout<<"m(B)= "; cin>>m;

   int A[n];

   int B[m];

   cout<<"\n\nInput "<<n<<" elements of A array: ";

   Input(A, n);

   Print(A,n);

   cout<<"\n\nInput "<<m<<" elements of B array: ";

   Input(B,m);

   Print(B,m); 

   while(command!=123)

   {

   cout<<"\n~~~~~~~~~~~~~~~~~~ MENU ~~~~~~~~~~~~~~~~~~~~~~~~~";

   cout<<"\n- To input value for searching press 1.\n- To search for all of the unique mutual values press 2.";

   cout<<"\n- To input value for searching WITH SORT press 3.\n- To search for all of the unique mutual values WITH SORT press 4.";

   cout<<"\n- To exit press 123.  \nInput command:";

   cin>>command;

   if (command==1)

   {

       cout<<"\nInput the value to search for: ";

       cin>>value;

       if(Search(A, n, B, m, value))

           cout<<"\nThis value appears in both arrays only one time.\n";

       else

           cout<<"\nThis value doesn't match the conditions.\n";

   }

   else if (command==3)

   {

       cout<<"\n\nSorted arrays are: ";

       Sort(A,n);

       Print(A,n);

       Sort(B,m);

       Print(B,m);

       cout<<"\nInput the value to search for: ";

       cin>>value;

       if(Search(A, n, B, m, value)) 

           cout<<"\nThis value appears in both arrays only one time.\n";

       else

           cout<<"\nThis value doesn't match the conditions.\n";

   }

   else if(command==2)

   {

       cout<<"\n\nSearching for the mutual unique elements: ";

       vector <int> mutual;

       SearchWithoutVal(A, n, B, m, mutual);

       for(size_t i =0; i<mutual.size(); ++i)

           cout<<mutual[i]<<"  ";

   }

   else if (command==4)

   {

       cout<<"\n\nSorted arrays are: ";

       Sort(A,n);

       Print(A,n);

       Sort(B,m);

       Print(B,m);

        cout<<"\n\nSearching for the mutual unique elements: ";

       vector <int> mutual;

       SearchWithoutVal(A, n, B, m, mutual);

       for(size_t i =0; i<mutual.size(); ++i)

           cout<<mutual[i]<<"  ";

   }

   }

   return 0;

}


Результат виконання 

Висновки

Набуто практичні навички застосування алгоритмів пошуку та сортування. В результаті виконання лабораторної роботи розроблено функції для пошуку в одновимірних масивах посортованих та непосортованих та для їх сортування. Оцінка часу виконання показала, що пошук виконується швидше у посортованих масивах, адже завдяки тому, що однакові елементи знаходяться поруч, то для пошуку по масиву достатньо дійти до потрібного значення, а далі шукати немає сенсу, бо наступні значення будуть рівними або більшими за поточне. 


 

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

46970. Процесс формирования институтов и их устойчивость. Особенности формирования неформальных институтов 49.84 KB
  Теория поведения потребителя в рыночной экономике. Потребительское поведение общая и предельная полезности закон убывающей предельной полезности Большое значение для развития производства товаров и их предложения имеет поведение потребителя. Однако в поведении среднего потребителя можно отметить ряд общих черт: спрос потребителя зависит от уровня его доходов влияющих на размер личного бюджета потребителя; каждый потребитель стремится получить за свои деньги все что можно т. максимизировать совокупную полезность; средний...
46971. Романтизм 19 век 50 KB
  XIX века унаследовал от эпохи Просвещения внимание к проблеме воспитания и образования. в крупнейших странах Европы развивается система среднего образования которое являлось привилегией имущих классов. Осуществляются образовательные реформы в ходе которых создаются национальные системы образования. На повестку дня выносятся вопросы управления школьной системой взаимоотношения образования и религии школы и Церкви права личности на образование структуры и содержания школьного образования.
46972. Свариваемость сталей. Группы 50.5 KB
  Группы Способность стали к образованию качественного сварного соединения называют свариваемостью которая определяется внешними и внутренними факторами. По свариваемости стали подразделяют на четыре группы: 1 хорошая свариваемость; 2 – удовлетворительная свариваемость; 3 ограниченная свариваемость; 4 – плохая свариваемость. К Первая группа – хорошо сваривающиеся стали у которых Сэкв не более 025. Эти стали при обычных способах сварки не дают трещин сварка таких сталей выполняется без предварительного и сопутствующего подогрева без...
46973. Система методов государственного управления 50.5 KB
  Система методов государственного управления Основные вопросы: Понятие метода управления. Понятие метода управления. Осуществление управленческого воздействия предполагает наличие у субъекта – органа управления или должностного лица – знания о возможностях и границах воздействия его формах и средствах. Использование методов управления которые апробированы в опыте иных организаций и органов управления предполагает достаточную степень определенности в знании и понимании особенностей применения методов воздействия.
46974. СУЩНОСТЬ ТИПИЗАЦИИ И КЛАССИФИКАЦИИ 50.66 KB
  При всем многообразии деталей машиностроительного производства среди них можно обнаружить большое количество деталей аналогичной конфигурации близких по точности материалам требованиям предъявляемым к качеству обработки их основных поверхностей а также сравнительно мало отличающихся по размерам. язя Типизация технологических процессов может производиться по грем направлениям: 1 обработки отдельных поверхностей; 2 обработки отдельных типовых сочетаний поверхностей; 3 обработки заготовок. Работа по типизации технологических процессов...
46975. Модель развития PR-технологий (Джеймс Грюниг и Том Хант) 40.5 KB
  Суть ее заключается в следующем: используются любые средства для привлечения внимания общественности для оказания давления на нее. Информирование информирование общественности общественная осведомленность Д. Ее характеристики: регулярная работа со средствами массовой информации; распространение информации является главной целью PR – деятельности; информация должна быть точной и правдивой однако только позитивной негативные факты и события замалчиваются; как и первая модель информирование относится к...
46977. Аудит нематериальных активов организации 40.5 KB
  Соглно ПБУ14 07 для принятия актива в качве НМА н мо сущестное выполне опредых усл:отсут матвещ формывозмть идентифик использе в прве прод. Цель Ата НМАформире мнения о достоверности БО по разделу НМА и устане соответсвия применяемых Мек учета и н о операций с НМА действующму законодву РФ. При Ате проверяются= :постановка кля за наличием НМА ведение синтго учета по поступю и выбытию НМА начислие и отражие амортизации. Инфая база для Ара:НА поб у и н обл НМА;уч пол;регистры бух учета;первич док;БО.
46978. Настроечные базы 40.97 KB
  Для осуществления настройки станка относительно определенных поверхностей заготовки необходимо чтобы эти поверхности занимали на станке при смене заготовок неизменное положение относительно упоров станка определяющих конечное положение обрабатывающего инструмента. К таким поверхностям относятся опорные поверхности заготовки что и предопределяет широкое их использование в крупносерийном производстве в качестве опорных...