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();


 

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

42067. Решение задачи о назначениях 3.01 MB
  В ячейках B21:H21 находятся суммы значений соответствующих столбцов изменяемых ячеек. в B21 находится сумма ячеек B14:B20; в С21 находится сумма ячеек С14:С20; в D21 находится сумма ячеек D14:D20; в E21 находится сумма ячеек E14:E20; в F21 находится сумма ячеек F14:F20. в G21 находится сумма ячеек G14:G20; в H21 находится сумма ячеек H14:H20. В ячейках I14:I20 находятся суммы значений соответствующих строк изменяемых ячеек.
42068. Определение кратчайшего пути между вершинами ориентированного графа с циклами 2.43 MB
  Длины дуг могут определять различные характеристики: расстояние стоимость время пропускную способность и т. Определить наикратчайший путь между вершиной 1 и вершиной 7 на графе с циклами представленном на рис. Рис. Матрица транспортных расходов соответствующая данному графу представлена на рис.
42069. Изучение работы жидкостного U-образного манометра и комплекта приборов для измерения давления пневматической ветви ГСП 764 KB
  В процессе выполнения лабораторной работы закрепить знания по разделу Измерение давления и Дистанционная передача сигнала измерительной информации теоретического курса Технические измерения и приборы. Ознакомиться с принципом действия устройством преобразователя измерительного разности давления пневматического 13ДД11 в комплекте с вторичным прибором ПКР. Присоединив оба свободных конца трубки прибора к двум полостям с разными давлениями можно по разности уровней жидкости в приборе определить разность давлений.
42070. Решение задачи динамического программирования 659.5 KB
  Требуется перевезти груз из пункта 1 в пункт 10 с минимальными затратами на перевозку. Сетевой график дорог Стоимость перевозки груза из пункта s s=129 в пункт j j=2310 представлена в таблице Маршрут Расстояние Маршрут Расстояние 12 4 27 13 11 37 14 3 47 4 25 3 58 9 35 1 68 45 4 78 7 26 4 59 8 36 6 69 5 46 6 79 12 810 5 910 3 Все множество вершин пунктов разбивается на подмножества: . На первом этапе принимается решение через какой пункт принадлежащий второму подмножеству везти груз из пункта 1. На...
42071. Решение задачи о распределении ресурсов методом динамического программирования 610.5 KB
  Средства X выделенные kому предприятию приносит в конце года прибыль . Функции заданы таблично: X f1X f2X f3X f4X 1 8 6 3 4 2 10 9 4 6 3 11 11 7 8 4 12 13 11 13 5 18 15 18 16 Определить какое количество средств нужно выделить каждому предприятию чтобы суммарная прибыль равная сумме прибылей полученных от каждого предприятия была наибольшей. Пусть количество средств выделенных kому предприятию. Уравнения на м шаге удовлетворяют условию: либо kому предприятию ничего не выделяем: либо не больше того что...
42072. Изучение работы приборов для измерения давления электрической ветви ГСП 101.5 KB
  Ознакомиться с принципом действия устройством преобразователя измерительного Метран43 в комплекте с вторичным прибором и приобретают навыки в определении давления при помощи измерительных преобразователей типа Метран43. Снять статическую характеристику измерительного преобразователя Метран43.1 Преобразователи давления типа Метран43 Преобразователи разности давления типа Метран43 предназначены для промышленных систем автоматического контроля и систем в составе АСУ ТП на базе микропроцессорной техники работающих со...
42073. Нахождение оптимального решения по векторному критерию 362.5 KB
  Метод ведущего критерия – все критерии кроме самого важного заносятся в систему ограничений. Метод равных и наименьших относительных отклонений – оптимизируемые критерии включают в число неизвестных задачи а систему ограничений дополняют требованием равных относительных отклонений значений критериев в компромиссном решении от их экстремальных значений. Найти решение следующей трехкритериальной задачи Система ограничений: 1 Применим информационные технологии Excel для решения задачи. Для нахождения компромиссного...
42074. Расчет производственной программы технического обслуживания и текущего ремонта главной передачи автомобиля Ваз 2107 с разработкой планировочного решения зоны текущего ремонта 2.25 MB
  Двойные главные передачи устанавливают на автомобилях большой грузоподъемности для увеличения общего передаточного числа трансмиссии и повышения передаваемого крутящего момента. В этом случае передаточное число главной передачи подсчитывается как произведение передаточных чисел конической