Задача 174. 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. 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.
Вправи та завдання
176. 176. Знайти різницю в рості між найвищим і найнижчим футболістом команди, якщо в складі команди 20 чоловік.
177. 177. В складі баскетбольної команди 12 гравців. Скільки гравців в команді мають зріст, менший за середній зріст команди?
178. 178. В зв’язку з економічною кризою в країні і скороченням коштів на потреби освіти в школі два 10 класи по 18 учнів у кожному було об’єднано в один. Вважаючи, що в класах навчались одні хлопці, об’єднати дані про зріст хлопців з двох масивів в один, але зберегти порядок шикування по зросту на уроці фізкультури (від вищих до нижчих). Вхідні масиви вважати відсортованими і заданими у вигляді констант.
179. 179. В кондитерський відділ магазину поступило 15 видів цукерок по різній ціні і в різній кількості. Знаючи дані про ціни і кількості товарів, знайти, яких цукерок було завезено в магазин за найбільші кошти.
180. 180. Описати числові масиви з цілих чисел X, Y, Z і виконати наступні перетворення:
а) переписати елементи масиву Х в масив Y в зворотному порядку;
б) сформувати масив Y таким чином: Y[1]:= X[1] + X[N]; Y[2]:= X[2] + X[N–1],..., Y[N]:= X[N] + X[1].
в) в масив Y занести лише ті елементи масиву Х, що знаходяться в заданому діапазоні [A, B].
г) в масив Y занести 10 найменших додатних елементів, а в масив Z – 15 найбільших за модулем.
д) записати в масив Y лише парні елементи, а в масив Z – лише ті, що діляться на 3.
е) в масив Y занести лише ті елементи масиву Х, що є числами Фіббоначі, а в масив Z – лише ті, квадратні корені яких є цілими числами.
181. 181. Шкільній футбольній команді з 15 чоловік потрібно закупити форму для участі у змаганнях. Підприємці пропонують М видів форми (10 Ј М Ј 15). Скільки найбільше футбольних м’ячів вартістю Р зможе купити команда, якщо вибере не найкращу форму? Яку форму при цьому буде закуплено для команди?
182. 182. У змаганнях з стрибків у довжину кожен спортсмен має право на 5 спроб. До підсумкового результату зараховується найкраща. Скласти програму, яка визначає учасників, що зайняли перші три призові місця і виводить на екран прізвища переможців з вказівкою місця, що посів спортсмен і його результат. Кількість спортсменів не перевищує 20.
183. 183. При складанні бухгалтерського звіту за рік від бухгалтера кооперативу «Колобок», що займається виготовленням і продажем хлібопекарних виробів забажали отримати відомості про кількість виробів, що продаються за найвищою ціною. Виготовлялось протягом року М виробів (10 Ј М Ј 20). Дані про ціни на вироби знаходяться в масиві Х. Скласти програму для полегшення роботи бухгалтера.
184. 184. Розв’язати попередню задачу у випадку, коли вимагається подати дані про найбільшу кількість виробів, що продаються за однаковою ціною.
185. 185. В заданому цілочисельному масиві знайти елементи, сума яких дорівнює заданому числу.
186. 186. Задано масив натуральних чисел. Знайти мінімальне натуральне число, яке не можна представити сумою ніяких елементів цього масиву.
187. 187. У відсортованому масиві з 1000 чисел знайти номер елемента, значення якого рівне K.
