11 клас (академ). Сортування одновимірних масивів. Пошук заданого значення у впорядкованому масиві. - 11 клас (академічний) - Інформатика - Каталог статей - Кабінет інформатики Черкаської СПШ №20
Кабінет 208
Головна | Реєстрація | Вхід
П`ятниця, 09.12.2016, 19:24
Меню сайту
Форма входу

Категорії розділу
5 клас [11]
6 клас [24]
7 клас [16]
8 клас [15]
9 клас [25]
10 клас (стардарт) [17]
10 клас (академічний) [23]
11 клас (стандарт) [21]
11 клас (академічний) [33]
Головна » Статті » Інформатика » 11 клас (академічний)

11 клас (академ). Сортування одновимірних масивів. Пошук заданого значення у впорядкованому масиві.
Сортування одновимірних масивів. 
Пошук заданого значення у впорядкованому масиві.


Багато програм на опрацювання значень елементів одновимірного працюватимуть значно швидше, якщо значення його елементів будуть упорядковані за зростанням або за спаданням. Це стосується перш за все задач пошуку потрібних значень серед значень елементів масиву.

Існує більше 10 різноманітних методів сортування одновимірного масиву. Одні з них виконуються швидше, інші повільніше, одні – більш складні за своєю логічною структурою, інші – простіші. Ми розглянемо один з методів сортування одновимірного масиву – метод вибору.

Сутність цього методу полягає в наступних діях:

1.        визначити значення найменшого елемента в усьому масиві і обміняємо його зі значенням першого елемента;

2.        визначити значення найменшого елемента в усьому масиві, крім першого, і обміняємо його зі значенням другого елемента;

3.        продовжити вказані дії N-1 раз.

Продемонструємо це метод на прикладі. Нехай нам потрібно впорядкувати за зростанням такий одновимірний масив з 6 елементів (табл. 2.5 стор. 110, рядок 0):

Процедура для реалізації цього методу має вигляд:

var a: array [1..10] of Integer; i, j, min, nmin: Integer;

begin

  for i := 1 to 10 do a[i] := StrToInt(Memo1.Lines[i-1]);

  for i := 1 to 9 do begin

     min := a[i]; nmin := i;

     for j := i+1 to 10 do  if a[j] < min then begin  min := a[j]; nmin := j; end;

     a[nmin] := a[i]; a[i] := min;

  end;

  Memo2.Lines.Clear;

  for i := 1 to 10 do Memo2.Lines.Append (IntToStr(a[i]))

end;

 

Повернемось Задачі 3 (пошук потрібного значення серед значень елементів масиву).

За умови, що масив невпорядкований та ситуації, що даного числа в масиві немає, потрібно буде порівняти дане число зі значеннями усіх елементів масиву. І якщо кількість елементів масиву велика, наприклад, 100 000, то й число порівнянь (а значить і час виконання проекту) може бути досить великим. Такий самий результат з часом виконання проекту нас очікуватиме, якщо шукане значення зберігається у прикінцевих елементах масиву.

Якщо масив впорядкований, то для з’ясування, чи є дане число в масиві, крім перебору  існують значно ефективніші методи. Один з таких методів пошуку заданого числа в одновимірному масиві називається методом половинного (бінарного) пошуку.

Пояснимо його на прикладі. Нехай маємо впорядкований за зростанням масив з 10 чисел: 2, 5, 8, 12, 13, 16, 17, 20, 22, 30 і деяке дане число х. Порівняємо це число із значенням елемента масиву, який знаходиться посередині масиву (з числом 13). Якщо дане число х дорівнює 13, то воно в масиві є, якщо ні, то з’ясуємо, чи більше дане число числа 13 (х>13). Якщо так, то його потрібно шукати тільки серед правої половини масиву, якщо ні, то тільки серед лівої половини масиву. Таким чином область пошуку звужується вдвічі. На наступному кроці поступаємо так саме: порівнюємо дане число із значенням елемента масиву, який знаходиться посередині тієї частини масиву, яка залишилися для пошуку. Знову або дане число дорівнює значенню цього елемента масиву, або залишаємо для пошуку або ліву, або праву половини тієї частини масиву, що залишилася, тобто область пошуку знову зменшується вдвічі.

Такий метод пошуку є значно ефективнішим, ніж попередній, бо значно швидше приводить до результату, особливо для великих N (максимум за [log2N] +1 кроків, де N – кількість елементів у масиві, а квадратними дужками тут позначена ціла частина числа).  Тобто, якщо є впорядкований масив із 1000 елементів, то звичайним перебором, щоб знайти значення, занесене до 998-го елементу масиву, потрібно виконати як мінімум 997 порівнянь, то методом бінарного пошуку достатньо виконати не більше 10 порівнянь ([log21000]+1=10).

Процедура для реалізації цього методу для впорядкованого масиву з 10 цілих чисел:

var a: array [1..10] of Integer; i, x, left, right, m: Integer; f: Boolean;

begin

  for i  := 1 to 10  do a[i] := StrToInt(Memo1.Lines[i-1]);

  x := StrToInt(Edit1.Text);

  left := 1;    right:= 10;    f := false;

  while (left <= right) and not f do begin

m := (left + right) div 2; // Номер елемента посередині частини масиву

if x > a[m] then left := m+1 // Зміна початкового номер елемента частини масиву

   else if x < a[m] then right := m-1 // Зміна останнього номера елемента частини масиву

else f := true; // Число в масиві знайшлося

  end;

  if f then Edit1.Text:='Число в масиві є' else Edit1.Text:='Числа в масиві немає';

end;


Домашнє завдання (1 хв)
 

§2.11 пит. 1-16 стор. 112 Впр. 6, 8 стор. 113   

Підготуватись до пр/роботи №11

Категорія: 11 клас (академічний) | Додав: admin (30.09.2013)
Переглядів: 1462
Пошук
Статистика

Онлайн всього: 1
Гостей: 1
Користувачів: 0
Copyright MyCorp © 2016
Безкоштовний хостинг uCoz