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

програмування в С++

Школа олімпійського резерву з інформатики
Інформаційний лист PDF Печать E-mail
Добавил(а) Administrator   
07.09.11 12:24

На виконання рішення обласної ради шостого скликання від 28.12.2010 р. №2/38 «Про внесення змін до обласної цільової Програми роботи з обдарованою молоддю на 2007-2010 роки» та з метою пошуку обдарованих дітей, підготовки їх до участі у Всеукраїнській олімпіаді з інформатики залучити учнів, переможців ІІІ етапу Всеукраїнської олімпіади з інформатики для навчання в школі обдарованих дітей з інформатики та додатково в школі обдарованих дітей з математики.

Заняття з інформатики проводяться в середу та п’ятницю з 15.00 до 17.00 в лабораторії інформатики Волинського ІППО і заочно на сайті http://schoololymp.byethost32.com.

Додаткову інформацію про роботу школи можна отримати в методиста лабораторії інформатики Гіся Ігоря Володимировича (контактний телефон (0332) 242225, моб.0509163106, кабінет №24 ВІППО).

Последнее обновление 07.09.11 13:06
 
Список сайтів PDF Печать E-mail
Добавил(а) Гісь   
16.08.11 12:03

1. Разбор олимпиадных задач по информатике от Михаила Густокашина
http://www.g6prog.narod.ru/

Этот сайт посвящен подробному разбору олимпиадных задач по информатике.
Здесь разобраны задачи школьных, городских, областных, Всероссийских,
международных, университетских, ACM олимпиад, а также задачи неопределенного
происхождения и собственного сочинения. Исходные тексты к задачам
не прилагаются. К некоторым задачам прилагаются тесты.
Кроме того имеется отличная подборка книг и статей,
великолепная коллекция ссылок и активно работающий форум.

 

2. http://kievoi.narod.ru/
Официальный сайт Киевских олимпиад по информатике. Содержит архив задач прошлых лет, обширный список материалов и ссылок, а также небольшой

подборку статей. Часть материала из этой подборки практически невозможно найти где-либо ещё в общеизвестных источниках.

 

3. http://acm.timus.ru
Сайт Уральских ACM-олимпиад. Обширный набор авторских задач на разные темы с системой тестирования плюс регулярные соревнования. Исходных

текстов, разборов, тестов – нет.

 

4. http://algolist.manual.ru/
Архив, посвящённый алгоритмам. Представляет собою тематический каталог статей об алгоритмах из разных областей знаний, зачастую с

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

статей переведено на русский язык, однако встречаются исключения. Функционирующий параллельно форум содержит ответы на те вопросы, которым

не нашлось места в статьях:)

 

5. http://alglib.sources.ru/
Проект, аналогичный описанному выше. Количество охваченных алгоритмов и тем слегка меньше, упор ставится на исходные тексты.

 

6. http://olympiads.ru
Сайт, посвящённый олимпиадной информатике. Более всего примечателен тем, что ведёт постоянное отслеживание всех крупных российских

информатических соревнований и предоставляет доступ к их материалам.

 

7. http://acm.mipt.ru
Олимпиады Московского физико-технологического института. Подборка алгоритмов, некоторые книги, небольшой архив задач, система тестирования

El Judge.

 

8. http://topcoder.com
Справедливость требует указать этот ресурс:)
Уникальный проект, посвящённый соревнованиям в компьтерным наукам как таковым, в разных категориях. Центральное направление всё же

принадлежит алгоритмистике. Регулярные онлайн-соревнования, гигантский архив задач от них, система проверки, включающая в себя несколько

пунктов, не имеющих аналогов (к примеру, ознакомление с исходными текстами соперников либо призовые баллы за удачно подобранный и внесённый

в основной набор тест и т.д.), несколько поддерживаемых языков (Паскаля на данный момент в списке нет). Каждый год проводится очный тур для

сильнейших.

 

9. http://www.olymp.vinnica.ua/
Всеукраинская ежегодная интернет-олимпиада по информатике

 

10. http://olympiada.km.ua/
Ежегодная интернет-олимпиада по информатике Хмельницкой области

 

11. http://sbs.km.ua/
Довольно часто проводяться турниры для подготовки и тренировки школьников различного уровня

Набор АСМ – сайтов: база задач + изредка проводимые онлайн – олимпиады

12. http://www.e-olimp.com.ua

13. http://acm.timus.ru/

14. http://icpcres.ecs.baylor.edu/onlinejudge/

15. http://acm.mipt.ru/

16. http://acm.lviv.ua/

17. http://acmp.ru/

 

18. http://www.topcoder.com/tc
Сайт, где регулярно (еженедельно) проводяться 75-минутные олимпиады, помогающие повысить как качество написание кода так и умение решать задачи. Также есть множество разобранных алгоритмов и методов программирования, раздел “только для школьников”, лучшие из которого ездят на ежегодную онсайт олимпиаду в США, матчи с более научными задачами и многое другое. Доступные языки: С++, С#, Vsiual Basic, Java, Python.

 

19. http://ace.delos.com/
Сайт команды США на международную олимпиаду. Раз в месяц проводяться олимпиады с разбором, есть большая база задач, разбитая на темы и

перемешанная с теорией, для каждой задачи после решения доступен разбор.

 

20. http://www.hsin.hr/coci/
Сайт подготовки к Всехорватской олимпиаде, ежемесячные олимпиады с разборами

 

21. http://olympiads.ru/
Сайт с задачами и разборами различных российских олимпиад. На нём проводиться Всероссийская интернет – олимпиада. Также есть несколько уроков с разборами алгоритмов, задачами на эти алгоритмы и разборами задач.

 

22. http://neerc.ifmo.ru/school/
Сайт с архивами Всероссийских, СПб олимпиад, регулярно проводяться командные и личные соревнования для подготовки к Всероссийской

 

23. http://code.google.com/codejam/
Ежегодное соревнование под эгидой гугла. Предполагает решение задач любым способом и предоставление верных ответов.

Сергей Могильный:

Только то, чего не указали ранее:

 

24. http://ceoi.inf.elte.hu/
Сайт Центрально-Европейской Олимпиады по Информатике, ежегодно проводится в июне-июле, каждый год есть онлайн трансляция. Там же ссылки на архив прошлых лет.

 

25. http://ioinformatics.org
Сайт IOI, имеются тесты практически ко всем задачам всех лет.

 

26. http://qbit.org.ua/
Архив Харьковских АСМ олимпиад, проверяющая система. Изредка проводятся онлайн трансляции различных чемпионатов.

 

 
Олімпіади з інформатики: корисні сайти PDF Печать E-mail
Добавил(а) Gis   
16.08.11 11:45

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

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

 

Перша адреса:

http://vippoolimp.byethost14.com - Волинська учнівська Інтернет-олімпіада з програмування

 
Задачі на повторення за рік PDF Печать E-mail
Добавил(а) Гісь   
23.05.11 09:22
v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} Normal 0 false false false MicrosoftInternetExplorer4 /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Обычная таблица"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman"; mso-ansi-language:#0400; mso-fareast-language:#0400; mso-bidi-language:#0400;}

Задачі (20.05.2011)

Завдання 1

Є 10 мішків з монетами. Відомо, що в одному з мішків всі монети фальшиві і

кожна з них на 1 грам легша від нефальшивої. За одне зважування на терезах з

гирями визначити, в якому з мішків знаходяться фальшиві монети.

Завдання 2

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

подорожній долає міст за різний час: першому потрібна 1 хвилина, другому – 2 хвилини, третьому – 5 хвилин, а четвертому – 10 хвилин. Якщо подорожні йдуть мостом вдвох, то вони пересуваються з швидкістю найповільнішого з них (наприклад, якщо йтимуть перший і четвертий, то вони здолають міст за 10 хвилин)

Завдання 3

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

Рішення
Ділим монетки на 3 купки по 4 монети
1 2 3 4 5 6 7 8 9 10 11 12
1. Перше зважування 1 2 3 4 і 5 6 7 8
(один варіант)
Якшо 1 2 3 4 = 5 6 7 8 Переходим на крок 2
Якшо 1 2 3 4 > 5 6 7 8 (якшо менше теж підходить але порядок ваги є важливий) переходим на крок 4
2. Друге зважування
(один варіант)
7 8 = 11 12 тобто фальшива є серед 9 і 10, бо 7 і 8 - справжні
7 8 11 12 то фальшива є серед 11 і 12
Переходим на крок 3
3. Третє зважування
(один варіант)
8 = 9 тоді фальшива 9
(8 = 11 тоді фальшива 12)
(другий варіант)
8 10 тоді фальшива 10
(8 11 тоді фальшива 11)
Переходим на крок 12

4. (другий варіант)
1 2 3 4 > 5 6 7 8 (якшо менше теж підходить але порядок ваги є важливий)
Переходим на крок 5
5. Друге зважування
Відкладєм 1 2 3
важим
(Варіант 1)
6. 4 5 6 7 > 8 9 10 11 оскільки монетки 1 2 3 не впливають на зміну ваги - вони справжні, І фальшива є
або 7 або 8. Переходи на крок 9
(Варіант 2)
7. 4 5 6 7 < 8 9 10 11 фальшива монета є серед 4 5 6 і фальшива монета є лекша Переходи на крок 10
(Варіант 3)
8. 4 5 6 7 = 8 9 10 11 фальшива монетка є серед 1 2 3 і фальшива монета є важча Переходи на крок 11
Важим
9. 7 і 12 якшо рівні то фальшива 8, якшо не рівні - фальшива 7-ма
10. 4 і 5 якшо рівні то фальшива 6, якшо 4 лекше за 5 то фальшива 4, якшо 4 важча за 5 то фальшива є 5
11. 1 і 2 якшо рівні то фальшива 3, якшо 1 важче за 2 то фальшива 1, якшо 1 лекша за 2 то вальшиває є 2
12. Кінець

Завдання 4

Дано послідовність з N чисел, котра містить різні числа від 0 до N. Визначити, якого числа не існує в даній послідовності.

Завдання 5

В таблиці а[1..100)]всі елементи рівні 2,3,4 або 5. Написати програму, яка заміняє 2 на 5, 3 на 4, 4 на 3, 5 на 2.

Завдання 6

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

fibonachi

Завдання 7 DOMINO

Написати програму, яка буде підраховувати кількість варіантів покриття прямокутника 2хN прямокутниками 2х1. Покриття, які перетворюються одне в одне симетріями рахувати різними.

Вхідні дані. Вхідний файл DOMINO.DAT містить число N (0 < N < 65536).

Вихідні дані. Вихідний файл DOMINO.SOL повинен містити одне число: кількість варіантів.

Завдання 8

За квитками на прем'єру нового мюзиклу вишикувалася черга з N людей, кожний з яких хоче купити 1 квиток. На всю чергу працювала тільки одна каса, тому продаж квитків йшов дуже повільно, приводячи людей черги у відчай. Найкмітливіші швидко відмітили, що, як правило, декілька квитків в одні руки касир продає швидше, ніж коли ці ж квитки продаються поодинці. Тому вони запропонували декільком людям, які стоять підряд віддавати гроші першому з них, щоб він купив квитки на всіх.

Проте для боротьби із спекулянтами касир продавала не більше 3-х квитків в одні руки, тому домовитися таким чином між собою могли лише 2 або 3 підряд вартих людини.

Відомо, що на продаж i-ій людині з черги одного квитка касир витрачає Ai секунд, на продаж двох квитків — Bi секунд, трьох квитків — Ci секунд. Напишіть програму, яка підрахує мінімальний час, за який могли бути продані квитки для всіх людей черги.

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

Формат вхідних даних

У вхідному файлі записано спочатку число N — кількість покупців в черзі (1<=N<=5000). Далі йде N трійок натуральних чисел Ai, Bi, Ci. Кожне з цих чисел не перевищує 3600. Люди в черзі нумеруються починаючи від каси.

Формат вихідних даних

У вихідний файл виведіть одне число — мінімальний час в секундах, за яке могли бути обслужені всі покупці.

Приклади

Bilet.dat

Bilet.sol

5

5 10 15

2 10 15

5 5 5

20 20 1

20 1 1

12

2

3 4 5

1 1 1

4


Завдання 9

В деякому місті шоферам заборонено при русі робити ліві повороти. За кожен такий поворот шофер повинен сплачувати штраф в розмірі М гривень. Для спостереження за рухом транспорту в місті встановлена комп'ютерна система, яка фіксує координати автомобіля на початку руху, в кінці та при кожному повороті.

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

Вхідні дані: В першому рядку вхідного файлу VIOLATION.DAT записано N - кількість зафіксованих координат руху деякого автомобіля та М - величина штрафу, в наступних рядках координати автомобіля в процесі руху - (хi, уi), і=1,2,...,М, де (х1, у1) - точка початку руху, (хNN) - остання точка маршруту автомобіля.

Всі числа цілі та знаходяться в межах від -1000 до 1000.

Вихідні дані: Єдиний рядок вихідного файлу VIOLATION.SOL має містити суму штрафу.

Приклад:

VIOLATION.DAT

VIOLATION.SOL

5 50

0 0

2 0

1 1

5 1

5 -1

50

Завдання 10

Міжнародна конференція

Вас найняли для того, щоб визначити мiсця дипломатiв за столом обговорень мiжнародної конференцiї. На конференцiю запрошенi по одному дипломату з N рiзних країн свiту. Кожен дипломат знає вiд однiєї до М мов. Дипломати, якi не знають спiльної мови, не можуть розмовляти один з одним. До того ж, деякi країни проголосили, що не будуть пiдтримувати дипломатичних стосункiв з деякими iншими, тобто представники цих країн не будуть розмовляти один з одним. Ваше завдання полягає в розробцi програми DIPLOMAT.*, що визначає мiсця за столом для дипломатiв таким чином, щоб кожен мiг розмовляти з обома своїми сусiдами, якi сидять лiворуч та праворуч вiд нього.

Стiл, що використовується, круглий i розрахований на N персон. Дипломат може спiлкуватись з дипломатом, який сидить лiворуч однiєю мовою, а з дипломатом, що сидить праворуч, – iншою.

Вхiднi данi:

В першому рядку текстового файлу DIPLOMAT.DAT – число N. Далi – N рядкiв, по одному рядку на дипломата. Кожен рядок – послiдовнiсть слiв. Сусiднi слова вiдокремленi пропуском. Кожне слово – це послiдовнiсть великих латинських лiтер. Перше слово – код країни – складається з 3 лiтер. Друге слово має довжину вiд 1 до 5 лiтер i представляє перелiк мов, на яких може спiлкуватись дипломат. Кожна мова позначена однiєю лiтерою. Далi iде список з не бiльш як N трилiтерних слiв – кодiв країн, з якими уряд дипломата пiдтримує стосунки.

Вихiднi данi:

До файлу DIPLOMAT.SOL треба вивести список дипломатiв в порядку розмiщення за столом (по одному дипломату в рядку). Кожен рядок складається з 3 слiв: перше – код мови, якою дипломат може спiлкуватись з сусiдом лiворуч, друге – код країни дипломата, третє – код мови для спiлкування з сусiдом праворуч. Можливе iснування декiлькох розв'язкiв. Вам потрiбно знайти один. Якщо розв'язку не iснує, Ваша програма повинна видати таке повiдомлення: NO SOLUTION EXISTS.

Приклад вхiдних даних

Приклад вихiдних даних

10

USA EF CHN GBR USR FRA FRG JPN ISR POR KOR

CHN CFE USA GBR FRA FRG

GBR ER USA CHN USR FRA FRG JPN ISR POR KOR

USR RF USA GBR FRA FRG

FRA F USA CHN GBR USR FRG JPN ISR POR

FRG ERG USA CHN GBR USR FRA JPN ISR POR

JPN JHG USA GBR FRA FRG JPN ISR POR KOR

ISR YER USA GBR FRA FRG JPN KOR

POR PGE USA GBR FRA FRG JPN

KOR KEC USA GBR USR JPN ISR

E USA E

E KOR E

E ISR H

H JPN G

G FRG G

G POR E

E GBR E

E USR F

F FRA F

F CHN E

Завдання 11 GoTo.

Учні, недавно що почали програмувати, вживають дуже багато операторів GOTO, що є майже неприпустимим для структурованої програми. Допоможіть викладачу інформатики написати програму, яка оцінюватиме ступінь структурованості відладженої програми школяра на мові Pascal, спершу просто підраховувавши кількість операторів GOTO в ній.

В синтаксично вірній програмі ключове слово оператора переходу GOTO може стояти або на початку рядка або після пропуску або після одного з символів — ‘;’, ‘:’, ‘}’, а після нього може стояти або пропуск або переклад рядка або символ ‘{‘ (табуляцію як роздільник розглядати не будемо).

Нагадаємо, що окрім позначення дійсно оператора переходу, слово GOTO може зустрічатися в тексті програми в рядкових константах, укладених в апострофи, або в коментарях, причому для простоти вважатимемо, що коментар завжди починається з символу ‘{‘, а закінчується першим що зустрівся після цього символом ‘}’, при цьому символ ‘{‘ повинен знаходитися не усередині рядкової константи. В цих випадках слово GOTO підраховувати не потрібно. Рядкові і прописні букви в Pascal не помітні.

У вхідному файлі goto.in знаходиться текст програми без синтаксичних помилок на мові Pascal. Розмір програми не перевершує 64К. У вихідному файлі goto.out повинне виявитися одне число – кількість операторів GOTO в цій програмі.

Приклад вхідного файлу:

label 1,2;

var I:byte;

begin

1: I:=I+1;

if I>10 then goto 2 else

writeln(¢ goto ¢); GoTo 1;

2: if I<10 then goto 1 {else { goto 2;}

end.

Вихідний файл для наведеного приклад

3

Завдання 12 «Циліндр»

Із аркушу паперу ножицями Ви можете вирізати дві поверхні, з яких можна скласти циліндр наступним чином:

1. Розрізати папір горизонтально (паралельно короткій стороні), отримавши дві прямокутні частини.

2. З першої частини вирізати круг максимального радіуса. Він буде лежати в основі циліндра.

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

За заданими розмірами паперу необхідно побудувати подібним чином циліндр максимального об'єму.

Технічні умови

Вхідні дані

Вхідні дані містять декілька тестів. Кожен тест містить два числа w і h (1 ≤ w ≤ h ≤ 100), які позначають ширину та висоту аркуша паперу. Останні тест містить два нулі і не опрацьовується.

Вихідні дані

Для кожного тесту у окремому рядку вивести значення найбільшого можливого об'єму циліндру, який можна побудувати з аркушу паперу заданих розмірів. Об'єм слід виводити з 3 десятковими знаками.

Приклад

Приклад вхідних даних

10 10
10 50
10 30
0 0

Приклад вихідних даних

54.247
785.398
412.095

 
Синтаксичний розбір виразів PDF Печать E-mail
Добавил(а) Administrator   
22.04.11 14:09

Тема: Синтаксичний розбір виразів

Однієї з головних причин, що лежать в основі появи мов програмування високого рівня, з'явилися обчислювальні задачі, що вимагають великих об'ємів рутинних обчислень. Тому до мов програмування пред'являлися вимоги максимального наближення форми запису обчислень до природної мови математики. В зв'язка з цей одній з перших областей системного програмування сформувалося дослідження способів виразів. Тут отримані численні результати, проте найбільше розповсюдження отримав метод трансляції за допомогою зворотного польського запису, який запропонував польський математик                Я. Лукашевіч.

              Нагадаємо, що існує цілий ряд  методів  синтаксичного  розбору і обчислення виразів. Нехай вирази є рекурсивними  структурними  даними, які визначаються в термінах самих себе.  Якщо ви обмежитеся використанням у виразах тільки операторів +,  -  * / і дужок,  то зможете сказати, що всі вирази можуть бути визначеними в термінах наступних правил:
              выраз=>терм[+терм][-терм]
              терм=>множник[*множник][/множник]
              множник=>змінна, число або (вираз) де будь-яка частина може бути порожньою.  Квадратні дужки  позначають  необов'язковість,  а => - утворення. Фактично правила є правилами утворення виразів. 
              Вираз             10+5*В складається з двох термів: 10 і 5*В. Проте, включає три множники:  10,  5 і В.  Цими множниками є два числа і одна змінна.
              З другого боку вираз          14*(7-С)   має два  терми 10 і (7-С),  один з яких є числом,  а інша дочірнім виразом. Дочірній вираз розпадається на одне число і одну змінну.
              Даний процес формує основу для рекурсивного низхідного  синтаксичного  розбору,  який є набором загальних  рекурсивних процедур,  що носять характер ланцюжка. На кожному відповідному кроці  синтаксичний розбір може виконувати задані операції в алгебра правильній послідовності. Наприклад розглянемо синтаксичний розбір вхідного виразу 9/3-(100 +56) і виконання операцій по кроках.

      Крок 1. Узяти першу лексему: 9/3

      Крок 2. Узяти обидва множники і виконати операцію поділу.

                     В результаті виходить 3.

      Крок 3. Узяти другу лексему: (100+56). В даній точці ви повинні рекурсивно  проаналізувати другий вираз.

      Крок 4. Узяти обидва числа і скласти. В результаті виходить                      156.

      Крок 5. Повернутися з рекурсивного виклику і відняти 156 з 3, що дає відповідь - 153.

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

 

 

 

 

Рядкові величини

- операція + (з’єднання)                        ‘місто’+’ ’+’Луцьк’

 

Функції роботи з рядками:

 

Назва функції

Призначення

Приклад

Результат

1.

Length(S)

визначає кількість символів у заданому рядку

Length (‘місто Луцьк’)

11

2.

Сору(S,n,m)

виділяє m символів рядка S, починаючи від символу з номером n

Copy (‘місто Луцьк’, 6, 5)

‘Луцьк’

3.

Pos(S1, S2)

визначає номер символу, з якого починається входження рядка (тексту) S1 у рядок S2

Pos (‘ ‘,‘місто Луцьк’)

6

4.

Concat(S1, S2,...)

з'єднує рядки в один рядок

Concat('20', '01')

‘2001’

 

Процедури роботи з рядками:

 

Назва функції

Призначення

Приклад

Результат

1.

Insert (A:string, var В: string, n:integer)

вставляє рядок А у рядок В, починаючи від позиції з номером n

S1:=’місто’;

S2:=’Луцьк’;

Insert(S1,S2,1);

’містоЛуцьк’;

 

2.

Delete (var S:string, n:integer, m:integer)

вилучає m символів з рядка S, починаючи від позиції n

S:=’містоЛуцьк’;

delete(S,1,5);

’Луцьк’;

 

3.

Str (A:integer, var S:string)

переводить числове дане A у дане типу рядок

A:=2001;

Str(A,S);

‘2001’

4.

Val (S: string, var A, KOD: integer)

засилає у числову змінну A числовий образ рядка S, повертаючи код помилки KOD

S:=’2001’;

Val(S,A,Kod);

2001

 

 
Алгоритми для роботи з рядками PDF Печать E-mail
Добавил(а) Гісь   
06.05.11 12:28

06 травня 2011року

Алгоритми для роботи з рядками

 

Перестановка слів

   Поменяйте в строке имя и фамилию человека.

 

Технічні умови

   Вхідні дані

   Вхідний файл містить один рядок, у якому записані прізвище та ім'я людини (відокремлені  рівно одним пропуском).

   Вихідні дані

   У вихідний файл виведіть цю ж інформацію, проте спочатку ім'я, а потім прізвище, також відокремлені рівно одним пропуском.

 

Інформація про задачу

Ліміт часу: 0.1 секунди
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 10
Складність: 1%
81/82

Приклад

Приклад вхідних даних

Pupkin Vasya

Приклад вихідних даних

Vasya Pupkin

 

 

Довгий корінь

   Для заданого натурального числа А потрібно знайти найбільше число В таке, що B2 ≤ A.

 

Технічні умови

   Вхідні дані

   У вхідному файлі записано натуральне число A (A ≤ 10100).

   Вихідні дані

   У вихідний файл виведіть максимальне натуральне число B, квадрат якого не перевищує A. Число B слід виводити без лідируючих нулів.

 

Інформація про задачу

Ліміт часу: 2 секунди
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 4.7619
Складність: 54%
16/35

Приклад

Приклад вхідних даних

17

Приклад вихідних даних

4

 

КМП

   Знайти всі входження рядка T у рядок S.

 

Технічні умови

   Вхідні дані

   У першому рядку вхідного файлу записано рядок S, у другому рядку вхідного файлу записано рядок T. Довжини рядків більші 0 і менші 50000, рядки містять лише латинські літери.

   Вихідні дані

   Виведіть номери символів, починаючи з яких рядок T входить у рядок S у порядку зростання. Як це за звичай прийнято у програмістів, нумерація символів починається з нуля.

 

Інформація про задачу

Ліміт часу: 2 секунди
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 11.1111
Складність: 10%
36/40

Приклад

Приклад вхідних даних

ababbababa
aba

Приклад вихідних даних

0 5 7

 

Рядки

   Хлопчик Кирило написав одного разу на аркуші паперу рядочок, який складався з великих та маленьких латинських літер, а після цього пішов грати у футбол. Коли ж він повернувся, то виявив, що його друг Дмитро написав під його рядочком ще один рядочок такої ж двожини. Дмитро стверджує, що свій рядочок він отримав циклічнм зсувом рядочка Кирила на декілька кроків праворуч (циклічний зсув рядка abcde на 2 позиції праворуч дасть рядок deabc). Проте Дмитро відомий тим, що може випадково помилитись у великій кількості обчислень, тому Кирил у розгубленості - чи вірити Дмитру? Допоможіть йому! За заданими рядками виведіть мінімально можливий розмір зсуву або -1, якщо Дмитро помилився.

 

Технічні умови

   Вхідні дані

   Перші два рядки вхідного файлу містять рядки Кирила та Дмитра відповідно. Довжини рядків однакові, не перевищують 10000 і не рівні 0.

   Вихідні дані

   У вихідний файл виведіть єдине число - відповідь на поставлену задачу.

 

Інформація про задачу

Ліміт часу: 2 секунди
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 11.1111
Складність: 30%
23/33

Приклад

Приклад вхідних даних

abcde
deabc

Приклад вихідних даних

2

 

Циклічний рядок

   Рядок S було записано багато разів підряд, після чого з отриманого рядка взяли підрядок і дали вам. Ваша задача визначити мінімально можливу довжину початкового рядка S.

 

Технічні умови

   Вхідні дані

   У першому і єдиному рядку вхідного файлу записано рядок, який містить лише латинські літери, довжина рядка не перевищує 50000 символів.

   Вихідні дані

   У вихідний файл потрібно вивести одне число - відповідь до задачі.

Інформація про задачу

Ліміт часу: 2 секунди
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 11.1111
Складність: 25%
3/4

Приклад

Приклад вхідних даних

abababa

Приклад вихідних даних

2

 

 
Розв'язуйте задачі PDF Печать E-mail
Добавил(а) Administrator   
22.04.11 14:15

www.e-olimp.com.ua

1. Розклад трицифрового числа

   Розкласти дане трицифрове число на цифри.

Технічні умови

   Вхідні дані

   У єдиному рядку задано трицифрове ціле число.

   Вихідні дані

   Вивести кожну цифру з нового рядка. Порядок виведення наведено у прикладі.

Інформація про задачу

Ліміт часу: 1 секунда
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 2
Складність: 18%
189/231

Приклад

Приклад вхідних даних

198

Приклад вихідних даних

1
9
8

 

2. Задача Іосифа Флавія

   Існує легенда, що Іосиф Флавій - відомий історик першого століття - вижив і став відомим завдяки математичній обдарованості. У ході іудейської війны він у складі загону з 41 іудейського воїна був загнаний римлянами у печеру. Віддаючи перевагу самовбивство полону, воїни вирішили вишукуватись у коло і послідовно вбивати кожного третього з живих до тих пір, доки не залишиться жодної людини. Проте Іосиф розом з одним зі своїх еднодумців вважав подібний кінець безглуздим - він швидко вирахував спасительні місця у порочному колі, на які поставив себе і свого товариша. І лише тому ми знаємо його історію.

   У нашому варіанті ми почнемо з того, що вшукуємо у коло N чоловік, пронумерованих числами від 1 до N, і будемо виключати кожного k-ого до тих пір, доки не вціліє лише одна людина. (Наприклад, якщо N=10, k=3, то спочатку помре 3-й, потім 6-й, потім 9-й, потім 2-й, потім 7-й, потім 1-й, потім 8-й, за ним - 5-й, і потім 10-й. Таким чином, вціліє 4-й.)

Технічні умови

   Вхідні дані

   У вхідному файлі задано натуральні числа N і k. 1N500, 1k100.

   Вихідні дані

   Вихідний файл повинен містити єдине число - номер людини, що залижилась в живих.

Інформація про задачу

Ліміт часу: 1 секунда
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 9.09091
Складність: 6%
60/64
Класифікація: Сортування та послідовності

Приклад

Приклад вхідних даних

10 3

Приклад вихідних даних

4

 

3. Сортування часу

   Відсортуйте час згідно заданому критерію.

Технічні умови

   Вхідні дані

   У вхідному файлі записано спочатку число N (1N100), а потім N моментів часу. Кожен момент часу задається 3 цілими числами - години (від 0 до 23), хвилини (від 0 до 60) і секунди (від 0 до 60).

   Вихідні дані

   У вихідний файл виведіть моменти часу, упорядковані в порядку неспадання (момент часу також виводиться у вигляді трьох чисел, ведучі нулі виводити не потрібно).

 

Інформація про задачу

Ліміт часу: 1 секунда
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 1.96078
Складність: 13%
53/61
Класифікація: Сортування та послідовності

Приклад

Приклад вхідних даних

4
10 20 30
7 30 00
23 59 59
13 30 30

Приклад вихідних даних

7 30 0
10 20 30
13 30 30
23 59 59

 

4. Велике сортування

   Відсортуйте N заданих чисел у неспадаючому порядку.

Технічні умови

   Вхідні дані

   Задано число N (1N100000), а потім в одному чи декількох рядках N натуральних чисел з діапазону від 1 до 100.

   Вихідні дані

   Виведіть у одному рядку N чисел у неспадаючому порядку.

Інформація про задачу

Ліміт часу: 0.1 секунди
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 7.14286
Складність: 27%
43/59
Класифікація: Сортування та послідовності

Приклад

Приклад вхідних даних

5
3 1 2 4 2

Приклад вихідних даних

1 2 2 3 4

 

5. Градуйований лексикографічний порядок

   Розглянемо цілі числа від 1 до n. Назвемо вагою числа його суму цифр, і позначимо вагу числа x як w(x).

   Потім упорядкуємо числа у так званому градуйованому лексикографічному порядку. Нехай задано два числа a та b. Якщо w(a) < w(b), то число a йде у градуйованому лексикографічному порядку до числа b. Якщо ж w(a) = w(b), тоді число a йде у градуйованому лексикографічному порядку до числа b якщо і лише якщо десяткове подання числа a лексикографічно менше десятикового подання числа b.

   Наприклад, у цьому порядку:

·                     число 120 йде до числа 4;

·                     число 555 йде до числа 78;

·                     число 20 йде до числа 200.

   За заданими n і k, знайдіть номер числа k і число, яке знаходиться на k-му місці, у градуйованому лексикографічному упорядкуванні натуральних чисел від 1 до n.

 

Технічні умови

   Вхідні дані

   У вхідному файлі записані числа n і k (1kn1018).

   Вихідні дані

   У першому рядку вихідного файлу виведіть номер числа k.

   У другому рядку виведіть число, яке знаходиться на k-му місці.

Інформація про задачу

Ліміт часу: 3 секунди
Ліміт пам`яті: 32 MB
Бали за пройдений тест: 4.7619
Складність: 50%
1/2
Класифікація: Сортування та послідовності

Приклад

Приклад вхідних даних

20
10

Приклад вихідних даних

2
14

 

 

 
Синтаксичний розбір і лексичний аналіз виразів PDF Печать E-mail
Добавил(а) Гісь   
22.04.11 14:12

Синтаксичний розбір і лексичний аналіз виразів

Однієї з головних причин, що лежать в основі появи мов програмування високого рівня, з'явилися обчислювальні задачі, що вимагають великих об'ємів рутинних обчислень. Тому до мов програмування пред'являлися вимоги максимального наближення форми запису обчислень до природної мови математики. В зв'язка з цей одній з перших областей системного програмування сформувалося дослідження способів виразів. Тут отримані численні результати, проте найбільше розповсюдження отримав метод трансляції за допомогою зворотного польського запису, який запропонував польський математик Я. Лукашевіч.

Зворотна польська нотація

Нехай заданий простий арифметичний вираз вигляду:

(A+B)*(C+D)-E                (1)

Представимо цей вираз у вигляді дерева, в якому вузлам відповідають операції, а гілкам - операнди. Побудову почнемо з кореня, як який вибирається операція, що виконується останньої. Лівій гілці відповідає лівий операнд операції, а правої гілки - правий. Дерево виразу (1) показано на рис. 1.

                           -
                          / \
                         /   \
                        *     E
                       / \
                      /   \
                     /     \
                    /       \
                   +         +
                  / \       / \
                 /   \     /   \
                А     B   С     D
                       рис. 1

Зробимо обхід дерева, під яким розумітимемо формування рядка символів з символів вузлів і гілок дерева. Обхід скоюватимемо від найлівішої гілки управо і вузол переписувати у вихідний рядок тільки після розгляду всіх його гілок. Результат обходу дерева має вигляд:

AB+CD+*E-                (2)

Характерні особливості виразу (2) полягають в проходженні символів операцій за символами операндів і у відсутності дужок. Такий запис називається зворотним польським записом.

Зворотний польський запис володіє поряд чудових властивостей, які перетворюють її на ідеальну проміжну мову при трансляції. По-перше, обчислення виразу, записаного в зворотному польському записі, може проводитися шляхом однократного перегляду, що є вельми зручним при генерації об'єктного коду програм.  наприклад, обчислення виразу (2) може бути проведено таким чином:

|-----|----------------------|-----------------------|
|  #  |    Аналізований      |    Дія                |
| п/п |       рядок          |                       |
|-----|----------------------|-----------------------|
|  0  |  А B + С D + * E -   |       r1=A+B          |
|  1  |  r1 З D + * E -      |       r2=C+D          |
|  2  |  r1 r2 * E -         |       r1=r1*r2        |
|  3  |  r1 E -              |       r1=r1-E         |
|  4  |  r1                  |  Обчислення закінчено |
|-----|----------------------|-----------------------|
Тут r1, r2 - допоміжні змінні. 

По-друге, отримання зворотного польського запису з початкового виразу може здійснюватися вельми просто на основі простого алгоритму, запропонованого Дейкстpой. Для цього вводиться поняття стекового пріоритету операцій(табл. 1):

        Таблиця 1
|----------|-----------|
| Операція | Пріоритет |
|----------|-----------|
|    (     |     0     |
|    )     |     1     |
|   +|-    |     2     |
|   *|/    |     3     |
|   **     |     4     |
|----------|-----------|

Є видимим початковий рядок символів зліва направо, операнди переписуються у вихідний рядок, а знаки операцій заносяться в стек на основі наступних міркувань:

а) якщо стек порожній, то операція з вхідного рядка переписується в стек;

б) операція виштовхує із стека всі операції з великим або рівним пріоритетом у вихідний рядок;

в) якщо черговий символ з початкового рядка є відкриваюча дужка, то він проштовхується в стек;

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

Процес отримання зворотного польського запису виразу (1) схемно представлений :

Cимвол

1

2

3

4

5

6

7

8

9

10

11

12

13

 

Вхідний рядок

(

A

+

B

)

*

(

C

+

D

)

-

E

 

Стан стека

(

(

+
(

+
(

 

*

(
*

(
*

+
(
*

+
(
*

*

-

-

 

Вихідний
рядок

 

A

 

B

+

 

 

C

 

D

+

*

E

-

 

 

Розбір арифметичного(і не тільки) виразу. Класичні алгоритми.

Алгоритм Рутісхаузера

Даний алгоритм є одним з найстаріших. Його особливістю є припущення про повну дужкову структуру виразу. Під повним дужковим записом виразу розуміється запис, в якому порядок дій задається розстановкою дужок. Неявне старшинство операцій при цьому не враховується. Наприклад:

D:=((C-(B*L))+K)

Обробляючи вираз з повною дужковою структурою, алгоритм привласнює кожному символу з рядка номер рівня за наступним правилом:

1. якщо це дужка або змінна, що відкривається, то значення збільшується на 1;

2. якщо знак операції або дужка, що закривається, то зменшується на 1.

Для виразу (А+(В+С)) привласнення значень рівня відбуватиметься таким чином :

      |-------|---------------------------------------|
      |N симв.| 1   2   3    4   5    6   7    8   9  |
      |-------|---------------------------------------|
      |Символи|                                       |
      |рядка  | (   А   +    (   B    *   З    )   )  |
      |-------|---------------------------------------|
      |Номера |                                       |
      |рівнів | 1   2   1    2   3    2   3    2   1  |
      |-------|---------------------------------------|

Алгоритм складається з наступних кроків:

1. виконати розстановку рівнів;

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

3. виділити трійку - два операнди з максимальним значенням рівня і операцію, яка укладена між ними;

4. результат обчислення трійки позначити допоміжній змінній;

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

6. виконувати п.п.2 - 5 до тих пір, поки у вхідному рядку не залишиться одна змінна, що позначає загальний результат виразу.

Приклад розбору :

          
     |------------|--------------------------------------|
     |Генерируючі |            Вираз                     |
     |   трійки   |                                      |
     |------------|--------------------------------------|
     |            |   ( ( ( ( А + В ) * З ) / D ) - E )  |
     |            | 0 1 2 3 4 5 4 5 4 3 4 3 2 3 2 1 2 1 0|
     |            |                                      |
     |+ А В - > R |      ( ( ( R * З ) / D ) - E )       |
     |            |    0 1 2 3 4 3 4 3 2 3 2 1 2 1 0     |
     |            |                                      |
     |* R З -> S  |          ( ( S / D ) - E )           |
     |            |        0 1 2 3 2 3 2 1 2 1 0         |
     |            |                                      |
     |------------|--------------------------------------|
 
     |------------|-----------------------------------|
     |Генерируючі |            Вираз                  |
     |   трійки   |                                   |
     |------------|-----------------------------------|
     |/ S D -> Q  |         ( Q - E )                 |
     |            |       0 1 2 1 2 1 0               |
     |            |                                   |
     |- Q E -> T  |             T                     |
     |------------|-----------------------------------|

Алгоритм Бауера і Замельзона

З ранніх стекових методів розглядається алгоритм Бауера і Замельзона. Алгоритм використовує два стеки і таблицю функцій переходу. Один стек використовується при трансляції виразу, а другий - під час інтерпретації виразу. Позначення: Т - стек транслятора, Е - стек інтерпретатора.

В таблиці переходів задаються функції, які повинен виконати транслятор при розборі виразу. Можливі шість функцій при прочитанні операції з вхідного рядка:

- f1 - заслати операцію з вхідного рядка в стек Т; читати наступний символ рядка;

- f2 - виділити трійку - узяти операцію з вершини стека Т і два операнди з вершини стека Е; допоміжну змінну, що позначає результат, занести в стек Е; заслати операцію з вхідного рядка в стек Т; читати наступний символ рядка;

- f3 - виключити символ із стека Т; читати наступний символ рядка;

- f4 - виділити трійку - узяти операцію з вершини стека Т і два операнди з вершини стека Е; допоміжну змінну, що позначає результат, занести в стек Е; по таблиці визначити функцію для даного символу вхідного рядка;

- f5 - видача повідомлення про помилку;

- f6 - завершення роботи.

Таблиця переходів для виразів алгебри матиме вигляд(символ $ є ознакою порожнього стека або порожнього рядка):

 |----------|---------------------------------|
 |          |     Операція з вхідного рядка  |
 |          |---------------------------------|
 |          |     $   (   +   -   *   /   )   |
 |----------|---|-----------------------------|
 |Операція  |$  | 6   1   1   1   1   1   5   |
 |на вершині|(  | 5   1   1   1   1   1   3   |
 |стека Т   |+  | 4   1   2   2   1   1   4   |
 |          |-  | 4   1   2   2   1   1   4   |
 |          |*  | 4   1   4   4   2   2   4   |
 |          |/  | 4   1   4   4   2   2   4   |
 |----------|---|-----------------------------|

Алгоритм проглядає зліва направо вираз і циклічно виконує наступні дії: якщо черговий символ вхідного рядка є операндом, то він безумовно переноситься в стек Е; якщо ж операція, то по таблиці функцій переходу визначається номер функції для виконання. Для виразу А+(В-С)*D нижче приводиться послідовність дій алгоритму.

    |-------|--------|-------|-------|----------|
    |стек Е | стік Т |Вхідний|Номер  |   Трійка |
    |       |        |символ |функції|          |
    |-------|--------|-------|-------|----------|
    |$      | $      |  А    |       |          |
    |$A     | $      |  +    |    1  |          |
    |$A     | $+     |  (    |    1  |          |
    |$A     | $+(    |  B    |       |          |
    |$AB    | $+(    |  -    |    1  |          |
    |$AB    | $+(-   |  З    |       |          |
    |$ABC   | $+(-   |  )    |    4  |- B З ->R |
    |$AR    | $+(    |  )    |    3  |          |
    |$AR    | $+     |  *    |    1  |          |
    |$AR    | $+*    |  D    |       |          |
    |$ARD   | $+*    |  $    |    4  |* R D ->Q |
    |$AQ    | $+     |  $    |    4  |+ А Q ->S |
    |$S     | $      |  $    |Кінец  |          |
    |-------|--------|-------|-------|----------|   

 

Задачі

Задача GoTo.

Учні, недавно що почали програмувати, вживають дуже багато операторів GOTO, що є майже неприпустимим для структурованої програми. Допоможіть викладачу інформатики написати програму, яка оцінюватиме ступінь структурованості відладженої програми школяра на мові Pascal, спершу просто підраховувавши кількість операторів GOTO в ній.

В синтаксично вірній програмі ключове слово оператора переходу GOTO може стояти або на початку рядка або після пропуску або після одного з символів — ‘;’, ‘:’, ‘}’, а після нього може стояти або пропуск або переклад рядка або символ ‘{‘ (табуляцію як роздільник розглядати не будемо).

Нагадаємо, що окрім позначення дійсно оператора переходу, слово GOTO може зустрічатися в тексті програми в рядкових константах, укладених в апострофи, або в коментарях, причому для простоти вважатимемо, що коментар завжди починається з символу ‘{‘, а закінчується першим що зустрівся після цього символом ‘}’, при цьому символ ‘{‘ повинен знаходитися не усередині рядкової константи. В цих випадках слово GOTO підраховувати не потрібно. Рядкові і прописні букви в Pascal не помітні.

У вхідному файлі goto.in знаходиться текст програми без синтаксичних помилок на мові Pascal. Розмір програми не перевершує 64К. У вихідному файлі goto.out повинне виявитися одне число – кількість операторів GOTO в цій програмі.

Приклад вхідного файлу:

label 1,2;

var I:byte;

begin

 1: I:=I+1;

    if I>10 then goto 2 else

      writeln(¢ goto ¢); GoTo 1;

 2: if I<10 then goto 1 {else { goto 2;}

end.

Вихідний файл для наведеного приклад

3

Додаткові задачі

1.      Правильність розстановки дужок.

арифметичних виразів за допомогою постфіксної нотації

Література

1.      Ахо А., Сети Р., Ульман Д. Компиляторы. Принципы, технологии, инструменты. М.: Вильямс, 2001.

2.      Бауэр Ф.Л., Гооз Г. Информатика. Вводный курс. Часть 2, М.: Мир, 1990.

3.      Кук Д., Бейз Г. Компьютерная математика. М.: Наука, 1990.

4.      Шень А. Программирование: теоремы и задачи. М.: МЦНМО, 1995.

5.      Грузман М.З. Евристика в інформатиці. Вінниця: Арбат, 1998.

 


Страница 23 из 27

Статистика

Пользователей : 152
Статей : 222
Просмотрено статей : 89856

Вход/Регистрация

Нет