|
Добавил(а) Гісь Ігор Володимирович
|
|
03.10.12 09:24 |
|
Задача 4. Task4
Для заданого натурального N(N<=100) знайти всі значення виразу a o b о c, яке повторюється найбільше, де a, b, c натуральні числа <=N операцією o(+ - *).
Вхідний файл Task4.in містить рядок з одного натурального числа.
Вихідний файл Task4.out містить рядок з знайденим результатом. Якщо таких значень декілька, то вивести максимальний. |
|
Последнее обновление 03.10.12 10:06 |
|
Готуємось до олімпіади з інформатики (додаток 3) |
 |
 |
 |
|
Добавил(а) Administrator
|
|
01.11.13 10:57 |
|
Додаток 3
Готуємось до олімпіади з інформатики
(додаток 3)
|
Єдиний спосіб вивчати нову мову програмування –
писати на ній програми.
Брайен Керніган
План роботи
|
- Олімпіадна інформатика. Методика організація роботи з обдарованими учнями.
- Тематика олімпіадних задач. Методика складання алгоритмів та їх аналіз.
- Правила проведення олімпіад по програмуванню. Типові помилки і налагодження програм. Система для автоматичного тестування програм ejudge.
- Практикум з розв’язування олімпіадних задач.
|
Олімпіадна інформатика
1. Що таке олімпіадна інформатика?
Що потрібне для успішної участі в олімпіадах по інформатиці? Як показує практика, тільки знання мови програмування для цього явно не достатньо. Взагалі, виявляється, що олімпіадні задачі по інформатиці лежать десь на стику математики і програмування. І дуже часто виявляється, що розв’язуючи задачі школярі не тільки вчаться програмувати, але і освоюють нові розділи математики.
2. Як перевіряються розв’язки задач олімпіади
Історично склалося так, що розв’язки на олімпіадах по програмуванню перевіряються автоматично. Ваше завдання написати програму, яка за заданими вхідними даними обчислює і виводить вихідні дані.
3.Апаратне та програмне забезпечення
Учасникам олімпіади можуть вибирати мову програмування с заданого переліку: Pascal, C або C++. Система програмування Free Pascal 2.0 (чи новішої версії), GCC 4.2 (чи новішої версії), Turbo Delphi Explorer, Visual C++ 2008 Express).
4. Тематика задача олімпіади
Завдання олімпіади мають бути алгоритмічного характеру, тобто основними результатами роботи учасника має бути: алгоритм, що правильно та ефективно розв’язує поставлену задачу, та програма, що реалізує запропонований алгоритм.
Основними категоріями олімпіадних задач є:
|
Геометрія
Графічні задачі
Динамічне програмування
Довга арифметика
Жадібний алгоритм
Задачі для початківців
Комбінаторика
Масиви
Математика
Математичне моделювання
|
Обробка рядків
Послідовності
Рекурсія, перебір
Логічні задачі
Сортування
Структури даних
Теорія графів
Теорія ігор
Теорія чисел
|
| |
- Етап олімпіади
- Інформатика
- Інформаційні технології
|
|
|
|
| |
|
- Теорія чисел: розклад числа на множники
- Обчислювальна геометрія: довжина відрізка, властивості геометричних фігур
- Пошук та сортування масивів
- Повний перебір, динамічне програмування
|
- Текстовий редактор: параметри сторінки, форматування шрифту і абзацу, колонтитули, форматування графічних об’єктів, колонки
- Презентації: створення авто фігур, налаштування анімації руху по колу з налаштуванням періоду
- Електронні таблиці: формули з використанням функцій (логічних, математичних ЕСЛИ, СУММЕСЛИ, ABS), побудова діаграм
- СУБД: створення таблиць, форм, запитів на вибір та з параметром, звітів з групуванням
|
|
| |
|
- Синтаксичний аналіз: робота з рядками
- Пошук та сортування масивів
- Теорія чисел: НСД
- Динамічне програмування
- Теорія графів
|
- Текстовий редактор: параметри сторінки, форматування шрифту і абзацу, колонтитули, форматування графічних об’єктів, колонки, розділи
- Презентації: створення авто фігур, групування, налаштування анімації, кнопки, гіперпосилання
- Електронні таблиці: формули з використанням функцій (логічних, математичних, посилання і масиви, перевірка властивостей і значень ЕСЛИ, СУММЕСЛИ, ABS, СТОЛБЕЦ, СТРОКА, ЕПУСТО), побудова діаграм, елементи форми
- СУБД: створення таблиць, зв’язок між таблицями, створення декількох ключових полів, форм в ручну, запитів на вибір та з параметром, групові операції , звітів з групуванням, макроси
|
|
| |
|
- Повний перебір
- Жадібні алгоритми
- Динамічне програмування
- Граф: пошук найкоротшого шляху, пошук в ширину
- Обчислювальна геометрія: опуклі многокутники
- Структури даних: дерево
|
- Текстовий редактор: макрос в режимі автозаписуванням
|
|
| |
|
|
|
|
5. Системи тестування
Працюйте в он-лайн системах, які автоматично перевіряють та тестують Ваші розв’язки:
http://olymp.sumdu.edu.ua - Веб-ресурс підтримки та проведення шкільних та студентських олімпіад з інформатики
http://www.e-olimp.com.ua/ - Інтернет-портал організаційно-методичного забезпечення дистанційних олімпіад з програмування для обдарованої молоді навчальних закладів України
http://www.olymp.vinnica.ua/ - Центр підтримки та проведення олімпіад школярів з використанням можливостей Internet.
Список тестуючи систем
7. Логічні задачі
Задача 1.
Переможці олімпіад.
П’ятеро однокласників: Ірина, Тарас, Катя, Сергій і Микола стали переможцями олімпіад школярів з фізики, математики, інформатики, літератури та географії. Відомо, що:
- переможець олімпіади з інформатики вчить Іірину і Тараса працювати на комп’ютері;
- Катя і Сергій також зацікавились інформатикою;
- Тарас завжди побоювався фізики;
- Катя, Тарас і переможець олімпіади з літератури займаються плаванням;
- Тарас і Катя привітали переможця олімпіади з математики;
- Іра шкодує, що в неї залишається мало часу на літературу.
Переможцем якої олімпіади став кожен з учнів?
8. Базові структури алгоритмів: слідування, розгалуження, цикл.
Задача 2. «Фотокартка» (PHOTO)
Учень на новенькому кольоровому струменевому принтері учень надрукував фотографії зроблені у свій день народження. Розмір фото AxB cм. Роздільна здатність принтера R точок на дюйм (1 дюйм = 2,54 см).
Завдання
Визначити скільки пікселів містить надруковане фото?
Вхідні дані
Перший рядок містить два дійсні числа, які задають розмір фотокартки. Останній рядок містить натуральне число, яке задає роздільну здатність. Усі числа вхідного файлу за абсолютною величиною не перевищують 1 000 000 000.
Вихідні дані
Єдиний рядок файлу містить шукану кількість мегапікселів на фотографії, як дійсне число з двома знаками після коми.
Приклад
|
input.dat
|
output.ans
|
|
2.54
2.54
1000
|
1.00
|
Задача 3. «Клас» .
На початку навчального року класний керівник між учнями класу поділила N зошитів та M олівців. Скільки учнів в класі, якщо відомо їх не менше ніж K і кожний з учнів отримав однакову кількість зошитів та олівців.
Вхідні дані
Перший рядок містить натуральні числа N, M, K. Усі числа вхідного файлу не перевищують 1 000 000 000.
Вихідні дані
Єдиний рядок файлу містить знайдену кількість учнів. Якщо результатів декілька, то вивести всі через пропуск в зростаючому порядку.
Приклад
|
input.dat
|
output.ans
|
|
92
138
25
|
46
|
Задача 4. «День народження» – 30 балів.
Учень на своє день народження роздав учням класу цукерки, в тому числі і собі. Хлопцям давав парну кількість, а дівчатам непарну кількість. Підрахувати кількість дівчат та хлопців в класі.
Вхідні дані
Перший рядок містить загальну кількість учнів, натуральне число N.
В наступних рядках кількість розданих цукерок.
Усі числа вхідного файлу не перевищують 1 000 000 000.
Вихідні дані
Єдиний рядок файлу містить кількість дівчат та хлопчиків через пропуск.
Приклад
|
input.dat
|
output.ans
|
|
5
3
1
2
4
3
|
3 2
|
9. Структуровані типи величин.
Операції з масивом.
|
Операція з масивом
|
Pascal
|
C++
|
|
Опис
|
Var a:array[1..100] of integer;
i, n:integer;//індекс, кількість елементів
|
int a[100];
int i, n;//індекс, кількість елементів
|
|
Введення
|
readln(n);
for i:=1 to n do read(a[i]);
|
cin>>n;
for(i=1;i<=n;i++)cin>>a[i];
|
|
Виведення
|
for i:=1 to n do write(a[i],’ ‘);
|
for(i=1;i<=n;i++)cout<<a[i]<<” “;
|
|
Сумування
|
s=0;
for i:=1 to n do s:=s+a[i];
|
s=0;
for(i=1;i<=n;i++)s=s+a[i];
|
|
Пошук
|
readln(k);
for i:=1 to n do if a[i]=k then writeln(i);
|
cin>>k;
for(i=1;i<=n;i++) if (a[i]==k) cout<<i;
|
|
Пошук максимального
|
max:=a[1];nmax:=1;
for i:=2 to n do if a[i]>max then begin max:=a[i];nmax:=i;end;
|
max=a[1];nmax=1;
for(i=2;i<=n;i++)if (a[i]>max) {max=a[i];nmax=i;}
|
|
Сортування
|
for i:=1 to n -1do
for j:=1 to n -1do
if a[j]>a[j+1] then begin
temp:=a[j];
a[j]:=a[j+1];
a[j+1]:=temp;
end;
|
for(i=1;i<n;i++)
for(j=1;j<n;j++)
if (a[j]>a[j+1])
{temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;}
|
|
Стирання
|
n:=n-1;
for i:=k to n do a[i]:=a[i+1];
|
n=n-1;
for(i=k;i<=n;i++)
a[i]=a[i+1];
|
|
Вставка
|
n:=n+1;
for i:=n downto k+1 do
a[i]:=a[i-1];
|
n=n+1;
for(i=n;i>=1;i--)
a[i]=a[i-1];
|
10. Робота з файлами
|
Pascal
|
C++
|
|
var f1,f2:text;
assign(f1,’input.dat’);
reset(f1);
read(f1,...);
close(f1);
assign(f2,’output.dat’);
rewite(f2);
write(f2,...);
close(f2);
|
#include <fstream.h>
void main()
{
ifstream inp;inp.open("input.dat");
int a,b,c;
inp>>a>>b;
inp.close();
c=a+b;
ofstream out;out.open("output.sol");
out<<c;
out.close();
}
|
|
assign(input,’input.dat’);
reset(input);
read(...);
close(input);
assign(output,’output.dat’);
rewite(output);
write(...);
close(output);
|
#include <fstream.h>
ifstream inp("input.dat");
ofstream out("output.sol");
void main()
{
int a,b,c;
inp>>a>>b;
c=a+b;
out<<c;
}
|
- Є велика кількість завдань, які вимагають знання з теорії чисел. Наприклад , знаходження простих чисел, розкладання на прості множники , поділ з остачею, НСД та НСК і т.д.
- Ряд
- Приклад
- Формула N елемента
- Рекурентне співвідношення
- Непарні числа
- 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21
- 2n-1
- an=an-1+2
- Арифметична прогресія
- 3, 6, 9, 12,15,18,21
- an=a1+(n-1)d
- an=an-1+d
- Прості
- 2, 3, 5, 7, 11, 13, 17, 23
- Фібоначчі
- 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
- 1/√5((1+√5)/2-(1-√5)/2)n
- F(n) = F(n-1) + F(n-2) для F(0) = 0 та
- F(1) = 1.
- Факторіал
- 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800
- n(n-1)(n-2)…2.1
- F(n)=F(n-1)*n
- Каталана
- 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796
- (2n)!/(n!(n+1)!)
- Cn=∑CiCn-1-i
- Комбінації
- 1,3,6,3,1
- n!/(k!(n-k)!
- Cmn=Cmn-1(m-n+1)/n
- …
|
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
|
Практичний тур
|
http:://olymp.gimn14.lutsk.ua/new-register
- вибрати турнір: Опорна школа. Теорія чисел
- створити обліковий запис, зареєструватися в системі ввівши логін, адресу електронну пошту (пароль записати)
- ввійти в систему
- відредагувати дані (ввести ім’я учасника: Прізвище, ім’я, школа)
- підтвердити реєстрацію
- протестувати задачі
|
Задача 5.
XVII Всеукраїнська олімпіада з інформатики. Другий тур. Працівники (100 балів)
На заводі кожна з N деталей може бути обробленою на одному з двох верстатів: A або B. Кожна деталь має порядковий номер від 1 до N. До обробки деталі поступають послідовно, у відповідності зі своїми номерами. Кількість деталей завжди парна.
Існують правила, за якими визначається чи можна обробляти деталь на певному верстаті.
- Якщо на поточний момент на верстаті B була оброблена така ж кількість деталей, як і на верстаті A, то наступна деталь повинна бути оброблена на верстаті A.
- У підсумку на кожному з верстатів повинно бути оброблено однакову кількість деталей.
Скільки існує людей, стільки і думок. Кожен із працівників цього заводу запропонував свою послідовність обробки деталей, причому всі пропозиції виявилися різними, але такими, що задовольняють правилам 1 і 2.
Завдання
Напишіть програму STAFF, що за інформацією про кількість деталей N визначає максимальну можливу кількість працівників заводу.
Вхідні дані
Єдиний рядок вхідного файлу STAFF.DAT містить парне число N (2≤N≤28) – кількість деталей яку необхідно обробити.
Вихідні дані
Єдиний рядок вихідного файлу STAFF.SOL має містити ціле число – максимальну можливу кількість працівників заводу.
Приклад вхідних та вихідних даних
Перший працівник вважає що на верстаті A необхідно обробити деталі 1 та 2, а на верстаті B, відповідно, 3 та 4. Другий має думку, що на верстаті A потрібно обробити деталі 1 та 3, а на станке B – деталі 2 та 4. Інших варіантів послідовності обробки немає.
Задача 6.
XIX Всеукраїнська олімпіада з інформатики. Перший тур. Дільники (100 балів)
За заданим натуральним числом N необхідно обчислити кількість натуральних чисел, які є дільниками N! (факторіалу числа N).
Наприклад, при N=4, N!=4·3·2·1=24. Це число має такі дільники: 1, 2, 3, 4, 6, 8, 12, 24. Таким чином шукана кількість дорівнює 8.
Завдання
Напишіть програму DIVISOR, що за натуральним N, знаходить кількість дільників його факторіалу.
Вхідні дані
Єдиний рядок вхідного файлу DIVISOR.DAT містить одне ціле число N (1≤N≤45).
Вихідні дані
Єдиний рядок вихідного файлу DIVISOR.SOL має містити одне ціле число – знайдену кількість дільників числа N!
Приклад вхідних та вихідних даних
Задача 7.
Просте число — це натуральне число, яке має рівно два натуральних дільника (лише 1 і саме число)
Послідовність простих чисел починається так:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113 , 127, 131, 137, 139, 149, …
Написати програму виведення простих чисел в діапазоні до N.
|
Мова програмування
|
Варіант 1
|
Варіант 2
|
|
Pascal
|
var n,i,j:integer;
p:integer;
begin
readln(n);
for i:=2 to n do
begin
p:=0;
for j:=2 to round(sqrt(i)) do
if i mod j =0 then p:=1;
if p=0 then write(i,' ');
end;
end.
|
var a:array[1..100000000] of integer;
j,k,n,i:integer;
begin
readln(n);
for i:=1 to n do a[i]:=i;
a[1]:=0;
i:=1;
while i<=n div 2 do begin
while a[i]=0 do i:=i+1;
j:=i+a[i];
while j<=n do begin
a[j]:=0;
j:=j+a[i];
end;
i:=i+1;
end;
for k:=1 to n do
if a[k]<>0 then write(a[k],' ');
writeln;
end.
|
|
С++
|
// прості 2 3 5 7 11 13 17
#include "stdafx.h"
#include "iostream"
using namespace std;
int main()
{int n,i,j,p;
cin>>n;
for (i=2;i<=n;i++)
{p=0;
for (j=2;j<i; j++)
if (i%j==0) p=1;
if ( p==0) cout<<i<<" ";}
return 0;
}
|
#include "iostream"
using namespace std;
int main()
{int n;
cin>>n;
int *a=new int[2*n];
int j,i;
for(i=1;i<=n;i++)a[i]=i;
a[1]=0;i=1;
while (i<=n/2)
{while (a[i]==0) i++;
j=i;
while (j<=n){j=j+a[i];a[j]=0;}
i++;
}
for (i=1;i<=n;i++)
if (a[i]!=0)cout<<a[i]<<" ";
}
|
Фіксація часу роботи програми
|
Pascal (Delphi)
|
C++ (Visual C++)
|
|
uses
SysUtils, windows;
var time:int64;
begin
time:=gettickcount;
//*****************************
time:=gettickcount-time;
writeln(time/1000:0:5);
end.
|
#include <time.h>
using namespace std;
int main()
{
//системний час до
clock_t start = clock();
//*********************
// час після
long double r=(clock() - start)*1. / CLOCKS_PER_SEC;
cout<<"times work = "<<r<<endl;
return 0;
}
|
Теорія графів
|
1
|
Пошук в глибину
|
void p(int k, int v)
{c[k]=v;
if (v==v2 || k>=n) {
if (v==v2)
{
//for (int i=1;i<=k;i++)cout<<c[i]<<" ";cout<<endl;
int s=0;
for (int i=1;i<k;i++)s=s+a[c[i]][c[i+1]];
//cout<<"s="<<s<<endl;
if (s<m) m=s;
}
}
else
for (int i=1;i<=n;i++)
if (a[v][i]>0) p(k+1,i);
}
|
|
2
|
Флойда
|
k= 1;
for(i= 1;i<=n;i++)x[i]=a[v1][i];
// {инвариант: x[i] = МинСт(1,i,k)}
while (k!=n)
{
for(s=1;s<=n;s++){
y[s]=x[s];
for(i=1;i<=n;i++) if (y[s]>x[i]+a[i][s]) y[s]= x[i]+a[i][s];
// {y[s] = МинСт(1,s,k+1)}
for (i=1;i<=n;i++) x[s]=y[s];
}
k++;
}
|
|
3
|
Форда
|
for (int k=1; k<=n; k++)
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
a[i][j] = min (a[i][j], a[i][k] + a[k][j]);
|
|
4
|
Прима
|
|
Задача 8. Дорога в гімназію.
Задача Дорога в школу
|
Имя входного файла:
|
input.dat
|
|
Имя выходного файла:
|
output.ans
|
|
Ограничение времени:
|
30 с
|
|
Ограничение памяти:
|
64 M
|
Задача 4. Дорога в гімназію
На вимогу класного керівника учень знайшов в Інтернеті карту міста на якій він визначив і задав в декартовій системі координат координати точок на шляху від доми до гімназії, і намалював дороги між ними (див. рис). Допоможіть учню визначити хоча б довжину найкоротшої дороги від доми до школи.
Формат вхідних даних
Наступні N рядків містять через проміжок координати Xi , Yi точок на карті. Значення координат по модулю менші 50000. Перші координати задають – координати доми, а останні – координати гімназії. Наступні рядків задають карту намальованих доріг початкова та кінцева точка.
Формат результату
Єдиний рядок має містити дійсне число з трьома знаками після коми – дожину найкоротшої дороги. Якщо дороги немає вивести "no".
Приклад
|
input.dat
|
output.ans
|
6
150 70
160 90
100 100
170 120
120 140
80 160
1 2
2 3
2 4
3 5
4 5
5 6
|
152.556
|
Задача 9. Дорога в гімназію 2.
На вимогу класного керівника учень знайшов в Інтернеті карту міста на якій він визначив і задав в декартовій системі координат координати точок на шляху від доми до гімназії, і намалював дороги між ними (див. рис). Допоможіть учню визначити довжину найкоротшої дороги та сам маршрут від доми до школи.
Формат вхідних даних
Наступні N рядків містять через проміжок координати Xi , Yi точок на карті. Значення координат по модулю менші 50000. Перші координати задають – координати доми, а останні – координати гімназії. Наступні рядків задають карту намальованих доріг початкова та кінцева точка.
Формат результату
Єдиний рядок має містити дійсне число з трьома знаками після коми – дожину найкоротшої дороги та рядок цілих чисел, які задають маршрут. Якщо дороги немає вивести "no".
Приклад
|
input.dat
|
output.ans
|
6
150 70
160 90
100 100
170 120
120 140
80 160
1 2
2 3
2 4
3 5
4 5
5 6
|
152.556
1 2 4 5 6
|
Задача 10.
Збирання мита (TALLAGE) -100 балів.
Король країни Аріїв завоював Nміст на території сусідніх держав.
Тепер йому необхідно створити систему збирання мита з завойованих територій. Він хоче збудувати таку систему шляхів між цими містами, щоб до будь-якого міста можна було дістатися (можливо, через інші міста) зі столиці, але у воєнному стані на транспорт виділяється дуже незначна частина фінансів, тому сумарна вартість побудованих шляхів сполучення між містами має бути мінімальною.
Вхідні дані:
Перший рядок вхідного файлу містить натуральне число N (1≤N≤100) – кількість міст у країні, а також цілі числа X та Y – координати столиці.
Наступні N рядків містять через проміжок координати Xi , Yi завойованих міст.
Значення координат по модулю менші 50000.
Вихідні дані:
Єдиний рядок має містити дійсне число з трьома знаками після коми – сумарну вартість побудованих доріг. Вважайте, що вартість одиниці довжини дороги дорівнює одній умовній одиниці.
Приклади:
|
input.dat
|
output.ans
|
|
6 0 0
1 1
-1 1
0 2
1 -1
-1 -1
0 -2
|
8.485
|
6. Список ресурсів
|
|
Последнее обновление 13.11.13 11:53 |
|
|
16_01_2012 Рядкові величини. Синтаксичний та лексичний розбір виразів. |
|
|
|
|
Добавил(а) Гісь Ігор Володимирович
|
|
16.01.13 12:47 |
|
Обробка тексту
Функції обробки тексту. По символьна обробка тексту. Пошук заданого підрядка в тексті. Алгоритм Бойєра-Мура. Використання хеш-функції для пошуку довільного підрядка у рядку. Рекурсивний синтаксичний аналіз виразів із дужками.
Рядкові величини
Pascal (Delphi)
- операція + (з’єднання) ‘місто’+’ ’+’Луцьк’
Функції роботи з рядками:
|
№
|
Назва функції
|
Призначення
|
Приклад
|
Результат
|
|
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
|
C++
Функції для опрацювання рядків
Модуль string.h
strlеn(<рядок>) - визначає фактичну кількість символів у рядку, застосовується у виразах;
strcat(rl, r2) - команда з'єднання рядків г1, г2 в один рядок, результат присвоює змінній г1;
strncat(M, г2, п) - до змінної г1 додає перших n символів рядка г2, команда;
strcpy(r1, r2) - копіює символи з рядка г2 в рядок г1, команда;
strncpy(r1, r2, n) - копіює перших n символів рядка г2 в рядок r1, команда;
strchr(r1, <символ>) - визначає перше входження деякого символу у рядок r1 так: повертає рядок, який починається від першого входження заданого символу до кінця рядка r1, застосовується у виразах;
strrchr(r1, <символ>) - визначає останнє входження заданого символу у рядок, застосовується у виразах;
strspn(r1, r2) - визначає номер першого символу, який входить у рядок г1, але не входить
у рядок г2, застосовується у виразах
strstr(r1, r2) - визначає в рядку г1 підрядок, що починається з першого входження рядка г2 у рядок г1, застосовується у виразах;
strtok(r1, r2) - визначає частину рядка г1, яка закінчується перед першим однаковим символом рядків г1 та г2;
strnset(r1, <символ>, n) - вставляє п разів заданий символ • перед рядком М, застосовується у виразах;
strupr(rl) - перетворює усі малі літери рядка у великі;
strlwr(rt) - перетворює усі великі літери рядка у малі;
strrev(rl) - записує рядок у зворотному порядку.
|
Застосування функцій
|
Результат
|
|
Lviv = "НУ Львівська політехніка"
|
|
n = strlen(Lviv)
|
n = 21
|
|
strcat(Un, Lviv)
|
Un = "НУ Львівська політехніка"
|
|
strncat(Un, Lviv, 10)
|
r1 = "НУ Львівська"
|
|
strcpy(r1, Lviv)
|
r1 = "Львівська Політехніка"
|
|
strncpy(r1, Lviv, 10)
|
r1 = "Львівська"
|
|
p = strchr(Lviv, 'П')
|
p = "політехніка"
|
|
p = strrchr(Lviv, Ї)
|
p = "іка"
|
|
n = strspn(Lviv, "Львів")
|
n = 5
|
|
p = strstr(Lviv, "теж")
|
p = "техніка"
|
|
p = strtok(Lviv, "кс")
|
p = "Львів"
|
|
p = strnset(Lviv, 'x', 10)
|
p = "ххххххххххполітехніка"
|
|
p = strupr("I Love You")
|
p = "і love you"
|
|
p = strlwr("I Love You")
|
p = "I LOVE YOU"
|
|
p = strrev('тexнiкa")
|
p = "акінхет"
|
Задачі
Задача1. ACM World Finals
Ім’я вхідного файлу: acm.in
Ім’я вихідного файлу: acm.out
Дехто з вас, мабуть, знає, що кожного року проводиться чемпіонат світу з програмування серед студентів. У фінал цього змагання проходять близько 80 команд з усього світу.
Кожна команда складається з трьох чоловік і має назву. Напишіть програму, яка по короткій назві команди і прізвищах її учасників, формує повну назву команди.
Повна назва команди складається з короткої назви команди і списку прізвищ її учасників. Прізвища учасників у списку мають бути впорядковані за абеткою і відділені одне від іншого комами. Назва команди від прізвищ учасників має бути відділена двокрапкою. Після кожного розділового знаку має бути рівно один пробіл.
Формат вхідних даних: вхідний файл містить рівно 4 рядки. Перший рядок містить назву команди. Кожен із наступних трьох рядків містить прізвище одного із членів команди. Довжини рядків не перевищують 50 символів.
Формат вихідних даних: єдиний рядок вихідного файлу має містити рівно один рядок з повною назвою команди.
Приклад вхідних і вихідних даних:
|
acm.in
|
acm.out
|
|
Dream Team
Knuth
Dijkstra
Cormen
|
Dream Team: Cormen, Dijkstra, Knuth
|
Задача2. 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
Задача 3. Дужки.
Перевірити в виразі правильність розставлення дужок. Вивести повідомлення (Yes|No).
Задача 4. Вираз
Обчислити вираз, який містить операції( +,-,*,/), цілі та дійсні числа (2, 2.5, -5.02), дужки.
Тема: Синтаксичний розбір виразів
Однієї з головних причин, що лежать в основі появи мов програмування високого рівня, з'явилися обчислювальні задачі, що вимагають великих об'ємів рутинних обчислень. Тому до мов програмування пред'являлися вимоги максимального наближення форми запису обчислень до природної мови математики. В зв'язка з цей одній з перших областей системного програмування сформувалося дослідження способів виразів. Тут отримані численні результати, проте найбільше розповсюдження отримав метод трансляції за допомогою зворотного польського запису, який запропонував польський математик Я. Лукашевіч.
Нагадаємо, що існує цілий ряд методів синтаксичного розбору і обчислення виразів. Нехай вирази є рекурсивними структурними даними, які визначаються в термінах самих себе. Якщо ви обмежитеся використанням у виразах тільки операторів +, - * / і дужок, то зможете сказати, що всі вирази можуть бути визначеними в термінах наступних правил:
выраз=>терм[+терм][-терм]
терм=>множник[*множник][/множник]
множник=>змінна, число або (вираз) де будь-яка частина може бути порожньою. Квадратні дужки позначають необов'язковість, а => - утворення. Фактично правила є правилами утворення виразів.
Вираз 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.
Якщо ви трохи заплуталися, не турбуйтеся. Це складна концепція. Потрібно засвоїти два моменти про даний рекурсивний погляд на вирази: по-перше, передування операторів є неявним при заданих правилах породження виразів; по-друге, даний метод синтаксичного розбору і обчислення виразів дуже схожий на те, як це робиться уручну. |
|
Последнее обновление 23.01.13 13:06 |
|
3. Готуємось до олімпіади з інформатики |
|
|
|
|
Добавил(а) Administrator
|
|
21.01.15 09:18 |
|
Готуємось до олімпіади з інформатики
$11. Сума арифметичної прогресії
|
int s=0;
for(int i=a1;i<=an;i=i+d)s=s+i;
|
.
int s=(a1+an)*n/2;
|
$12. Числа Фібоначі
|
int a1(1),a2(1);
for (int i=3;i<=n;i++)
{a3=a1+a1;
a1=a2;
a2=a3;
}
|
int a[100];
a[1]=1; a[2]=1;
for (int i=3;i<=n;i++)
a[i]=a[-1]+a[i-2];
|
#include "stdafx.h"
#include <iostream>
#include <math.h>
using namespace std;
int main(){
double n,f;
cin>>n;
f=1/sqrt(5.0)*(pow((1+sqrt(5.0))/2.0,n)+pow((1-sqrt(5.0))/2.0,n));
cout.precision(0);
cout<<fixed<<f<<endl;
return 0;
}
Exp(y*ln(x)
Power(x,y)
A:=strtoint(‘123’);
|
$13. Алгоритм Евкліда
|
#include "stdafx.h"
#include <iostream>
using namespace std;
int main(){
int a,b,a1,b1,t;
cin>>a>>b;
a1=a;b1=b;
while (b!=0)
{t=a%b;
a=b;
b=t; }
int nsd=a;
int nsk=a1*b1/nsd;
cout<<nsd<<endl;
cout<<nsk<<endl;
return 0;
}
|
$14. Прості числа (решето Ератосфена)
|
#include "iostream"
#include "math.h"
using namespace std;
int main()
{int n,p;
cin>>n;
for(int i=2;i<=n; i++)
{p=0;
for(int j=2;j<=int(sqrt(double (i)));j++)
if (i%j ==0)p=1;
if (p==0) cout<<i<<endl;
}
return 0;
}
|
#include "iostream"
#include "math.h"
using namespace std;
int a[10000];
int main()
{int n,p,i,j;
cin>>n;
for(i=1;i<=n; i++)a[i]=i;
a[1]=0;i=1;
while (i<=n/2)
{
while (a[i]==0)i++;
j=i+a[i];
while (j<=n)
{a[j]=0;
j=j+a[i];}
i++;
}
for(i=1;i<=n;i++)
if (a[i]!=0 ) cout<<a[i]<<" ";
}
|
$15. Зчитування та порівняння рядків та символів
|
char a;
cin>>a;
if (a=='A') cout<<"ok"<<endl;else cout<<"no"<<endl;
|
#include “string.h”
char a[1000],b[1000];
cin.getline(a,sizeof(a));
cin.getline(b,sizeof(b));
if (strcmp(a,b)==0)cout<<”ok”<<endl;
{Менше нуля a менше b
Нульa рівне b
Більше нуляa більше b
}
|
#include <fstream>
#include <string>
using namespace std;
int main(){
ifstream cin(“input.txt”);
ofstream cout(“output.txt”);
string s1, s2;
getline (cin, s1);
getline (cin, s2);
cout<<s1<<endl;
cout<<s2<<endl;
if(s1==s2)
cout << "Ok..\n";
return 0;
}
|
$16. Швидке сортування
|
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{int n,i;
cin>>n; vector<int> a(n);
for (i=0; i<n; i++)cin>>a[i];
sort(a.begin(),a.end());
for (i=0; i<n-1; i++)cout<<a[i]<<" ";
cout<<a[n-1]<<"\n";
return 0;
}
|
$17. Повний перебір
|
#include <fstream>
#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
#include <time.h>
using namespace std;
vector <int> a;
// ifstream cin("input.dat");
//ofstream cout("output.ans");
void printper(int n);
int main()
{
int n;
cin >> n;
for (int i=1;i<=n;i++){a.push_back(i);
}
|
printper(n);
clock_t start = clock();
while (next_permutation(a.begin(),a.end())){
// printper(n);
};
// час перебору
long double r=(clock() - start)*1. / CLOCKS_PER_SEC;
cout<<"times work = "<<r<<endl;
return 0;
}
void printper(int n)
{
for (int i=0;i<n-1;i++){
cout << a[i] << " ";
}
cout << a[n-1] << endl;
}
|
$18. Векторний добуток
|
#include<fstream>
using namespace std;
ifstream cin("input.txt");
- ofstream cout("output.txt");
int main()
{
int i,n,m,k=0,x[10001],y[10001],a[10001],b[10001],v[10001];
cin>>n>>m;
for(i=1;i<=n;i++) cin>>x[i]>>y[i];
for(i=1;i<=n-1;i++)
{
a[i]=x[i+1]-x[i];
b[i]=y[i+1]-y[i];
}
for(i=1;i<=n-2;i++){
v[i]=a[i]*b[i+1]-a[i+1]*b[i];
if(v[i]>0) k++;}
cout<<k*m<<endl;
}
|
$19. Повний обхід дерева
|
#include "iostream"
using namespace std;
int c[100],n;
void p(int i,int v)
{c[i]=v;
if(i==n)
{for(int j=1;j<=n;j++)
cout<<c[j];cout<<endl;}
else{p(i+1,0);p(i+1,1);}}
int _tmain()
{cin>>n;
p(1,0);
p(1,1);
}
|
$110. Рекурсивний пошук шляху в графі
|
#include "iostream"
using namespace std;
int a[100][100],c[100],n;
void p(int i, int v)
{c[i]=v;
if (v==n || i>n)
{for(int j=1;j<=n;j++)
cout<<c[j]<<" ";
cout<<endl;
}
else
for(int j=1;j<=n;j++)
if(a[v][j]>=1) p(i+1,j);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for (int j=1;j<=n;j++)cin>>a[i][j];
p(1,1);
}
|
$111. Побудова остового дерева
|
#include <iostream>
#include <math.h>
using namespace std;
int main()
{int n,int p=0;
int a[n][n];
int x[1000],y[1000],kol_ver[1000],v[1000];
int k,i,j,vi,vj,min,s;
int ver[1000][3];
int f;
for(i=0;i<n;i++)
for (j=0;j<n;j++)
cin>>a[i][j];
k=0; v[k]=p;s=0;
|
while (k<n-1) {
min=100000;
for (i=0;i<=k;i++)
for(j=0;j<n;j++)
if (a[v[i]][j]<min) {min=a[v[i]][j];vi=v[i];vj=j;}
f=1;
for (i=0;i<=k;i++)if (vj==v[i])f=0;
if (f==1) {k=k+1;
ver[k][1]=vi;
ver[k][2]=vj;
v[k]=vj;
kol_ver[vj]=kol_ver[vj]+1;
kol_ver[vi]=kol_ver[vi]+1;
s=s+a[vi][vj];
}
a[vi][vj]=1e30;a[vj][vi]=1e30;
}
cout<<s<<endl;
for(i=1;i<n;i++) cout<<ver[i][1]<<' '<<ver[i][2]<<endl;
return 0;
}
|
$112. Пошук мінімального шляху (Флойд)
|
for (int k=0; k<n; ++k)
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
if (d[i][j]< d[i][k] + d[k][j])
d[i][j] = d[i][j]; else d[i][j]=d[i][k] + d[k][j];
|
ІІI етап Всеукраїнської учнівської олімпіади з інформатики (м.Луцьк) 2012-2013н.р
http://176.31.28.231/cgi-bin/new-client?contest_id=11
ІІIетапВсеукраїнськоїучнівськоїолімпіадизінформатики(м.Луцьк) 2013-2014н.р
http://www.e-olimp.com.ua/problems/7234
http://www.e-olimp.com.ua/ua/problems/7235
http://www.e-olimp.com.ua/ua/problems/7236
http://www.e-olimp.com.ua/ua/problems/7237
http://www.e-olimp.com.ua/ua/problems/7238
http://www.e-olimp.com.ua/ua/problems/7239
http://www.e-olimp.com.ua/ua/problems/7240
http://www.e-olimp.com.ua/ua/problems/7241
http://www.e-olimp.com.ua/ua/problems/7242
http://www.e-olimp.com.ua/ua/problems/7243 |
|