WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Пошук за ключем у масиві - Реферат

Пошук за ключем у масиві - Реферат

(2,-1). Точка (3,0) опинилася всередині його, точка (2,2) - на стороні.
Комп'ютер не бачить плану саду, тому доведеться пояснити йому докладніше, як одержати потрібну оболонку. Один із способів оснований на тім, що спочатку точки сортуються за зростанням, наприклад, координати Y. Тепер це не просто множина, а певним чином упорядкована послідовність. Врахування цього дозволяє створити простий та прозорий алгоритм побудови оболонки.
За початкову точку можна взяти точку із найменшою координатою Y. Таких точок може бути кілька - виберемо з них ту, координата X якої найменша. Далі ми будуємо дві послідовності точок, починаючи обхід множини як зліва, так і справа. Назвемо їх лівою та правою. Друга точка додається до обох. Далі після обробки кожної точки будується оболонка тієї множини точок, які вже розглянуто.
Нехай A та B - остання й передостання точки послідовності, побудованої при обході зліва, C - нова точка. Якщо при переході з відрізка BA на відрізок AC ми робимо лівий поворот або рухаємося по прямій, то точку A можна вилучити з послідовності. Так само треба вилучити й точку B, якщо перед нею в послідовності є точка Z, така що, ZBC - лівий поворот або відрізок прямої. І так далі. Нарешті, або дві останні точки послідовності разом із новою утворюють правий поворот, або всі, крім першої, вилучено.
Визначення, чи утворюють точки BAC лівий поворіт, здійснюється за знаком векторного добутку , як у прикладі 7.5 з підрозділу 7.4. Є особливий випадок обробки точки - коли дві останні точки послідовності розташовані горизонтально. Якщо нова точка належить тій же горизонталі, то векторний добуток рівний 0. Нова точка "витісняє" останню точку A, коли відрізок BA продовжується нею або вона розташована ліворуч від A .
Після обробки послідовності нова точка додається до неї. Виключенням є випадок, коли нова точка лежить на відрізку між останніми точками лівої та правої послідовностей обходу. Перевірити це дуже просто, оскільки з упорядкованості точок за координатою Y випливає, що такий відрізок може бути лише горизонтальним.
Симетричним чином точка додається (або не додається) до правої послідовності.
Упорядкованість точок по вертикалі забезпечує, що при обробці нової точки не виникає одночасно лівого повороту до неї з кінця лівої послідовності та правого - з правої. Крім того, якщо точка була кінцевою в обох послідовностях, то після обробки наступної точки вона буде вилучена принаймні з однієї з них. Упорядкованість також гарантує, що необроблені точки лежать не нижче від тих, за якими побудовано поточну оболонку. Врахування усіх цих властивостей суттєво спрощує алгоритм.
Отже, після обробки останньої точки ми маємо ліву та праву послідовності. Результат ми одержимо, друкуючи, наприклад, ліву послідовність з її початку, а потім праву з її кінця. Це відповідає обходу нашого саду ззовні за годинниковою стрілкою.
Перейдемо до реалізації алгоритму. Координати точок подамо масивом структур з полями X і Y. При його сортуванні ми не будемо переставляти місцями значення його елементів, тобто структури. Створимо допоміжний масив індексів і відсортуємо його так, щоб перше значення в ньому вказувало на структуру з найменшим значенням Y, друге - на структуру з другим за порядком значенням тощо. Наприклад, якщо послідовні структури мають координати Y
10 -1 33 15 0,
то значеннями послідовних елементів допоміжного масиву є номери структур у їх упорядкуванні:
2 5 1 4 3.
У сортуванні масиву структур A за їх координатою Y з допоміжним індексовим масивом замість порівнянь полів та обмінів значень елементів A[i] та A[k] відбуваються порівняння елементів A[B[i]].Y і A[B[k]].Y та обміни значень B[i] і B[k].
Після сортування відшукаємо початкову точку - з найменшою координатою X серед тих, що мають найменшу координату Y.
Ліву та праву послідовності зберігатимемо в додатковому масиві індексів. Ліва заповнює його з початку, права - з кінця. Нехай всього точок n. Посилання на початкову точку запам'ятаємо двічі в крайніх елементах масиву. З точок, що залишилися, лише остання може з'явитися в обох послідовностях одночасно.Тому для них достатньо n елементів масиву. Отже, всього нам потрібно n+2 елементи.
Наведемо лише необхідні означення. Доповнити їх до програми залишається вправою.
const mx=5000; {максимальна кількість точок}
type int=integer; pnt=record x, y : int end;
var a : array[1 .. mx] of pnt; {масив точок}
b, {індексовий масив}
c : array[0..mx+1]of int; {масив для лівої та правої послід-тей}
n : int; {кількість точок}
ll, rr : int;{індекси останніх елементів посл-тей у масиві c}

procedure init;
var k : int; km, xm, ym : int; …
begin
Читання n точок у масив A;
Сортування за неспаданням координати Y - результатом є масив B, такий, що A[B[1]].Y<= … <= A[B[n]].Y;
Вибір початкової точки:
k:=2; km:=1; ym:=a[b[1]].y; xm:=a[b[1]].x;
while (k<=n) and (a[b[k]].y=ym)do
begin
if a[b[k]].x 0 ) or ( x3-x2=0 )
end;
function right ( tp : pnt ) : boolean;
var x1, y1, x2, y2, x3, y3 : real;
begin
y1:=a[c[rr+1]].y; y2:=a[c[rr]].y; y3:=tp.y;
x1:=a[c[rr+1]].x; x2:=a[c[rr]].x; x3:=tp.x;
if (y3=y2) and (x3=x2) then
right:=false else
if (y2=y1) and (y3=y2) then
right:=( (x2-x1)*(x3-x2)>0 ) or ( x3-x2>0 )
else right:=( (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)=1) and left(tp) do ll:=ll-1;
if (tp.y > a[c[ll]].y) or (tp.y > a[c[rr]].y)or
not( (tp.x>a[c[ll]].x)and(tp.xthen begin ll:=ll+1; c[ll]:=b[k] end;
while (rr a[c[ll]].y) or (tp.y > a[c[rr]].y)or
not( (tp.x>a[c[ll]].x)and(tp.xthen begin rr:=rr-1; c[rr]:=b[k] end;
end;
end;
procedure done;
var k : int;
begin
for k:=0 to ll do writeln(a[c[k]].x, ' ', a[c[k]].y);
if not((a[c[ll]].x=a[c[rr]].x)and(a[c[ll]].y=a[c[rr]].y))
then writeln(a[c[rr]].x, ' ', a[c[rr]].y);
for k:=rr+1 to n do
writeln(a[c[k]].x, ' ', a[c[k]].y);
end;
BEGIN
init; run; done
END.
Проаналізуємо складність наведеного алгоритму. Для сортування масиву потрібно O(nlogn) операцій. В процесі побудови оболонки кожна точка додається до послідовностей та вилучається з них не більше, ніж по одному разу. Тому складність власне побудови оболонки лінійна, і весь алгоритм має складність O(nlogn).
Задачі
15. Написати підпрограму підрахунку кількості різних значень елементів числового масиву. Складність підпрограми повинна бути O(nlogn), де n - кількість елементів масиву.
16. Написати підпрограму складності O(nlogn), що задає обчислення
а)перетину; б) симетричної різниці
двох n-елементних числових множин, поданих масивами.
17. Обчислити кількість трикутників, які можна скласти з N відрізків попарно різних додатних довжин, N < 2000. Складність програми не повинна перевищувати O(N2).
18. За N-елементним масивом A та перестановкою p(1), p(2), … , p(N) чисел 1, 2, … , N побудувати масив A[p(1)], A[p(2)], … , A[p(N)]. Допоміжний масив не використовувати.
19. Розглянемо прямокутний масив. Розташуємо елементи кожного рядка за зростанням. Потім розташуємо за зростанням елементи кожного стовпця. Довести, що кожний рядок залишиться впорядкованим.
20. (Задача про два станки) Є n деталей, кожна з яких проходить обробку спочатку на першому станку, потім на другому. Кожний станок здатний обробляти одночасно одну деталь і готовий до обробки наступної деталі одразу після обробки попередньої. Відомий час обробки кожної деталі на кожному із станків. Упорядкувати деталі таким чином, щоб час від початку обробки першої деталі до закінчення обробки останьої був якнайменшим. Наприклад, якщо перша деталь обробляється на станках 20 і 10 одиниць часу, а друга - 10 і 20, то за порядку деталей (перша, друга) одержимо час 50, а за порядку (друга, перша) - 40.
Loading...

 
 

Цікаве