75659

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

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

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

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

Украинкский

2015-01-24

338.16 KB

3 чел.

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

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

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

Кафедра ПЗ

Лабораторна робота №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;

}


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

Висновки

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


 

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

83509. Поняття і джерела права міжнародних організацій 34.3 KB
  Право міжнародних організацій є сукупністю норм що регулюють процес утворення діяльності та припинення діяльності організації взаємодії з іншими субєктами міжнародного права та міжнародних відносин. Право міжнародних організацій як самостійна галузь міжнародного права складається з двох груп міжнародних норм утворюючих: поперше внутрішнє право організації норми що регулюють структуру організації компетенцію її органів і порядок роботи статус персоналу інші правовідносини і подруте зовнішнє право організації норми договорів...
83510. Поняття, характеристика та види міжнародних організацій 36.26 KB
  Характерні риси організації: створення шляхом укладення особливого договору що є засновницьким актом; \'система постійно діючих органів; автономний статус і відповідні функції. За характером членства міжнародні організації поділяються а міжурядові та неурядові. За колом учасників міжнародні міжурядові організації поділі ються на універсальні відкриті для участі всіх держав світу ООН її спеціалізовані установи і регіональні членами яких можуть бути держави одного регіону Африканський Союз Організація америкав ських держав. Міжурядові...
83511. Правовий статус і міжнародна правосуб’єктність міжнародних організацій 36.36 KB
  В основі правової природи міжнародних організацій лежить наявність спільних цілей і інтересів держав-членів. Для правової природи міжнародної організації істотним є те, що її цілі і принципи, компетенція, структура і т.п. має узгоджену договірну основу.
83512. Функції міжнародних організацій 32.88 KB
  У багатщ випадках держави зобов\'язані регулярно представляти доповіді про виконання ними норм міжнародного права і актів організації у відповідній області особливо в області прав людини. Оперативна функція полягає в досягненні цілей організації шляхом безпосередньої діяльності власними засобами організації. Організації надають економічну науковотехнічну і іншу допомогу консультаційні послуги.
83513. Правова природа актів міжнародних організацій 44.29 KB
  Так у сучасній міжнародноправовій літературі звертається увага на подібність процедури розробки міжнародних стандартів з одного боку і процесом вироблення міжнародної угоди в рамках міжнародної організації з іншого. Крім того висловлюється позиція що регламенти міжнародних організацій є результат їх законодавчої або Квазізаконодавчо діяльності. За своєю юридичною силою акти міжнародних орагнізацій можуть бути як рекомендаційними так і носити юридично обов\'язковий характер.
83514. Створення і припинення діяльності міжнародних організацій 34.13 KB
  Міжнародні організації як вторинні похідні суб’єкти міжнародного права створюються державами. Процес створення нової міжнародної організації проходить в три етапи: ухвалення засновницького документу; створення матеріальної структури організації; скликання головних органів що свідчить про початок функціонування організації. Злагоджене волевиявлення держав щодо створення міжнародної організації може бути зафіксовано 2 способами: у міжнародному договорі; у рішенні вже існуючої міжнародної організації. Укладення міжнародного договору припускає...
83515. ООН: цілі і принципи діяльності 37.81 KB
  Організація Об’єднаних Націй ООН універсальна міжнародна міжурядова організація що діє на підставі Статуту підписаний 26 червня 1945 р. Статут ООН є універсальним загальнообов’язковим міжнародним договором що закріплює основи сучасного міжнародного правопорядку. ООН переслідує наступні цілі: підтримувати міжнародний мир і безпеку і з цією метою вживати ефективні колективні заходи для запобігання і усунення загрози миру і придушення актів агресії або інших порушень миру й проводити мирними засобами вирішення міжнародних спорів;...
83516. Рада безпеки ООН, її функції. Членство. Порядок прийняття рішень 36.98 KB
  Рада Безпеки є одним з головних органів ООНщо виконує основну роль в підтримці міжнародного миру і безпеки та згідно з п. Рада безпеки уповноважена розслідувати будьякий спір або ситуацію для визначення того чи не може продовження цього спору або ситуації загрожувати міжнародному миру і безпеці. Сторони спору продовження якого може загрожувати міжнародному миру або безпеці мають право самостійно ухвалити рішення про його передачу на вирішення Ради Безпеки.
83517. Генеральна Асамблея ООН, її структура. Порядок роботи та порядок прийняття рішень 36.41 KB
  Порядок роботи та порядок прийняття рішень Генеральна Асамблея один з головних органів ООН що складається з представників всіх державчленів ООН. Делегація кожної державичлена ООН складається не більш ніж з п\'яти представник і п\'яти їх заступників. Генеральна Асамблея в межах Статуту ООН має право обговори вати та робити рекомендації членам ООН або Раді Безпеки з будьяких питань або справ в межах Статуту крім питань що знаходяться розгляді Ради Безпеки стосовно будьякого спору або ситуації.