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


 

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

48469. Аэропорт как составная авиатранспортной системы 69 KB
  В случае нарушения равновесия могут возникать такие последствия: неполное функционирование аэропорта и авиакомпаний; неудовлетворительные условия для пассажиров; неадекватне условия для пассажиров; недостаточность обеспечения полетов; ненадежность функционирования систем аэропорта; повышение стоимости перевозок для пользователей; ухудшение обеспечения авиакомпаний оборудованием; понижение уровня обслуживания пассажиров.обслуживание пассажиров; 2. Авиационная деятельность связана с обеспечением полетов обслуживанием...
48470. Схемотехника аналоговых электронных устройств. Качественные показатели и характеристики аналоговых электронных устройств 975.68 KB
  В результате изучения дисциплины студенты должны: знать принципы функционирования основных аналоговых электронных устройств и их базовых элементов особенности схемотехники этих устройств в том числе и учитывающие возможность их реализации по интегральной технологии и необходимость обеспечения стабильности их работы; знать и уметь применять методы анализа усилительных и других аналоговых электронных устройств основанные на использовании эквивалентных схем; уметь составлять эти схемы на базе принципиальных схем анализируемых устройств; ...
48471. Моделирование систем. Конспект лекций 20.26 MB
  Морозов Моделирование систем Конспект лекций Рязань 2011 Введение Моделирование как создание некой системы системымодели второй системы имеющей определенное сходство с системойоригиналом первой системой. Теория моделирования применяется: а при аналитическом отыскании зависимостей соотношений и решений конкретных задач; б при обработке результатов экспериментальных исследований и испытаний различных технических устройств в тех случаях когда результаты представлены в обобщенных критериальных зависимостях; в при...
48472. РЕКОМЕНДАЦИИ ПО СОВЕРШЕНСТВОВАНИЮ СИСТЕМЫ МОТИВАЦИИ ПЕРСОНАЛА ОАО «ЭТК» 543.5 KB
  Путь к эффективному управлению человеком лежит через понимание его мотивации. Только зная то, что движет человеком, что побуждает его к деятельности, какие мотивы лежат в основе его действий, можно попытаться разработать эффективную систему форм и методов управления им.
48473. Виробничий менеджмент. Конспект лекцій 464.5 KB
  Все це вимагає від керівників глибокої теоретичної підготовки та вміння ефективного управління організаціями. Тому на сьогоднішній день актуальною стає проблема підготовки спеціалістів з управлінням виробництвом. Це поьребує від фахівців виробничої сфери чітко усвідомити закони принципи і методи ефективного управління оперативною діяльністю всього відтворювального циклу. Менеджмент передбачає управління всією різноманітною функціональною діяльністю організації.
48474. ДЕНЬГИ. КРЕДИТ. БАНКИ 1.15 MB
  Необходимость возникновение сущность и функции денег Происхождение денег и их эволюция. Предпосылки появления денег и их значение и необходимость. Сущность и функции денег Роль денег в экономике и социальной сфере. Особенности проявления роли денег при разных моделях экономики Лекция 2.
48475. Компьютерная (машинная) графика 418.5 KB
  Таким образом появляется возможность хранить не все точки изображения а координаты узлов примитивов и их свойства цвет связь с другими узлами и т. это требует пересчета сравнительно небольшого числа координат узлов. Таким образом любой цвет можно разложить на оттенки основных цветов и обозначить его набором цифр цветовых координат. Векторы представляют собой математическое описание объектов относительно точки начала координат.
48476. ДОКУМЕНТАЦИЯ БУХГАЛТЕРСКОГО УЧЕТА 130 KB
  Первичные документы Для непрерывного отражения объектов бухгалтерского учета необходимо фиксировать каждую хозяйственную операцию. Затем осуществляются регистрация и экономическая группировка их данных в системе синтетических и аналитических счетов бухгалтерского учета. Формы регистров бухгалтерского учета разрабатываются и рекомендуются Министерством финансов РФ органами которым федеральными законами предоставлено право регулирования бухгалтерского учета или федеральными органами исполнительной власти.
48477. Основные понятия налогообложения участников внешнеэкономической деятельности 152.5 KB
  Резиденты: а физические лица являющиеся гражданами Российской Федерации за исключением граждан Российской Федерации признаваемых постоянно проживающими в иностранном государстве в соответствии с законодательством этого государства; б постоянно проживающие в Российской Федерации на основании вида на жительство предусмотренного законодательством Российской Федерации иностранные граждане и лица без гражданства; в юридические лица созданные в соответствии с законодательством Российской Федерации; г находящиеся за пределами территории...