Сайт підготовки до олімпіади з інформатики

Вступна робота

1. Як за допомогою скляних трилітрової і п’ятилітрової банок відміряти об’єм рідини що дорівнює 1) 7 л; 2)12 л; 3)14 л; 4) 1 л.

2. Початкове розташування чорних та білих шашок таке:

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

3.  Записати у вигляді схеми алгоритм вгадування задуманого
числа в проміжку:

1) від 0 до 7;      2) від 0 до 15;    3) від 0 до 31;    4) від 0 до 100.

Під час вгадування можна задавати лише одне із запитань типу: «Ваше число менше за ...?» або ж «Ваше число більше за ...?» Відповіддю на запитання може бути «Так» або «Ні». За яку найменшу кількість кроків можна це зробити? Визначити тин цього алгоритму.

4. Двоє хлопчиків грають у гру Наше. За умовою кожний гравець за один хід має право брати від 1 до 3 предметів. Виграє той, хто візьме останній предмет. Як повинен грати перший хлопчик, щоб напевне виграти, якщо на столі знаходиться:

1)   15 предметів;

2)   17 предметів;

3)  8 предметів.

Сформулювати виграшну стратегію для першого гравця за наявності будь-якої кількості предметів. Визначити тип Цього алгоритму.

5. Є 12 монет, серед яких одна фальшива. За 3 зважування на терезах без гирок визначити фальшиву монету і відповісти на запитання: «Фальшива монета легша чи важча?» Скласти схему алгоритму, визначити його тип.

6. Скількома способами хлопчик може піднятися по сходах на 5 сходинку, якщо він може підніматися на наступну сходинку, або переступати через одну чи дві сходинки? Сформулювати алгоритм визначення кількості способів сходження на N-ну сходинку.

7. З’ясувати, яка з двох дат передує іншій.

8. За координатами вершин опуклого чотирикутника встановити:

а) його вид (квадрат, ромб, прямокутник, паралелограм, трапеція);

б) чи є він вписаним;

в) описаним.

9. Написати алгоритм пошуку виходу в лабіринті.

10. Задача про вісім ферзів. На шаховій дошці розміром 8x8
розташувати вісім ферзів так, щоб вони не загрожували один
одному.

11. «Ханойські башти». Є три стержні А, В, С та п дисків різного розміру, перенумерованих від 1 до я в порядку зростання їх розмірів. Спочатку всі диски насаджені на стержень А таким чином, що на кожному диску зверху лежить менший за розміром диск. Необхідно перенести всі диски із стержня А на стержень С, враховуючи такі умови: диски можна переносити лише по одному і більший диск не можна ставити на менший. Для цієї операції необхідно скористатися стержнем В. Надрукувати послідовно в сі кроки, вказуючи пари стержнів, які в них використовуються (першим — стержень, з якого знімається диск, другим —  стержень, на який він перекладається). Напишіть для N=4.