3673

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

Лекция

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

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

Украинкский

2012-11-05

40.5 KB

46 чел.

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

Алгоритми пошуку застосовуються для знаходження, наприклад, у масиві елемента з потрібними властивостями. Звичайно розрізняють постановки завдання пошуку для першого й останнього входження елемента. В усіх нижче викладених алгоритмах будемо вважати, що виробляється пошук у масиві 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();


 

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

54807. Площі паралелограмів 13.66 MB
  Підготовча робота: За тиждень до проведення уроку учні класу об’єднуються в три групи і отримують завдання застосовуючи знання теми Площі прямокутників і паралелограмів: 1. Обладнання: Мультимедійна дошка презентації вчителя і учнів набори паралелограмів картки консультанти картки інструкції картки з домашнім завданням креслярські інструменти банки з фарбою тестові завдання для роботи за комп’ютером. № Вид діяльності Час 1 Організаційний момент 4хв 2 Актуалізація опорних знань 6хв 3 Перегляд учнівських робіт 12хв 4...
54808. Паралелограми 736 KB
  2хв 3 Корекція зорового образу: робота з зашумленим рисунком; упізнання методом виключення 6хв 4 Встановлення взаємозв’язків різних видів паралелограмів за допомогою кіл Ейлера та опорної схеми 6хв 5 Фізкультхвилинка для зняття зорового напруження 15 хв 6 Корекція образно логічного сприйняття матеріалу шляхом встановлення відповідності між властивостями поданими в усній формі різних видів...
54809. «Учнівський парламент» - форма організації учнівського самоврядування в школі 189.5 KB
  Активну роль у підготовці сьогоднішніх школярів до реального суспільного самоврядування і формування в них готовності виконувати свій громадянський обовязок покликане відіграти учнівське самоврядування загальноосвітньої середньої школи. Однак сформована на сьогодні система організації діяльності учнівського самоврядування в школі відсутність відповідного соціального замовлення на практичну діяльність учнів законодавства в державному масштабі про трудову діяльність підлітків і учнівської молоді призвели до того що по суті учнівське...
54810. Універсальна модернізована одномісна учнівська парта 4.39 MB
  Стосовно запропонованої учнівської парти то вона має ряд переваг над стандартною. Буде методично правильно коли коли при вивченні графічної грамоти на уроках трудового навчання чи при виконанні графічних робіт на уроках креслення дані завдання виконувати не при горизонтальному положенні столика парти а при вертикальному. Щоб зробити вертикальне положення столика парти достатньо лівою рукою дістатися важіля в передній частині опустити його вниз і столик набуває...
54811. Holidays and traditions in Ukraine and English-speaking countries 1.3 MB
  Dear pupils. I am glad to see you again. The theme of our lesson is “Holidays and traditions in Ukraine and English-speaking countries.” Today we are going to read the text about traditions in English speaking countries and Ukraine, we’ll listen to the text about Thanksgiving Day in Canada and of course you’ll speak English and present your projects. Let’s start.
54812. Parties and Holidays 78.5 KB
  Objectives: to practice pupils’ listening and speaking skills; to enrich the pupils’ vocabulary; to train the usage of the lexical material in practice; to widen students’ knowledge about the celebration of different parties and holidays in Ukraine and English-speaking countries; to develop their critical thinking; to enrich their outlook;
54814. FOOD AND COOKERY 90 KB
  It is not a secret that Ukrainian people are big eaters. Our women cook very much and they cook tasty. But our men like to eat what our women cook and they are thankful for tasty dishes.
54815. Турнір знавців Паскаля 255 KB
  Алгоритмізація та програмування для учнів є більш складними розділами інформатики. Тому варто зробити декілька уроків трішки цікавішими, навіть розважальними. Це може бути, наприклад, узагальнюючий урок напередодні тематичного оцінювання, підсумковий урок теми.