3673

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

Лекция

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

Алгоритми пошуку в одновимірних масивах Алгоритми пошуку застосовуються для знаходження, наприклад, у масиві елемента з потрібними властивостями. Звичайно розрізняють постановки завдання пошуку для першого й останнього входження елемента. В усіх ниж...

Украинкский

2012-11-05

40.5 KB

45 чел.

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

Алгоритми пошуку застосовуються для знаходження, наприклад, у масиві елемента з потрібними властивостями. Звичайно розрізняють постановки завдання пошуку для першого й останнього входження елемента. В усіх нижче викладених алгоритмах будемо вважати, що виробляється пошук у масиві A з N цілих чисел елемента, рівного X.

Лінійний пошук

Лінійний пошук здійснюється циклом (while ) з подвійною умовою. Перша умова контролює індекс на приналежність масиву, наприклад, (i<=N). Друга умова - це умова пошуку. У нашому випадку в циклі while ця умова продовження пошуку: (A[i]<>X), (A[i]=X). У тілі циклу звичайно пишеться тільки один оператор: зміна індексу в масиві.

Після виходу із циклу необхідно перевірити, по якому з умов ми вийшли. В операторі if звичайно повторюють перша умова циклу. Можна говорити про успішний пошук із циклом while при виконанні цієї умови.

Приклад 23.1. : Лінійний пошук

Console.WriteLine("Введите число ");

int n = Int32.Parse(Console.ReadLine());

int[] a = new int[n+1];

Random r = new Random();

int i, min, i1;

for (i = 1; i <= n; i++)

{

a[i] = r.Next(100);

Console.Write(a[i] + " ");

}

Console.WriteLine();

Console.WriteLine("Введите число ");

int m = Int32.Parse(Console.ReadLine());

i = 1;

while ((i < n) && (a[i] != m)) i++;

{

if (i < n) { Console.WriteLine("Перше входження" + m + "место" + i); }

else { Console.WriteLine("Нет такого елемента"); }

}

Console.ReadLine();

При пошуку останнього входження після уведення повинні йти оператори:

Console.WriteLine("Введите число ");

int n = Int32.Parse(Console.ReadLine());

int[] a = new int[n+1];

Random r = new Random();

int i, min, i1;

for (i = 1; i <= n; i++)

{

a[i] = r.Next(100);

Console.Write(a[i] + " ");

}

Console.WriteLine();

Console.WriteLine("Введите число ");

int m = Int32.Parse(Console.ReadLine());

i = n;

while ((i > 1) && (a[i] != m)) i--;

{

if (i > 1) { Console.WriteLine("Перше входження" + m + "место" + i); }

else { Console.WriteLine("Нет такого елемента"); }

}

Console.ReadLine();

Пошук бар’єром

Ідея пошуку з бар'єром полягає в тому, щоб не перевіряти щораз у циклі умова, пов'язане із границями масиву. Це можна забезпечити, установивши в масив так званий бар'єр: будь-який елемент, що задовольняє умові пошуку. Тим самим буде обмежена зміна індексу.

Вихід із циклу, у якому тепер залишається тільки умова пошуку, може відбутися або на знайденому елементі, або на бар'єрі. Таким чином, після виходу із циклу перевіряється, не чи бар'єр ми знайшли? Обчислювальна складність пошуку з бар'єром менше, ніж у лінійного пошуку, але також є величиною того ж порядку, що й N - кількість елементів масиву.

Існує два способи установки бар'єра: додатковим елементом або замість крайнього елемента масиву.

Приклад 23.2.: Пошук з бар'єром

Console.WriteLine("Введите число ");

int n = Int32.Parse(Console.ReadLine());

int[] a = new int[n+2];

Random r = new Random();

int i, min, i1;

for (i = 1; i <= n; i++)

{

a[i] = r.Next(100);

Console.Write(a[i] + " ");

}

Console.WriteLine();

Console.WriteLine("Введите число ");

int m = Int32.Parse(Console.ReadLine());

a[n + 1] = m;

i = 1;

while (a[i] != m) i++;

{

if (i <=n ) { Console.WriteLine("Перше входження" + m + "место" + i);

else { Console.WriteLine("Нет такого елемента"); }

}

Console.ReadLine();

Двійковий (БІНАРНИЙ) пошук

Алгоритм двійкового пошуку можна використати для пошуку елемента із заданою властивістю тільки в масивах, упорядкованих по цій властивості. Так при пошуку числа із заданим значенням необхідно мати масив, упорядкований по зростанню або по убуванню значень елементів. А, наприклад, при пошуку числа із заданою сумою цифр масив повинен бути впорядкований по зростанню або по убуванню сум цифр елементів.

Ідея алгоритму полягає в тому, що масив щораз ділиться навпіл і вибирається та частина, де може перебувати потрібний елемент. Розподіл триває поки частина масиву для пошуку більше одного елемента, після чого залишається перевірити цей елемент, що залишився, на виконання умови пошуку.

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

У процесі роботи алгоритму двійкового пошуку розмір фрагмента, де цей пошук повинен тривати, щораз зменшується приблизно у два рази. Це забезпечує обчислювальну складність алгоритму порядку логарифма N по підставі 2, де N - кількість елементів масиву.

Приклад 23.3. : Пошук в упорядкованому по зростанню масиві першого входження числа X.

Console.WriteLine("Введите число ");

int n = Int32.Parse(Console.ReadLine());

int[] a = new int[n+2];

Random r = new Random();

int i;

for (i = 1; i <= n; i++)

{

a[i] = r.Next(100);

Console.Write(a[i] + " ");

}

Console.WriteLine();

for (i=1; i<=n-1;i++)

for (int j = 1; j <= n - 1; j++)

{

if (a[j] > a[j + 1])

{

int b = a[j]; a[j] = a[j + 1]; a[j + 1] = b;

}

}

for (i = 1; i <= n; i++)

{

Console.Write(a[i] + " ");

}

Console.WriteLine();

Console.WriteLine("Введите число ");

int m = Int32.Parse(Console.ReadLine());

int left = 1; int right = n;

while (left < right)

{

int c = (left + right) / 2;

Console.WriteLine(left+ " " + right + " " +c);

if (m > a[c]) { left = c + 1; } else { right = c; }

}

if (m == a[left]) { Console.WriteLine("Перше входження" + m + "место" + left); }

else { Console.WriteLine("Нет такого елемента"); }

 

 

Console.ReadLine();


 

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

53189. ГРА НА УРОЦІ АНГЛІЙСЬКОЇ МОВИ ЯК ЗАСІБ ПІДВИЩЕННЯ ПІЗНАВАЛЬНОЇ АКТИВНОСТІ ШКОЛЯРІВ 83 KB
  У школярів молодшого віку переважають ігрові інтереси, довільна поведінка, наочнообразне мислення, практичне ставлення до розвязування завдань. Зважаючи на все це, доцільно у роботі з ними на уроках іноземної мови систематично застосовувати елементи гри у поєднані з бесідою, елементами самостійної роботи.
53190. Інтерактивна ділова гра ток-шоу «Я так думаю» 37.5 KB
  Правила гри: Усі учасники мають рівні права; Кожен учасник має право висловити свою думку; Думка кожного має бути почута врахована та прийнята. Учасники ділової гри: всі педагогічні працівники. Загальний сценарій: учасники об’єднуються в чотири групи – Батьки Діти Педагоги та Експерти; ведучий роз’яснює мету гри загальний сценарій та правила гри; групова гра: розігрування ситуації відповідно до обраних ролей; міжгрупова дискусія керована ведучим; підсумок гри за допомогою експертів.
53191. Гра як засіб всебічного розвитку учнів 139.5 KB
  За її допомогою діти пізнають світ. В грі діти перевіряють свою силу і спритність у них виникають бажання фантазувати відкривати таємниці і прагнути чогось прекрасного. Захопившись грою діти не помічають що навчаються до активної діяльності залучаються навіть найпасивніші учні. Захопившись грою діти не помічають що навчаються.
53192. Гра не тільки розважає, а й здоров’я додає! 94.5 KB
  Від ставлення людини до особистого здоров’я залежить його збереження та зміцнення. Одне з найважливіших завдань сучасної школи – навчити дітей та їх батьків берегти і зміцнювати своє здоров’я. Вчитель повинен сформувати в учнів свідоме ставлення до свого здоров’я надати життєві навички здорового способу життя та безпечної для здоров’я поведінки.
53193. Літературна гра на тему: Шевченко - художник 32.5 KB
  Шевченка створена на тему його однойменної поеми Катерина Картина проектується на екран. На екран проектується репродукція картини Т.На екран проектується обкладинка першого видання Кобзаря. ВовчкуАвтопортрет зі свічкою Репродукція проектується на екран.
53194. Гра «Поле чудес» План-конспект узагальнюючого уроку на тему «Світлотінь» для 6 класу 308 KB
  Завдання можуть бути суто теоретичними а можуть чергуватися практичні та теоретичні питання. Нас чекають цікаві завдання відкриття призи. Познайомимося з умовами гри: Розподіл барабана на сектори: Кожен сектор має своє позначення: Намальований пензлик це означає що гравуць отримує практичне завдання виконати в кольорі аквареллю на папері пейзаж натюрморт розмивання набризк і т. Намальований олівець практичне завдання виконати простим олівцем малюнок геометричне тіло з світлотінню глечик вазу і т.
53195. Фізико-математична гра «Щасливий випадок» 241.5 KB
  Правила: В цьому раунді кожній команді буде задано деяку кількість простих запитань з математики, інформатики, фізики та астрономії за обмежений час (1 хв.) Кожна правильна відповідь оцінюється 1 балом. Приймаються лише перші відповіді команди. Якщо ніхто з учасників команди не знає відповіді на запитання, можна говорити «Пас» або «Далі». Очки при цьому не нараховуються.
53196. Гра – тренінг «Обираємо професію разом» 41.5 KB
  Учитель: одна мудра людина сказала: Щастяце коли хочеться іти на працю а у вечорі йти додому Просто правда Але тільки на перший погляд. проводила тест на визначення профорієнтації за результатами цього тесту ви об’єднались в групи: 1 людина людина; 2 людина – техніка; 3 людина – природа; 4 людиназнакова система; 5 людина мистецтво. Завдання 1: на столі знаходяться речі дивлячись на них ви повинні відповісти на такі запитання: людина – людина: 1. Яка ємкість одноразового стаканчика людина техніка: 1.