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


 

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

21024. Информационные системы и технологии. Контур «Логистика» 504 KB
  Процесс реализации регламентируют следующие документы: прайслисты документыоснования счета расходные накладные на отпуск МЦ складские ордера. Перейдя в модуль Настройка проверьте статус ДО на продажу: Настройка =Настройка= Настройка Настройки Галактики Логистика Документы Управление сбытом ДО на продажу Значения по умолчанию Статус оформляемый. Сформируем счет на продажу: Управление сбытом Документы Счета ДО на продажу [F7] формирование нового ДО. Сформируем накладную на отпуск МЦ: Управление сбытом ...
21025. Контур «Бухгалтерский учет» Теоретические положения 253.5 KB
  Теоретические положения Прайслисты удобно использовать в бизнеспроцессах операций сбыта для определения отпускной цены. В прайслисты включаютсятовары или услуги описанные в каталоге МЦ или каталоге услуг. Каждый товар либо услуга могут быть представлены в нескольких прайслистах причем иметь в них разные цены. Для формирования прайслиста подадим команды Управление сбытом Прайслисты Формирование рис.
21026. Контур «Бухгалтерский учет» Финансово-расчетные операции (ФРО 1.36 MB
  С другой стороны при формировании документов в каждом из этих модулей можно вызвать для выполнения Типовые хозяйственные операции ТХО настройка которых выполняется в том числе и в модуле ХозОперации.2 ТХО можно выполнить только войдя непосредственно в модуль ХозОперации. В данном разделе рассматриваются вопросы относящиеся к ТХО. В этом случае необходимы три ТХО.
21027. ЗНАКОМСТВО С ERP СИСТЕМОЙ «ГАЛАКТИКА» 605.5 KB
  После запуска системы Галактика на экране отображается Главное меню системы фрагмент Главного меню показан на рис. Панель главного окна системы Для запуска модуля достаточно щелкнуть мышью по соответствующей кнопке Главного меню. Кнопки Главного меню снабжены всплывающими подсказками которые появляются при установке указателя мыши на кнопку меню. Для перемещения панели Главного меню необходимо установить указатель мыши на логотип корпорации Галактика в левом верхнем углу панели нажать левую кнопку мыши и удерживая ее переместить...
21028. ЗНАКОМСТВО С СИСТЕМОЙ АДМИНИСТРИРОВАНИЯ КОМПЛЕКСА «ГАЛАКТИКА» «SUPPORT» 257.5 KB
  Модуль Консоль администратора является интсрументом администраторов системы и доступен только администраторам. Модуль предназначен для интерактивного мониторинга и администрирования лицензий пользователями контуров и компонентов системы Галактика ERP. Консоль администратора позволяет: Регистрировать пользователей систем Регистрировать группы пользователей систем Регистрировать системы в которых осуществляется администрирование использования лицензий пользователями Отслеживать захват лицензий каждым пользователем определить сколько...
21029. Модуль логистики и управления системой «ГАЛАКТИКА ERP» 39 KB
  Сделать это можно из главного меню программы пролистав до самого конца или из открывшегося окна перейдя следующим образом: меню Сервис Главное меню Остальное Остальное Настройка. Путь от главного меню: Настройка Заполнение каталогов Организации и банки. Введите группы контрагентов которые необходимы вашей организации функция локального меню Создать группу организаций CtrlF7. Для этого установите курсор на необходимую группу и вызовите функцию локального меню Добавить организацию в текущую группу.
21030. Модуль настройки системы «Галактика ERP» Настройка общесистемных каталогов 173.5 KB
  Настройка осуществляется в модуле Настройка. Настройка общесистемных каталогов Каталог сотрудников предприятия Для того чтобы перейти в к настройке этого каталога необходимо зайти в модуль Заработная плата. Настройка каталога материальноответственных лиц Для настройки этого каталога необходимо перейти в модуль Настройка. Далее переходим по меню следующим образом: Настройка Заполнение каталогов Материальноответственные лицаМОЛ.
21031. Модуль настройки системы «Галактика ERP» Настройка каталогов материальных ценностей (МЦ) 215 KB
  Настройка осуществляется в модуле Настройка. Настройка общесистемных каталогов Настройка каталогов материальных ценностей МЦ В каталоге МЦ содержатся сведения обо всех товарноматериальных ценностях ТМЦ проходящих через организацию. Путь от главного меню: Настройка =Настройка= Настройка. Заполнение каталога МЦ Путь от главного меню: Настройка =Настройка= Заполнение каталогов МЦ Каталог МЦ.
21032. Модуль настройки системы «Галактика ERP» Настройка системы под пользователя и организацию 163 KB
  В этой части будет рассмотрена общая настройка системы Галактика ERP. Настройка осуществляется в модуле Настройка. Настройка системы под пользователя и организацию Команды для перехода к настройке параметров системы: Настройка =Настройка= Настройка Настройка рис. Ниже приводятся команды путь от Главного меню и значения некоторых важных параметров настройки системы: Настройка =Настройка= Настройка Настройки Галактики Оперативный контур.