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


 

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

19207. Движение в неоднородном магнитном поле 333 KB
  Лекция № 3. Движение в неоднородном магнитном поле. Дрейфовое приближение условия применимости дрейфовая скорость. Дрейфы в неоднородном магнитном поле. Адиабатический инвариант. Движение в скрещенных электрическом и магнитном полях. Общий случай скрещенных поля л...
19208. Аналогия световой и электронной оптики. Электронная оптика параксиальных пучков 735 KB
  Лекция № 4. Аналогия световой и электронной оптики. Электронная оптика параксиальных пучков. Движение заряженных частиц в аксиальносимметричном электрическом поле. Основные типы электростатических линз. IV. Электронная оптика. 4.1. Аналогия световой и электрон
19209. Движение заряженных частиц в аксиально-симметричном магнитном поле. Магнитные линзы 412.5 KB
  Лекция № 5. Движение заряженных частиц в аксиальносимметричном магнитном поле. Магнитные линзы. Фокусировка короткой катушкой. Магнитные квадрупольные линзы жесткая фокусировка. Магнитные электронные микроскопы. Аберрация электронных линз. V. Магнитные линзы. ...
19210. Ограничение тока пространственным зарядом в диоде. Формула Ленгмюра и Богуславского для плоских и цилиндрических электродов 325.5 KB
  Лекция № 6. Ограничение тока пространственным зарядом в диоде. Формула Ленгмюра и Богуславского для плоских и цилиндрических электродов. Учет начальных скоростей частиц. Образование виртуального катода. Предельная плотность тока пучка частиц в пролетном промежутке
19211. Расхождение пучков заряженных частиц под действием собственного объемного заряда 421.5 KB
  Лекция № 7. Расхождение пучков заряженных частиц под действием собственного объемного заряда. Прямолинейные пучки электронных лучей электронные пушки Пирса. VII. Формирование электронных и ионных пучков. 7.1. Расплывание пучков заряженных частиц под действи
19212. Электромагнитные ускорители плазмы. МГД приближение для описания динамики 269 KB
  Лекция 8 VIII. Плазменные ускорители. Электромагнитные ускорители плазмы. МГД приближение для описания динамики. Одножидкостная модель. Магнитное давление. Равновесие плазменной границы. Рельсотрон. 8.1. МГД приближение. Для описания ускорения плазмы магни...
19213. Термоэлектронная эмиссия. Статистический и термодинамические вывод формулы плотности тока термоэлектронной эмиссии 557.5 KB
  Лекция № 9. Термоэлектронная эмиссия. Статистический и термодинамические вывод формулы плотности тока термоэлектронной эмиссии. Влияние внешнего электрического поля Эффект Шоттки. Распределение термоэлектронов по энергиям. Средняя энергия термоэлектронов. Эксп
19214. Влияние поверхностной неоднородности материала катода на термоэмиссию 557 KB
  Лекция № 10. Влияние поверхностной неоднородности материала катода на термоэмиссию. Пленочные катоды. Оксидные катоды. Автоэлектронная эмиссия. Изменение температуры эмиттера при термо и автоэлектронной эмиссии. 9.7. Влияние поверхностной неоднородности материала...
19215. Фотоэлектронная эмиссия. Законы Столетова и Эйнштейна. Теория фотоэмиссии 476 KB
  Лекция № 11. Фотоэлектронная эмиссия. Законы Столетова и Эйнштейна. Теория фотоэмиссии. Кривая Фаулера. Применение фотоэмиссии в технике. Фотокатоды. XI. ФОТОэлектронная эмиссия. 11.1. Законы фотоэффекта. В широком смысле фотоэффект – это возникновение или измене