75659

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

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

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

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

Украинкский

2015-01-24

338.16 KB

4 чел.

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

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

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

Кафедра ПЗ

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

}


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

Висновки

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


 

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

53743. Обобщающий урок по теме “Природа”. Урок - КВН 51 KB
  Природа Да все что нас окружает это природа. Природа прекрасна в любое время года. Весной мы можем наблюдать как вся природа просыпается от зимней спячки.
53744. Роль имени прилагательного в русском языке 88.5 KB
  Цель: Обучающая учить детей правильно использовать имена прилагательные в речи находить прилагательные и по существенным признакам определять предмет; Развивающая развивать критическое мышление умение ставить проблемные вопросы выдвигать гипотезы анализировать и сравнивать обобщать полученные данные и делать выводы; развивать устную и письменную речь учащихся; Воспитывающая создать условия для формирования познавательного интереса к русскому языку воспитания культуры общения в группе со сверстниками; воспитывать...
53745. Столетняя война 72 KB
  Учитель приветствует учеников и организует повторение ими материала прошлого урока. Учитель проводит фронтальный опрос класса по теме прошлого урока. которая подтвердила права и вольности церкви городов рыцарей баронов свободного населения Что такое совет двадцати пяти совет баронов который следил за исполнением Великой хартии вольностей; в случае нарушения условий этой хартии бароны могли начать военные действия против короля всяческими способами добиваться исправления нарушений Затем учитель заслушивает письменные ответы...
53746. Ателье мод 47 KB
  Как вы думаете какие Правильно основной материал для изготовления одежды это ткань. Что такое ткань Ткань изделие изготовленное путём плотного соединения накрест переплетённых нитей расположенных двумя рядами продольными основа и поперечными уток. Первая ткань которую мы с вами рассмотрим это хлопок. Преимущества хлопковой ткани: Мягкость Хорошая поглощающая способность в тёплое время Лёгкость в окраске Давайте с вами заполним табличку хлопковая ткань она натуральная или синтетическая Пощупайте хлопковую ткань она...
53747. Конструирование из бумаги. Изготовление новогодней елочки 95.5 KB
  Технологии: технология сотрудничества, деятельностный подход, активное обучение, технологии объяснительно-иллюстративного обучения (в основе которых информирование, просвещение учащихся и организация из репродуктивных действий с целью выработки у них общеучебных умений и навыков).
53748. Теорема Виета 95 KB
  Предметные результаты: наблюдать и анализировать связь между корнями и коэффициентами квадратного уравнения. Формулировать и доказывать теорему Виета, а также обратную теорему, применять теоремы для решения уравнений и задач.
53749. Прогнозирование экономических показателей. Модели финансового планирования 27.5 KB
  Экономический прогноз — это научно обоснованное предвидение возможных направлений и результатов развития субъектов хозяйствования и их структурных подразделений. Методы экономического прогнозирования можно условно объединить в две группы. Наверняка все из вас пускали самолетики лодочки красовались в треуголке из бумаги различных форм фигурок это и есть оригами. Однако независимые традиции складывания из бумаги хоть и не столь развитые как в Японии существовали среди прочего в Китае Корее Германии и Испании.
53750. День святого Валентина 43.5 KB
  Как они называются валентинки А знаете ли вы что согласно легенде в далекие времена жестокий римский император Клавдий II решил что одинокий мужчина без семьи и жены лучше сражается на поле битвы и запретил мужчинам жениться. Сегодня нам предстоит пусть с опозданием но изготовить валентинки для своих родных а может и любимых своими руками потому что мы знаем знаменитую пословицу: Лучше поздно чем ...
53751. Звери в лесу 48.5 KB
  Закрепить навык разметки по шаблонам, вырезание деталей сложной формы в виде встречного реза, выполнение алгоритма изготовления аппликации умение составлять композицию, намазывать детали клеем используя подкладной лист, приклеивать последовательно детали аппликации используя притирочный лист.