Зміст вступ 5
| Вид материала | Документы |
| § 8.4 Приклади розв’язання задач з використанням масивів |
- Зміст, 429.02kb.
- Зміст, 329.83kb.
- Зміст вступ, 361.97kb.
- Зміст, 242.29kb.
- Зміст, 384.58kb.
- Зміст, 410.71kb.
- Зміст вступ, 388.95kb.
- Зміст перелік скорочень, 569.12kb.
- Зміст вступ, 540.64kb.
- Зміст Вступ, 574.44kb.
§ 8.4 Приклади розв’язання задач з використанням масивів
Задача 174 У відсортованому за зростанням масиві з 1000 різних чисел знайти номер елемента, значення якого рівне K. Вважати, що елемент обов’язково присутній у масиві.
Розв’язання: Ми з вами вже розглядали алгоритми пошуку для невпорядкованих масивів. Дана задача для нас є цікавою тим, що масив вже впорядковано і тому пробігати по всьому масиву мабуть не має сенсу. Існує досить швидкий алгоритм пошуку у впорядкованому масиві, який називають алгоритмом пошуку елемента діленням пополам. Суть алгоритму полягає в тому, що спочатку встановлюються межі пошуку – початок і кінець ділянки масиву, де може міститись шуканий елемент. Розглядається елемент, що знаходиться посередині між цими значеннями. Якщо він співпав з шуканим, то його номер і є шуканим. Якщо ж ні, то у випадку, коли розглядуваний елемент більший за даний, то зменшуємо праву межу пошуку, а якщо менший – то збільшуємо ліву. Даний алгоритм легко зрозумілий з приведеної програми.
program poisk_2;
const n = 1000;
var k, p, a, b : integer;
mas : array[1..n] of integer;
begin
for a := 1 to n do mas[a] := a;
write('K = '); readln(k);
a := 1; b := n;
while a <> b do
begin
p := (a + b) div 2;
if mas[p] < k then a := p + 1
else b:=p
end;
write('Номер шуканого елементу = ',a);
readln
end.
Задача 175 (ХІ Всеукраїнська олімпіада з інформатики – м. Київ, 10.04.1998 р.)
Годинник. Жителі планети Олімпія полюбляють літати в гості на інші планети. Вчені планети розробили годинника, що може налагоджуватися для відліку часу на будь–якій планеті. Цей годинник складається з кульок, лотка (черги) і трьох чаш: секундної, хвилинної і годинної. В кожен момент часу кількість кульок в чашах показує час (секунди, хвилини та години відповідно). Кожну секунду перша кулька з черги потрапляє в секундну чашу. Якщо секундна чаша наповнилась (кількість кульок дорівнює кількості секунд в хвилині на цій планеті), то ця кулька переходить до хвилинної чаші, а решта кульок переходять з секундної чаші в кінець черги в порядку, зворотному до їх надходження до секундної чаші. Аналогічно, при наповненні хвилинної чаші остання кулька переходить до годинної чаші, а решта кульок з хвилинної чаші переходить в кінець черги в порядку, зворотному до їх надходження до хвилинної чаші. Якщо заповнюється годинна чаша, то всі кульки з неї переходять в кінець черги в порядку, зворотному до їх надходження в годинну чашу. Всі кульки пронумеровані в початковий момент часу містяться в черзі. Написати програму, яка буде обчислювати мінімальну кількість діб, необхідних для того, щоб початкове положення кульок в черзі повторилося.
Розв’язання: Дана задача цікава тим, що в ній містяться нові структури даних, з якими ми раніше не зустрічалися, а саме: черга і стек. Перед тим як приступити безпосередньо до розв’язання задачі, розглянемо, що це за структури і як з ними можна працювати.
Черга в програмуванні, як і черга в магазині, має свій початок і свій кінець. Новий елемент стає в кінець черги, а якщо потрібно взяти елемент, то його беруть з початку черги. Роль черги в описаній задачі виконує лоток.
У стеці ж елементи доступні тільки з одного кінця. Таку структуру даних у програмуванні називають LIFO – Last In – First Out, що розуміється як останнім прийшов – першим пішов. Роль стека в розглядуваній задачі виконує кожна чаша. Описаний вище годинник зручно уявити як механізм, у якому з лотка (черги) кульки капають у циліндричні чаші (стеки), радіус яких дорівнює радіусу кульок. Коли заповнюється секундна чаша-циліндр, то зверху у ній відкривається клапан і верхня кулька (прийшла останньою) скочується по новому жолобу у хвилинну чашу. Клапан закривається і відкривається інший клапан (також зверху) і в цей же час спрацьовує поршень, який виштовхує всі кулі з чаші, – вони по новому жолобу поступають у кінець черги у зворотному порядку. Так само працюють хвилинна і годинна чаші-циліндри. Отже ми в одній задачі одночасно маємо справу і з чергою і з стеком.
Для збереження номера першого вільного місця у черзі, стеку хвилин та годин використаємо нульові елементи відповідних масивів. Ідея розв’язку задачі полягає в тому, що ми моделюємо роботу годинника протягом доби, саме через добу відновиться кількість кульок у лотку. Нам не потрібно моделювати далі роботу годинника, так як знайшовши положення кульки через добу ми зможемо на підставі отриманих даних порахувати період кульки. Знайшовши період для кожної кульки знаходимо найменше спільне кратне їх періодів, яке і буде найменшою кількістю діб, через яку повториться початкове розташування кульок. Для цього використаємо функцію nsk і процедуру period. Все інше зрозуміло з тексту програми та коментарів до неї. Відмітимо тільки той факт, що моделювати падіння кожної кульки у секундну чашу-циліндр ми не будемо. Ми будемо переміщувати одразу стільки кульок, скільки їх міститься в одній хвилині. Це дасть змогу значно прискорити виконання програми. Втім, судіть самі:
program clock;
uses crt;
var s,m,h : byte;
sec, min, time : array[0..60] of integer;
lotok : array[0..1060] of integer;
kul,i : integer;
function nsk(a,b:longint):longint;
var a1,b1 : longint;
begin
a1:=a; b1:=b;
while a<>b do if a>b then a:=a-b else b:=b-a;
nsk := (a1 div a)*b1;
end;
procedure period;
var j : integer;
t,l : longint;
begin
t:=1; write('Періоди: ');
for i:=1 to kul do
begin
j:=i;l:=0;
repeat
j:=lotok[j];inc(l);
until j=i;
t:=nsk(t,l);write(l,' ');
end; writeln;
writeln('Найменше спільне кратне = ',t);
writeln(' Повторення через ',t,' діб ');
end;
begin
writeln;
write('Скільки секунд у хвилині: ');readln(s);
write('Скільки хвилин у годині: ');readln(m);
write('Скільки годин у добі: ');readln(h);
write('Скільки кульок у лотку: ');readln(kul);
{ моделювання роботи годинника з використанням черги та стеків }
for i:=1 to kul do lotok[i]:=i; { початкове розташування кульок }
lotok[0]:=kul+1; { номер першого вільного місця в черзі }
min[0]:=1; { номер першого вільного місця в стеку хвилин }
time[0]:=1; { номер першого вільного місця в стеку годин}
while time[0]<=h do
begin
for i:=1 to s do sec[i]:=lotok[i]; { кульки впали у секундну чашу }
for i:=1 to kul-s do lotok[i]:=lotok[i+s]; { зміни в черзі у лотку }
lotok[0]:=lotok[0]-s; { новий номер першого вільного місця у черзі }
min[min[0]]:= sec[s]; { кулька впала у хвилинну чашу }
{ а всі інші перейшли в кінець черги у зворотному порядку }
for i:=1 to s-1 do lotok[lotok[0]+i-1]:=sec[s-i];
lotok[0]:=lotok[0]+s-1;{новий номер першого вільного місця в черзі}
inc(min[0]); { пройшла ще 1 хвилина }
if min[0]=m+1 then { хвилинна чаша заповнена повністю }
begin
time[time[0]]:=min[m]; { кулька впала у годинну чашу }
{ а всі інші перейшли в кінець черги у зворотному порядку }
for i:=1 to m-1 do lotok[lotok[0]+i-1]:=min[m-i];
lotok[0]:=lotok[0]+m-1; { новий номер вільного місця у черзі }
min[0]:=1; { звільнилась хвилинна чаша }
inc(time[0]); { пройшла ще одна година }
end;
if time[0]=h+1 then { пройшла доба – годинну чашу заповнено }
begin
{ кульки переходять до черги у лотку у зворотному порядку }
for i:=1 to h do lotok[lotok[0]+i-1]:=time[h-i+1];
end;
end; { пройшла доба – шукаємо періоди кульок і їх (періодів) НСК }
period;
readln
end.