Школа олімпійського резерву з інформатики

10_04_2013 Динамічне програмування

Добавил(а) Administrator
30.05.13 15:12
Задача 4 «Зернинки» Задача 5. Банкомат Задачі 6. Купування квитків
Читать полностью

Методика підготовки до олімпіади (навчаємось постійно)

Добавил(а) Гісь Ігор Володимирович

11.06.13 11:19

Тематика

1. Олімпіадна інформатика

2. Тематика завдань

3. Системи тестування (ejudge, e-olymp, Contester )

4. Оптимізація розв’язку (прості числа, лічилка)

5. Довга арифметика (факторіал, фібоначі)

6. Повний перебір (лексичний перебір)

7. Обчислювальна геометрія (ліві повороти, площа многокутника)

8. Теорія графів (пошук в глибину, остове дерево, алгоритм флойда)

9. Практикум з розв’язування задач

1.Олімпіадна інформатика

Що потрібне для успішної участі в олімпіадах по інформатиці? Як показує практика, тільки знання мови програмування для цього явно не достатньо. Взагалі, виявляється, що олімпіадні задачі по інформатиці лежать десь на стику математики і програмування. І дуже часто виявляється, що розв’язуючи задачі школярі не тільки вчаться програмувати, але і освоюють нові розділи математики.

Як перевіряються розв’язки задач олімпіади

Історично склалося так, що розв’язки на олімпіадах по програмуванню перевіряються автоматично. Ваше завдання написати програму, яка за заданими вхідними даними обчислює і виводить вихідні дані.

Апаратне та програмне забезпечення

Учасникам олімпіади можуть вибирати мову програмування с заданого переліку: Pascal, C або C++. Система програмування Free Pascal 2.0 (чи новішої версії), GCC 4.2 (чи новішої версії), Turbo Delphi Explorer, Visual C++ 2008 Express).

2. Тематика задача олімпіади

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

Основними категоріями олімпіадних задач є:

Геометрія

Графічні задачі

Динамічне програмування

Довга арифметика

Жадібний алгоритм

Задачі для початківців

Комбінаторика

Масиви

Математика

Математичне моделювання

Обробка рядків

Послідовності

Рекурсія, перебір

Логічні задачі

Сортування

Структури даних

Теорія графів

Теорія ігор

Теорія чисел

3.Системи тестування (ejudge, e-olymp, Contester )

Працюйте в он-лайн системах, які автоматично перевіряють та тестують Ваші розв’язки:

http://olymp.sumdu.edu.ua - Веб-ресурс підтримки та проведення шкільних та студентських олімпіад з інформатики

http://www.e-olimp.com.ua/ - Інтернет-портал організаційно-методичного забезпечення дистанційних олімпіад з програмування для обдарованої молоді навчальних закладів України

http://www.olymp.vinnica.ua/ - Центр підтримки та проведення олімпіад школярів з використанням можливостей Internet.

Список тестуючи систем

Назва	Сайт	Система
ejudge	ejudge.ru	Linux
Contester	contester.ru	Windows, Linux

Список ресурсів

http://vippolabinfo.16mb.com – сайт «Лабораторія інформатики сьогодні», методична підтримки напрямків роботи.

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

http://schoololymp.byethost32.com – заочна школа роботи з обдарованими учнями з інформатики.

4. Оптимізація розв’язку (прості числа, лічилка)

За означенням поодільності на 1 та сааме себе

Решето Ератосфена

program prog1;

{$APPTYPE CONSOLE}

uses

SysUtils,

windows;

var n,i,j:integer;

p:integer;

time:int64;

begin

readln(n);

time:=gettickcount;

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;

writeln;

time:=gettickcount-time;

writeln(time/1000:0:5);

readln;

end.

program prog2;

{$APPTYPE CONSOLE}

uses

SysUtils,

windows;

var a:array[1..100000000] of integer;

j,k,n,i:integer;

time:int64;

begin

readln(n);

time:=gettickcount;

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;

//writeln(i);readln;

j:=i+a[i];

while j<=n do begin

a[j]:=0; j:=j+a[i];

end;

i:=i+1;

//for k:=1 to n do write(a[k],' ');readln;

end;

for k:=1 to n do

if a[k]<>0 then ///write(a[k],' ');

writeln;

time:=gettickcount-time;

writeln(time/1000:0:5);

readln;

end.

5.Довга арифметика (факторіал, фібоначі)

Цикл

Рекурсія

Довгий факторіал

#include "stdafx.h"

#include "iostream"

using namespace std;

int main()

{int n,i;

long long f=1;

cin>>n;

for(i=1;i<=n;i++) f*=i;

cout<<f<<endl;

return 0;

}

#include "stdafx.h"

#include "iostream"

using namespace std;

long long f(int i)

{

long long t;

if (i==0) t=1;

else t=i*f(i-1);

return t;

}

int main()

{int n;

cin>>n;

cout<<f(n)<<endl;

return 0;

}

#include "stdafx.h"

#include "iostream"

using namespace std;

int main ()

{

int n,i,k,os;

cin>>n;

int a[1000],b[1000];

for (i=0;i<1000;i++)a[i]=0;

for (i=0;i<1000;i++)b[i]=0;

a[0]=1;a[1]=1;b[0]=1;

for (k=1;k<=n;k++)

{ os=0;

for ( i=1;i<=a[0];i++)

{b[i]=(a[i]*k+os)%10;

os=(a[i]*k+os)/10;}

while(os>0){b[0]++;b[b[0]]=os%10;os=os/10;}

for ( i=0;i<=b[0];i++)a[i]=b[i];

}

for (i=b[0];i>=1;i--)

cout<<b[i];

cout<<"\n";}

6.Повний перебір (лексичний перебір)

Побудуємо лексичний перебір для довільних елементів масиву

X=3 2 4 2 4 3 1

а) Рухаємось справа наліво. Крок вперед можна зробити, якщо наступне число більше за попереднє. Ми зупинилися перед числом 2. Це число потрібно помітити.

X=3 2 4 2 4 3 1

б) Рухаємось справа наліво. Крок вперед можна зробити, якщо число менше за знайдене число(2). Ми зупинилися перед числом 3. Це число потрібно помітити.

X= 3 2 4 2 4 3 1

в) Переставляємо знайдені числа.

X= 3 2 4 3 4 2 1

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

X=3 2 4 3 1 2 4

7.Обчислювальна геометрія (ліві повороти, площа многокутника)

Ліві повороти

{Визначення координат векторів}
x[n+1]:=x[1];
y[n+1]:=y[1];
for i:=1 to n do begin
a[i]:=x[i+1]-x[i];
b[i]:=y[i+1]-y[i];
end;
{Підрахунок кількості додатних добутків}
a[n+1]:=a[1];
b[n+1]:=b[1];
k:=0;
for i:=1 to n do
if a[i]*b[i+1]-a[i+1]*b[i]>=0 then k:=k+1;

За заданими кількістю вершин і координатами n-кутника визначити його площу (15 балів).

x[n+1]=x[1]

y[n+1]=y[1]

s=0

для i=1 дo n

s=s+ (x[i]*y[i+1]-x[i+1]*y[i]

s=1/2*abs(s);

8.Теорія графів (пошук в глибину, остове дерево, алгоритм флойда)

Основні поняття теорії графів

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

Неорієнтований граф:

Відкриті Ейлером властивості графа:

1. Число непарних вершин зв'язного графа завжди парне. Неможливо накреслити граф з непарним числом непарних вершин.

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

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

4. Граф з більше ніж двома непарними вершинами неможливо накреслити одним розчерком.

Гамільтонів шлях проходить через кожну вершину по одному разу (по ребрах проходить декілька разів або жодного)

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

Задача про туриста (пошук в глибину)

Турбаза мала для ночівлі N місць, з’єднаних стежками. Туристів можна вести в одну сторону. Довжина стежки – одноденний перехід. Пройти і перевірити всі M-денні маршрути, які починаються на базі K.

Орієнтований ненавантажений граф.

n=6; m=3; k=1;

Дано орієнтований ненавантажений граф. N вершин. Знайти всі маршрути довжини m=3, які виходять з вершини з номером k.

Алгоритм Флойда-Уоршелла

З алгоритму Дейкстри зрозуміло, що можна знайти найкоротшу відстань від заданої вершини графа до решти його вершин. А якщо ця інформація потрібна для будь-якої вершини графа? Найперша відповідь, яка спадає на думку: необхідно виконати алгоритм Дейкстри в циклі для всіх вершин графа. Питання лише в часі виконання такого алгоритму, оскільки його оцінка буде О(п³). Однак існує компактніший за записом алгоритм Флойда-Уоршелла, з яким ми зараз і ознайомимося.

Запишемо сам алгоритм:

1. Визначити вершину графа k = 1, через яку буде здійснюватися перерахунок відстані між вершинами і та j.

2. Визначити вершину і = 1. Визначити вершину j = 1,

3. Якщо величина d_j_, _k + d_k_,_j менша за значення d_i_,_j ,то замінити значення d_i_,_j на d_i_, _k + d_k_,і . В іншому разі залишити значення d_i,j без змін.

4. Якщо j <= п, то перейти до наступної вершини j+ 1 і повернутися до п. 4.

5. Якщо i<= п, то перейти до наступної вершини і + 1 і повернутися до п. 3.

6. Якщо k<=n, то перейти до наступної вершини k + 1 і повернутися до п. 2,

7. Завершити алгоритм.

У результаті виконання алгоритму елементи d_i_,_j будуть містити найкоротшу відстань між відповідними вершинами графа і та j.

Реалізація алгоритму Флойда-Уоршелла мовою Pascal буде такою:

for k := 1 to n do

for і := 1 to n do

for j := 1 to n do

if d[i,k]+d[k,j]<d[i,j] then d[i,j]:=d[i, k]+d[k,j];

0 20 3 2

20 0 40 3

3 40 0 4

2 3 4 0

0 5 3 2

5 0 7 3

3 7 0 4

2 3 4 0

0 20 3 2

20 0 40 3

3 40 0 4

2 3 4 0

0 20 3 2

20 0 23 3

3 40 0 4

2 3 4 0

0 20 3 2

20 0 23 3

3 23 0 4

2 3 4 0

0 5 3 2

20 0 23 3

3 23 0 4

2 3 4 0

0 5 3 2

5 0 23 3

3 23 0 4

2 3 4 0

0 5 3 2

5 0 7 3

3 23 0 4

2 3 4 0

0 5 3 2

5 0 7 3

3 7 0 4

2 3 4 0

9.Практикум з розв’язування задач

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=3 – ІІ етап (районний) Всеукраїнської олімпіади з інформатики 2012-2013 н.р. (логін user400-user430; пароль 400-430).

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=11 – ІІІ етап (обласний) Всеукраїнської олімпіади з інформатики 2012-2013 н.р. (логін user400-user430; пароль 400-430).

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=12 – тренувальний тур по підготовці до ІV етапу Всеукраїнської олімпіади з інформатики 2012-2013 н.р. (логін user400-user414; пароль 400-414).

Последнее обновление 11.06.13 11:38

Практикум з розв'язування задач

Добавил(а) Administrator

14.05.14 10:21

Практикум з розв’язування задач

1. Задача 1 (ІІІ етап Всеукраїнської олімпіади з інформатики 2013-2014 н.р.)

A. "Все, Степан! Ти мене дістав!"

Input file name:	bubble.in
Output file name:	bubble.out
Time limit:	100 ms
Memory limit:	256 M

Степан нещодавно відпочивав у Японії і привіз звідти нову жувальну гумку. На першій парі в університеті він поділився гумкою зі своїм товаришем. Дочекавшись моменту, коли лектор повернувся до дошки, на рахунок "три - чотири" хлопці дружньо почали надувати бульбашки. Відомо, що Степан надуває бульбашку до максимально можливого розміру за час t₁, після чого бульбашка миттєво лопається, і Степан починає надувати бульбашку заново з тією ж швидкістю. Товариш Степана робе те ж саме за час t₂.

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

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

Наприклад, якщо t₁ = 2, t₂ = 3, то буде відбуватись наступне:

Степан надуває бульбашку з моменту часу t = 0 до моменту часу t = 2, потім бульбашка лопається, і він надуває бульбашку заново - з моменту часу t = 2 до моменту часу t = 4, а потім ще раз - з моменту часу t = 4 до t = 6.

Товариш Степана надуває бульбашку з t = 0 до t = 3 і ще раз з t = 3 до t = 6.

В момент часу t = 6 бульбашки лопаються одночасно в обох студентів, викладач повертається і каже: "Все, Степан! Ти мене дістав!".

Формат вхідних даних: Перший рядок вхідного файлу містить два цілих числа t₁, t₂ (1 ≤ t₁, t₂ ≤ 10⁹).

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

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

bubble.in	bubble.out
2 3	6
1 16	16

Підхід	Програмний код	Тести
Підбір в циклі з перевіркою остачі від ділення	nsk=a; while (nsk%a!=0\|\|nsk%b!=0)nsk++;	Зараховано 63.6%
Підбір в циклі з перевіркою остачі від ділення	for (int i=1;i<=a;i++) if(a%i==0&&b%i==0)nsd=i; nsk=a*b/nsd;	Зараховано 63.6%
Алгоритм Евклідіа	while (b!=0) {t=a%b; a=b; b=t; }	Зараховано 100%
Алгоритм Евклідіа	while (b!=0) {a=a%b; swap(a,b); }	Зараховано 100%

http://www.e-olimp.com.ua/problems/7239

2. Задача 2 (ІV етап Всеукраїнської олімпіади з інформатики 2013-2014 н.р.)

Відрізки (Роман Рубаненко, Роман Фурко)

Умова. Петрик дуже любить іграшки у формі геометричних фігур. Нещодавно він помітив, що серед його іграшок немає жодного трикутника. Це дуже засмутило Петрика, тому він пішов до найближчого магазину, щоб придбати новісінький трикутник. В магазині Петрику сказали, що всі трикутники вже давно розкупили, але в наявності є N прямих відрізків.

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

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

Вхідні дані. В першому рядку вхідного файла segments.dat записано єдине число N — кількість відрізків. Далі в N рядках записана інформація про самі відрізки. Кожен такий рядок містить відповідні Li (1 ⩽ Li ⩽ 10⁹ ) та Сi . Ціни утворюють перестановку чисел від 1 до N, тобто є попарно різними натуральними числами, не більшими за N.

Вихідні дані. Вихідний файл segments.sol має містити єдине число — мінімальну вартість трьох відрізків, з яких можна скласти трикутник, або «−1» (лапки для наочності) в тому випадку, якщо вибрати рівно три такі відрізки неможливо.

Оцінювання. Набір тестів складається з 4 блоків, для яких додатково виконуються такі умови:

1 ⩽ N ⩽ 100.

210 < N ⩽ 3000.

3000 < N ⩽ 10⁴ .

o 30 балів: 10⁴ < N ⩽ 10⁵ .

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

segments.dat

segments.sol

1 1

2 2

3 3

4 4

3 1

5 3

10 2

-1

Підхід	Програмний код	Тести
Розглянемо найпростіший алгоритм розв’язання задачі. Перебиратимемо всі трійки відрізків. Для кожної трійки треба перевірити можливість існування відповідного трикутника. Якщо три- кутник існує, підрахуємо сумарну вартість трьох відрізків, а з усіх знайдених вартостей вибе- ремо найменшу. Складність алгоритму — O(N ³ ).	for(int i=0;i<n-2;i++) for(int j=i+1;j<n-1;j++) for(int k=j+1;k<n;k++) if(l[i]<l[j]+l[k] && l[j]<l[i]+l[k] && l[k]<l[i]+l[j]) if (c[i]+c[j]+c[k]<m)m=c[i]+c[j]+c[k];
А от швидше розв’язання. Розглядатимемо всі відрізки в порядку від найкоротших до найдовших і підтримуватимемо таку структуру даних: масив F, у комірці F[c] якого зберігається найбільша сумарна довжина двох відрізків (з числа перших k відрізків) із загальною вартістю c.
Тепер розглянемо оптимальне розв’язання. Воно базується на такій нескладній властивості: Властивість. Якщо серед натуральних чисел L1 , L2 , ..., Lk немає трьох таких, що утворюють сторони трикутника, то найбільше з цих чисел не може бути меншим за k-й член послідовності Фібоначі.	#pragma comment(linker, "/STACK:64000000") #include <algorithm> #include <memory.h> #include <cstdio> #include <iostream> #include <cmath> #include <string> #include <cassert> #include <map> #include <set> #include <vector> #include <queue> using namespace std; #define prev privet1 #define next privet2 #define y1 privet3 #define rank privet4 #define left privet5 #define right privet6 #define y0 privet7 const double pi = 3.141592653589793238; const int INF = 1 << 30, ENOUGH_VALUE_OF_N = 300; long long a[ENOUGH_VALUE_OF_N + 2]; int main() { freopen("segments.dat", "r", stdin); freopen("segments.sol", "w", stdout); int n, i, j, u; scanf("%d", &n); long long len; int cost; for (i = 1; i <= n; i++) { scanf("%lld%d", &len, &cost); if (cost <= ENOUGH_VALUE_OF_N) a[cost] = len; } n = min(n, ENOUGH_VALUE_OF_N); int ans = INF; for (i = 1; i <= n; i++) for (j = i + 1; j <= n; j++) for (u = j + 1; u <= n; u++) if (i + j + u < ans && a[i] < a[j] + a[u] && a[j] < a[i] + a[u] & a[u] < a[i] + a[j]) ans = i + j + u; if (ans == INF) ans = -1; printf("%d\n", ans); }

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=3 – ІІ етап (районний) Всеукраїнської олімпіади з інформатики 2012-2013 н.р. (логін user400-user430; пароль 400-430).

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=11 – ІІІ етап (обласний) Всеукраїнської олімпіади з інформатики 2012-2013 н.р. (логін user400-user430; пароль 400-430).

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=12 – тренувальний тур по підготовці до ІV етапу Всеукраїнської олімпіади з інформатики 2012-2013 н.р. (логін user400-user414; пароль 400-414).

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=15 – Підготовка до олімпіади 2013 (логін user400-user430; пароль 400-430).

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=22 - Тренувальний турнір до міської олімпіади з інформатики (програмування) 2013 (м.Луцьк)

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=25 - ІІ етап Всеукраїнської учнівської олімпіади з інформатики (м.Луцьк) 2013-2014н.р.

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=26 - Волинська обласна Інтернет-олімпіада 2013

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=27 - Тренувальний турнір до обласної олімпіади 2014

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=28 - ІІI етап Всеукраїнської учнівської олімпіади з інформатики (м.Луцьк) 2013-2014 н.р.

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=29 - Підготовка до IV етапу олімпіади з інформатики (м.Луцьк) 2013-2014н.р.

Матеріали XXVII Всеукраїнської учнівської олімпіади з інформатики 2013/14 н. р.

Добавил(а) Administrator

14.05.14 10:12

Матеріали XXVII Всеукраїнської учнівської олімпіади з інформатики 2013/14 н. р.

Умови та розв'язки

Авторські розв'язки

Результати

Розбаловка по тестах

Матеріали з минулорічних олімпіад

03.09.2014 Повторення "Мова програмування С++"

Добавил(а) Administrator

04.09.14 22:19

«Мова програмування С, С++ »

Єдиний спосіб вивчати нову мову програмування –писати на ній програми. (Брайен Керніган)

Visual C++

C++

Порядок роботи

$11. Запустити середовище Головне меню\Програми\Visual C++ 9.0 Express Edition\Microsoft Visual C++ 2008 Express Edition.

$12. Створити новий проект «Консольний додаток Win32», який зберігати в власну папку.

$13. Перевірити програми з додатку.

Зауваження

Для компіляції та виконання натискуйте клавішу Ctrl F5

// Під'єднання модулів

#include "stdafx.h" //генерація файлу предкомпільованих заголовків

#include <iostream>//організація введення-виведення в мові програмування C++

#include <math.h>//виконання простих математичних операцій

using namespace std;// звернення до об'єктів напряму

int _tmain()

{

int a,b; //опис цілих

float c; //опис дійсних

cin>>a>>b;//ведення даних

c=a/b;

cout<<c<<”\n”;//виведнння даних

}

#include "stdafx.h"

#include "iostream"

using namespace std;

int 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();

}

Функції

Ім'я	Опис
abs(i)	модуль числа
ceil(f)	округлення до найближчого більшого цілого числа
fabs(f)	абсолютне значення
floor(f)	округлення до найближчого меншого цілого цілого
fmod(a,b)	повертає залишок від ділення двох чисел
modf(x,p)	повертає цілу та дробову частину аргументу х зі знаком
pow(x,y)	вираховує значення x^y
sqrt(f)	квадратний корінь

#include "stdafx.h"

#include "iostream"

#include "math.h"

using namespace std;

int _tmain()

{

double f;

f=-5.5; cout<<abs(f)<<endl;//5.5

f=-5.5; cout<<fabs(f)<<endl;//5.5

f=5.8; cout<<floor(f)<<endl;//5

f=5.8; cout<<ceil(f)<<endl;//6

f=9.0; cout<<sqrt(f)<<endl;//3

f=5; cout<<pow(f,2)<<endl;//25

f=5.5; cout<<fmod(f,2)<<endl;//1.5

f=17.25;double p,y;y=modf(f,&p); f=5.2; cout<<y<<" "<<p<<endl;//0.25 17

return 0;}

Операції

Ім'я	Опис
+	с=a+b; k=k+1; k++; s+=k;
-	c=a-b; k=k-1; k--; s-=k;
*	c=a*b;
/	a=5.0/2;//2.5 a=5/2;//2
%	a=5%2;//1

#include "stdafx.h"

#include "iostream"

using namespace std;

int _tmain()

{

int n,a,b;

cin>>n;/* 12 */

a=n/10;

b=n%10;

cout<<a<<endl;/* 1 */

cout<<b<<endl;/* 2 */

return 0;

}

Розгалуження	Цикл
Операції порівняння	З параметром
<, >. <=,>=, !=, ==	for (i=1;i<=n;i++) {блок операторів};
Логічні операції	З перед умовою
&&, \|\|, !	while (умова){блок операторів};
Умовний оператор	Після умовою
if (умова) команда 1; else команда 2;	do {блок операторів} while (умова);

Масиви

С++

Операція	Лінійний масив	Прямоктна таблиця
Опис	Int a[100]; int i, n;//індекс, кількість елементів	Int a[100][100]; int i,j, n,m;//індекс, кількість елементів
Введення	cin>>n; for(i=1;i<=n;i++)cin>>a[i];	cin>>n>>m; for(i=1;i<=n;i++) for(j=1;j<=m;j++) cin>>a[i][j];
Виведення	for(i=1;i<=n;i++)cout<<a[i<<>" ";	for(i=1;i<=n;i++) for(j=1;j<=m;j++)cout<<a[i][j]<<" ";
Сумування	s=0; for(i=1;i<=n;i++)s=s+a[i];	s=0; for(i=1;i<=n;i++) for(j=1;j<=m;j++)s=s+a[i][j];
Пошук	cin>>k; for(i=1;i<=n;i++) if (a[i]==k) cout<<i;	cin>>k; for(i=1;i<=n;i++) for(j=1;j<=m;j++)if (a[i][j]==k)cout<<i<<" "<<j;
Пошук максимального	max=a[1];nmax=1; for(i=2;i<=n;i++)if (a[i]>max) {max=a[i];nmax=i;}	max=a[1];imax=1;jmax=1; for(i=1;i<=n;i++) for(j=1;j<=m;j++)if (a[i][j]>max) {max=a[i][j]; imax=i;jmax=j;}
Сортування	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;i<=n;i++)a[i]=a[i+1];
Вставка	n=n+1; for(i=n;i>=1;i--)a[i]=a[i-1];

ЗАДАЧІ

Структура програми

#include "stdafx.h"

#include "iostream"

#include <math.h>

using namespace std;

int main()

{

cout <<"Okey";

return 0;

}

Слідування

1. Два резистори R₁ і R₂ з'єднані паралельно. Визначити сумарний опір за формулою .

2. Обчислити відстань між двома точками з координатами X₁,Y₁ і X₂,Y₂ за формулою L=

#include "stdafx.h"

#include "iostream"

#include <math.h>

using namespace std;

int main()

{

float x1,y1,x2,y2;

cin>>x1>>y1>>x2>>y2;

float l=sqrt(pow((x1-x2),2)+pow(y1-y2,2));

cout<<("L="<<l<<endl;

}

3. В рядку S символів, на сторінці R рядків. Скільки символів в книжці, у якої N сторінок?

За скільки хвилин учень прочитає книгу, якщо він одну сторінку читає за T хвилин?

#include "stdafx.h"

#include "iostream"

using namespace std;

int main()

{

int s,r,n,t;

cin>>s>>r>>n>> t;

int a=s*r*n;

cout<<"A=”<<a<<”\n;

int b=a/t;

cout<<"B=”<<b<<”\n;

int g,h;

g=b/60; h=b%60;

cout<<g<<”:”<<h;

}

4. Скільки лампочок потрібно, щоб освітити вулицю довжиною D км, як що стовпи з ліхтарями стоять на відстані V м?

5. Одна серія фільму по телевізору триває F хв. Скільки часу в годинах необхідно, щоб переглянути N серій?

Розгалуження

6. Знайти максимальне значення серед двох чисел введених з клавіатури.

#include "stdafx.h"

#include "iostream"

using namespace std;

int main()

{

int a,b,max;

cin>>a>>b;

if (a>b) max=a; else max=b;

court<<max<<endl;

}

7. Знайти максимальне значення серед трьох чисел введених з клавіатури.

#include "stdafx.h"

#include "iostream"

using namespace std;

int main()

{

int a,b,c,max;

cin>>a>>b>>c;

if (a>=b && a>=c) max=a;

if (b>=a && b>=c) max=b;

if (c>=a && c>=b) max=c;

cout<<max<<endl;

}

8. Введене число перевірити: додатне, від'ємне чи дорівнює нулю.

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

10.Введене число перевірити: менше, більше чи дорівнює воно 100.

11. Перевірити, чи існує трикутник із сторонами A, B, C.

Цикл

12.Скласти програму виведення на екран квадратiв всiх натуральних чисел менших за 20.

#include "stdafx.h"

#include "iostream"

using namespace std;

int main()

{for (int i=1;i<20;i++) cout<<i<<”*”<<i<<”=”<<,i*i;

}

13. Скласти програму знаходження суми всiх чисел кратних трьом з вiдрiзка [n,50].

#include "stdafx.h"

#include "iostream"

using namespace std;

int main()

{int n; cin>>n;

int i=48;int s=0;

while (i>=n)

{s+=i;i-=3;}

cout<<s<<endl;

}

14. Протабулювати функцію f(x)=cos(2x) на проміжку [a,b] розбитого на n проміжків.

#include "stdafx.h"

#include "iostream"

using namespace std;

int main()

{

const a=0, b=10, n=10;

float h=(b-a)/n;

float x=a;

float y;

while (x<=b)

{

y=cos(2*x);

cin<<x<< “ “<<y;

x=x+h;}

}

15. Написати таблицю переведення температури з градусів по шкалі Цельсія (С) в градуси шкали Фаренгейта (F) за формулою F=1.8*C+32 для значень від 10 до 20 градусів з кроком 2 градуси.

16. Написати таблицю переведення радіуса в площу круга для значень радіуса від 1 до 18 В кроком 2.

Масив

17. Дано лінійну таблицю із n цілих чисел. Знайти суму S всіх елементів.

#include "stdafx.h"

#include "iostream"

using namespace std;

int main()

{

int a[100];

int i,n,s;

cin>>n;

for (i=1;i<=n;i++){cin>> a[i];}

s=0;

for (i=1;i<=n;i++) s=s+a[i];

cout<<s;

}

18. З масиву стерти K-тий елемент.

#include "stdafx.h"

#include "iostream"

using namespace std;

int main()

{

int a[100];

int i,n,k,s;

cin>>n;

for (i=1;i<=n;i++) cin>>a[i];

cin>>k;

for (i=k;i<=n;i++) a[i]=a[i+1];

n--;

for (i=1;i<=n;i++) cout<<a[i]<<” “;

}

19. В масив вставити елемент на К-те місце

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

21. Скласти програму підрахунку суми елементів з непарними номерами масиву A[1..25].

22. Задано таблиця A[1..N]. Побудувати таблицю B[1..N], в якій першими розміщені всі від`ємні елементи таблиці A, а потім всі додатні.

23. Дано натуральна таблиця A[1..10]. В таблицю М записати тільки ті числа, остача від ділення яких на 3 рівна 1, а на 5 рівна 2.

24. Заданий одномірний числовий масив. Визначити суму добутків всіх пар сусідніх чисел.

25. Дано масив A[1..M]. Скласти програму перестановки місцями елементів з парними та непарними номерами.

26. Скласти програму запису в таблицю квадратів чисел від 1 до 100.

27. Скласти програму підрахунку кількості мінімальних елементів в масиві A[1..N].

28.В одномірному числовому масиві всі від`ємні елементи замініть нуля ми.

29. Перевірити, чи є одномірний числовий масив упорядкованим по зростанню.

Последнее обновление 06.10.14 11:37

Другие статьи...

Страница 2 из 43

Главное меню

Статистика

Пользователей : 269
Статей : 225
Просмотрено статей : 127705

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

Нет

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

Матеріали XXVII Всеукраїнської учнівської олімпіади з інформатики 2013/14 н. р.

Матеріали з минулорічних олімпіад

Главное меню

Статистика

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